Another Graph Game

思路：（官方题解）

若没有边权，则对点权从大到小排序即可。。

考虑边，将边权拆成两半加到它所关联的两个点的点权中即可。

。。因为当两个人分别选择不同的点时，这一权值将互相抵消。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define LL __int64
 6 using namespace std;
 7 const int maxn=100010;
 8 double st[maxn];
 9 bool cmp(double a,double b)
10 {
11     return a>b;
12 }
13 int main()
14 {
15     int n,m;
16     while(scanf("%d%d",&n,&m)!=EOF)
17     {
18         int i,j;
19         for(i=1;i<=n;i++)
20         {
21             scanf("%lf",&st[i]);
22         }
23         int u,v;
24         double w;
25         for(i=1;i<=m;i++)
26         {
27             scanf("%d%d%lf",&u,&v,&w);
28             st[u]+=w/2;
29             st[v]+=w/2;
30         }
31         sort(st+1,st+n+1,cmp);
32         double sum=0;
33         for(i=1;i<=n;i+=2)
34         {
35             if(i+1<=n)
36             {
37                 sum+=(st[i]-st[i+1]);
38             }
39             else
40             sum+=st[i];
41         }
42         printf("%I64d
",(LL)sum);
43     }
44     return 0;
45 }

View Code

problem 1006（hdu 4648）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4648

Magic Pen 6

思路：（官方题解）

题意转化一下就是：

给出一列数a[1]...a[n]，求长度最长的一段连续的数，使得这些数的和能被M整除。

分析：

设这列数前i项和为s[i],

则一段连续的数的和 a[i]+a[i+1]+...+a[j-1]+a[j]=s[j]-s[i-1]，

所以这段连续的数的和能被m整除的条件就是 (s[j]-s[i-1]) % m == 0，

即 s[j]%m-s[i-1]%m == 0，

因此，只需要每一个余数找使s[i]%m等于该余数的最小的i，和s[j]%m等于该余数的最大的j，相减即为最长的连续的数的长度。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define LL __int64
 6 using namespace std;
 7 const int maxn=10010;
 8 LL sum[maxn*10];
 9 int hash[maxn];
10 int main()
11 {
12     //freopen("1006.in","r",stdin);
13    // freopen("output.out","w",stdout);
14     int n,m;
15     while(scanf("%d%d",&n,&m)!=EOF)
16     {
17         int i;
18         LL a;
19         int mmax=0;
20         memset(hash,-1,sizeof(hash));
21         hash[0]=0;
22         for(i=1; i<=n; i++)
23         {
24             scanf("%I64d",&a);
25             a=a%m;
26             if(a<0)
27                 a+=m;
28             if(i==1)
29                 sum[i]=a;
30             else
31                 sum[i]=sum[i-1]+a;
32             sum[i]%=m;
33             if(hash[sum[i]]==-1)
34             {
35                 hash[sum[i]]=i;
36             }
37             int ch;
38             ch=i-hash[sum[i]];
39             if(ch>mmax)
40                 mmax=ch;
41         }
42         printf("%d
",mmax);
43     }
44     return 0;
45 }

View Code

problem 1007（hdu 4649）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4649

Professor Tian

思路：

dp[i][j]表示该位取前i个数，运算得到j(0或1)的概率是多少。

则：有状态转移方程

若不选择第i个数：
dp[i][j][0]=dp[i-1][j][0]*p[i];//第j位为0的概率

dp[i][j][1]=dp[i-1][j][1]*p[i];//第j位为1的概率
若选择第i个数：

dp[i][j][(0|da[i][j])]+=dp[i-1][j][0]*(1-p[i]);//操作为'|'时j位为0的概率
dp[i][j][(1|da[i][j])]+=dp[i-1][j][1]*(1-p[i]);//操作为‘|’时j位为1的概率

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 const int maxn=205;
 6 double dp[maxn][21][2];
 7 int  data[maxn];
 8 double p[maxn];
 9 char sstr[maxn*4];
10 char str[maxn];
11 int da[maxn][21];
12 int main()
13 {
14     int n;
15     int k=0;
16     while(scanf("%d",&n)!=EOF)
17     {
18 
19         int i,j;
20         k++;
21         memset(da,0,sizeof(da));
22         memset(dp,0,sizeof(dp));
23         for(i=0; i<=n; i++)
24         {
25             scanf("%d",&data[i]);
26             for(j=0; j<20; j++)
27             {
28                 if(((1<<j)&data[i])!=0)
29                 da[i][j]=1;
30                 else
31                 da[i][j]=0;
32             }
33         }
34         getchar();
35         gets(sstr);
36         //puts(sstr);
37         int len=strlen(sstr);
38         int u=1;
39         for(i=0; i<len; i++)
40         {
41             if((sstr[i]=='|')||(sstr[i]=='&')||(sstr[i]=='^'))
42             {
43                 str[u]=sstr[i];
44                 u++;
45                 //printf("[%c]
 ",sstr[i]);
46             }
47         }
48         for(i=1; i<=n; i++)
49         {
50             scanf("%lf",&p[i]);
51         }
52         for(j=0; j<20; j++)
53         {
54             if(da[0][j]==1)
55             {
56                 dp[0][j][1]=1;
57                 dp[0][j][0]=0;
58             }
59             else
60             {
61                 dp[0][j][0]=1;
62                 dp[0][j][1]=0;
63             }
64         }
65         for(i=1; i<=n; i++)
66         {
67             for(j=0; j<20; j++)
68             {
69                 dp[i][j][0]=dp[i-1][j][0]*p[i];
70                 dp[i][j][1]=dp[i-1][j][1]*p[i];
71                 if(str[i]=='|')
72                 {
73                     dp[i][j][(0|da[i][j])]+=dp[i-1][j][0]*(1-p[i]);
74                     dp[i][j][(1|da[i][j])]+=dp[i-1][j][1]*(1-p[i]);
75                 }
76                 else if(str[i]=='&')
77                 {
78                     dp[i][j][(0&da[i][j])]+=dp[i-1][j][0]*(1-p[i]);
79                     dp[i][j][(1&da[i][j])]+=dp[i-1][j][1]*(1-p[i]);
80                 }
81                 else
82                 {
83                     dp[i][j][(0^da[i][j])]+=dp[i-1][j][0]*(1-p[i]);
84                     dp[i][j][(1^da[i][j])]+=dp[i-1][j][1]*(1-p[i]);
85                 }
86                 //printf("%d %d = %.6f %.6f
",i,j,dp[i][j][0],dp[i][j][1]);
87             }
88 
89         }
90         double ans=0;
91         for(i=0; i<20; i++)
92         {
93             //printf("%f
",dp[n][i][1]);
94             ans+=dp[n][i][1]*(1<<i);
95         }
96         printf("Case %d:
",k);
97         printf("%.6f
",ans);
98     }
99 }

View Code

problem 1009（hdu 4651）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4651

Partition

思路：五边形定理

公式：P(n)=(-1)^(i-1)*P(n-q(i))...q(i)=3*（i^2)±i，（i=0，±1，±2，.......)

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int maxn=100010;
 7 const __int64 mod=1000000007;
 8 __int64 res[maxn];
 9 __int64 q[maxn];
10 __int64 fq[maxn];
11 void init()
12 {
13     int i;
14     memset(res,0,sizeof(res));
15     res[0]=1;
16     res[1]=1;
17     res[2]=2;
18     res[3]=3;
19     for(i=1;i<=1000;i++)
20     {
21         q[i]=(3*i*i-i)/2;
22         fq[i]=(3*i*i+i)/2;
23         if(fq[i]>2*maxn)
24         {
25             break;
26         }
27     }
28     int fi;
29     int n;
30     for(n=4;n<maxn-5;n++)
31     {
32         int num=0;
33         i=1;
34         while(n-q[i]>=0)
35         {
36             num+=pow(-1,i-1)*res[n-q[i]];
37             num%=mod;
38             if(n-fq[i]>=0)
39             {
40                 fi=-i;
41                 num+=pow(-1,fi-1)*res[n-fq[i]];
42                 num%=mod;
43             }
44             else
45             break;
46             i++;
47         }
48         res[n]=num%mod;
49         if(res[n]<0)
50         res[n]+=mod;
51     }
52 }
53 int main()
54 {
55     int T;
56     scanf("%d",&T);
57     init();
58     while(T--)
59     {
60         int n;
61         scanf("%d",&n);
62         printf("%I64d
",res[n]);
63     }
64     return 0;
65 }

View Code