A题
枚举每一位，如果是偶数就加上i
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; int main(){ ios::sync_with_stdio(false); int n; cin>>n; string s; cin>>s; int ans=0; s=" "+s; for(int i=1;i<(int)s.size();i++){ int x=s[i]-'0'; if(x%2==0){ ans+=i; } } cout<<ans<<endl; return 0; }
B题
这题一定要注意一个细节，之后选的数不能小于前面选的数
也就是你前面选的都会被后面制约
因此只能从后往前考虑。显然最后全拿，之后就是a[i]和x-1取min，其中x是当前数后面的约束
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; int n; int a[N]; int main(){ ios::sync_with_stdio(false); cin>>n; int i; int x=1e9+1; for(i=1;i<=n;i++) cin>>a[i]; ll ans=0; for(i=n;i>=1;i--){ x=min(a[i],x-1); if(x<=0) break; ans+=x; } cout<<ans<<endl; return 0; }
C题
正难则反还是好用，正着很难想，但是反着看，答案不就是全部个数-没有经过黑边个数，那么就是连通块划分，每个连通块里面随便选
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=4e5+10; const int mod=1e9+7; int h[N],ne[N],e[N],w[N],idx; int st[N]; int cnt; ll ans; ll qmi(ll a,ll b){ ll res=1; while(b){ if(b&1){ res=res*a%mod; } a=a*a%mod; b>>=1; } return res; } void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dfs(int u,int fa){ st[u]=1; cnt++; for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(st[j]) continue; if(w[i]==1) continue; dfs(j,u); } } int main(){ ios::sync_with_stdio(false); memset(h,-1,sizeof h); int n,k; cin>>n>>k; int i; for(i=1;i<n;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); } ans=qmi(n,k); for(i=1;i<=n;i++){ if(!st[i]){ cnt=0; dfs(i,-1); ans=(ans-qmi(cnt,k)+mod)%mod; } } cout<<ans<<endl; return 0; }
D题
神tm莫比乌斯反演，我说怎么想不出来，鸽了，不会数论算法
E题
二分图好题啊，看不出来。这题可以用二分图匹配来做，就是一种巧妙地建图，用能力值和社团连边。我当时思考过图论模型但是没有进一步的想法
这里要注意的一点是，一一对应一定是最优的，因为我们用两个相同权值的是没有意义的，因此这是二分图性质，这样就从0开始枚举看看能否匹配。
但是这里会删边，对于一些不能删边的维护操作，例如并查集和现在的二分图匹配，最好的办法就是倒序，变成加边，很多题都有这种套路，以后做题的时候我要注意一下。
并且我们加边不会导致答案变劣，因此直接继续做就行
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; const int mod=1e9+7; int h[N],ne[N],e[N],idx; int st[N],match[N]; int p[N],c[N]; int ans[N],k[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool find(int x){ int i; for(i=h[x];i!=-1;i=ne[i]){ int j=e[i]; if(!st[j]){ st[j]=1; if(match[j]==-1||find(match[j])){ match[j]=x; return true; } } } return false; } int main(){ ios::sync_with_stdio(false); memset(h,-1,sizeof h); int n,m; cin>>n>>m; int i; for(i=1;i<=n;i++){ cin>>p[i]; } for(i=1;i<=n;i++){ cin>>c[i]; } int d; cin>>d; for(i=1;i<=d;i++){ cin>>k[i]; st[k[i]]=1; } for(i=1;i<=n;i++){ if(!st[i]){ add(p[i],c[i]); } } int sum=0; memset(match,-1,sizeof match); for(i=d;i>=1;i--){ memset(st,0,sizeof st); while(find(sum)){ sum++; memset(st,0,sizeof st); } ans[i]=sum; add(p[k[i]],c[k[i]]); } for(i=1;i<=d;i++){ cout<<ans[i]<<endl; } return 0; }
F题
经典套路+思路转化
这题看上去就比较像偏序题，而且可以离线，应该考虑CDQ分治，但是有个小问题
CDQ分治必须是&&的情况，但是本题绝对值拆开后发现有两种讨论。我刚开始想的是能否通过容斥删掉重复，但是发现他们因为条件不同，没有前缀和性质，因此放弃
但是这个必须要处理，经过探索发现，题目中有一个inc和p的大小关系，然后发现对于绝对值的两种情况，因为有inc和p的约束，所以两个必须不等式必须同时成立，因此直接把这两个作为偏序。
并且舍弃inc和p的约束，因为这个已经被绝对值式子表达了，之后做CDQ三维偏序就行
另外，排序的时候需要注意不要忘了把type==1的放在前面，因为我们要考虑全等情况，这也是满足题意的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; const int mod=1e9+7; int p[N],s[N],b[N]; int inc[N],pre[N]; int ans[N]; int tr[N]; vector<int> num; struct node{ int p,s,b,id,type,res; bool operator <(const node &t) const{ if(p!=t.p) return p<t.p; if(s!=t.s) return s<t.s; if(b!=t.b) return b<t.b; return type<t.type; } }q[N],w[N]; int find(int x){ return lower_bound(num.begin(),num.end(),x)-num.begin()+1; } int lowbit(int x){ return x&-x; } void add(int x,int c){ int i; for(i=x;i<N;i+=lowbit(i)){ tr[i]+=c; } } int sum(int x){ int res=0; int i; for(i=x;i;i-=lowbit(i)){ res+=tr[i]; } return res; } void cdq(int l,int r){ if(l>=r) return ; int mid=l+r>>1; cdq(l,mid);cdq(mid+1,r); int i=l,j=mid+1,k=0; while(i<=mid&&j<=r){ if(q[i].s<=q[j].s){ if(q[i].type==1) add(q[i].b,1); w[k++]=q[i++]; } else ans[q[j].id]+=sum(q[j].b),w[k++]=q[j++]; } while(i<=mid){ if(q[i].type==1) add(q[i].b,1); w[k++]=q[i++]; } while(j<=r) ans[q[j].id]+=sum(q[j].b),w[k++]=q[j++]; for(i=l;i<=mid;i++) if(q[i].type==1) add(q[i].b,-1); for(i=l,j=0;j<k;i++,j++) q[i]=w[j]; } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int i,j; for(i=1;i<=n;i++){ cin>>p[i]; } for(i=1;i<=n;i++){ cin>>s[i]; } for(i=1;i<=n;i++){ cin>>b[i]; } for(i=1;i<=m;i++){ cin>>inc[i]; } for(i=1;i<=m;i++){ cin>>pre[i]; } for(i=1;i<=n;i++){ num.push_back(p[i]-b[i]); num.push_back(p[i]+b[i]); num.push_back(-s[i]); q[i]={-s[i],p[i]+b[i],p[i]-b[i],0,1,0}; } for(i=n+1;i<=n+m;i++){ num.push_back(inc[i-n]-pre[i-n]); num.push_back(-inc[i-n]); num.push_back(inc[i-n]+pre[i-n]); q[i]={-inc[i-n],inc[i-n]+pre[i-n],inc[i-n]-pre[i-n],i-n,2,0}; } sort(num.begin(),num.end()); num.erase(unique(num.begin(),num.end()),num.end()); for(i=1;i<=n+m;i++){ q[i].p=find(q[i].p); q[i].s=find(q[i].s); q[i].b=find(q[i].b); } n=n+m; sort(q+1,q+1+n); cdq(1,n); for(i=1;i<=m;i++){ cout<<ans[i]<<" "; } cout<<endl; return 0; }