2013多校第1回

C:法則の問題を探します.主にテーマの加算をマッチ取りのモデルと結びつけて,配列の組み合わせの原理を利用して式を探す.
小结:私は最初からずっとすべての数とすべての数の出现の回数を研究して、およびテーマの与えるf(n)=2^(n-1)はどんな関系があって、最后にも何の结论を研究していないで、题解を见てやっと知ったのです.
コード:

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 2005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define MOD 1000000007
using namespace std;
long long POW(long long a,long long n)
{
    long long ret=1;
    while(n)
    {
        if(n&1)
        {
            ret=(ret*a)%MOD;
        }
        n/=2;
        a=(a*a)%MOD;
    }
    return ret;
}
int main()
{
    int t;
    int n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);//2^(n-k-2)*(n-k+3)  n>k
        if(n<k)
        {
            printf("0
");
        }
        else if(n==k)
        {
            printf("1
");
        }
        else if(n==(k+1))
        {
            long long ans=(n-k+3)/2;
            cout<<ans<<endl;
        }
        else
        {
            long long ans=POW(2,n-k-2)*(n-k+3)%MOD;
            cout<<ans<<endl;
        }
    }
	return 0;
}

H木の直径を求めて、それから探し出した公式に連絡します.
木の直径を求めて、使ったのは双DFSの方法です.
DFS(u),uは任意の点をとり,d[v]最大の点v,すなわちuまでの距離が最大の点を見つける.
そしてDFS(v)は、最大距離d[u']の最大値、すなわちツリーの直径を求める.
探している点数が木の直径+1より小さい場合、答えはk-1です.そうでなければ、直径を歩くたびに枝の点に多くアクセスし、l+(k-l-1)*2.
コード:

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 100005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define MOD 1000000007
using namespace std;
vector<int> g[maxn];
int n,m,k,l;
int d[maxn];
void dfs(int u,int pre,int st)
{
   d[u]=st;
   for(int i=0;i<g[u].size();i++)
   {
       if(g[u][i]!=pre)
       dfs(g[u][i],u,st+1);
   }
}
int main()
{
    int t,u,v,ret;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            g[v].push_back(u);
            g[u].push_back(v);
        }
        ret=1;
        dfs(ret,0,0);
        for(int i=2;i<=n;i++)
        {
            if(d[i]>d[ret])
            ret=i;
        }
        dfs(ret,0,0);
        for(int i=1;i<=n;i++)
        {
            if(d[i]>d[ret])
            ret=i;
        }
        int l=d[ret];
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&k);
            if(k<=(l+1))
            {
                //cout<<k-1<<endl;
                printf("%d
",k-1);
            }
            else
            {
                //cout<<l+(k-l-1)*2<<endl;
                printf("%d
",l+(k-l-1)*2);
            }
        }
    }
    return 0;
}

J.シミュレーション問題、シミュレーション大数加算.
私は配列で各数を保存し、ある数が10に達すると1に進み、本位は0になる.
コード:

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 100005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define MOD 1000000007
using namespace std;
char s[maxn];
int a[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        int l=strlen(s),sum=0;
        if(l==1&&s[0]=='0')
        {
            cout<<19<<endl;
            continue;
        }
        a[0]=0;
        for(int i=0;i<l;i++)
        {
            sum+=(s[i]-'0');
            a[i+1]=(s[i]-'0');//1-l
        }
        sum++,a[l]++;
        int flag=0;
        while(sum%10!=0)
        {
            if(flag==1)
            {
                sum++;
                a[l]++;
            }
            flag=1;
            for(int i=l;i>=1;i--)
            {
                if(a[i]==10)
                {
                    a[i]=0;
                    a[i-1]++;
                    sum-=9;
                }
                else
                {
                    break;
                }
            }
        }
        if(a[0]!=0) cout<<a[0];
        for(int i=1;i<=l;i++)
        cout<<a[i];
        cout<<endl;
    }
    return 0;
}