《第二届太原理工大学程序设计新生赛决赛》

没人写题解..那我来水一发.
A：博弈论。
可以发现连续的一段可以看成一样的。
那么由于1起手。
所以如果两边都是黑。相当于后手变先手。
然后统计下能操作的次数为奇偶即可。
Code:

void run()
{
    int n;sd(n);
    string s;cin >> s;
    char c = s[n-1];
    int ma = 0;
    for(int i = n-2;i >= 0;--i)
    {
        if(s[i] != c)
        {
            ma++;
            c = s[i];
        }
    }
    if(ma == 0)
    {
        if(c == '1') printf("Qiy win\n");
        else printf("Vanis win\n");
    }
    else if((ma&1) || (s[n-1] == '1' && s[0] == '1')) printf("Qiy win\n");
    else printf("Vanis win\n");
}  
int main()
{
    run();
    //system("pause");
    return 0;
}

C:
栈模拟下。
Code:

void run()
{
    int n;sd(n);
    string s1,s2;
    cin >> s1 >> s2;
    int tot = 0;
    stack<int> S;
    for(int i = 0;i < s1.size();++i)
    {
        S.push(s1[i]);
        while(!S.empty())
        {
            if(s2[tot] == S.top())
            {
                tot++;
                S.pop();
            }
            else break;
        }
    }
    bool f = true;
    while(!S.empty())
    {
        if(S.top() != s2[tot]) f = false;
        else tot++;
        S.pop();
    }
    if(f) printf("Yes\n");
    else printf("No\n");
}  
int main()
{
    run();
    //system("pause");
    return 0;
}

M:签到
Code:

void run()
{
    int a,b,c,d;
    sdd(a,b),sdd(c,d);
    if(a*c <= b) b = a*c;        
    int t = d/b;
    int ans = t*c;
    d -= t*b;
    ans += d/a;
    pr(ans);
}  
int main()
{
    run();
   // system("pause");
    return 0;
}

J:
一开始以为质数排列。
后面发现以一个数开始一直连续到它的2倍或者n肯定会存在最优的至少一种。
如果只有一种，那么把最大的偶数换成它的一半也是可以的。
Code：

int ans[N];
void run()
{
    int n;sd(n);
    int Maxx = -1,ma;
    for(int i = 1;i <= n;++i)
    {
        if(2*i <= n) ma = i;
        else ma = n-i+1;
        Maxx = max(Maxx,ma);
    }
    int cnt = 0;
    for(int i = 1;i <= n;++i)
    {
        if(2*i <= n) ma = i;
        else ma = n-i+1;
        if(ma == Maxx)
        {
            cnt++;
            for(int j = i;j <= i+ma-1;++j) ans[j-i+1] = j;
            for(int j = 1;j <= ma;++j) printf("%d%c",ans[j],j == ma ? '\n' :' ');
            if(cnt == 2) break;
        }
    }
    if(cnt != 2)
    {
        if(ans[Maxx] % 2 == 0) ans[Maxx] /= 2;
        else ans[Maxx-1] /= 2;
        for(int j = 1;j <= Maxx;++j) printf("%d%c",ans[j],j == Maxx ? '\n' :' ');
    }
}  
int main()
{
    run();
  //  system("pause");
    return 0;
}

L：
贪心：
可以发现对于凑成的方式只有三种。
A-B-C. A-B-C显然浪费更多，不可能有A-B-C优.
B-C-A.
C-A-B.
先凑成一种，然后将它转化为1半，而不是四份之一，肯定在之中之间更优。
那么这三种只要存在一个就YES.
Code:

int w[4];
bool cal(int a,int b,int c,int x,int y,int z)
{
    if(a >= w[x]) a -= w[x],b += a/2;
    else return false;
    if(b >= w[y]) b -= w[y],c += b/2;
    else return false;
    if(c < w[z]) return false;
    return true;
}
void run()
{
    int n,a,b,c;cin >> n >> a >> b >> c;
    for(int i = 1;i <= n;++i)
    {
        int t,ww;sdd(t,ww);
        w[t] += ww;
    }
    if(cal(a,b,c,1,2,3) || cal(b,c,a,2,3,1) || cal(c,a,b,3,1,2)) printf("YES\n");
    else printf("NO\n");
}  
int main()
{
    run();
    system("pause");
    return 0;
}

