直接暴力枚举所有情况。
1 #include <bits/stdc++.h> 2 using namespace std; 3 map<string,int> mp1; 4 map<string,int> mp2; 5 struct node{ 6 int name,val,pos; 7 } a[55]; 8 int n; 9 int ans; 10 int b[55][55]; 11 int va; 12 string na,po; 13 14 int vis[55]; 15 void dfs(int now,int n1,int n2,int n3,int n4){ 16 if(now>24) return; 17 if(n1>1||n2>4||n3>4||n4>2) return; 18 if(n1==1&&n2==4&&n3==4&&n4==2){ 19 int tmp=0; 20 for(int i=1;i<=23;i++){ 21 if(vis[i]) { 22 tmp+=a[i].val; 23 for(int j=i+1;j<=23;j++){ 24 if(vis[j]) tmp+=b[i][j]; 25 } 26 } 27 } 28 ans=max(ans,tmp); 29 return; 30 } 31 32 vis[now]=1; 33 if(a[now].pos==1) dfs(now+1,n1+1,n2,n3,n4); 34 else if(a[now].pos==2) dfs(now+1,n1,n2+1,n3,n4); 35 else if(a[now].pos==3) dfs(now+1,n1,n2,n3+1,n4); 36 else if(a[now].pos==4) dfs(now+1,n1,n2,n3,n4+1); 37 vis[now]=0; 38 39 dfs(now+1,n1,n2,n3,n4); 40 41 return; 42 } 43 44 int main(){ 45 mp2["goalkeeper"]=1; 46 mp2["defender"]=2; 47 mp2["midfielder"]=3; 48 mp2["striker"]=4; 49 while(cin>>na>>va>>po){ 50 memset(vis,0,sizeof(vis)); 51 memset(b,0,sizeof(b)); 52 ans=-10000000; 53 mp1.clear(); 54 55 mp1[na]=1; 56 a[1].name=1; 57 a[1].val=va; 58 a[1].pos=mp2[po]; 59 for(int i=2;i<=23;i++){ 60 cin>>na>>va>>po; 61 mp1[na]=i; 62 a[i].name=i; 63 a[i].val=va; 64 a[i].pos=mp2[po]; 65 } 66 int m; 67 scanf("%d",&m); 68 for(int i=1;i<=m;i++){ 69 cin>>na>>po>>va; 70 b[mp1[na]][mp1[po]]=va; 71 b[mp1[po]][mp1[na]]=va; 72 } 73 74 dfs(1,0,0,0,0); 75 if(ans==-10000000) printf("impossible "); 76 else printf("%d ",ans); 77 } 78 79 return 0; 80 }
所拆除的边一定是在树的直径上，枚举这些边，每次拆成两棵树，将两棵树中心相连即可，取两棵树直径和中心相连后三个长度的最大值。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 struct node{ 5 int v,w; 6 }; 7 vector<node> g[3005]; 8 void addedge(int u,int v,int w){ 9 g[u].push_back((node){v,w}); 10 g[v].push_back((node){u,w}); 11 } 12 struct node2{ 13 int u,v,w; 14 }; 15 vector<node2> e[3005]; 16 int n; 17 int dis[3005]; 18 int vis[3005]; 19 int deep[3005]; 20 int SPFA(int s,int lim){ 21 memset(vis,0,sizeof(vis)); 22 memset(dis,inf,sizeof(dis)); 23 int ans=s,res=0; 24 queue<int> q; 25 q.push(s); 26 dis[s]=0; vis[s]=1; 27 while(!q.empty()){ 28 int u=q.front(); 29 q.pop(); vis[u]=0; 30 if(dis[u]>res) res=dis[u],ans=u; 31 for(int i=0;i<g[u].size();i++){ 32 int v=g[u][i].v; 33 int w=g[u][i].w; 34 if(v==lim) continue; 35 if(dis[u]+w<dis[v]){ 36 dis[v]=dis[u]+w; 37 if(!vis[v]){ 38 q.push(v); 39 vis[v]=1; 40 } 41 } 42 } 43 } 44 return ans; 45 } 46 int head,tail; 47 bool dfs1(int u,int fa,int ss){ 48 int flag=0; 49 for(int i=0;i<g[u].size();i++){ 50 int v=g[u][i].v; 51 int w=g[u][i].w; 52 if(v==fa) continue; 53 if(dfs1(v,u,ss)){ 54 e[1].push_back((node2){v,u,w}); 55 return true; 56 } 57 } 58 if(u==ss) return true; 59 return false; 60 } 61 void dfs2(int u,int fa,int d){ 62 deep[u]=d; 63 for(int i=0;i<g[u].size();i++){ 64 int v=g[u][i].v; 65 int w=g[u][i].w; 66 if(v==fa) continue; 67 dfs2(v,u,d+1); 68 } 69 } 70 void dfs3(int u,int T,int fa,int lim,int d){ 71 dis[u]=max(dis[u],d); 72 for(int i=0;i<g[u].size();i++){ 73 int v=g[u][i].v; 74 int w=g[u][i].w; 75 if(v==lim) continue; 76 if(v==fa) continue; 77 dfs3(v,T,u,lim,d+w); 78 } 79 } 80 int fun(int S,int T,int lim,int &tmp){ 81 tmp=0; 82 memset(dis,-1,sizeof(dis)); 83 dis[S]=0; 84 dfs3(S,T,0,lim,0); 85 dfs3(T,S,0,lim,0); 86 int res=inf; 87 for(int i=1;i<=n;i++) { 88 if(dis[i]!=-1) res=min(res,dis[i]); 89 tmp=max(dis[i],tmp); 90 } 91 return res; 92 } 93 int solve(int u,int v,int w){ 94 int res=w; 95 int tmp1; 96 int head1=SPFA(u,v); 97 int tail1=SPFA(head1,v); 98 res+=fun(head1,tail1,v,tmp1); 99 int tmp2; 100 int head2=SPFA(v,u); 101 int tail2=SPFA(head2,u); 102 res+=fun(head2,tail2,u,tmp2); 103 res=max(res,tmp1); 104 res=max(res,tmp2); 105 return res; 106 } 107 int main(){ 108 int t; 109 scanf("%d",&t); 110 int T=t; 111 while(t--){ 112 scanf("%d",&n); 113 for(int i=1;i<=n;i++) g[i].clear(); 114 for(int i=1;i<=n;i++) e[i].clear(); 115 for(int i=1;i<n;i++){ 116 int x,y,z; 117 scanf("%d%d%d",&x,&y,&z); 118 addedge(x+1,y+1,z); 119 } 120 head=SPFA(1,0); tail=SPFA(head,0); 121 deep[1]=1; dfs2(1,0,1); dfs1(head,0,tail); 122 int ans=inf; 123 for(int i=0;i<e[1].size();i++) 124 ans=min(ans,solve(e[1][i].u,e[1][i].v,e[1][i].w)); 125 printf("Case %d: %d ",T-t,ans); 126 } 127 128 return 0; 129 }
最大费用流。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 struct edge{ 5 int to,cap,cost,rev; 6 }; 7 vector<edge> g[1000005]; 8 int V; 9 int dis[1000005],vis[1000005]; 10 int prevv[1000005],preve[1000005]; 11 void addedge(int from,int to,int cap,int cost){ 12 g[from].push_back((edge){to,cap,cost,g[to].size()}); 13 g[to].push_back((edge){from,0,-cost,g[from].size()-1}); 14 } 15 void SPFA(int s,int t){ 16 fill(dis,dis+V,inf); 17 fill(vis,vis+V,0); 18 dis[s]=0; vis[s]=1; 19 queue<int> q; 20 q.push(s); 21 while(!q.empty()){ 22 int v=q.front(); 23 q.pop(); 24 vis[v]=0; 25 for(int i=0;i<g[v].size();i++){ 26 edge &e=g[v][i]; 27 if(e.cap>0&&dis[e.to]>dis[v]+e.cost){ 28 dis[e.to]=dis[v]+e.cost; 29 prevv[e.to]=v; 30 preve[e.to]=i; 31 vis[e.to]=1; 32 q.push(e.to); 33 } 34 } 35 } 36 } 37 int min_cost_flow(int s,int t,int f){ 38 int res=0; 39 while(f>0){ 40 SPFA(s,t); 41 if(dis[t]==inf) return -1; 42 int d=f; 43 for(int v=t;v!=s;v=prevv[v]){ 44 d=min(d,g[prevv[v]][preve[v]].cap); 45 } 46 f-=d; 47 res+=d*dis[t]; 48 for(int v=t;v!=s;v=prevv[v]){ 49 edge &e=g[prevv[v]][preve[v]]; 50 e.cap-=d; 51 g[v][e.rev].cap+=d; 52 } 53 } 54 return res; 55 } 56 int n; 57 int val[205][205]; 58 string s[205]; 59 int solve(string s1,string s2){ 60 int cnt=0; 61 int L=s1.size()-1,R=0; 62 while(L>=0&&R<s2.size()){ 63 if(s1[L]==s2[R]) cnt++; 64 else break; 65 L--,R++; 66 } 67 return cnt; 68 } 69 int main(){ 70 while(cin>>n){ 71 for(int i=1;i<=n;i++) cin>>s[i]; 72 for(int i=1;i<=n;i++) 73 for(int j=1;j<=n;j++){ 74 if(i==j) val[i][j]=0; 75 else val[i][j]=solve(s[i],s[j]); 76 } 77 V=n+n+2; 78 for(int i=0;i<V;i++) g[i].clear(); 79 for(int i=1;i<=n;i++){ 80 addedge(0,i,1,0); 81 addedge(i+n,n+n+1,1,0); 82 } 83 for(int i=1;i<=n;i++) 84 for(int j=1;j<=n;j++){ 85 addedge(i,j+n,1,-val[i][j]); 86 } 87 printf("%d ",-min_cost_flow(0,n+n+1,n)); 88 } 89 90 return 0; 91 }
先把所有商品字符串存入字典树。对于每个条形码，取最大值，然后判断每个数是0还是1。匹配的时候跑一遍字典树。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int cnt; 4 struct Trie{ 5 int Next[35]; 6 int ok; 7 } trie[100005]; 8 void add(char s[],int p,int len){ 9 for(int i=0;i<len;i++){ 10 if(trie[p].Next[s[i]-'a']==0){ 11 trie[p].Next[s[i]-'a']=++cnt; 12 } 13 p=trie[p].Next[s[i]-'a']; 14 trie[p].ok++; 15 } 16 } 17 int query(char s[],int p,int len){ 18 for(int i=0;i<len;i++){ 19 if(trie[p].Next[s[i]-'a']==0) return 0; 20 p=trie[p].Next[s[i]-'a']; 21 } 22 return trie[p].ok; 23 } 24 int n,m,k; 25 double a[10]; 26 char s[10005][35]; 27 int pp[]={1,2,4,8,16,32,64,128,256,512}; 28 char fun(){ 29 double ma=a[1]; 30 for(int i=1;i<=8;i++) ma=max(ma,a[i]); 31 ma/=1.5; 32 int res=0; 33 for(int i=1;i<=8;i++){ 34 int now=a[i]<ma?0:1; 35 res=((res<<1)|now); 36 } 37 return res; 38 } 39 int tot; 40 char tmp[35]; 41 int main(){ 42 while(~scanf("%d%d",&n,&m)){ 43 cnt=0; 44 memset(trie,0,sizeof(trie)); 45 for(int i=1;i<=n;i++) { 46 scanf("%s",s[i]); 47 int len=strlen(s[i]); 48 add(s[i],0,len); 49 } 50 int ans=0; 51 for(int i=1;i<=m;i++){ 52 tot=0; 53 scanf("%d",&k); 54 for(int j=1;j<=k;j++){ 55 for(int p=1;p<=8;p++) scanf("%lf",&a[p]); 56 tmp[tot++]=fun(); 57 } 58 ans+=query(tmp,0,tot); 59 //cout<<"ans="<<ans<<endl; 60 } 61 printf("%d ",ans); 62 } 63 64 return 0; 65 }
主席树模板题。（直接把所有int改long long MLE了。。。）
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=200005; 5 int n,m,cnt,tot; 6 int T[N],a[N]; 7 struct node{ 8 int l,r,sum; 9 } tre[N*40]; 10 int c[N]; 11 int lowbit(int x){ 12 return x&(-x); 13 } 14 void add(int pos,int val){ 15 for(int i=pos;i<=n;i+=lowbit(i)) 16 c[i]+=val; 17 } 18 int sum(int pos){ 19 int res=0; 20 for(int i=pos;i>0;i-=lowbit(i)) 21 res+=c[i]; 22 return res; 23 } 24 void update(int l,int r,int &x,int y,int pos){ 25 tre[++cnt]=tre[y]; 26 tre[cnt].sum++; 27 x=cnt; 28 if(l==r) return; 29 int mid=(l+r)/2; 30 if(mid>=pos) 31 update(l,mid,tre[x].l,tre[y].l,pos); 32 else 33 update(mid+1,r,tre[x].r,tre[y].r,pos); 34 } 35 int query(int l,int r,int x,int y,int k){ 36 if(l==r) return l; 37 int mid=(l+r)/2; 38 int sum=tre[tre[y].l].sum-tre[tre[x].l].sum; 39 if(sum>=k) 40 return query(l,mid,tre[x].l,tre[y].l,k); 41 else 42 return query(mid+1,r,tre[x].r,tre[y].r,k-sum); 43 44 } 45 vector<int> v; 46 int getid(int x){ 47 return lower_bound(v.begin(),v.end(),x)-v.begin()+1; 48 } 49 struct Query{ 50 int op,x,y,z; 51 } que[200005]; 52 int main(){ 53 int Case=0; 54 while(~scanf("%d",&m)){ 55 Case++; 56 v.clear(); 57 tot=cnt=0; 58 memset(c,0,sizeof(c)); 59 LL ans1=0,ans2=0,ans3=0; 60 for(int i=1;i<=m;i++){ 61 char tmp[15]; 62 int x,y,z; 63 scanf("%s",tmp); 64 if(!strcmp(tmp,"Insert")){ 65 que[i].op=1; 66 scanf("%d",&que[i].x); 67 v.push_back(que[i].x); 68 } 69 if(!strcmp(tmp,"Query_1")){ 70 que[i].op=2; 71 scanf("%d%d%d",&que[i].x,&que[i].y,&que[i].z); 72 } 73 if(!strcmp(tmp,"Query_2")){ 74 que[i].op=3; 75 scanf("%d",&que[i].x); 76 } 77 if(!strcmp(tmp,"Query_3")){ 78 que[i].op=4; 79 scanf("%d",&que[i].x); 80 } 81 } 82 sort(v.begin(),v.end()); 83 v.erase(unique(v.begin(),v.end()),v.end()); 84 n=v.size(); 85 for(int i=1;i<=m;i++){ 86 if(que[i].op==1){ 87 tot++; 88 add(getid(que[i].x),1); 89 update(1,n,T[tot],T[tot-1],getid(que[i].x)); 90 } 91 if(que[i].op==2){ 92 ans1+=v[query(1,n,T[que[i].x-1],T[que[i].y],que[i].z)-1]; 93 } 94 if(que[i].op==3){ 95 ans2+=sum(getid(que[i].x)-1)+1; 96 } 97 if(que[i].op==4){ 98 ans3+=v[query(1,n,T[0],T[tot],que[i].x)-1]; 99 } 100 } 101 102 printf("Case %d: ",Case); 103 printf("%lld ",ans1); 104 printf("%lld ",ans2); 105 printf("%lld ",ans3); 106 } 107 108 return 0; 109 }
二分图匹配，因为要求字典序最大，所以匹配时从后往前匹配即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int V,n; 4 int x,y; 5 vector<int> g[111111]; 6 int vis[111111],match[111111]; 7 void addedge(int u,int v){ 8 g[u].push_back(v); 9 g[v].push_back(u); 10 } 11 bool dfs(int u){ 12 vis[u]=1; 13 for(int i=0;i<g[u].size();i++){ 14 int v=g[u][i],w=match[v]; 15 if(w<0 || !vis[w] && dfs(w)){ 16 match[v]=u; 17 match[u]=v; 18 return true; 19 } 20 } 21 return false; 22 } 23 int hungarian(){ 24 int res=0; 25 memset(match,-1,sizeof(match)); 26 for(int u=V-1;u>=0;u--){ 27 if(match[u]<0){ 28 memset(vis,0,sizeof(vis)); 29 if(dfs(u)) res++; 30 } 31 } 32 return res; 33 } 34 int main(){ 35 int t; 36 scanf("%d",&t); 37 while(t--){ 38 for(int i=0;i<110000;i++) 39 g[i].clear(); 40 scanf("%d",&n); 41 for(int i=1;i<=n;i++){ 42 scanf("%d%d",&x,&y); 43 for(int j=x;j<=y;j++){ 44 addedge(i-1,j+n-1); 45 } 46 } 47 V=n; 48 hungarian(); 49 vector<int> ans; 50 for(int i=0;i<n;i++){ 51 if(match[i]!=-1) ans.push_back(i+1); 52 } 53 printf("%d ",ans.size()); 54 for(int i=0;i<ans.size();i++){ 55 printf("%d",ans[i]); 56 if(i==ans.size()-1) printf(" "); 57 else printf(" "); 58 } 59 } 60 61 return 0; 62 }