2017ACM-ICPC沈阳区域赛

I-Little Boxes【大数】

hdu6225 http://acm.hdu.edu.cn/showproblem.php?pid=6225

题意：

就是给四个大数，输出和。

思路：

java大法好。用long longWA了一发

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 
 4 public class Main {
 5 
 6     //static Scanner scan;
 7     //static BigInteger a, b, c, d;
 8     static public void main(String[] args){
 9         Scanner scan = new Scanner(System.in);
10         int t = scan.nextInt();
11         BigInteger a, b, c, d;
12         for(int i = 0; i < t; i++){
13             a = scan.nextBigInteger();
14             b = scan.nextBigInteger();
15             c = scan.nextBigInteger();
16             d = scan.nextBigInteger();
17             BigInteger ans = a.add(b).add(c).add(d);
18 
19             System.out.println(ans);
20         }
21 
22     }
23 }

View Code

K-Rabbits

hdu6227 http://acm.hdu.edu.cn/showproblem.php?pid=6227

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn = 500 + 5;
 5 
 6 int a[maxn];
 7 
 8 int main()
 9 {
10     int T;
11     cin >> T;
12     while (T--) {
13         int N;
14         cin >> N;
15         int ans = 0;
16         for (int i = 0; i < N; i++) {
17             scanf("%d", a+i);
18             if (i >= 1)
19                 ans += a[i]-a[i-1]-1;
20         }
21         ans -= min(a[1]-a[0]-1, a[N-1]-a[N-2]-1);
22         cout << ans << endl;
23     }
24     return 0;
25 }
26 /*
27 5
28 6
29 1 3 5 7 9 11
30 6
31 1 3 5 7 9 12
32 */

View Code

F-Haron and His Triangle【大数】【规律】

hdu6222 http://acm.hdu.edu.cn/showproblem.php?pid=6222

题意：一个三角形的边长分别是t -1, t, t+1，要求他的面积是整数。问大于等于n的最小的t是多少。

思路：首先海伦公式推出一个式子。打了前10000的表，czc秒看出递推公式。i+1 = 4 * i - (i-1)。又一次java大法。因为刚好10^30忘记放进去了WA了一发，下次还是要注意不要开刚好的，稍微大一点。

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 
 4 public class Main {
 5 
 6     //static Scanner scan;
 7     //static BigInteger a, b, c, d;
 8     static BigInteger[] num = new BigInteger[100000];
 9     static public void main(String[] args){
10         Scanner scan = new Scanner(System.in);
11         num[1] = new BigInteger("4");
12         num[2] = new BigInteger("14");
13         BigInteger maxn = new BigInteger("10");
14         maxn = maxn.pow(31);
15         //System.out.println(maxn);
16         int i;
17         for(i = 3; ; i++){
18             num[i] = new BigInteger("0");
19             BigInteger x = new BigInteger("4");
20             BigInteger tmp = BigInteger.ZERO;
21             tmp = num[i - 1].multiply(x);
22             tmp = tmp.subtract(num[i - 2]);
23             if(tmp.compareTo(maxn) == 1)break;
24             else num[i] = tmp;
25         }
26 
27         //System.out.println(i);
28         int t = scan.nextInt();
29         for(int cas = 1; cas <= t; cas++){
30             BigInteger n = scan.nextBigInteger();
31             for(int j = 1; j <= i; j++){
32                 if(num[j].compareTo(n) != -1){
33                     System.out.println(num[j]);
34                     break;
35                 }
36             }
37         }
38     }
39 }

View Code

L-Tree【DFS】

hdu6228 http://acm.hdu.edu.cn/showproblem.php?pid=6228

题意：

给一棵有n个节点的树上k种颜色。边集Ei表示使颜色i的所有节点联通的最小边集。求所有边集E的交集的最大值。

思路：

一条边可行或是不可行，就看他连接的两块。如果两块的大小都大于等于k，那么这条边肯定是交集的一部分，因为肯定存在一种上色方案使得左边k种颜色右边k种，而且大家肯定都要经过这条边，所以这条边肯定在交集里面。DFS一遍。

