hdu 6480"/>
hdu 6480
Problem A
题意：
给你一个串，问你这个串内有多少个只含有一种字符的子串
分析：
双指针扫描，每次向右扫描相同字符，设每次扫描到的长度为 l e n len len，最终答案为 l e n ∗ ( l e n + 1 ) 2 \frac{len*(len+1)}{2} 2len∗(len+1)
代码：
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
char str[maxn];
typedef long long ll;
int main()
{//freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){scanf("%s",str);int l=0,r=0;int len=strlen(str);ll res=0;while(l<len&&r<len){while(r<len&&str[l]==str[r]) r++;int tmp=(r-l);res+=1ll*tmp*(tmp+1)/2;l=r;}cout<<res<<endl;}
}
Problem B
Problem C
分析：
从(0,y)到(x,0)的路径的方案数，由组合数学知道是C(x+y,x)，所以总的方案数就是C(x1+y1,x1)*C(x2+y2,x2)。然后我们要减去重叠的方案，两条路径会相交，那么我们在相交点换一下各自的路径，就变成从(0,y1)到(x2,0)和从(0,y2)到(x1,0)的方案数，那么就是C(x1+y2,x1)*C(x2+y1,x2)。两者相减就是答案
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200005;
const int mod=1e9+7;
long long f[maxn],inv[maxn],finv[maxn];
void init(){f[0]=finv[0]=inv[0]=inv[1]=1;for (int i=2;i<maxn;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;for (int i=1;i<maxn;i++){f[i]=f[i-1]*i%mod;finv[i]=finv[i-1]*inv[i]%mod;}
}
ll C(ll n,ll m){if (n<0||m<0||m>n) return 0;return f[n]*finv[m]%mod*finv[n-m]%mod;
}
int main()
{init();int T;while(~scanf("%d",&T)){while (T--){ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld",&x1,&x2,&y1,&y2);ll sum=C(x1+y1,x1)*C(x2+y2,x2)%mod;ll tmp=C(x1+y2,x1)*C(x2+y1,x2)%mod;ll ans=(sum-tmp+mod)%mod;printf("%lld\n",ans);}}return 0;
}
Problem D
题意：
给你一个长度为 n n n的序列，以及 m m m个询问，每个询问给你一个区间 [ l , r ] [l,r] [l,r]，其中 m x mx mx为区间最大值， m i n min min为区间最小值，现在问你在区间 [ l , r ] [l,r] [l,r]中是否存在从 m i n min min到 m x mx mx中的所有的数
分析：
问题显然可以转化为求区间 [ l , r ] [l,r] [l,r]中不同的数的个数 c n t cnt cnt，如果 m x − m i n = c n t mx-min=cnt mx−min=cnt则证明符合条件，反之则不符合条件。
故此时的问题就转化成区间不同的数的个数以及RMQ问题。
故我们可以用莫队和ST表分别维护者两个东西。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000005;
int dp[200005][20];
int mm[200005];
void initRMQ(int n,int b[]){mm[0]=-1;for(int i=1;i<=n;i++){mm[i]=((i&(i-1)==0))?mm[i-1]+1:mm[i-1];dp[i][0]=b[i];}for(int j=1;j<=mm[n];j++){for(int i=1;i+(1<<j)-1<=n;i++){dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}}
}
int rmq1(int x,int y){int k=mm[y-x+1];return max(dp[x][k],dp[y-(1<<k)+1][k]);
}
int rmq2(int x,int y){int k=mm[y-x+1];return min(dp[x][k],dp[y-(1<<k)+1][k]);
}
struct Q{int l,r,id;int t;bool operator<(const Q &b)const{if(t==b.t) return r<b.r;else return t<b.t;}
}q[maxn];
int a[maxn];
int ans=0;
unordered_map<int,int>cnt;
void del(int x){if(cnt.count(a[x])) cnt[a[x]]--;
}
void add(int x){if(!cnt.count(a[x])) cnt[a[x]]++;
}
int Res[maxn];
int n,m;
int main()
{//freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}cnt.clear();initRMQ(n,a);int len=sqrt(n);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;q[i].t=(q[i].l-1)/len+1;}sort(q+1,q+1+m);int l=1,r=0;for(int i=1;i<=m;i++) {while (l > q[i].l) add(l - 1), l--;while (l < q[i].l) del(l), l++;while (r < q[i].r) add(r + 1), r++;while (r < q[i].r) del(r), r--;int maxx=rmq1(q[i].l,q[i].r);int minn=rmq2(q[i].l,q[i].r);Res[q[i].id] = (maxx-minn+1)>cnt.size()?1:0;}for(int i=1;i<=m;i++){cout<<(Res[i]==1?"NO":"YES")<<endl;}}return 0;
}
Problem E
温暖的签到题，判断一下 n n n是否整除 m m m就没了。
Problem F
题意：
给你两个串 s t r 1 , s t r 2 str_1,str_2 str1,str2，现在让你找到最大的 s s s，使得从 s t r 1 str_1 str1和 s t r 2 str_2 str2分别获得一个长度为 s s s的子串后，最多有 k k k个字符不相同。
分析：
第一个串和第二个串各取一个子串，子串相匹配求其中最长的不同个数不超过k的子串长度，这个一共有多少匹配情况呢，我们可以固定第一个串，枚举第二个串的开头，用第一个串去直接匹配第二个串的开头到结尾的子串，这样就可以完整地匹配所有情况。因为如果在第一个串的中间取一个子串来匹配，他这个小情况，可以变成对应第一个串匹配第二个串的某一个开头，其中这种匹配情况下，最长的满足题意的子串长度。
接下来就是求每一种匹配情况下的最优答案了，这个可以用 d p dp dp来实现， d p [ i ] dp[i] dp[i]表示当前匹配到第i位的最长长度，随便记录一下最长长度的不同个数，接下来当不同个数到k时我们要减去最远的一个不同的匹配，这个可以用队列记录一下位置，把 d p [ i ] dp[i] dp[i]减去最远和次最远之间的长度，最后对每一个 d p dp dp取 max \max max就是答案。时间复杂度 O ( ( n + m ) 2 ) \mathcal{O}((n+m)^2) O((n+m)2)
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=4007;
char s1[maxn],s2[maxn];
int dp[2][maxn][2];
queue<int>a[maxn<<1];
int main(){// freopen("in.txt","r",stdin);int t,n,m,k;while (~scanf("%d",&t)){while (t--){scanf("%d",&k);scanf("%s %s",s1+1,s2+1);n=strlen(s1+1),m=strlen(s2+1);for (int i=1;i<=n+m+1;i++)while (!a[i].empty()) a[i].pop();for (int i=1;i<=m;i++) a[i].push(n+1);for (int i=m+1;i<=n+m+1;i++) a[i].push(n-i+m+1);for (int i=0;i<=1;i++) {dp[i][m+1][0]=dp[i][m+1][1]=0;dp[i][m][0]=dp[i][m][1]=0;}for (int i=0;i<=m+1;i++) {dp[0][i][0]=dp[0][i][1]=dp[1][i][0]=dp[1][i][1]=0;}int ans=0;for (int i=n;i>=1;i--)for (int j=m;j>=1;j--){if (s1[i]==s2[j]){dp[i%2][j][0]=dp[(i+1)%2][(j+1)][0]+1;dp[i%2][j][1]=dp[(i+1)%2][(j+1)][1];}else {int x=j+n-i;a[x].push(i);dp[i%2][j][0]=dp[(i+1)%2][(j+1)][0]+1;dp[i%2][j][1]=dp[(i+1)%2][(j+1)][1]+1;if (dp[i%2][j][1]>k){int tmp=a[x].front();a[x].pop();dp[i%2][j][0]-=tmp-a[x].front();dp[i%2][j][1]--;}}ans=max(ans,dp[i%2][j][0]);}printf("%d\n",ans);}}
}
Problem G
题意：
给你一个长度为 n n n的数组，每次你都可以选取 n − 1 n-1 n−1个 数组，令他们都 − 1 -1 −1，现在问你能否使他们都变成同一个数，如果可以，输出最小的操作次数。
分析：
正难则反，取 n − 1 n-1 n−1个数令他们减 1 1 1，等价于每次取 1 1 1个数令它加 1 1 1，因此我们只需正着做，每次对一个数进行操作即可。
代码：
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
ll a[maxn],ans[maxn];
int main()
{//freopen("in.txt","r",stdin);int t;while (~scanf("%d",&t)){while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+1+n);ll sum=0;for (int i=1;i<=n;i++) ans[i]=a[n]-a[i],sum+=ans[i];bool f=1;for (int i=1;i<=n;i++){if (a[i]<=sum-ans[i]){f=0;break;}}if (f) printf("%lld\n",sum);else puts("-1");}}return 0;
}
Problem H
初中物理题，记住几个公式： P = m v \mathcal{P}=\frac{m}{v} P=vm， F 浮 = P g V 排 F_{浮}=\mathcal{P}gV_{排} F浮=PgV排就没了
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
double sum,l,p;
int main()
{int T;while(~scanf("%d",&T)){while(T--){int n;scanf("%d",&n);sum=0;for(int i=1;i<=n;i++){scanf("%lf%lf",&l,&p);if(p<1)sum+=l*l*l*p;else sum+=l*l*l;}double s,h,v;scanf("%lf%lf%lf",&s,&h,&v);v+=sum;double ans=v/s;ans=min(h,ans);printf("%.2f\n",ans);}}
}Problem I
Problem J
温暖的签到，模拟一下即可。
代码：
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
char str[maxn];
typedef long long ll;
int a[maxn],id[maxn];
int main()
{//freopen("in.txt","r",stdin);int t;while (~scanf("%d",&t)){while (t--){int n;scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);id[a[i]]=i;}int ans=0;for (int i=1;i<=n;i++){if (a[i]!=i){ans++;int tmp=a[i],idd=id[i];swap(a[i],a[id[i]]);swap(id[tmp],id[i]);}}
// for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
// for (int i=1;i<=n;i++) cout<<id[i]<<' ';cout<<endl;printf("%d\n",ans);}}return 0;
}
更多推荐
hdu 6480
发布评论