1001 Arranging Your Team
直接暴力枚舉所有情況。
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\n");
76 else printf("%d\n",ans);
77 }
78
79 return 0;
80 } Psong
1002 Building Roads
所拆除的邊一定是在樹的直徑上，枚舉這些邊，每次拆成兩棵樹，将兩棵樹中心相連即可，取兩棵樹直徑和中心相連後三個長度的最大值。
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\n",T-t,ans);
126 }
127
128 return 0;
129 } Psong
1003 Card Game
最大費用流。
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\n",-min_cost_flow(0,n+n+1,n));
88 }
89
90 return 0;
91 } Psong
1004 Delta Wave
1005 Encoded Barcodes
先把所有商品字元串存入字典樹。對于每個條形碼，取最大值，然後判斷每個數是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\n",ans);
62 }
63
64 return 0;
65 } Psong
1006 Farm
1007 Graph and Queries
1008 Jewel
主席樹模闆題。（直接把所有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:\n",Case);
103 printf("%lld\n",ans1);
104 printf("%lld\n",ans2);
105 printf("%lld\n",ans3);
106 }
107
108 return 0;
109 } Psong
1009 Hyperspace Travel
1010 I'm Telling the Truth
二分圖比對，因為要求字典序最大，是以比對時從後往前比對即可。
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\n",ans.size());
54 for(int i=0;i<ans.size();i++){
55 printf("%d",ans[i]);
56 if(i==ans.size()-1) printf("\n");
57 else printf(" ");
58 }
59 }
60
61 return 0;
62 } Psong
轉載于:https://www.cnblogs.com/N-Psong/p/7196536.html