正好碰上大二他们周赛拉了这题自己写了一下

 1 #include <iostream>
 2 #include <set>
 3 #include <cmath>
 4 #include <stdio.h>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 using namespace std;
11 typedef long long LL;
12 #define inf 0x7f7f7f7f
13 
14 int t, n, k;
15 const int maxn = 2e5 + 5;
16 struct edge{
17     int u, v, nxt;
18 }e[maxn];
19 int head[maxn], tot;
20 int cnt_son[maxn];
21 
22 void addedge(int u, int v)
23 {
24     e[tot].v = v;
25     e[tot].u = u;
26     e[tot].nxt = head[u];
27     head[u] = tot++;
28     e[tot].v = u;
29     e[tot].u = v;
30     e[tot].nxt = head[v];
31     head[v] = tot++;
32 }
33 
34 void init()
35 {
36     tot = 0;
37     for(int i = 0; i <= n; i++){
38         head[i] = -1;
39         cnt_son[i] = 0;
40     }
41 }
42 
43 void dfs(int rt, int fa)
44 {
45     for(int i = head[rt]; i != -1; i = e[i].nxt){
46         if(e[i].v == fa)continue;
47         dfs(e[i].v, rt);
48         cnt_son[rt] += cnt_son[e[i].v];
49     }
50     cnt_son[rt]++;
51 }
52 
53 int main()
54 {
55     scanf("%d", &t);
56     while(t--){
57         scanf("%d%d", &n, &k);
58         init();
59         for(int i = 0; i < n - 1; i++){
60             int u, v;
61             scanf("%d%d", &u, &v);
62             addedge(u, v);
63         }
64         dfs(1, 0);
65         //cout<<1<<endl;
66         int cnt = 0;
67         /*for(int i = 1; i <= n; i++){
68             cout<<cnt_son[i]<<endl;
69         }*/
70         for(int i = 0; i < tot; i++){
71             int v = e[i].v, u = e[i].u;
72             if(cnt_son[u] < cnt_son[v]){
73                 swap(u, v);
74             }
75             if(cnt_son[v] >= k && n - cnt_son[v] >= k){
76                 cnt++;
77             }
78         }
79         printf("%d
", cnt / 2);
80     }
81     return 0;
82 }

View Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=150000+10;
 4 
 5 int n,k;
 6 int ans;
 7 
 8 struct Edge{
 9     int u,v;
10     Edge(int u=0,int v=0){this->u=u,this->v=v;}
11 };
12 vector<Edge> E;
13 vector<int> G[maxn];
14 void init(int l,int r)
15 {
16     E.clear();
17     for(int i=l;i<=r;i++) G[i].clear();
18 }
19 void addedge(int u,int v)
20 {
21     E.push_back(Edge(u,v));
22     G[u].push_back(E.size()-1);
23 }
24 
25 int vis[maxn];
26 int dfs(int now)
27 {
28     vis[now]=1;
29     int tot=1;
30     for(int i=0;i<G[now].size();i++)
31     {
32         Edge &e=E[G[now][i]]; int nxt=e.v;
33         if(!vis[nxt]) tot+=dfs(nxt);
34     }
35     if(n-tot>=k && tot>=k) ans++;
36     return tot;
37 }
38 
39 int main()
40 {
41     int T;
42     cin>>T;
43     while(T--)
44     {
45         scanf("%d%d",&n,&k);
46         init(1,n);
47         for(int i=1;i<n;i++)
48         {
49             int u,v;
50             scanf("%d%d",&u,&v);
51             addedge(u,v);
52             addedge(v,u);
53         }
54 
55         memset(vis,0,sizeof(vis));
56         ans=0;
57         dfs(1);
58         printf("%d
",ans);
59     }
60 }

View Code

M-Wandering Robots【概率】（未）

hdu6229 http://acm.hdu.edu.cn/showproblem.php?pid=6229

题意：

给定一个n*n的矩形，机器人初始在（0,0）。矩形中有k个障碍物，给定他们的坐标。机器人在格子（i，j）时，他走到邻近的可走的格子和停留在原地的概率相同。

问最后机器人停在（x,y）其中x+y>=n-1的概率是多少。

思路：

当我们走了很久以后，每一个格子都已经走到了。那么对于这个正方形来说，每一个小格子都有xi种走法（即自己+相邻的可走的格子数），总的正方形一共有N种走法。对于某一个格子（i，j）有（自己+相邻的可走的格子数）种走法是可以到达自己的。所以答案就是要求区域的走法/所有格子的走法

由于n比较大数组是开不下的，所以只能存障碍。用map来映射一下。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int,int> pii;
 4 
 5 const int maxn=10000+10;
 6 const int maxk=1000+10;
 7 const int dx[4]={0,1,0,-1};
 8 const int dy[4]={1,0,-1,0};
 9 
10 int n,k;
11 map<pii,bool> mp;
12 int p,q;
13 
14 inline int gcd(int m,int n){return n?gcd(n,m%n):m;}
15 inline int check(const int &x,const int &y)
16 {
17     if(x<0||x>=n||y<0||y>=n) return 0;
18 
19     if((x==0||x==n-1) && (y==0||y==n-1))  return 3;
20     else if((x==0||x==n-1) && (y!=0&&y!=n-1))  return 4;
21     else if((y==0||y==n-1) && (x!=0&&x!=n-1))  return 4;
22     else return 5;
23 }
24 
25 int main()
26 {
27     int T;
28     cin>>T;
29     for(int kase=1;kase<=T;kase++)
30     {
31         mp.clear();
32 
33         scanf("%d%d",&n,&k);
34         for(int i=1,x,y;i<=k;i++)
35         {
36             scanf("%d%d",&x,&y);
37             mp[make_pair(x,y)]=1;
38         }
39 
40         p=3*3+2*(n-2)*4+(n-2)*(n-1)/2*5;
41         q=4*3+4*(n-2)*4+(n-2)*(n-2)*5;
42         for(map<pii,bool>::iterator it=mp.begin();it!=mp.end();it++)
43         {
44             int x=((*it).first).first;
45             int y=((*it).first).second;
46             if(x+y>=n-1) p-=check(x,y);
47             q-=check(x,y);
48 
49             for(int i=0;i<4;i++)
50             {
51                 int nxtx=x+dx[i];
52                 int nxty=y+dy[i];
53                 if(check(nxtx,nxty)>0 && mp.count(make_pair(nxtx,nxty))==0)
54                 {
55                     if(nxtx+nxty>=n-1) p--;
56                     q--;
57                 }
58             }
59         }
60 
61         int g=gcd(p,q);
62         printf("Case #%d: %d/%d
",kase,p/g,q/g);
63     }
64 }

View Code

G--Infinite Fraction Path【暴力】【规律】（未）

hdu6223 http://acm.hdu.edu.cn/showproblem.php?pid=6223

题意：

给定一个串，第i位会走到第（i*i+1）%n位去。问能表示的最大的数是多少。

思路：

发现循环节很短，暴力。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int MAX_L = 50;
 6 const int MAX_N = 150000 + 5;
 7 
 8 int ind[MAX_N];
 9 int ansind[MAX_L];
10 bool vis[MAX_N];
11 
12 int main()
13 {
14     int T, kase = 1;
15     cin >> T;
16     while (T--) {
17         int N;
18         string num;
19         cin >> N >> num;
20         for (ll i = 0; i < N; i++)
21             ind[i] = (i*i+1)%N;
22 
23         string ans;
24         for (int jjj = 0; jjj < MAX_L; jjj++)
25             ans += '0';
26         for (int i = 0; i < N; i++) {
27             int jjj = 0, iii = i;
28             while (jjj < MAX_L && num[iii] == ans[jjj]) {
29                 iii = ind[iii];
30                 jjj++;
31             }
32             if (num[iii] < ans[jjj])
33                 continue;
34             while (jjj < MAX_L) {
35                 ans[jjj] = num[iii];
36                 ansind[jjj] = iii;
37                 jjj++;
38                 iii = ind[iii];
39             }
40         }
41         memset(vis, false, sizeof vis);
42         int j;
43         for (j = MAX_L-1; j >= 0; j--) {
44             if (vis[ansind[j]])
45                 break;
46             vis[ansind[j]] = true;
47         }
48         int jjjjj = ansind[j];
49         printf("Case #%d: ", kase++);
50         for (int i = 0; i < N; i++) {
51             if (i < MAX_L)
52                 cout << ans[i];
53             else {
54                 jjjjj = ind[jjjjj];
55                 cout << num[jjjjj];
56             }
57         }
58         cout << endl;
59     }
60     return 0;
61 }
62 /*
63 4
64 3
65 149
66 5
67 12345
68 7
69 3214567
70 9
71 261025520
72 */

View Code

C-Empty Convex Polygon【最大空凸包】

poj1259The Picnic & hdu6219

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6219

http://poj.org/problem?id=1259

一份代码A两题。

题意：

给n个点，求一个面积最大的空凸包。

思路：

空凸包，就是一个内部没有其他给定点的凸包。

详细讲解见：https://blog.csdn.net/nyroro/article/details/45268767

总的来说就是先枚举凸包的最左下角的点O。按照极坐标排序。

dp[i][j]表示组成凸包的最后一个三角形的是Oij时的最大面积。dp[i][j]=max(dp[i][j],triangle(O,i,j)+dp[j][k])

再枚举凸包上最后的一个点i，枚举所有比i小的合法的j。

具体讲解见：https://blog.csdn.net/cdsszjj/article/details/79366813

复杂度O(n^3)

  1 #include<iostream>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<stdio.h>
  5 #include<cstring>
  6 #include<vector>
  7 #include<map>
  8 #include<set>
  9 
 10 #define inf 0x3f3f3f3f
 11 using namespace std;
 12 typedef long long LL;
 13 
 14 const int maxn = 105;
 15 struct point{
 16     double x, y;
 17     point(){}
 18     point(double _x, double _y):x(_x), y(_y){}
 19     point operator + (const point &b) const{return point(x + b.x, y + b.y);}
 20     point operator - (const point &b) const{return point(x - b.x, y - b.y);}
 21     double operator * (const point &b) const {return x * b.y - y * b.x;}
 22     double len() const {return x * x + y * y;}
 23     /*int operator < (const point &a) const
 24     {
 25         if((*this)*a > 0 || (*this) *a == 0 && len() < a.len())
 26             return 1;
 27         return 0;
 28     }*/
 29 
 30 }a[maxn], p[maxn], yuan;
 31 /*bool cmp(const point &a, const point &b)
 32 {
 33     int c = a * b;
 34     if(c == 0)return a.len() < b.len();
 35     return c > 0;
 36 }*/
 37 double dp[maxn][maxn], ans;
 38 int t, n, m;
 39 bool cmp(const point &a, const point &b)
 40 {
 41     int res = (a - yuan) * (b - yuan);
 42     if(res)return res > 0;
 43     return (a - yuan).len() < (b - yuan).len();
 44 }
 45 void solve()
 46 {
 47     memset(dp, 0, sizeof(dp));
 48     sort(p + 1, p + m + 1, cmp);
 49     for(int i = 1; i <= m; i++){
 50         int j = i - 1;
 51         while(j && !((p[i] - yuan) * (p[j] - yuan)))j--;
 52         bool bz = (j == i - 1);
 53         while(j){
 54             int k = j - 1;
 55             while(k && (p[i] - p[k]) * (p[j] - p[k]) > 0)k--;
 56             double area = fabs((p[i] - yuan) * (p[j] - yuan)) / 2;
 57             if(k) area += dp[j][k];
 58             if(bz) dp[i][j] = area;
 59             ans = max(ans, area);
 60             j = k;
 61         }
 62         if(bz){
 63             for(int j = 1; j < i; j++){
 64                 dp[i][j] = max(dp[i][j], dp[i][j - 1]);
 65             }
 66         }
 67     }
 68 }
 69 
 70 int getint()
 71 {
 72     int i = 0, f = 1;
 73     char c;
 74     for(c = getchar(); (c != '-') && (c < '0' || c > '9'); c = getchar());
 75     if(c == '-')f = -1, c = getchar();
 76     for(;c >= '0' && c <= '9'; c = getchar())i = (i << 3) + (i << 1) + c - '0';
 77     return i * f;
 78 }
 79 
 80 int main(){
 81 
 82     //scanf("%d", &t);
 83     t = getint();
 84     while(t--){
 85         //scanf("%d", &n);
 86         n = getint();
 87         ans = 0;
 88         for(int i = 1; i <= n; i++){
 89             cin>>a[i].x>>a[i].y;
 90         }
 91         for(int i = 1; i <= n; i++){
 92             yuan = a[i];
 93             m = 0;
 94             for(int j = 1; j <= n; j++){
 95                 if(a[j].y > a[i].y || a[j].y == a[i].y && a[j].x > a[i].x)
 96                     p[++m] = a[j];//只取右上角的点
 97             }
 98             solve();
 99 
100         }
101         printf("%0.1f
", ans);
102     }
103     return 0;
104 }

View Code

H-Legends of the Three Kingdoms

题意：

三国杀游戏大模拟。有主公忠臣反贼内奸，告诉你他们的血量，每回合砍一个人，主公忠臣不会互相砍。为最后的胜率。

思路：

因为血量最大是40，4个人，所以可以暴力记忆化搜索。

存一下当前这样分数的情况下的胜率。

dfs的时候先判断有没有出现游戏结束，再判断如果当前回合轮到的人死了怎么办

然后就是根据回合砍人，找到胜率最大的更新。

数组刚开始开到45MLE了，然后TLE了。因为用了memset。

其实每次是不需要重新初始化的，因为相当于边跑边打表。反正是不影响的。而且memset emmm...秦皇岛T的还不够开心吗。

  1 #include<iostream>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<stdio.h>
  5 #include<cstring>
  6 #include<vector>
  7 #include<map>
  8 #include<set>
  9 
 10 #define inf 0x3f3f3f3f
 11 using namespace std;
 12 typedef long long LL;
 13 
 14 int t;
 15 int zhugong, zhongchen, fanzei, neijian;
 16 double pzhu[4][40][40][40][40], pfan[4][40][40][40][40], pnei[4][40][40][40][40];
 17 bool vis[4][40][40][40][40];
 18 
 19 struct node{
 20     double pz, pf, pn;
 21     void init()
 22     {
 23         pz = pf = pn = -1;
 24     }
 25     //node(){}
 26     //node(double a, double b, double c):pz(a), pf(b), pn(c){}
 27 };
 28 
 29 
 30 //出牌顺序 主0反1忠2内3
 31 node dfs(int turn, int zhu, int zhong, int fan, int nei)
 32 {
 33     if(vis[turn][zhu][zhong][fan][nei])
 34         return (node){pzhu[turn][zhu][zhong][fan][nei], pfan[turn][zhu][zhong][fan][nei], pnei[turn][zhu][zhong][fan][nei]};
 35     vis[turn][zhu][zhong][fan][nei] = true;
 36     if(zhu == 0 && zhong == 0 && fan == 0 && nei > 0){//内奸获胜
 37         pzhu[turn][zhu][zhong][fan][nei] = 0;
 38         pfan[turn][zhu][zhong][fan][nei] = 0;
 39         pnei[turn][zhu][zhong][fan][nei] = 1;
 40     }
 41     else if(zhu == 0){//反贼获胜
 42         pzhu[turn][zhu][zhong][fan][nei] = 0;
 43         pfan[turn][zhu][zhong][fan][nei] = 1;
 44         pnei[turn][zhu][zhong][fan][nei] = 0;
 45     }
 46     else if(fan == 0 && nei == 0){//主公忠臣获胜
 47         pzhu[turn][zhu][zhong][fan][nei] = 1;
 48         pfan[turn][zhu][zhong][fan][nei] = 0;
 49         pnei[turn][zhu][zhong][fan][nei] = 0;
 50     }
 51     else if(fan == 0 && turn == 1){
 52         node tmp = dfs((turn + 1) % 4, zhu, zhong, fan, nei);
 53         pzhu[turn][zhu][zhong][fan][nei] = tmp.pz;
 54         pfan[turn][zhu][zhong][fan][nei] = tmp.pf;
 55         pnei[turn][zhu][zhong][fan][nei] = tmp.pn;
 56     }
 57     else if(zhong == 0 && turn == 2){
 58         node tmp = dfs((turn + 1) % 4, zhu, zhong, fan, nei);
 59         pzhu[turn][zhu][zhong][fan][nei] = tmp.pz;
 60         pfan[turn][zhu][zhong][fan][nei] = tmp.pf;
 61         pnei[turn][zhu][zhong][fan][nei] = tmp.pn;
 62     }
 63     else if(nei == 0 && turn == 3){
 64         node tmp = dfs((turn + 1) % 4, zhu, zhong, fan, nei);
 65         pzhu[turn][zhu][zhong][fan][nei] = tmp.pz;
 66         pfan[turn][zhu][zhong][fan][nei] = tmp.pf;
 67         pnei[turn][zhu][zhong][fan][nei] = tmp.pn;
 68     }
 69     else{
 70         if(turn == 0){
 71             node tmp[2];
 72             for(int i = 0; i < 2; i++)tmp[i].init();
 73             if(fan > 0){
 74                 tmp[0] = dfs((turn + 1) % 4, zhu, zhong, fan - 1, nei);
 75             }
 76             if(nei > 0){
 77                 tmp[1] = dfs((turn + 1) % 4, zhu, zhong, fan, nei - 1);
 78             }
 79             double zhumax = max(tmp[0].pz, tmp[1].pz);
 80             int cnt = 0;
 81             double zhus = 0, fans = 0, neis = 0;
 82             for(int i = 0; i < 2; i++){
 83                 if(zhumax == tmp[i].pz){
 84                     cnt++;
 85                     zhus += tmp[i].pz;
 86                     fans += tmp[i].pf;
 87                     neis += tmp[i].pn;
 88                 }
 89             }
 90             pzhu[turn][zhu][zhong][fan][nei] = zhus / cnt;
 91             pfan[turn][zhu][zhong][fan][nei] = fans / cnt;
 92             pnei[turn][zhu][zhong][fan][nei] = neis / cnt;
 93         }
 94         else if(turn == 1){
 95             node tmp[3];
 96             for(int i = 0; i < 3; i++)tmp[i].init();
 97             if(zhu > 0){
 98                 tmp[0] = dfs((turn+1)%4, zhu - 1, zhong, fan, nei);
 99             }
100             if(zhong > 0){
101                 tmp[1] = dfs((turn + 1) % 4, zhu, zhong - 1, fan, nei);
102             }
103             if(nei > 0){
104                 tmp[2] = dfs((turn + 1) % 4, zhu, zhong, fan, nei - 1);
105             }
106             double fanmax = max(tmp[0].pf, tmp[1].pf);
107             fanmax = max(fanmax, tmp[2].pf);
108             int cnt = 0;
109             double zhus = 0, fans = 0, neis = 0;
110             for(int i = 0; i < 3; i++){
111                 if(fanmax == tmp[i].pf){
112                     cnt++;
113                     zhus += tmp[i].pz;
114                     fans += tmp[i].pf;
115                     neis += tmp[i].pn;
116                 }
117             }
118             pzhu[turn][zhu][zhong][fan][nei] = zhus / cnt;
119             pfan[turn][zhu][zhong][fan][nei] = fans / cnt;
120             pnei[turn][zhu][zhong][fan][nei] = neis / cnt;
121         }
122         else if(turn == 2){
123             node tmp[2];
124             for(int i = 0; i < 2; i++)tmp[i].init();
125             if(fan > 0){
126                 tmp[0] = dfs((turn + 1) % 4, zhu, zhong, fan - 1, nei);
127             }
128             if(nei > 0){
129                 tmp[1] = dfs((turn + 1) % 4, zhu, zhong, fan, nei - 1);
130             }
131             double zhongmax = max(tmp[0].pz, tmp[1].pz);
132             int cnt = 0;
133             double zhus = 0, fans = 0, neis = 0;
134             for(int i = 0; i < 2; i++){
135                 if(zhongmax == tmp[i].pz){
136                     cnt++;
137                     zhus += tmp[i].pz;
138                     fans += tmp[i].pf;
139                     neis += tmp[i].pn;
140                 }
141             }
142             pzhu[turn][zhu][zhong][fan][nei] = zhus / cnt;
143             pfan[turn][zhu][zhong][fan][nei] = fans / cnt;
144             pnei[turn][zhu][zhong][fan][nei] = neis / cnt;
145         }
146         else if(turn == 3){
147             node tmp[3];
148             for(int i = 0; i < 3; i++)tmp[i].init();
149             if(zhu > 0){
150                 tmp[0] = dfs((turn + 1) % 4, zhu - 1, zhong, fan, nei);
151             }
152             if(zhong > 0){
153                 tmp[1] = dfs((turn + 1) % 4, zhu, zhong - 1, fan, nei);
154             }
155             if(fan > 0){
156                 tmp[2] = dfs((turn + 1) % 4, zhu, zhong, fan - 1, nei);
157             }
158             double neimax = max(tmp[0].pn, tmp[1].pn);
159             neimax = max(neimax, tmp[2].pn);
160             int cnt = 0;
161             double zhus = 0, fans = 0, neis = 0;
162             for(int i = 0; i < 3; i++){
163                 if(neimax == tmp[i].pn){
164                     cnt++;
165                     zhus += tmp[i].pz;
166                     fans += tmp[i].pf;
167                     neis += tmp[i].pn;
168                 }
169             }
170             pzhu[turn][zhu][zhong][fan][nei] = zhus / cnt;
171             pfan[turn][zhu][zhong][fan][nei] = fans / cnt;
172             pnei[turn][zhu][zhong][fan][nei] = neis / cnt;
173         }
174     }
175     return (node){pzhu[turn][zhu][zhong][fan][nei], pfan[turn][zhu][zhong][fan][nei], pnei[turn][zhu][zhong][fan][nei]};
176 }
177 
178 int main(){
179 
180     scanf("%d", &t);
181     while(t--){
182         scanf("%d%d%d%d", &zhugong, &zhongchen, &fanzei, &neijian);
183         //memset(vis, 0, sizeof(vis));
184         /*for(int i = 0; i < 4; i++){
185             for(int a = 0; a <= zhugong; a++){
186                 for(int b = 0; b <= zhongchen; b++){
187                     for(int f = 0; f <= fanzei; f++){
188                         for(int n = 0; n <= neijian; n++){
189                             vis[i][a][b][f][n] = 0;
190                         }
191                     }
192                 }
193             }
194         }*/
195         node ans = dfs(0, zhugong, zhongchen, fanzei, neijian);
196         printf("%.6f %.6f %.6f
", ans.pz, ans.pf, ans.pn);
197     }
198     return 0;
199 }

View Code

以及：

本次重现最令人开心的事情哈哈哈哈哈哈哈哈哈哈哈哈