1009 I-number

题目本身很简单，找出比给出的数大的第一个各位数相加和是10的倍数的数

只是因为数据量很大，数字的长度最大为10^5，所以要用char来存和计算，会用的JAVA BIGＩＮＴ的人会很简单。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

char s[100005];
int sum,aa;

int main()
{
    int t;
    int n,m,l;
    int q;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        q = 0;
        gets(s);
        l = strlen(s);
        sum = 0;
        for(int i=0; i<l; i++)
        {
            sum += s[i] - '0';
        }
        if(s[l-1] == '9')
        {
            aa = 0;
            sum++;
            aa++;
            s[l-1] = '0';
            m = l - 2;
            while(m>=0&&s[m] == '9')
            {
                sum++;
                aa++;
                s[m] = '0';
                m--;
            }
            if(m>=0)
            {
                s[m] = s[m] + 1;
            }
            else
            {
                q = 1;
            }
            sum++;
            aa++;
            //cout<<aa<<endl;
        }
        else
        {
            sum++;
            s[l-1] = s[l-1] + 1;
        }
        while(sum%10!=0)
        {
            if(s[l-1] == '9')
            {
                sum++;
                s[l-1] = '0';
                m = l - 2;
                while(m>=0&&s[m] == '9')
                {
                    sum++;
                    s[m] = '0';
                    m--;
                }
                if(m>=0)
                {
                    s[m] = s[m] + 1;
                }
                else
                {
                    q = 1;
                }
                sum++;
            }
            else
            {
                sum++;
                s[l-1] = s[l-1] + 1;
            }
        }
        if(q == 1)
        {
            printf("1%s\n",s);
        }
        else
        {
            printf("%s\n",s);
        }
    }
    return 0;
}

１００８　Park Visit

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define inf 1<<28
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c = getchar();
    }
    while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
struct xl
{
    int e , next;
} ed[11111111];
int head[111111] ,num;
int dis[11111111] ;
int pp  ;
int n , m ;
bool vis[1111111] ;
int qe[11111111] ;
void init(int a ,int b )
{
    ed[num].e = b ;
    ed[num].next = head[a] ;
    head[a] = num ++ ;
}
void init()
{
    memset(head,-1,sizeof(head));
    num=0;
}
int bfs(int pos)
{
    int i,h = 0 ,t = 0 ;
    for(i = 0 ; i <= n ; i ++ )
    {
        dis[i]=inf;
        vis[i]=0;
    }
    dis[pos] = 0 ;
    qe[h ++ ] = pos ;
    int mx = 0 ;
    vis[pos] = 1 ;
    while(h > t)
    {
        int temp = qe[t ++ ] ;
        for (int i = head[temp] ; ~i ; i  = ed[i].next )
        {
            int now = ed[i].e ;
            if(dis[now] > dis[temp] + 1)
            {
                dis[now] = dis[temp] + 1 ;
                qe[h ++ ] = now ;
                if(dis[now] > mx)
                {
                    mx = dis[now] ;
                    pp = now ;
                }
            }
        }
    }
    return mx ;
}
int main()
{

    int T,i;
    scanf("%d",&T);
    while(T--)
    {

        init() ;
        scanf("%d%d",&n,&m);
        int a , b ;
        for(i=0; i<n-1; i++)
        {
            RD(a);
            RD(b);
            init(a,b) ;
            init(b,a) ;
        }
        bfs(1) ;
        int mm = bfs(pp) ;
        while(m--)
        {
            int k ;
            RD(k) ;
            if(k <= mm)
            {
                printf("%d\n", k-1) ;
            }
            else
            {
                printf("%d\n",(k-mm-1)*2+mm) ;
            }
        }
    }
    return 0 ;
}