剑锋所指,心之所向。

30 场 edu a2e 第 1 场

2.13 - 2.19

A.Erasing Zeros

给定一个 01s,擦除最少的字符,使得所有为 1 的字符都是在下标上连续的

|s| \leq 100

模拟


模拟即可

在对比的过程中,我发现最简单的实现是:记录最靠边的 1 的位置,然后扫一遍得到中间的 0 的个数即可

时间复杂度 O(n)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100 + 10;

int n, ans;
char str[MAXN];

void solve() {
    scanf("%s", str + 1);
    n = strlen(str + 1), ans = 0;
    bool flg = false;
    for (int i = 1; i <= n; ++i) {
        if (str[i] == '1') {
            int j = i + 1;
            while (j <= n && str[j] == '0') j ++;
            if (j < n + 1) ans += j - i - 1;
        }
    }
    printf("%d\n", ans);
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

我发现我写了一种不太优美的写法

B.National Project

有个无限长的,周期的 01 数列,周期为 \underbrace{1, 1 \cdots 1}_{a\ 个\ 1}, \underbrace{0, 0, \cdots}_{b\ 个\ 0},求在这个数列上选 n 个数,使得 1 的个数大于等于 0 的个数,最小化最后一个被选的数的下标

数学


随便推一推式子

首先 1 的个数至少为 \big \lceil \dfrac{n}{2}\big \rceil,即为 d

那么选出这么多个 1 至少要 \big \lfloor \dfrac{d}{a} \big \rfloor 个完整的周期和至多一个不完整的周期(即只选为 1 的数),即为 r

分两种情况讨论:

case 1: 当 d \bmod a = 0 时:

  • 即取完完整的周期之后就不用再取了,那么答案为 r * (a + b) - b

case 2: otherwise:

  • 则需要在下一个周期去 d \bmod a 这么多,答案为 r * (a + b) + d \mod a

当然,我们只保证了第一个要求(1 大于 0),未保证取 n 个,所以与 n\max 即可

时间复杂度 O(1)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    ll n, a, b;
    scanf("%lld %lld %lld", &n, &a, &b);
    ll days_of_good = (n + 1) / 2;
    ll days_of_all = days_of_good / a * (a + b);
    if (days_of_good % a == 0) days_of_all -= b;
    else days_of_all += (days_of_good % a);
    printf("%lld\n", max(days_of_all, n));
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

C.Perfect Keyboard

给出一串字符 S,构造一个字符 T,使得对于任意 S(i), S(i + 1),在 T 中都是相邻的

|S| \leq 1000

模拟,DFS


模拟即可

另一种方式是以字母为点,将 S 中相邻的两个点连边

则问题变为:以任意一个字母出发,能否找到一种遍历全图的方式,使得整个轨迹是一条链

时间复杂度 O(n)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000 + 10;

int n;

void solve() {
    char s[MAXN], ans[MAXN];
    int vis[MAXN];
    memset(s, 0, sizeof s), memset(ans, 0, sizeof ans), memset(vis, 0, sizeof vis);
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int cur = 500;
    ans[cur] = s[1]; vis[s[1] - 'a'] = true;
    for (int i = 2; i <= n; ++i) {
        if (!vis[s[i] - 'a']) {
            if (!ans[cur + 1]) ans[++cur] = s[i];
            else if (!ans[cur - 1]) ans[--cur] = s[i];
            else { puts("NO"); return ; }
            vis[s[i] - 'a'] = true;
        } else {
            if (s[i] == ans[cur - 1]) cur --;
            else if (s[i] == ans[cur + 1]) cur ++;
            else { puts("NO"); return ; }
        }
    }
    puts("YES");
    for (int i = 1; i < MAXN; ++i) {
        if (ans[i]) { printf("%s", ans + i); break; }
    }
    for (int i = 0; i <= 25; ++i) {
        if (!vis[i]) printf("%c", i + 'a');
    }
    puts("");
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

未经允许再贴一下 DFS 做法 (authour: wucstdio)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Edge
{
    int to;
    int nxt;
}e[200005];
int t,n,edgenum,d[27],head[27],xx[27],top;
char s[100005],ans[27];
void add(int u,int v)
{
    e[++edgenum].to=v;
    e[edgenum].nxt=head[u];
    head[u]=edgenum;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s+1);
        n=(int)strlen(s+1);
        memset(head,0,sizeof(head));
        edgenum=0;
        for(int i=1;i<n;i++)
        {
            add(s[i]-'a',s[i+1]-'a');
            add(s[i+1]-'a',s[i]-'a');
        }
        bool flag=1;
        int num=0,c=0;
        for(int i=0;i<26;i++)
        {
            int a=-1,b=-1;
            for(int hd=head[i];hd;hd=e[hd].nxt)
            {
                int to=e[hd].to;
                if(a==to||b==to)continue;
                if(a==-1)a=to;
                else if(b==-1)b=to;
                else
                {
                    flag=0;
                    break;
                }
            }
            if(flag==0)break;
            if(a!=-1&&b==-1)num++;
            if(a!=-1)c++;
            if(a==-1)xx[i]=0;
            else if(b==-1)xx[i]=1;
            else xx[i]=2;
        }
        if(c>=2&&num!=2)flag=0;
        if(!flag)
        {
            puts("NO");
            continue;
        }
        puts("YES");
        for(int i=0;i<26;i++)
          if(!xx[i])printf("%c",i+'a');
        for(int i=0;i<26;i++)
        {
            if(xx[i]==1)
            {
                int x=i,pre=-1;
                while(1)
                {
                    int y=x;
                    printf("%c",x+'a');
                    for(int hd=head[x];hd;hd=e[hd].nxt)
                    {
                        int to=e[hd].to;
                        if(to!=pre)
                        {
                            pre=x;
                            x=to;
                            break;
                        }
                    }
                    if(x==y)break;
                }
                break;
            }
        }
        printf("\n");
    }
    return 0;
}

