这场要是算分的话估计就有机会涨到紫了，4个题1A。
A题：
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000100; const int INF=1<<29; int n,m; int a[maxn]; int main() { freopen("in.txt","r",stdin); while(cin>>n>>m){ REP(i,1,n) scanf("%d",&a[i]); sort(a+1,a+n+1); int ans=0; for(int i=n;i>=1;i--){ if(m<=0) break; m-=a[i]; ans++; } cout<<ans<<endl; } return 0; }
B题：
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000100; const int INF=1<<29; int n,m; int a[maxn]; ll cnt[maxn]; ll dfs(int st,int cur) { if(st>=m||cur>m) return 0; ll res=cnt[st]*cnt[cur]; if(cur==m) return res+dfs(st+1,st+2); else return res+dfs(st,cur+1); } int main() { freopen("in.txt","r",stdin); while(cin>>n>>m){ MS0(cnt); REP(i,1,n) scanf("%d",&a[i]),cnt[a[i]]++; cout<<dfs(1,2)<<endl; } return 0; }
C题：
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000100; const int INF=1<<29; int n; int a[maxn]; bool cmp(int a,int b) { return a>b; } int main() { freopen("in.txt","r",stdin); while(cin>>n){ ll s=0; REP(i,1,n) scanf("%d",&a[i]),s+=a[i]; sort(a+1,a+n+1,cmp); ll ans=0; REP(i,1,s%n){ if(a[i]>s/n+1) ans+=a[i]-(s/n+1); } REP(i,s%n+1,n){ if(a[i]>s/n) ans+=a[i]-s/n; } cout<<ans<<endl; } return 0; }
E题：多次询问包括某条边的最小生成树。树链剖分找这条边路径上的最大边权，然后将这条边权去掉就好了。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; typedef long long ll; const int maxn=1000100; const int INF=1<<29; int n,m; ll mst; struct Edge { int u,v;ll w; int id; friend bool operator<(Edge A,Edge B) { return A.w<B.w; } };Edge e[maxn]; int Fa[maxn]; struct Tree { int u,v; ll w; };Tree tr[maxn];int trn; vector<int> G[maxn]; int fa[maxn],dep[maxn],son[maxn],siz[maxn]; int top[maxn]; int id[maxn],num; ll Max[maxn<<2]; ll val[maxn]; int Find(int x) { return Fa[x]==x?x:Fa[x]=Find(Fa[x]); } void dfs1(int u,int f,int d) { fa[u]=f; dep[u]=d; son[u]=0; siz[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f) continue; dfs1(v,u,d+1); if(siz[v]>siz[son[u]]) son[u]=v; siz[u]+=siz[v]; } } void dfs2(int u,int tp) { top[u]=tp; id[u]=++num; if(son[u]) dfs2(son[u],tp); for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } void push_up(int rt) { Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); } void build(int l,int r,int rt) { if(l==r){ Max[rt]=val[l]; return; } int m=(l+r)>>1; build(lson); build(rson); push_up(rt); } ll query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return Max[rt]; int m=(l+r)>>1; ll res=-INF; if(L<=m) res=max(res,query(L,R,lson)); if(R>m) res=max(res,query(L,R,rson)); return res; } ll cha(int u,int v) { ll res=-INF; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); res=max(res,query(id[top[u]],id[u],1,num,1)); u=fa[top[u]]; } if(u!=v){ if(dep[u]>dep[v]) swap(u,v); res=max(res,query(id[son[u]],id[v],1,num,1)); } return res; } bool cmpID(Edge A,Edge B) { return A.id<B.id; } int main() { freopen("in.txt","r",stdin); while(cin>>n>>m){ REP(i,1,m) scanf("%d%d%I64d",&e[i].u,&e[i].v,&e[i].w),e[i].id=i; sort(e+1,e+m+1); REP(i,1,n) Fa[i]=i; mst=0;trn=0; REP(i,1,n) G[i].clear(); REP(i,1,m){ int x=Find(e[i].u),y=Find(e[i].v); if(x!=y){ Fa[x]=y; mst+=e[i].w; tr[++trn]={e[i].u,e[i].v,e[i].w}; G[e[i].u].push_back(e[i].v); G[e[i].v].push_back(e[i].u); } } //REP(i,1,trn) cout<<tr[i].u<<" "<<tr[i].v<<" -- "<<tr[i].w<<endl; dfs1(1,0,1); num=0; dfs2(1,1); REP(i,1,trn){ if(dep[tr[i].u]>dep[tr[i].v]) swap(tr[i].u,tr[i].v); val[id[tr[i].v]]=tr[i].w; } build(1,num,1); sort(e+1,e+m+1,cmpID); REP(i,1,m){ ll tmp=cha(e[i].u,e[i].v); printf("%I64d ",mst-tmp+e[i].w); } } return 0; }