G:
树形问题。
可以发现肯定是到一个点然后走到这个点能延伸的最下面。
所以枚举从哪个点可以往下即可。
之前dp统计下i点向下的最大路径。
注意的是一个点能否上还需要满足x到这个点的时间小于1到这个点的时间，不然就会被抓到。
这个时间就树上距离求下。
注意MAXX赋为0，可能存在x = 1的情况。
Code:

int n,x,dp[N],dep[N],f[N][25],lg[N],ans = 0;
vector<int> G[N];
void init()
{
    for(int i = 1;i < N;++i) lg[i] = lg[i-1]+((1<<lg[i-1]) == i);
}
void dfs(int u,int fa)
{
    dep[u] = dep[fa]+1;f[u][0] = fa;
    for(int i = 1;i <= lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:G[u])
    {
        if(v == fa) continue;
        dfs(v,u);
        dp[u] = max(dp[u],dp[v]+1);
    }
}
int LCA(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    while(dep[x] > dep[y])
    {
        x = f[x][lg[dep[x]-dep[y]]-1];
    }
    if(x == y) return x;
    for(int i = lg[dep[x]]-1;i >= 0;--i)
    {
        if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    }
    return f[x][0];
}
int dis(int x,int y)
{
    return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
void dfs1(int u,int fa)
{
    int dis1 = dis(u,1),dis2 = dis(u,x);
    if(dis1 > dis2)
    {
        int ma = 2*dp[u]+2*dis1;
        ans = max(ans,ma);
    }
    for(auto v:G[u])
    {
        if(v == fa) continue;
        dfs1(v,u);
    }
}
void run()
{
    init();
    sdd(n,x);
    for(int i = 1;i < n;++i)
    {
        int u,v;sdd(u,v);
        G[u].pb(v),G[v].pb(u);
    }
    dfs(1,0);
    dfs1(1,0);
    pr(ans);
}  
int main()
{
    run();
  //  system("pause");
    return 0;
}

H:
树形背包。比赛快结束的时候想到了。没时间写..
dp[i][j]表示到i点时,i点代价变为j的最小代价。
因为这样直接背包统计有N^3复杂度。
但可以发现对于j = x.
它的子节点为[0~x]都满足。所以递推过程中mixx记录最小值。
然后这个改变的代价先在每个点之前处理出来。
因为每个子节点都满足所以dp + 每个子节点满足的最小值。
注意j稍微比1000大一点点。(1000应该也可以把)
Code:

int n,a[1005];
vector<int> G[1005];
LL dp[1005][1005];
void dfs(int u,int fa)
{
    for(int j = 0;j < 1005;++j) dp[u][j] = abs(a[u]-j);
    for(auto v:G[u])
    {
        if(v == fa) continue;
        dfs(v,u);
        LL mixx = INF;
        for(int j = 0;j < 1005;++j)
        {
            mixx = min(mixx,dp[v][j]);
            dp[u][j] += mixx;
        }
    }
}
void run()
{
    sd(n);
    for(int i = 1;i <= n;++i)
        for(int j = 0;j < 1005;++j) dp[i][j] = INF;
    for(int i = 1;i < n;++i)
    {
        int x;sd(x);
        G[x].pb(i+1);
        G[i+1].pb(x);
    }
    for(int i = 1;i <= n;++i) sd(a[i]);
    dfs(1,0);
    LL ans = INF; 
    for(int j = 0;j < 1005;++j) ans = min(ans,dp[1][j]);
    plr(ans);
}  
int main()
{
    run();
    //system("pause");
    return 0;
}

E题不会。。如果有会的大佬教下蒟蒻好吗