CF1305C
题解:
我们发现虽然 $n$ 很大,但是模数很小,所以相当于 $n$ 个数对 $m$ 取模后不能有重复数字.
那么其实这个 $n$ 最大也就是 $m$ ,直接 $O(m^2)$ 暴力算就行了.
code:
#include <bits/stdc++.h> #define ll long long #define N 2004 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int vis[N],arr[200007],bu[200007]; int main() { // setIO("input"); int i,j,n,mod; scanf("%d%d",&n,&mod); for(i=1;i<=n;++i) { scanf("%d",&arr[i]); bu[i]=arr[i]; arr[i]%=mod; if(vis[arr[i]]) { printf("0\n"); return 0; } vis[arr[i]]=1; } int ans=1; int tmp=1; for(i=1;i<=n;++i) { for(j=i+1;j<=n;++j) { if(bu[i]<bu[j]) tmp*=-1; ans=ans*(arr[i]-arr[j]+mod)%mod; } } printf("%d\n",(tmp*ans+mod)%mod); return 0; }
CF1310A
我们发现最优的操作方式一定是从小到大,价格高到价格低来进行操作的.
而我们每增加 1,就会少一个数,所以只需维护当前数中代价最大的就行.
然后当碰到下一个数的时候来一个堆的启发式合并就行了.
code:
#include <bits/stdc++.h> #define N 200007 #define ll long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; int rk[N],a[N],t[N],A[N],id[N]; map<int,int>mp; priority_queue<int>q[N]; ll sum[N]; int main() { // setIO("input"); int i,j,n; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%d",&a[i]),A[i]=a[i],mp[a[i]]=1; for(i=1;i<=n;++i) scanf("%d",&t[i]); sort(A+1,A+1+n); int tmp=unique(A+1,A+1+n)-A-1; for(i=1;i<=n;++i) rk[i]=lower_bound(A+1,A+1+tmp,a[i])-A; for(i=1;i<=n;++i) { q[rk[i]].push(t[i]); sum[rk[i]]+=t[i]; } ll ans=0; for(i=1;i<=tmp;++i) id[i]=i; for(i=1;i<=tmp;++i) { int cur=A[i]; for(j=cur;(j==cur||!mp[j])&&!q[id[i]].empty();++j) { int u=q[id[i]].top(); q[id[i]].pop(); ans+=sum[i]-u; sum[i]-=u; } if(!q[id[i]].empty()) { if(q[id[i+1]].size()<q[id[i]].size()) { while(!q[id[i+1]].empty()) { q[id[i]].push(q[id[i+1]].top()); q[id[i+1]].pop(); } id[i+1]=id[i]; } else { while(!q[id[i]].empty()) { q[id[i+1]].push(q[id[i]].top()); q[id[i]].pop(); } } sum[i+1]+=sum[i]; } } printf("%lld\n",ans); return 0; }
CF1316C
题解:给定两个多项式,求相乘后第几项不会被质数 $p$ 整除.
直接硬推的话是推不出来的,因为多项式相乘是卷积运算.
但是假如说我们能在两个多项式中分别找到第一项不能被 $p$ 整除的 $i,j$ 的话第 $(i+j)$ 项就一定是答案了.
至于正确性,手画一下多项式卷积的情况就可以得知,在 $(i+j)$ 项的系数模 $p$ 后只有 $a[i] \times b[j]$ 是有贡献的.
由于题目保证了 $gcd(a[0],a[1],....a[n])=gcd(b[0],b[1],....b[m])=1$,故一定能找到这样的 $i,j$.
code:
#include <bits/stdc++.h> #define ll long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; int main() { // setIO("input"); int i,j,n,m,mod,a1=-1,a2=-1; scanf("%d%d%d",&n,&m,&mod); for(i=0;i<n;++i) { int x; scanf("%d",&x); if((x%mod)&&a1==-1) a1=i; } for(i=0;i<m;++i) { int x; scanf("%d",&x); if((x%mod)&&a2==-1) a2=i; } printf("%d\n",a1+a2); return 0; }
CF1320C
题解:我们可以一维枚举,另一位用线段树维护(扫描线). 这个套路挺常见的.
code:
#include <bits/stdc++.h> #define ll long long #define N 200007 #define lson now<<1 #define rson now<<1|1 #define MAX 1000000 #define inf 10000000000000000 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int A[MAX+2],B[MAX+2]; struct node { int x,y,z; }no[N]; struct data { ll tag,maxx; }s[(MAX+1)<<2]; bool cmp(node a,node b) { return a.x<b.x; } inline void mark(int now,ll v) { s[now].maxx+=v; s[now].tag+=v; } inline void pushdown(int now) { if(s[now].tag) { mark(lson,s[now].tag); mark(rson,s[now].tag); s[now].tag=0; } } void build(int l,int r,int now) { if(l==r) { s[now].maxx=(ll)B[l]?(ll)-B[l]:-inf; return ; } int mid=(l+r)>>1; build(l,mid,lson),build(mid+1,r,rson); s[now].maxx=max(s[lson].maxx,s[rson].maxx); } void update(int l,int r,int now,int L,int R,int v) { if(l>=L&&r<=R) { mark(now,v); return ; } pushdown(now); int mid=(l+r)>>1; if(L<=mid) update(l,mid,lson,L,R,v); if(R>mid) update(mid+1,r,rson,L,R,v); s[now].maxx=max(s[lson].maxx,s[rson].maxx); } int main() { // setIO("input"); int i,j,n,m,p; scanf("%d%d%d",&n,&m,&p); for(i=1;i<=n;++i) { int x,y; scanf("%d%d",&x,&y); if(!A[x]||A[x]>y) A[x]=y; } for(i=1;i<=m;++i) { int x,y; scanf("%d%d",&x,&y); if(!B[x]||B[x]>y) B[x]=y; } for(i=1;i<=p;++i) scanf("%d%d%d",&no[i].x,&no[i].y,&no[i].z); sort(no+1,no+1+p,cmp); build(1,MAX,1); ll ans=-inf; for(i=j=1;i<=MAX;++i) { if(A[i]) { for(;j<=p&&no[j].x<i;++j) if(no[j].y<MAX) update(1,MAX,1,no[j].y+1,MAX,no[j].z); ans=max(ans,(ll)-A[i]+s[1].maxx); } } printf("%lld\n",ans); return 0; }
CF1321C
题解:手画一下发现这个东西是不能 $DP$ 的(因为有后效性).
所以们为了满足没有后效性,就先删字符大的,后删字符小的,整个过程用链表维护即可.
code:
#include <bits/stdc++.h> #define N 205 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int n; char str[N]; int a[N],pre[N],nxt[N],vis[N]; int main() { // setIO("input"); int i,j; scanf("%d%s",&n,str+1); a[0]=a[n+1]=-1; for(i=1;i<=n;++i) a[i]=str[i]-'a',pre[i]=i-1,nxt[i]=i+1; int ans=0; for(i=25;i;--i) { for(int cnt=1;cnt<=100;++cnt) { for(j=1;j<=n;++j) { if(!vis[j]&&a[j]==i&&(a[pre[j]]==i-1||a[nxt[j]]==i-1)) { vis[j]=1; ++ans; nxt[pre[j]]=nxt[j]; pre[nxt[j]]=pre[j]; } } } } printf("%d\n",ans); return 0; }