Another Graph Game

思路：（官方题解）

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

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

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

1 #include 
      
        2 #include
       
         3 #include
        
          4 #include
         
           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             else40             sum+=st[i];41         }42         printf("%I64d\n",(LL)sum);43     }44     return 0;45 }

View Code

problem 1006（hdu 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 
      
        2 #include
       
         3 #include
        
          4 #include
         
           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             else31                 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\n",mmax);43     }44     return 0;45 }

View Code

problem 1007（hdu 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
      
        2 #include
       
         3 #include
        
          4 #include
         
           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<

View Code

problem 1009（hdu 4651）

题目：

Partition

思路：五边形定理

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

1 #include 
      
        2 #include
       
         3 #include
        
          4 #include
         
           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
          
           =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             else45             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\n",res[n]);63     }64     return 0;65 }