CodeForces475

A. Splits

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <set>

 #include <list>

 #include <map>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const long maxn=1e5;

 const long mod=1e9+;

 int main()

 {

     long n,i;

     scanf("%ld",&n);

     printf("%ld",+n/);

     return ;

 }

B. Messages

贪心

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <set>

#include <list>

#include <map>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

const long maxn=1e5;

const long mod=1e9+;

int main()

{

    long n,a,b,c,T,t,v,i,sum=;

    scanf("%ld%ld%ld%ld%ld",&n,&a,&b,&c,&T);

    sum=a*n;

    for (i=;i<=n;i++)

    {

        scanf("%ld",&t);

        if (b<=c)

            sum=sum+(c-b)*(T-t);

    }

    cout<<sum<<endl;

    return ;

}

C. Alternating Sum

快速幂 求逆元 等比数列

1. 1e9+9不是素数

2. 等比数列，公比可能为0

3. 数的数目为n+1

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <set>

 #include <list>

 #include <map>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const long maxn=1e5;

 const long long mod=1e9+;

 #define ll long long

 ll x,y;

 ll mul(ll s,long ci)

 {

     ll r=;

     while (ci)

     {

         if ((ci & )==)

             r=r*s%mod;

         s=s*s%mod;

         ci=ci>>;

     }

     return r;

 }

 void gcd(ll a,ll b)

 {

     if (b==)

     {

         x=;

         y=;

     }

     else

     {

         ll r;

         gcd(b,a%b);

         r=x;

         x=y;

         y=r-a/b*y;

     }

 }

 ll ni(ll s)

 {

     gcd(mod,s);

     return (y%mod+mod)%mod;

 }

 int main()

 {

     long n,k,i;

     long long a,b,ni_a,ni_a_k,a_k,b_k,sum,c,d;

     char ch;

     scanf("%ld%lld%lld%ld\n",&n,&a,&b,&k);

     c=mul(a,n);

     b_k=mul(b,k);

     a_k=mul(a,k);

     ni_a=ni(a);

     ni_a_k=ni(a_k);

     sum=;

     for (i=;i<=k;i++)

     {

         scanf("%c",&ch);

         if (ch=='+')

             sum=(sum+c)%mod;

         else

             sum=(sum-c+mod)%mod;

     }

     d=(n+)/k;

     c=ni_a_k * b_k %mod;

     if (c==)

         printf("%lld",sum*d%mod);

     else

         printf("%lld",sum* ((mul(c,d)%mod-+mod)%mod) %mod *ni(c-)%mod);

     return ;

 }

D. Destruction of a Tree

树结构，从叶子向根，先确定子节点是否删边，然后父节点是否删边就可以确定，当根节点不删边，则成立，否则不成立

输出删点次序：从叶子向根，遇到需要删边的点，则删边，通过遍历所有的子辈节点，遇到不需要删除边的点，则输出，继续遍历，否则结束

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <set>

 #include <list>

 #include <map>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const long maxn=2e5+;

 const long long mod=1e9+;

 #define ll long long

 struct node

 {

     long d;

     struct node *next;

 }*point[maxn];

 long need[maxn],fa[maxn];

 bool vis[maxn],feng[maxn];

 long pr[maxn],pr_count=;

 void dfs(long d)

 {

     long cc=;

     vis[d]=true;

     struct node *p=point[d];

     while (p)

     {

         if (!vis[p->d])

         {

             cc++;

             dfs(p->d);

             need[d]=need[d] ^ need[p->d];

         }

         else

             fa[d]=p->d;

         p=p->next;

     }

 }

 void print(long d)

 {

     printf("%ld\n",d);

     struct node *p=point[d];

     while (p)

     {

         if (fa[d]!=p->d && need[p->d]==)

             print(p->d);

         p=p->next;

     }

 }

 void work(long d)

 {

     struct node *p=point[d];

     struct node *q;

     while (p)

     {

         if (fa[d]!=p->d)

             work(p->d);

         p=p->next;

     }

     if (need[d]==)

     {

         printf("%ld\n",d);

         p=point[d];

         while (p)

         {

             if (fa[d]!=p->d && need[p->d]==)

                 print(p->d);

             p=p->next;

         }

     }

 }

 int main()

 {

     struct node *p;

     long n,root,i,y;

     scanf("%ld",&n);

     for (i=;i<=n;i++)

     {

         point[i]=NULL;

         need[i]=;    //

         vis[i]=false;

     }

     for (i=;i<=n;i++)

     {

         scanf("%ld",&y);

         if (y==)

             root=i;

         else

         {

             p=(struct node *) malloc (sizeof(struct node));

             p->d=y;

             p->next=point[i];

             point[i]=p;

             p=(struct node *) malloc (sizeof(struct node));

             p->d=i;

             p->next=point[y];

             point[y]=p;

         }

     }

     need[root]=;

     fa[root]=;

     dfs(root);

     if (need[root]==)

     {

         printf("NO");

         return ;

     }

     printf("YES\n");

     work(root);

     return ;

 }

 /*

 9

 0 1 1 2 2 2 3 6 6

 9

 0 1 1 1 3 3 3 6 6

 5

 0 1 2 3 4

 */