codeforces1303解题报告

A. Erasing Zeroes

【题意】

给出一个 $01$ 串求出最小删除多少个0，使得所有的1是连续的。

【思路】

特判全是 $0$ 的情况。

答案就是最左边的 $1$ 和最右边的 $1$ 之间的 $0$ 的个数。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[110];
int main() {
    int T = read();
    while(T--) {
        scanf("%s",s + 1);
        int n = strlen(s + 1);
        int ans = 0,flag = 0;
        for(int i = 1;i <= n;++i) {
            if(s[i] == '1') flag = 1;
            if(s[i] == '0') ans += flag;
        }
        if(!flag) {
            puts("0");continue;
        }
        flag = 0;
        for(int i = n;i >= 0;--i) {
            if(s[i] == '1') break;
            ans--;
        }
        printf("%d\n",ans);
    }

    return 0;
}

B. National Project

【题意】

铺设一条长度为 $n$ 的道路，先铺设连续 $g$ 天高质量道路，再连续铺设 $b$ 天低质量道路，每天铺设长度为1的道路。每天都可以拒绝铺设。要求铺设完成后高质量道路长度占道路总长的一半或以上。问最少多少天可以铺设完成。

【思路】

如果 $g\ge b$ 答案就是n。

否则，相当于从 $g,b,g,b,g,b.....$ 这样的循环中选择 $\lceil\frac{n}{2}\rceil$ 个g中的数字。

设 $k=\lceil \frac{\lceil \frac{n}{2}\rceil}{g} \rceil$ ,答案就是 $max(n,(k - 1)(g+b)+ \lceil\frac{n}{2}\rceil - g(k-1))$

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 300;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];
int head[N],ejs;
struct node {
    int v,nxt;
}e[N << 1];
void add(int u,int v) {
    e[++ejs].v =v ;e[ejs].nxt = head[u];head[u] = ejs;
}
void dfs(int u,int fa) {
    putchar(u + 'a' - 1);
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u);
    }
}
int ma[30][30],du[N];
void solve() {
    scanf("%s",s + 1);
    int n = strlen(s + 1);

    if(n == 1) {
        puts("YES");
        for(int i = 0;i <= 25;++i) putchar(i + 'a');
            puts("");
        return;
    }

    for(int i = 2;i <= n;++i) {
        int t1 = s[i] - 'a' + 1,t2 = s[i - 1] - 'a' + 1;
        if(!ma[t1][t2]) {
            ma[t1][t2] = ma[t2][t1] = 1;
            du[t1]++;du[t2]++;
            if(du[t1] > 2 || du[t2] > 2) {
                puts("NO");return;
            }
            add(t1,t2);add(t2,t1);
        }
    }

    for(int i = 1;i <= 26;++i) {
        if(du[i] == 1) {
            puts("YES");
            dfs(i,0);
            for(int j = 1;j <= 26;++j) {
                if(!du[j]) putchar(j + 'a' - 1);
            }
            puts("");
            return;
        }
    }
    puts("NO");
}
int main() {
    int T = read();
    while(T--) {
        memset(head,0,sizeof(head));
        ejs = 0;
        memset(ma,0,sizeof(ma));
        memset(du,0,sizeof(du));
        solve();
    }

    return 0;
}

C. Perfect Keyboard

【题意】

给出一个字符串 $s$ ，求出 $26$ 个字母的一个排列要求在 $s$ 中相邻的字符在这个排列中必须相邻。

【思路】

将 $s$ 中相邻的字符之间连一条边，如果有解最后肯定是一条链，依次输出这条链。将其他的字符随便输出即可。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 300;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];
int head[N],ejs;
struct node {
    int v,nxt;
}e[N << 1];
void add(int u,int v) {
    e[++ejs].v =v ;e[ejs].nxt = head[u];head[u] = ejs;
}
void dfs(int u,int fa) {
    putchar(u + 'a' - 1);
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u);
    }
}
int ma[30][30],du[N];
void solve() {
    scanf("%s",s + 1);
    int n = strlen(s + 1);

    if(n == 1) {
        puts("YES");
        for(int i = 0;i <= 25;++i) putchar(i + 'a');
            puts("");
        return;
    }

    for(int i = 2;i <= n;++i) {
        int t1 = s[i] - 'a' + 1,t2 = s[i - 1] - 'a' + 1;
        if(!ma[t1][t2]) {
            ma[t1][t2] = ma[t2][t1] = 1;
            du[t1]++;du[t2]++;
            if(du[t1] > 2 || du[t2] > 2) {
                puts("NO");return;
            }
            add(t1,t2);add(t2,t1);
        }
    }

    for(int i = 1;i <= 26;++i) {
        if(du[i] == 1) {
            puts("YES");
            dfs(i,0);
            for(int j = 1;j <= 26;++j) {
                if(!du[j]) putchar(j + 'a' - 1);
            }
            puts("");
            return;
        }
    }
    puts("NO");
}
int main() {
    int T = read();
    while(T--) {
        memset(head,0,sizeof(head));
        ejs = 0;
        memset(ma,0,sizeof(ma));
        memset(du,0,sizeof(du));
        solve();
    }

    return 0;
}

