题目链接：https://codeforces.com/contest/985
’A.Chess Placing
题意：给了一维的一个棋盘，共有n（n必为偶数）个格子。棋盘上是黑白相间的。现在棋盘上有n/2个棋子，让你全部移动到黑色格子或者白色格子，要求步数最少，并输出步数。
题解：由于黑色或者白色都是固定位置，我们对棋子位置排个序，然后全部移动到任意一个颜色，取两个最小步数的最小值就好了。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 1000000007 5 #define INF 0x3f3f3f3f 6 #define LL long long 7 #define pb push_back 8 #define pbk pop_back 9 #define ls(i) (i<<1) 10 #define rs(i) (i<<1|1) 11 #define mp make_pair 12 using namespace std; 13 const int N=1e5+10; 14 int a[N],p[N]; 15 int n,d,ans1,ans2; 16 int main() 17 { 18 scanf("%d",&n); 19 ans1=ans2=0; 20 n/=2; 21 for(int i=1;i<=n;i++) 22 scanf("%d",p+i); 23 sort(p+1,p+n+1); 24 for(int i=1;i<=n;i++) 25 { 26 ans1+=abs(p[i]-i*2); 27 ans2+=abs(p[i]-(i*2-1)); 28 } 29 printf("%d ",min(ans1,ans2)); 30 return 0; 31 }
B.Switches and Lamps
题意：有n个开关和m盏灯，每个开关都关联一些灯，按下该开关后这些关联的灯如果亮着就保持不变，关着就会亮起。问你存不存在n-1个开关的组合，使得按下这n-1个开关后，所有灯全部亮起。
题解：用0和1标记按下开关i后第j个灯是否亮起。然后求每个灯关联的开关数。接着遍历所有开关。如果存在一组开关，使得他对每个灯的亮起标记数全部小于每个灯的关联开关数，则存在这样一个组合，这个组合是除他以外的其他所有开关。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 1000000007 5 #define INF 0x3f3f3f3f 6 #define LL long long 7 #define pb push_back 8 #define pbk pop_back 9 #define ls(i) (i<<1) 10 #define rs(i) (i<<1|1) 11 #define mp make_pair 12 using namespace std; 13 const int N=2e3+10; 14 int a[N],b[N],n,m; 15 string s[N]; 16 bool flag; 17 int main() 18 { 19 ios::sync_with_stdio(false); 20 cin.tie(0); 21 cout.tie(0); 22 cin>>n>>m; 23 for(int i=1;i<=n;i++) 24 { 25 cin>>s[i]; 26 for(int j=0;j<m;j++) 27 { 28 if(s[i][j]=='1') 29 a[j+1]++; 30 } 31 } 32 for(int i=1;i<=n;i++) 33 { 34 clr(b); 35 flag=0; 36 for(int j=0;j<m;j++) 37 if(s[i][j]=='1') 38 b[j+1]++; 39 for(int j=1;j<=m;j++) 40 if(b[j]==a[j]) 41 { 42 flag=1; 43 break; 44 } 45 if(flag==0) 46 return !printf("YES "); 47 } 48 return !printf("NO "); 49 }
C.Liebig's Barrels
题意：给你n*k块木板，要你做n个桶，每个桶由k块木板组成。每个桶的盛水量由最短的木板决定。让你最大化这n个木桶的总盛水量，并且每每对木桶的盛水量差不超过l。
题解：给所有板从小到大排个序，然后看最短板往上n块板是不是都小于等于其长度+l，如果不满足则做不出这样的桶组合。现在我们取n块板来造这n个木桶，作为每个桶的最短板。先算其长度+l的木板所在的位置t，然后从第一块最短板开始，每隔k个取一块板，直到板位置超过了t。然后从t位置往前取，除了前面取过的位置，一个一个地取板。按照上述操作取板，直到取了n块板作为木桶的最短板。这时候盛水量就为这n块板长度和。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 1000000007 5 #define INF 0x3f3f3f3f 6 #define LL long long 7 #define pb push_back 8 #define pbk pop_back 9 #define ls(i) (i<<1) 10 #define rs(i) (i<<1|1) 11 #define mp make_pair 12 using namespace std; 13 const int N=1e5+10; 14 int a[N],b[N],n,m,k,l,t,pp; 15 LL ans; 16 int main() 17 { 18 ios::sync_with_stdio(false); 19 cin.tie(0); 20 cout.tie(0); 21 cin>>n>>k>>l; 22 m=n*k; 23 for(int i=1;i<=m;i++) 24 cin>>a[i]; 25 sort(a+1,a+m+1); 26 if(a[n]-a[1]>l) 27 { 28 cout<<0<<endl; 29 return 0; 30 } 31 t=upper_bound(a+1,a+m+1,a[1]+l)-a; 32 ans=0; 33 t--; 34 pp=0; 35 for(int i=1;i<=t && pp<n;i+=k) 36 ans+=1LL*a[i],pp++; 37 for(int i=t;i>=1 && pp<n;i--) 38 { 39 if(i%k==1) 40 continue; 41 else 42 ans+=1LL*a[i],pp++; 43 } 44 printf("%I64d ",ans); 45 return 0; 46 }
D.Sand Fortress
题意：给你无穷个点，从左到右为0,1,2,3…+∞。然后给你n块积木往点上放，要求所有相邻两个点间的积木高度差不超过1。并且约束第一堆积木的高度最大值。问你把这n块积木分配到这些点上后，有放积木的点的数量最少为多少？
题解：如果要求第一堆积木数量最大为1，我们可以想象我们如果要放积木到k堆上积木数最大的情况是形成一个小山一样的，相邻堆差为1的情况。那现在我们约束了第一堆最大高度为h，我们要造k堆。那么积木数最大时，我们第一堆右侧的情况，就是(k+h-1)这个小山中第k堆（包含第k堆）左侧的小山翻转过来的样子。那么我们要求更小的积木数时，就可以通过从上到下拿走积木构成，因此k堆的可达成的积木数是0~这个最大值。对于本题，我们二分查找构成的堆数，用上述方法判断该堆能不能放n个积木，来找到堆数最小值。
此题还需要一点高精度。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 100000000 5 #define LL long long 6 #define pb push_back 7 #define pbk pop_back 8 #define ls(i) (i<<1) 9 #define rs(i) (i<<1|1) 10 #define mp make_pair 11 using namespace std; 12 LL n,h,lt,rt; 13 LL mid; 14 LL t[50],k[50]; 15 void mul(LL *a,LL p) 16 { 17 LL g[50],ans[50]; 18 clr(g); 19 clr(ans); 20 g[0]=p%mod; 21 p/=mod; 22 g[1]=p%mod; 23 p/=mod; 24 g[2]=p%mod; 25 for(int i=0;i<15;i++) 26 { 27 for(int j=0;j<3;j++) 28 ans[i+j]+=g[j]*a[i]; 29 } 30 for(int i=0;i<45;i++) 31 ans[i+1]+=ans[i]/mod,ans[i]%=mod; 32 for(int i=0;i<50;i++) 33 a[i]=ans[i]; 34 return ; 35 } 36 void add(LL *a,LL p) 37 { 38 LL g[50]; 39 clr(g); 40 g[0]=p%mod; 41 p/=mod; 42 g[1]=p%mod; 43 p/=mod; 44 g[2]=p%mod; 45 for(int i=0;i<15;i++) 46 a[i]=a[i]+g[i]; 47 for(int i=0;i<15;i++) 48 a[i+1]+=a[i]/mod,a[i]%=mod; 49 return ; 50 } 51 void sub(LL *a,LL *b) 52 { 53 for(int i=0;i<45;i++) 54 { 55 a[i]-=b[i]; 56 if(a[i]<0) 57 a[i]+=mod,a[i+1]--; 58 } 59 return ; 60 } 61 bool cmp(LL *a,LL p) 62 { 63 LL g[50]; 64 clr(g); 65 g[0]=p%mod; 66 p/=mod; 67 g[1]=p%mod; 68 p/=mod; 69 g[2]=p%mod; 70 for(int i=49;i>=0;i--) 71 if(a[i]>g[i]) return true; 72 else if(a[i]<g[i]) return false; 73 return true; 74 } 75 int main() 76 { 77 scanf("%I64d%I64d",&n,&h); 78 lt=0; 79 rt=n; 80 while(rt-lt>1) 81 { 82 clr(t); 83 t[0]=1; 84 mid=lt+rt>>1; 85 if(mid<=h) 86 mul(t,((mid+1)%2==0?(mid+1)/2:(mid+1))),mul(t,mid%2==0?mid/2:mid); 87 else 88 { 89 if((mid+h-1)&1) 90 mul(t,(mid+h-1)/2),mul(t,(mid+h+1)/2),add(t,(mid+h-1)/2+1); 91 else 92 mul(t,(mid+h-1)/2),mul(t,(mid+h+1)/2); 93 clr(k); 94 k[0]=1; 95 mul(k,h%2==0?h/2:h); 96 mul(k,(h-1)%2==0?(h-1)/2:(h-1)); 97 sub(t,k); 98 } 99 if(cmp(t,n)) 100 rt=mid; 101 else 102 lt=mid; 103 } 104 printf("%I64d ",rt); 105 return 0; 106 }
E.Pencils and Boxes
题意：给你n个数字，让你把他们随意分配到任意数量的集合里，要求集合内数字的个数不小于k，并且任意两个数字之差不大于d。问是否能找到这样的一种集合构造。
题解：我们仍旧把数字排个序，可知每个集合包含排序后的一段连续数字。然后从后往前dp，dp他是不是能成为某个集合左端点（最小数字）。如果该数字为集合左端点，则该位置标记1，否则标记0。处理到第i个数字时，我们lower_bound出他的值+d的数字位置t，然后看看[i+k,t+1]位置有没有左端点，如果有，那么该位置也能成为左端点，标记1。由于这个区间可能很大，我们写个最大值线段树来查询这个位置区间。最后如果1能成为左端点，那么说明存在这样的集合构造，否则不存在。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 1000000007 5 #define INF 0x3f3f3f3f 6 #define LL long long 7 #define pb push_back 8 #define pbk pop_back 9 #define ls(i) (i<<1) 10 #define rs(i) (i<<1|1) 11 #define mp make_pair 12 using namespace std; 13 const int N=5e5+100; 14 int n,k,d; 15 int a[N]; 16 struct node 17 { 18 int l,r,maxn; 19 }tree[N<<2]; 20 void init(int i,int l,int r) 21 { 22 tree[i]=(node){l,r,0}; 23 if(l==r) return ; 24 int mid=l+r>>1; 25 init(ls(i),l,mid); 26 init(rs(i),mid+1,r); 27 return ; 28 } 29 void upd(int i,int pos,int val) 30 { 31 if(tree[i].l==tree[i].r) {tree[i].maxn=val; return ; } 32 int mid=tree[i].l+tree[i].r>>1; 33 if(mid>=pos) upd(ls(i),pos,val); 34 else upd(rs(i),pos,val); 35 tree[i].maxn=max(tree[ls(i)].maxn,tree[rs(i)].maxn); 36 return ; 37 } 38 int qy(int i,int l,int r) 39 { 40 if(tree[i].l>=l && tree[i].r<=r) return tree[i].maxn; 41 int mid=tree[i].l+tree[i].r>>1; 42 int ans=0; 43 if(l<=mid) ans=max(ans,qy(ls(i),l,r)); 44 if(r>mid) ans=max(ans,qy(rs(i),l,r)); 45 return ans; 46 } 47 int main() 48 { 49 scanf("%d%d%d",&n,&k,&d); 50 for(int i=1;i<=n;i++) 51 scanf("%d",a+i); 52 sort(a+1,a+n+1); 53 init(1,1,n); 54 for(int i=n-k+1;i>=1;i--) 55 { 56 int t=upper_bound(a+1,a+n+1,a[i]+d)-a; 57 t--; 58 if(t==n) {upd(1,i,1); continue;} 59 if(i+k>t+1) continue; 60 upd(1,i,qy(1,i+k,t+1)); 61 } 62 if(qy(1,1,1)==1) printf("YES "); 63 else printf("NO "); 64 return 0; 65 }
F.Isomorphic Strings
题意：给你一个字符串s，然后q个询问。每个询问给出两个该串的子串（长度相同），问能否对每个字母找到一个双射f(x)，使得子串1能够通过双射f(x)变成子串2，子串2能通过f(x)反函数f'(x)变为子串1。
题解:我们把26个字母拆开来，如果该位置有该字母则标1，否则标0，对该字符串做26个字母的双hash。然后询问时，我们对每个询问子串h1，看其内所有出现过的字母在h2里有没有一样的标记序列（hash值）。如果都有那么说明存在这样的双射。如果其中有一个没有那么则不存在。
为什么双hash？ 因为有个大佬造了一组数据卡单hash里的ull情况orz。真的是很强。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define pb push_back 6 #define pbk pop_back 7 #define ls(i) (i<<1) 8 #define rs(i) (i<<1|1) 9 #define mp make_pair 10 using namespace std; 11 const int N=2e5+10; 12 const int maxn=2e5; 13 const LL mod[2]={1000000007,987654323}; 14 LL bit[N][2]; 15 LL rk[N][26][2],num[N][26]; 16 int n,m,t,h1,h2,len; 17 char s[N]; 18 bool flag,rflag; 19 int main() 20 { 21 bit[0][0]=bit[0][1]=1; 22 for(int i=1;i<=maxn;i++) 23 for(int j=0;j<2;j++) 24 bit[i][j]=(bit[i-1][j]<<1)%mod[j]; 25 scanf("%d%d",&n,&m); 26 scanf("%s",s+1); 27 for(int i=1;s[i];i++) 28 { 29 t=s[i]-'a'; 30 for(int j=0;j<26;j++) 31 { 32 for(int k=0;k<2;k++) 33 if(t==j) 34 rk[i][j][k]=(rk[i-1][j][k]<<1|1)%mod[k]; 35 else 36 rk[i][j][k]=(rk[i-1][j][k]<<1)%mod[k]; 37 if(t==j) 38 num[i][j]=num[i-1][j]+1; 39 else 40 num[i][j]=num[i-1][j]; 41 } 42 } 43 for(int i=1;i<=m;i++) 44 { 45 scanf("%d%d%d",&h1,&h2,&len); 46 rflag=1; 47 for(int j=0;j<26;j++) 48 if(num[h1+len-1][j]>num[h1-1][j]) 49 { 50 flag=0; 51 for(int k=0;k<26;k++) 52 { 53 if(((rk[h1+len-1][j][0]-rk[h1-1][j][0]*bit[len][0]%mod[0])%mod[0]+mod[0])%mod[0]==((rk[h2+len-1][k][0]-rk[h2-1][k][0]*bit[len][0]%mod[0])%mod[0]+mod[0])%mod[0] && ((rk[h1+len-1][j][1]-rk[h1-1][j][1]*bit[len][1]%mod[1])%mod[1]+mod[1])%mod[1]==((rk[h2+len-1][k][1]-rk[h2-1][k][1]*bit[len][1]%mod[1])%mod[1]+mod[1])%mod[1] ) 54 { 55 flag=1; 56 break; 57 } 58 } 59 if(flag==0) 60 { 61 rflag=0; 62 break; 63 } 64 } 65 if(rflag) 66 printf("YES "); 67 else 68 printf("NO "); 69 } 70 return 0; 71 }
G.Team Players
题意：给出数字0~(n-1)，并给出m个数字对，要求你找出所有的三元组(a,b,c),a<b<c，并且其中不能包含这些数字对。然后让你输出所有三元组A*a+B*b+C*c的和。
题解：我们用容斥定理，把所有三元组和求出来，减去包含至少包含其中一个数字对的三元组的和，加上至少包含其中两个数字对的三元组的和，减掉包含其中三个数字对的三元组的和。最后一个情况要找三元环，通过了大佬的写法才知道怎么有技巧的暴力查找这样的三元环orz。
由于要mod 2^64，直接用ull去做就好了。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 1000000007 5 #define INF 0x3f3f3f3f 6 #define LL long long 7 #define pb push_back 8 #define pbk pop_back 9 #define ls(i) (i<<1) 10 #define rs(i) (i<<1|1) 11 #define mp make_pair 12 #define ull unsigned long long 13 #define fi first 14 #define se second 15 using namespace std; 16 const int N=2e5+10; 17 ull a,b,c,ans; 18 vector<int> e[N]; 19 vector<pair<int,int> > pe; 20 vector<int> g[N]; 21 int n,m,k,t,u,v,r,d; 22 int sz[N]; 23 ull calc(int p0,int p1,int p2) 24 { 25 int st[3]={p0,p1,p2}; 26 sort(st,st+3); 27 return a*st[0]+b*st[1]+c*st[2]; 28 } 29 int main() 30 { 31 ios::sync_with_stdio(false); 32 cin.tie(0); 33 cout.tie(0); 34 cin>>n>>m; 35 cin>>a>>b>>c; 36 ans=0; 37 for(int i=0;i<n;i++) 38 { 39 ans+=a*i*((ull)(n-1-i)*(n-2-i)/2); 40 ans+=b*i*i*(n-1-i); 41 ans+=c*i*((ull)i*(i-1)/2); 42 } 43 pe.pb(mp(0,0)); 44 for(int i=1;i<=m;i++) 45 { 46 cin>>u>>v; 47 e[u].pb(v); 48 e[v].pb(u); 49 pe.pb(mp(u,v)); 50 if(u>v) swap(u,v); 51 ans-=(a*u+b*v)*(n-1-v)+c*((ull)(v+n)*(n-1-v)/2); 52 ans-=(a*u+c*v)*(v-u-1)+b*((ull)(u+v)*(v-u-1)/2); 53 ans-=(b*u+c*v)*u+a*((ull)(u-1)*u/2); 54 } 55 for(int i=0;i<n;i++) 56 { 57 r=0; 58 sz[i]=e[i].size(); 59 sort(e[i].begin(),e[i].end()); 60 for(int j=0;j<sz[i];j++) 61 { 62 d=e[i][j]; 63 if(d<i) 64 ans+=a*d*(sz[i]-1-j)+b*d*j,r++; 65 else 66 ans+=b*d*(sz[i]-1-j)+c*d*j; 67 } 68 ans+=a*i*((ull)(sz[i]-r)*(sz[i]-r-1)/2)+b*i*r*(sz[i]-r)+c*i*((ull)r*(r-1)/2); 69 } 70 for(int i=1;i<=m;i++) 71 { 72 u=pe[i].fi; 73 v=pe[i].se; 74 if(sz[u]>sz[v] || (sz[u]==sz[v] && u>v)) swap(u,v); 75 g[u].pb(v); 76 } 77 for(int i=0;i<n;i++) 78 sort(g[i].begin(),g[i].end()); 79 for(int i=1;i<=m;i++) 80 { 81 u=pe[i].fi; 82 v=pe[i].se; 83 auto p0=g[u].begin(); 84 auto p1=g[v].begin(); 85 while(p0!=g[u].end() && p1!=g[v].end()) 86 if(*p0==*p1) ans-=calc(u,v,*p0),p0++,p1++; 87 else if(*p0<*p1) p0++; 88 else p1++; 89 } 90 cout<<ans<<endl; 91 return 0; 92 }