Codeforces 135 div2

A.   k-String

简单题，不解释，统计每个字母出现的次数之后YY即可

B.   Special Offer! Super Price 999 Bourles! 

YY题，枚举末尾9的出现次数，然后找到出现这么多9且小于n的最大数，然后判断他们两数之差是否小于等于d即可。

代码很挫

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int digit[30];
int next[30];
int a[30];
int b[30];
int up;

long long Change(int *p)
{
  //  printf("%d\n",up);
    int n=up,i;
    __int64 ret=0;
    for (i=0;i<n;i++)
    {
        ret=ret*10+p[i];
    }
    return ret;
}

int main()
{
    int t,i,tag,j,ok;
    __int64 n,m,k,x,y,d;
    scanf("%I64d%I64d",&n,&d);
    t=0;
    m=n;
    up=0;
    while(m)
    {
        a[up++]=m%10;
        m/=10;
    }
    for (i=0;i<up/2;i++)
    {
        t=a[i];
        a[i]=a[up-i-1];
        a[up-i-1]=t;
    }
    for (i=up;i>=0;i--)
    {
        ok=0;
        for (j=up-1;j>up-i-1;j--)
        {
            b[j]=9;
            if (b[j]>a[j]) ok=1;
        }
        for (j=up-i-1;j>=0;j--)
        {
            if (ok==1)
            {
                if (a[j]==0) b[j]=9;
                else
                {
                    b[j]=a[j]-1;
                    ok=0;
                }
            }
            else
            {
                b[j]=a[j];
            }
        }
        for (j=0;j<up;j++)
        {
            if (a[j]>b[j]) break;
            if (a[j]<b[j]) break;
        }
        if (j!=up && a[j]<b[j]) continue;
        x=Change(b);
        y=Change(a);
        if (y-x>d) continue;
        t=0;
        while(b[t]==0) {t++;}
        for (j=t;j<up;j++)
        {
            printf("%d",b[j]);
        }
        printf("\n");
        break;
    }
    return 0;
}
           

C.简单dp。

dp[i][j]表示排到第i个，该位置颜色为j的最小替换次数，然后就是简单的状态转移再加记录路径。

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define INF 1000000000

int dp[500005][30];
char str[500005];
char ans[500005];

int main()
{
    int i,j,n,k,m,tag,s;
    scanf("%d%d",&n,&m);
    scanf("%s",str);
    for (i=0;i<n;i++)
    {
        for (j=0;j<m;j++)
        {
            dp[i][j]=INF;
        }
    }
    for (i=0;i<m;i++)
    {
        if (str[0]=='A'+i) dp[0][i]=0;
        else dp[0][i]=1;
    }
    for (i=1;i<n;i++)
    {
        for (j=0;j<m;j++)
        {
            for (k=0;k<m;k++)
            {
                if (j==k) continue;
                if (str[i]==j+'A') dp[i][j]=min(dp[i][j],dp[i-1][k]);
                else dp[i][j]=min(dp[i][j],dp[i-1][k]+1);
            }
        }
    }
    tag=-1;
    s=INF;
    for (i=0;i<m;i++)
    {
        if (s>dp[n-1][i])
        {
            s=dp[n-1][i];
            tag=i;
        }
    }
    printf("%d\n",s);
    for (i=n-1;i>0;i--)
    {
        ans[i]=tag+'A';
        for (j=0;j<m;j++)
        {
            if (j==tag) continue;
            if (str[i]!=tag+'A' && dp[i][tag]==dp[i-1][j]+1 || str[i]==tag+'A' && dp[i][tag]==dp[i-1][j])
            {
                tag=j;
                break;
            }
        }
    }
    ans[i]=tag+'A';
    for (i=0;i<n;i++)
    {
        printf("%c",ans[i]);
    }
    printf("\n");
    return 0;
}
           

D.树形dp。

扫两遍，第一遍求出dp[i]，表示通过翻转边使得i能达到以i为根节点的子树上的所有节点的翻转次数。

第二遍求出ans[i]，表示从i点出发能到达所有点的翻转次数。

假设父节点为last，子节点为t，那么假设已知父节点的ans[last]，那么ans[t]=ans[last]+delta

其中delta表示如果存在的边是last->t，那么在ans[last]时就已经多加了个1，所以要减去1.

如果存在的边是t->last，表示ans[last]在这条边上是没有加1的，所以要加上1.

代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef struct Point
{
    int x,y;
    bool operator<(const Point &other) const
    {
        if (x!=other.x) return x<other.x;
        return y<other.y;
    }
};

int dp[510005];
vector <int> p[510005];
map <Point,int> m;
int ans[510005];

void DFS1(int t,int last)
{
    int i,j,k;
    Point tag;
    dp[t]=0;
    for (i=0;i<p[t].size();i++)
    {
        k=p[t][i];
        if (k==last) continue;
        DFS1(k,t);
        tag.x=t;
        tag.y=k;
        dp[t]+=dp[k]+m[tag];
    }
}

void DFS2(int t,int last)
{
    int i,j,k;
    Point tag;
    tag.x=last;
    tag.y=t;
    if (last==-1) ans[t]=dp[t];
    else
    {
        if (m[tag]==0) ans[t]=ans[last]+1;
        else ans[t]=ans[last]-1;
    }
    for (i=0;i<p[t].size();i++)
    {
        k=p[t][i];
        if (k==last) continue;
        DFS2(k,t);
    }
}

int main()
{
    int i,j,n,x,y,ok,s;
    Point tag;
    scanf("%d",&n);
    for (i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        p[x].push_back(y);
        p[y].push_back(x);
        tag.x=y;
        tag.y=x;
        m[tag]=1;
    }
    DFS1(1,-1);
    DFS2(1,-1);
    s=100000005;
    for (i=1;i<=n;i++)
    {
        s=min(s,ans[i]);
    }
    printf("%d\n",s);
    ok=0;
    for (i=1;i<=n;i++)
    {
        if (ok==0 && s==ans[i])
        {
            printf("%d",i);
            ok=1;
        }
        else if (s==ans[i])
        {
            printf(" %d",i);
        }
    }
    printf("\n");
}