D. Fill The Bag

【题意】

有m个盒子，每个盒子的大小均为2的非负整数次幂。每次可以将一个盒子切成两个大小相等的两个盒子。问恰好填满一个大小为n的背包至少需要切割多少次。

【思路】

按照n的二进制位从大到小考虑。

如果n的二进制第i位为1，则用大小相等的盒子填满。

如果n的二进制第i位为0，那么考虑如果不切割大小为 $2^i$ 的盒子，是否可以恰好填满。不可以的话就切割当前的盒子。可以证明，每个盒子切割之后在每个二进制位只会用一次，所以不用考虑个数。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll cf[N],cnt[60];

void solve() {
    ll n = read();int m = read();
    ll sum = 0;
    for(int i = 1;i <= m;++i) {
        int x = read();
        sum += x;
        int t = 0;
        while(x) ++t,x >>= 1;
        cnt[t - 1]++;
    }
    // printf("%d\n",cnt[6]);
    if(sum < n) {
        puts("-1");return;
    }
    int ans = 0;
    for(int i = 31;i >= 0;--i) {
        while(cnt[i]) {
            if(n >= (1ll << i)) {
                n -= (1ll << i);cnt[i]--;
                sum -= (1ll << i);
            }
            else if(sum - (1ll << i) < n) {
                cnt[i]--;cnt[i - 1]++;ans++;
                sum -= (1ll << (i - 1));
                if(n >= (1ll << (i - 1))) n -= (1ll << (i - 1));
            }
            else cnt[i]--,sum -= (1ll << i);
        }
    }
    printf("%d\n",ans);

}
int main() {
    int T = read();
    while(T--) {
        memset(cnt,0,sizeof(cnt));
        solve();
    }

    return 0;
}

E. Erase Subsequences

【题意】

给出一个长度为 $n$ 的字符串 $s$ ，一个长度为 $m$ 的字符串 $t$ 。问是否能从 $s$ 中找到两个不相交的子序列，使得拼接后形成 $t$ 。

【思路】

在 $t$ 中枚举两个子序列切割的位置。用 $f[i][j]$ 表示第一个子序列到了位置 $i$ ，第二个子序列到了位置 $j$ ，在 $s$ 中最少需要到达的位置。

预处理出 $nxt[i][j]$ 表示 $s$ 中位置 $i$ 后面的下个 $j$ 出现的位置

转移如下:

$f[i+1][j]=min(f[i + 1][j],nxt[f[i][j]][t[i + 1]]) \\ f[i][j + 1] = min(f[i][j + 1],nxt[f[i][j]][t[j + 1]])$

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 510;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N],t[N];
int nxt[N][30],f[N][N];
void solve() {
    scanf("%s",s + 1);
    scanf("%s",t + 1);
    int n = strlen(s + 1),m = strlen(t + 1);

    for(int i = 0;i <= 25;++i)
        nxt[n][i] = n + 1;

    for(int i = n - 1;i >= 0;--i) {
        for(int j = 0;j < 26;++j)
            nxt[i][j] = nxt[i + 1][j];
        nxt[i][s[i + 1] - 'a'] = i + 1;
    }

    for(int k = 1;k <= m;++k) {

        for(int i = 0;i <= m;++i)
            for(int j = 0;j <= m;++j)
                f[i][j] = n + 1;

        f[0][k - 1] = 0;

        for(int i = 0;i < k;++i) {
            for(int j = k - 1;j <= m;++j) {
                if(f[i][j] == n + 1) continue;
                if(i + 1 < k) f[i + 1][j] = min(f[i + 1][j],nxt[f[i][j]][t[i + 1] - 'a']);
                if(j + 1 <= m) f[i][j + 1] = min(f[i][j + 1],nxt[f[i][j]][t[j + 1] - 'a']);
            }
        }

        if(f[k - 1][m] <= n) {
            puts("YES");return;
        } 
    }
    puts("NO");

}
int main() {
    int T = read();
    while(T--) solve();


    return 0;
}