Codeforces Round #574 (Div. 2)

原题链接：http://codeforces.com/contest/1195

A Drinks Choosing

#include<bits/stdc++.h> using namespace std; const int maxn=1010; int num[maxn]; int n,k; int main() { while(~scanf("%d%d",&n,&k)){ for(int i=1;i<=n;i++) num[i]=0; for(int i=1,x;i<=n;i++){ scanf("%d",&x);num[x]++; } int ans=0; for(int i=1;i<=k;i++) ans+=num[i]&1; printf("%d\n",n-ans/2); } return 0; }

B Sport Mafia（简单二分）

题意：每次从盘子加、取糖，第一次加1糖，后面每次可以选择加糖、取糖；取糖只能取1颗，加糖要在上次加糖的基础上多加一颗。给你操作次数n，和最后盘中糖数k，求取糖数。直接二分枚举即可

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=1010; int num[maxn]; int n,k; ll ok(int cur) { return 1LL*cur*(cur+1)/2-(n-cur); } int main() { while(~scanf("%d%d",&n,&k)){ int l=1,r=n,ans=0; while(l<=r){ int mid=(l+r)>>1; ll res=ok(mid); // printf("mid:%d res:%d\n",mid,res); if(res==1LL*k){ ans=mid;break; }else if(res>1LL*k){ r=mid-1; }else{ l=mid+1; } } printf("%d\n",n-ans); } return 0; }

C Basketball Exercise（简单dp）

题意：从2列数（都是正数）中挑选出任意下标不同的数，要求相邻数在不同列。

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=100010; int num[maxn]; int n,k; int a[2][maxn]; ll dp[2][maxn]; int main() { while(~scanf("%d",&n)){ for(int k=0;k<2;k++) for(int i=0;i<n;i++) scanf("%d",&a[k][i]); dp[0][0]=a[0][0];dp[1][0]=a[1][0]; ll mx[2];mx[0]=dp[0][0];mx[1]=dp[1][0]; for(int i=1;i<n;i++){ for(int k=0;k<2;k++){ dp[k][i]=a[k][i]+mx[1-k]; // printf("dp[%d][%d]:%I64d \n",k,i,dp[k][i]); } for(int k=0;k<2;k++) mx[k]=max(dp[k][i],mx[k]); } printf("%I64d\n",max(dp[0][n-1],dp[1][n-1])); } return 0; }

D2 Submarine in the Rybinsk Sea (hard edition)（思维）

参考：https://www.cnblogs.com/bxd123/p/11213051.html 题意：给你n个数，定义f(x,y)为…好吧很难描述，看图 题解：很nice的一个思路，把每个数对应位置的贡献都累加起来（%10)，然后我们再枚举累加每个位置的数的贡献即可，复杂度为O（20*n）。

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=100010; const int mod=998244353; int n,a[maxn]; int len[maxn]; ll val[maxn],p10[50]; int cal(int x) { int len=0; while(x){ val[++len]+=x%10; x/=10; } return len; } void init() { p10[0]=1; for(int i=1;i<=30;i++) p10[i]=p10[i-1]*10%mod; } int main() { init(); while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&a[i]); len[i]=cal(a[i]); } ll ans=0; for(int k=1;k<=30;k++){ for(int i=1;i<=n;i++){ if(k<=len[i]) ans+=p10[(k-1)*2]*11%mod*val[k]%mod,ans%=mod; else ans+=p10[k+len[i]-1]*2%mod*val[k]%mod,ans%=mod; } } printf("%I64d\n",ans); } return 0; }

E OpenStreetMap（单调队列求子矩阵最小值之和）

参考：https://www.cnblogs.com/changer-qyz/p/11251786.html 题意：给一个$n\ast m$矩阵，求所有的子矩阵$a\ast b$的最小值之和。 题解：对每一行求单调队列，求出每b个元素中的最小值，并保存在$mp[][]$中，再对每一列在$mp[][]$中，求出每a个元素$mp[][]$的最小值。好题！！

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=3010; int mp[maxn][maxn],g[maxn][maxn]; int q[maxn],l,r; int n,m,a,b; int v0,t1,t2,p; int main() { while(~scanf("%d%d%d%d",&n,&m,&a,&b)){ scanf("%d%d%d%d",&v0,&t1,&t2,&p); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ g[i][j]=v0; v0=(1LL*v0*t1%p+t2)%p; } } for(int i=1;i<=n;i++){ l=1;r=0; for(int j=1;j<=b;j++){ while(r>=l&&g[i][q[r]]>=g[i][j]) r--;// q[++r]=j; } mp[i][1]=g[i][q[l]]; for(int j=2;j+b-1<=m;j++){ while(r>=l&&q[l]<j) l++; while(r>=l&&g[i][q[r]]>=g[i][j+b-1]) r--;// q[++r]=j+b-1; mp[i][j]=g[i][q[l]]; } } ll ans=0; for(int j=1;j+b-1<=m;j++){ l=1;r=0; for(int i=1;i<=a;i++){ while(r>=l&&mp[q[r]][j]>mp[i][j]) r--; q[++r]=i; } ans+=mp[q[l]][j]; for(int i=2;i+a-1<=n;i++){ while(r>=l&&q[l]<i) l++; while(r>=l&&mp[q[r]][j]>mp[i+a-1][j]) r--; q[++r]=i+a-1; ans+=mp[q[l]][j]; } } printf("%I64d\n",ans); } }

F Geometers Anonymous Club（闵可夫斯基求和）

闵可夫斯基求和：https://blog.csdn.net/jinzhilong580231/article/details/6819586 参考：https://blog.csdn.net/yopilipala/article/details/96619299 题意：给你n个多边形，q个查询，求[l,r]区间内多边形闵可夫斯基求和后的多边形的顶点数 题解：用闵可夫斯基求和的一个定理，有多少顶点，对应有多少向量，我们只需统计[l,r]这些多边形共有多少向量即可，注意重边的情况。

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=500010;// int n,k,q2; struct Point{ int x,y; Point(){} Point(int _x,int _y):x(_x),y(_y){} Point operator - (const Point &b)const{ return Point(x-b.x,y-b.y); } bool operator <(const Point &b)const{ return x==b.x?y<b.y:x<b.x; } }p1,p2; typedef Point Vector; typedef Point Query; vector<Vector> ve,tmp; vector<Query> query; map<Vector,int> mps; int l[maxn],r[maxn]; int ans[maxn]; vector<int> q[maxn]; int sum[maxn]; int gcd(int x,int y) { return x?gcd(y%x,x):y; } int lowbit(int k) { return k&(-k); } void Add(int pos,int val) { while(pos<maxn){ sum[pos]+=val; pos+=lowbit(pos); } } int Sum(int pos) { int res=0; while(pos){ res+=sum[pos];pos-=lowbit(pos); } return res; } int main() { while(~scanf("%d",&n)){ mps.clear(); ve.clear(); memset(sum,0,sizeof(sum)); ve.push_back(Vector(-1,-1)); int a,b,len; for(int i=1;i<=n;i++){ scanf("%d",&k); tmp.clear(); for(int j=0;j<k;j++){ scanf("%d%d",&a,&b); tmp.push_back(Point(a,b)); } len=tmp.size(); l[i]=ve.size(); for(int i=0;i<len;i++){ p1=tmp[i];p2=tmp[(i+1)%len]; p2=p2-p1; a=gcd(abs(p2.x),abs(p2.y)); p2.x/=a;p2.y/=a; ve.push_back(p2); } r[i]=ve.size()-1; } scanf("%d",&q2); for(int i=0;i<q2;i++){ scanf("%d%d",&a,&b); Query tmp=Query(l[a],r[b]); query.push_back(tmp); q[tmp.y].push_back(i); } // for(int i=1;i<=n;i++) // printf("Q[%d].siz:%d \n",i,q[i].size());// for(int i=1;i<ve.size();i++){ if(mps.find(ve[i])!=mps.end()){ Add(mps[ve[i]],-1); } Add(i,1); mps[ve[i]]=i; for(int j=0;j<q[i].size();j++) // printf("r_sum:%d l_sum:%d\n",Sum(query[q[i][j]].y),Sum(query[q[i][j]].x)), ans[q[i][j]]=Sum(query[q[i][j]].y)-Sum(query[q[i][j]].x-1); } for(int i=0;i<q2;i++) printf("%d\n",ans[i]); } }