CCC2019 解题报告

T1

题意

给出一个长度在 10^5 以内的字符串 s ，删除其中出现次数小于 k 的字母，并输出修改后的字符串。

思路

开个桶记录一下每个字母出现的次数，扫一遍输出即可。

代码

#include <cstdio>
const int MAXN=110000;
const int MAXS=256;
int k, cnt[MAXS];
char s[MAXN];
int main()
{
    scanf("%d%s", &k, s);
    for (int i=0; s[i]; i++) cnt[s[i]]++;
    for (int i=0; s[i]; i++)
        if (cnt[s[i]]>=k) putchar(s[i]);
    putchar('\n');
    return 0;
}

T2

题意

给出一个长度为 l (l\leq 100000) 的二进制正整数 n （保证 n 是一个完全平方数），求 \sqrt n 的二进制表示。

思路

• 针对数据范围：l\leq 3000 （90分）；
• 首先，根据乘法的性质可知，答案 a 的位数 m 一定在 \left \lfloor \frac{n+1}2 \right \rfloor 以内。这里规定所有二进制数都从 0 位起，即最低位是第 0 位；
• 从高位到低位确定答案。如下图，假设我们从第 m-1 位开始，即将处理答案的第 i 位，那么 [i+1, m-1] 位的答案都是已经确定好的，这里设为 a ：
• 那么，如果把 a[i] 填上 1 ，则有 a'=a+2^i 。显然，只有 a'^2\leq n 时，第 i 为才可以是 1 ，否则只能为 0 。把上面的条件展开，得 a'^2=(a+2^i)^2=a^2+a\times 2^{i+1}+2^{2i}\leq n 。其中 a^2 可以在处理前一位时维护； a\times 2^{i+1} 相当于把 a 左移 i+1 位； 2^{2i} 相当于一个只有第 i 位为 1 ，其他位为 0 的二进制数。把这三项相加，与 n 比较即可。可以用一个 bitset 并手写二进制加法和比较。

代码

#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
const int MAXN=3300;
int l; char s[MAXN];
bitset<MAXN> n, a, b, t; // 这里 b 就是维护的 a^2
bitset<MAXN> operator + (const bitset<MAXN>& a, const bitset<MAXN>& b)
{
    bitset<MAXN> c;
    for (int i=0; i<=l; i++)
        c[i+1]=a[i]+b[i]+c[i]>=2, c[i]=a[i]^b[i]^c[i];
    return c; 
}
bool operator <= (const bitset<MAXN>& a, const bitset<MAXN>& b)
{
    for (int i=l; i>=0; i--)
        if (a[i]^b[i]) return b[i];
    return 1;
}
bitset<MAXN> bin(int i)
{
    bitset<MAXN> a; a.set(i);
    return a;
}
void print(const bitset<MAXN>& a)
{
    int len=l;
    while (len>1&&!a[len-1]) len--;
    for (int i=len-1; i>=0; i--) putchar((bool)a[i]^'0');
    putchar('\n');
}
int main()
{
    scanf("%s", s); l=strlen(s);
    for (int i=0; i<l; i++) n[i]=s[l-i-1]^'0';
    for (int i=l-1>>1; i>=0; i--)
    {
        t=b+(a<<i+1)+bin(i<<1);
        if (t<=n) a.set(i), b=t;
    }
    print(a);
    return 0;
}

T3

题意

给出一个长度为 n 的序列 a_0,a_1,\dots ,a_{n-1} 。把这个序列围成一个环，可以把环上相邻的两个值都为 v 的元素合并成一个值为 v+1 的元素。求能合并出的最大元素的值。

数据范围：n\leq 10^5,a_i\in [1,40] 。

思路

• 考场上只想出来一个 O(n^3) 的 dp 。。针对数据范围：n\leq 500 （40分）；
• 为了处理环上问题，我们把 a 序列复制一遍后 dp ；
• 定义 f[i][j] 表示从第 i 个元素到第 j 个元素合成一个元素的值。若它们无法合成一个元素，则 f[i][j]=0 ；
• 容易得出状态转移方程如下: f[i][j]=f[i][k]\;(i\leq k<j,f[i][k]=f[k+1][j],f[i][k]\neq 0)
• 按区间长度分阶段转移即可。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1100;
int n, a[MAXN];
int f[MAXN][MAXN];
int main()
{
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    for (int i=0; i<n; i++) a[i+n]=a[i];
    for (int i=1; i<=2*n; i++) f[i][i]=a[i];
    for (int l=2; l<=n; l++)
        for (int i=1; i<=2*n-l+1; i++)
            for (int j=i+l-1, k=i; k<j; k++)
                if (f[i][k]&&f[i][k]==f[k+1][j])
                    f[i][j]=f[i][k]+1;
    int ans=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            ans=max(ans, f[i][i+j-1]);
    printf("%d\n", ans);
    return 0;
}

T4

题意

给出 n,m 和一个正整数序列 a1,a2,\dots,am ，求：

\sum(\pm\sqrt{a_1}\pm\sqrt{a_2}\pm\dots\pm\sqrt{a_m})^n

数据范围：n\leq10^9+7,m\leq10 。

可以证明答案一定是整数。

思路

• 并没有什么思路。。
• 考场上就写了个快速幂混了10分qwq
• 不放代码了。。

T5

题意

给出一棵树，边上有权，其中每个点都属于一个不同的集合。有多次询问，每次询问要建立一个新集合，并把之前有的两个集合合并到这个新集合中，问这个新集合中有没有距离（路径边权和）不小于 k 的点对。

思路

• 后悔考场上没看这题。。据说暴力合并+dfs就能有65分；
• 目前还没想到更好的办法。

总结

本次总分

100+90+40+10+0=240

教训

• 以后应先看完所有题后再写。。没思路就先打暴力
• T2 写的时间太长了。