BestCoder Round #75 解题报告

King's Cake

【思路】

    递推

    公式：f(n,m)=f(max(m,n-m),min(m,n-m))+1，n>m

【代码】

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 int max(int a,int b) 
 6 {
 7     return a>b? a:b;
 8 }
 9 int min(int a,int b) 
10 {
11     return a>b? b:a;
12 }
13 int f(int n,int m)
14 {
15     if(n==m) return 1;
16     return f(max(m,n-m),min(m,n-m))+1;
17 }
18 
19 int main()
20 {
21     int T,n,m;
22     scanf("%d",&T);
23     while(T--) {
24         scanf("%d%d",&n,&m);
25         printf("%d
",f(max(n,m),min(n,m)));
26     }
27     return 0;
28 }
View Code

King's Phone

【思路】

    模拟

【代码】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 #define LL long long
 7 int map[5][5];
 8 int a[10],b[10];
 9 int t,k,c,p,q;
10 bool f,f1,f2;
11 void change(int c,int i){
12         if(c>6) a[i]=3,b[i]=c-6;
13         else if(c>3) a[i]=2,b[i]=c-3;
14         else a[i]=1,b[i]=c;
15 }
16 void fuc(int i){
17     if(abs(a[i]-a[i-1])>1) f1=1; else f1=0;
18     if(abs(b[i]-b[i-1])>1) f2=1; else f2=0;
19 }
20 void judge() {
21     map[a[1]][b[1]]=1;
22     for(int i=2;i<=k;i++)
23     {
24         if(map[a[i]][b[i]]) f=0;
25         map[a[i]][b[i]]=1;
26         fuc(i);
27         if(f1&&f2){
28              if(map[2][2]==0) f=0;
29         }
30         else if(f1&&b[i]==b[i-1]){
31             if(map[2][b[i]]==0) f=0;
32         } 
33         else if(f2&&a[i]==a[i-1]){
34              if(map[a[i]][2]==0) f=0;
35         }
36         if(f==0) return ;
37     }
38 }
39 int main() {
40     scanf("%d",&t);
41     while(t--) {
42         memset(map,0,sizeof(map)); f=1;
43         cin>>k; 
44         for(int i=1;i<=k;i++)
45         {
46             cin>>c;
47             if(c>9||c==0) f=0;
48             change(c,i);
49         }
50         if(f==0||k<4||k>9) 
51         {
52             puts("invalid");
53             continue;
54         }
55         judge();
56         if(f) puts("valid");
57         else puts("invalid");
58     }
59 }
View Code

King's Order

【思路】

    DP

    设f[i][j][k]表示i位数，最后为j，且已有k个连续，则有转移式：

        f[i+1][j’][1]<-f[i][j][k]

        f[i+1][j][k+1]<-f[i][j][k]，k+1<=3

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int N = 2e3+10;
 6 const int M = 30;
 7 const int MOD = 1e9+7;
 8 
 9 int f[N][M][4],n,T;
10 
11 int main()
12 {
13     scanf("%d",&T);
14     while(T--) {
15         memset(f,0,sizeof(f));
16         scanf("%d",&n);
17         for(int i=0;i<26;i++) f[1][i][1]=1;
18         for(int i=1;i<=n;i++)
19             for(int j=0;j<26;j++)
20                 for(int k=1;k<=3;k++) if(f[i][j][k]) {
21                     if(k<3) f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%MOD;
22                     for(int jj=0;jj<26;jj++) if(jj!=j)
23                         f[i+1][jj][1]=(f[i+1][jj][1]+f[i][j][k])%MOD;
24                 }
25         int ans=0;
26         for(int i=0;i<26;i++)
27             for(int j=1;j<=3;j++)
28                 ans=(ans+f[n][i][j])%MOD;
29         printf("%d
",ans);
30     }
31     return 0;
32 }
View Code

King's Game

【思路】

    约瑟夫问题变种

    对应正常约瑟夫:有n个人，每隔k个去一个。设f[n]表示n个人最后剩下的人：

        f[n]=f[n-1]+k mod n

    对于本题设f[n][k]表示n个人规则为k，则有递推公式：

        f[n][k]=f[n-1][k+1]+k mod n

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int N =  5e3+10;
 6 
 7 int f[N][2],cur;
 8 
 9 void get_pre()
10 {
11     for(int i=2;i<=5000;i++) {
12         for(int j=i-2;j>=0;j--) {
13             f[i][(j%2)]=(f[i][(j%2)^1]+j+1)%(i-j);
14         }
15     }
16 }
17 
18 int main()
19 {    
20     int T,n;
21     get_pre();
22     scanf("%d",&T);
23     while(T--) {
24         scanf("%d",&n);
25         printf("%d
",f[n][0]+1);
26     }
27     return 0;
28 }
View Code

King's Pliot

【思路】

    最大流最小费用流。

    构图：

 

    不过这个题，如果只由S向Yp连边，不连Xi Xi+1也可以AC

    对于Yi->Yi+1的INF连边是不是说一个飞行员可以延迟上班时间，如果是这样那么题目描述显然有误 [思考熊]。

　 UPD：题目中的描述“他会在上次工作 T​j​​ 天后重新回来工作”实在模糊，如果按照题解中的思路他的意思应该为在Tj天之后的任意天回来。

【代码】

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
  6 using namespace std;
  7 
  8 typedef long long LL;
  9 const int maxn = 4000+10;
 10 const int INF = 1e9;
 11 
 12 struct Edge{ 
 13     int u,v,cap,flow,cost;
 14     Edge(int u=0,int v=0,int cap=0,int flow=0,int cost=0)
 15         :u(u),v(v),cap(cap),flow(flow),cost(cost){}
 16 };
 17 
 18 struct MCMF {
 19     int n,m,s,t;
 20     int inq[maxn],a[maxn],d[maxn],p[maxn];
 21     vector<int> G[maxn];
 22     vector<Edge> es;
 23     
 24     void init(int n) {
 25         this->n=n;
 26         es.clear();
 27         for(int i=0;i<=n;i++) G[i].clear();
 28     }
 29     void AddEdge(int u,int v,int cap,int cost) {
 30         es.push_back(Edge(u,v,cap,0,cost));
 31         es.push_back(Edge(v,u,0,0,-cost));
 32         m=es.size();
 33         G[u].push_back(m-2);
 34         G[v].push_back(m-1);
 35     }
 36     
 37     bool SPFA(int s,int t,int& flow,int& cost) {
 38         for(int i=0;i<n;i++) d[i]=INF;
 39         memset(inq,0,sizeof(inq));
 40         d[s]=0; inq[s]=1; p[s]=0; a[s]=INF; 
 41         queue<int> q; q.push(s);
 42         while(!q.empty()) {
 43             int u=q.front(); q.pop(); inq[u]=0;
 44             for(int i=0;i<G[u].size();i++) {
 45                 Edge& e=es[G[u][i]];
 46                 int v=e.v;
 47                 if(e.cap>e.flow && d[v]>d[u]+e.cost) {
 48                     d[v]=d[u]+e.cost;
 49                     p[v]=G[u][i];
 50                     a[v]=min(a[u],e.cap-e.flow);        //min(a[u],..)
 51                     if(!inq[v]) { inq[v]=1; q.push(v); }
 52                 }
 53             }
 54         }
 55         if(d[t]==INF) return false;
 56         flow+=a[t] , cost+=a[t]*d[t];
 57         for(int x=t; x!=s; x=es[p[x]].u) {
 58             es[p[x]].flow+=a[t]; es[p[x]^1].flow-=a[t];
 59         }
 60         return true;
 61     }
 62     void Mincost(int s,int t,int& flow,int& cost) {
 63         flow=0; cost=0;
 64         while(SPFA(s,t,flow,cost)) ;
 65     }
 66 } mc;
 67 
 68 int n,K,T,m,P,Q;
 69 
 70 int main()
 71 {
 72     scanf("%d",&T);
 73     while(T--) {
 74         scanf("%d%d",&n,&K);
 75         mc.init(n*2+4);
 76         int s=0,t=n*2+1;
 77         int p,sum=0;
 78         FOR(i,1,n) {
 79             scanf("%d",&p);
 80             sum+=p;
 81             mc.AddEdge(s,i,p,0);
 82             mc.AddEdge(i+n,t,p,0);
 83             if(i>1) {
 84                 mc.AddEdge(i-1,i,INF,0);
 85                 mc.AddEdge(i-1+n,i+n,INF,0);
 86             }
 87         }
 88         scanf("%d%d%d",&m,&P,&Q);
 89         FOR(i,1,m) {
 90             int ss,tt;
 91             scanf("%d%d",&ss,&tt);
 92             FOR(j,1,n)
 93                 if(j+tt<=n) mc.AddEdge(j,n+j+tt,INF,ss);
 94                 else break;
 95         }
 96         mc.AddEdge(s,n+1,K,0);
 97         mc.AddEdge(s,P+n,INF,Q);
 98         int flow,cost;
 99         mc.Mincost(s,t,flow,cost);
100         if(flow!=sum) puts("No solution");
101         else printf("%d
",cost);
102     }
103     return 0;
104 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lidaxin/p/5309606.html