D.Fill the Bag

给出 m2 的幂,定义操作 1 为将某个数 a 分解为两个值为 \dfrac{a}{2} 的数,操作 2 为其逆操作,要求通过若干次操作,使得存在若干个数的和为 n,并最小化操作 1 的次数

n \leq 10^{18}, m \leq 10^5

贪心,按位


观察发现是按位贪心

贪心策略十分显然:

如果这 m 个数的和大于等于 n,则一定有解(将所有数分解为 1

从低到高位扫,如果这位 n1 但我们没有,那么就向后找到第一个为 1 的位,把它分解到没有的位即可。如果有多余的,就对所有多余的执行操作 2

正确性显然

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXBIT = 64 + 10;

ll n, sum;
int m, cnt, num[MAXBIT], ans;
bool bit[MAXBIT];

void solve() {
    scanf("%lld %d", &n, &m);
    cnt = 0, sum = 0, ans = 0;
    memset(num, 0, sizeof num);
    for (ll tmp = n; tmp; tmp >>= 1) {
        if (tmp == 0) break;
        bit[cnt++] = tmp & 1;
    }
    cnt --;
    for (int i = 1, x; i <= m; ++i) {
        scanf("%d", &x); sum += x;
        num[__builtin_ctz(x)] ++;
    }
    if (sum < n) { puts("-1"); return ; }
    for (int i = 0; i <= cnt; ++i) {
        if (bit[i] == 1) {
            if (num[i] == 0) {
                int j = i + 1;
                while (!num[j]) j ++;
                num[j] --;
                for (int k = j - 1; k >= i; --k) num[k] ++;
                num[i] ++;
                ans += j - i;
            } else {
                int tmp = num[i] - 1;
                num[i + 1] += tmp / 2, num[i] -= tmp / 2 * 2;
            }
            num[i] --;
        } else {
            num[i + 1] += num[i] / 2, num[i] -= num[i] / 2 * 2;
        }
    }
    printf("%d\n", ans);
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

E.Erase Subsequences

给出两个串 S, T,问能否在 T 中找到两个不交的子序列 t_1, t_2,使得将子序列 t_2 拼接到 t_1 后为 S

|S|, |T| \leq 400

DP,经典


首先构造子序列自动机 \text{nxt},并在上面进行 dp

f(block, i, j, k) 表示:t_1t_2 的界限为 S 的第 block 位,T 考虑到 it_1 写到了第 j 位,t_2 写到了第 k 位这种情况的可行性

则有明显的转移:

f(block, i, j, k) \rightarrow \begin{cases} f(block, \text{nxt}(i, S(j + 1)), j + 1, k) & \text{nxt}(i, S(j + 1)) \leq |T| \\ f(block, \text{nxt}(i, \text{nxt}(i, (S(block + k + 1))), j, k + 1) & \text{nxt}(i, S(block + k + 1)) \leq |T| \end{cases}

时间复杂度 O(n^4),不能接受

我们发现如果一个 f 只用来表示 0, 1 就太浪费空间了,那么我们决定以空间换时间,将 f 的一维加入进他的值里面

即,f(block, i, j) 表示:界限为 blockT 考虑到了 it_1 写到了 jt_2 最多能写到哪一位

则有明显的转移:

f(block, i, j) + 1 \operatorname{updateMax} f(block, \text{nxt}(i, S(block + k + 1)), j)\\ f(block, i, j) \operatorname{updateMax} f(block, \text{nxt}(i, S(i + 1)), j + 1)

那么答案为

\text{exsit}:f(block, i, block) = |T| - block, \text{for} 1 \leq block \leq |S|, 1 \leq i \leq |T|

时间复杂度 O(n^3)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 400 + 10, SZ = 26 + 10;

int n, m, nxt[MAXN][SZ], f[MAXN][MAXN];
char s[MAXN], t[MAXN];

void checkmax(int& a, int b) { if (a < b) a = b; }

void solve() {
    scanf("%s %s", s + 1, t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    for (int j = 0; j < 25; ++j) nxt[n][j] = n + 1;
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j < 25; ++j) nxt[i - 1][j] = nxt[i][j];
        nxt[i - 1][s[i] - 'a'] = i;
    }
    for (int blc = 0; blc <= m; ++blc) {
        memset(f, -0x3f, sizeof f);
        f[0][0] = 0;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= blc; ++j) {
                if (j < blc) checkmax(f[nxt[i][t[j + 1] - 'a']][j + 1], f[i][j]);
                if (f[i][j] >= 0 && f[i][j] < (m - blc)) checkmax(f[nxt[i][t[blc + f[i][j] + 1] - 'a']][j], f[i][j] + 1);
            }
            if (f[i][blc] == (m - blc)) { puts("YES"); return ; }
        }
    }
    puts("NO");
}

int main() {
    int t; scanf("%d", &t);
    for (; t --; ) solve();
    return 0;
}

然而这种以空间换时间,将某一维加入到值的优化方式并不是第一次出现了

atcoder dp contest e.knapsack 2

01 背包,数量 100,价值 1000,体积 10^9,求最大价值

这题正解就是 f(i) 表示价值为 i 时的最小体积

for (int i = 1; i <= n; ++i) {
    for (int j = MAXW - 1; j >= wgh[i]; --j) {
        f[j] = min(f[j], f[j - wgh[i]] + val[i]);
        if (f[j] <= m) ans = max(ans, j);
    }
}

如出一辙的优化方式,但我怎么就想不到呢?

空间换时间,将表示的值也纳入考虑范围内

总结

  • ABCD 能比较快的切出来

  • 有些细节,码力还是不够
  • F 连 n^4 都没想出来
  • F 不会优化

感谢 Juanzhang 对我的指导!

OI-数学 OI-模拟 OI-dp

仅有一条评论

  1. Tommy Tommy

    tql

codeforces 1295/edu. 81 题解与总结
上一篇 «
数论学习笔记
» 下一篇