ICPC2018青岛站

回家参加icpc。
这次总体发挥还可以吧，获得了银奖。

C.Flippy Sequence

只有\(s\)串和\(t\)串有至多连续2段不同时才可行。分情况讨论即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

char s[1000010],t[1000010];

int main() {
    int T;
    scanf("%d",&T);
    for (; T--;) {
        int n;
        scanf("%d%s%s",&n,s + 1,t + 1);
        int l[3],r[3];
        l[1] = l[2] = -1;
        r[1] = r[2] = -1;
        int flag = 0;
        for (int i = 1; i <= n; i++)
            if (s[i] != t[i]) {
                if (s[i - 1] == t[i - 1]) {
                    flag++;
                    if (flag > 2)
                        break;
                    l[flag] = 1;
                }
            }
            else
                if (s[i - 1] != t[i - 1])
                    r[flag] = i - 1;
        if (s[n] != t[n])
            r[flag] = n;
        if (flag > 2)
            puts("0");
        else
            if (flag == 0)
                printf("%lld\n",(long long)n * (n - 1) / 2 + n);
            else
                if (flag == 1)
                    printf("%lld\n",2ll * (l[1] - 1 + (n - r[1]) + (r[1] - l[1])));
                else
                    puts("6");
    }
    return 0;
}

E.Plants vs. Zombies

二分答案判断即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=100000+10;
LL m,a[MAXN],d[MAXN];
int T,n;
inline bool check(LL x)
{
    LL t=m,now;
    for (int i=1;i<=n;++i) d[i]=0;
    for (int i=1;i<=n;++i) if (d[i]+a[i]<x)
    {
        if (t==0) break;
        now=(x-d[i])/a[i];
        if ((x-d[i])%a[i]!=0) ++now;
        if (t<now*2-1) return 0;
        t-=now*2-1;
        d[i]+=a[i]*now;
        d[i+1]+=a[i+1]*(now-1);
    }
    else
    {
        if (t==0) break;
        t-=1;
        d[i]+=a[i];
    }
    for (int i=1;i<=n;++i) if (d[i]<x) return 0;
    return 1;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%lld",&n,&m);
        for (int i=1;i<=n;++i) scanf("%lld",&a[i]);
        LL l=0,r=1e17,mid;
        /*check(6);
        for (int i=1;i<=n;++i) cout<<d[i]<<endl;*/
        while (l<r)
        {
            mid=(l+r+1)/2;
            if (check(mid)) l=mid; else r=mid-1;
        }
        printf("%lld\n",l);
    }
    return 0;
}

F.Tournament

最多安排的轮数显然与lowbit有关。若\(n=2^xy\)，其中\(y\)为奇数，则最多安排的轮数为\(2^x-1\)。按照顺序构造安排方案即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int p[1010][1010];

void work(int id,int st1,int st2,int k) {
    if (k == 0) {
        p[id][st1] = st2;
        p[id][st2] = st1;
        return;
    }
    work(id,st1,st2,k - 1);
    work(id,st1 + (1 << (k - 1)),st2 + (1 << (k - 1)),k - 1);
    work(id + (1 << (k - 1)),st1,st2 + (1 << (k - 1)),k - 1);
    work(id + (1 << (k - 1)),st1 + (1 << (k - 1)),st2,k - 1);
}

int main() {
    int T;
    scanf("%d",&T);
    for (; T--;) {
        int n,m;
        scanf("%d%d",&n,&m);
        int k = 0;
        int tn = n;
        for (; ! (tn & 1); tn >>= 1)
            k++;
        if (m >= (1 << k)) {
            puts("Impossible");
            continue;
        }
        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= n; j += (1 << i))
                work((1 << (i - 1)),j,j + (1 << (i - 1)),i - 1);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j < n; j++)
                printf("%d ",p[i][j]);
            printf("%d\n",p[i][n]);
        }
    }
    return 0;
}

J.Books

如果价格为\(0\)的书的数量大于\(m\)，则不可能。如果\(n=m\)，则输出Richman。否则，答案为前m本书的价格和加上后面的书的最小价格减一。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int oo = 0x7fffffff;

int a[100010];

int main() {
    int T;
    scanf("%d",&T);
    for (; T--;) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; i++) {
            scanf("%d",&a[i]);
            if (! a[i]) {
                n--;
                i--;
                m--;
            }
        }
        if (m < 0) {
            puts("Impossible");
            continue;
        }
        if (n == m) {
            puts("Richman");
            continue;
        }
        long long ans = 0;
        for (int i = 1; i <= m; i++)
            ans += a[i];
        int mn = oo;
        for (int i = m + 1; i <= n; i++)
            mn = min(mn,a[i]);
        ans += mn - 1;
        printf("%lld\n",ans);
    }
    return 0;
}

M.Function and Function

显然当次数很大的时候就会变成01交替。一直暴力计算直到变为0，然后根据剩下的次数计算即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int f[10] = {1,0,0,0,1,0,1,0,2,1};

int cal(int x) {
    if (x == 0)
        return 1;
    int res = 0;
    for (; x > 0; x /= 10)
        res += f[x % 10];
    return res;
}

int main() {
    int T;
    scanf("%d",&T);
    for (; T--;) {
        int x,k;
        scanf("%d%d",&x,&k);
        int i = 1;
        for (; i <= k; i++) {
            x = cal(x);
            if (x == 0)
                break;
        }
        if (i > k)
            printf("%d\n",x);
        else
            if ((k - i) & 1)
                puts("1");
            else
                puts("0");
    }
    return 0;
}