CSP-J/S 2019 游记 & CSP-S 2019 自己的题解

发表于 | 分类于 | 6

如题。

游记

作为一只参加第一届 CSP-J/S 且在此之前从未参加过 NOIP 提高组的蒟蒻，我感觉自己还是太菜了……

Day -???:

要开始停课了呢。
大概是第一次为了 OI 而停课吧，从前只是远远望着罢了，从未想过自己这么快就要接触到传说中的「停课」了。

集训的日子让我似放松而非放松，似紧张而非紧张；如此一天天过着，每晚回去做做文化课的作业，依然和同班同学们住在一起，大抵也就这样吧。

曾经的同学逐渐也知道了这事，然而总有对「OI」与「停课」抱有刻板印象的人认为「真爽啊」。凡此种种，我都不想多解释了；毕竟「OI」的意义，也不是人人都认识得到，也不是人人的认识都一样吧。

机房没法上洛谷，我都掉蓝了……

Day -4 ~ -3:

周一。
不愿面对的期中考。

最后到这一步了，我还能怎么逃避？
硬着头皮上吧。

果然力不从心了，成绩早已不如从前。
然而另一个一起停课的同学却考到了年级前十？
我果然太菜了啊。

罢了。
我明明是在为 CSP-J/S 备战吧。

Day -2 ~ -1:

这几天文化课那边也比较放松了，基本没啥作业，就当自己是他人的放松中的另类吧。

依然在训练。
被 JZ 的题虐爆了。

Day 0:

今天没有任务了。
文化课那边去研学了。

刷了下天天爱跑步、列队和保卫王国。
就开始颓废了。

这时 P6174 问我要不要面基，我说我在二中考场，他说他和 snakes、codesonic 都在六中考场玩，问我要不要坐地铁。
这是真的没办法啊……

晚上，也总算是出发了吧。
这到底是集训到最后的释怀，还是大敌当前的恐惧？
我无从得知。

到酒店了，本来打算是双人房加个床三人住（我，LHF，ZYM，虽然中间那个人似乎不大愿意）的，服务员说不能加床。
然后问我要不要一个人睡大床房，教练还说只要交一个人的钱。
果断摇头。
（不要问为什么）

Day 1:

自以为「久等了」的却其实是初次面对的 CSP-S，终于让我见了一面么？

考试开始。
看到 T1 题目名大概就知道啥东西了，看了眼题目就秒了。
T2 不知道为什么自然而然地想到了转化成 1/−1 然后再做，虽然做法没问题，不过好像不是很主流？
T3 没想出来，打了个自以为的 35pts 的程序滚粗了。

Day1 100+100+35=235，成功拿到大众分。

下午是 J，本来觉得能好好发挥一把，没想到也崩掉了，似乎乐观估计只有 250？
（此处 Orz LHF 大佬，280 吊打我，以及一个初一的家伙似乎四题都想到了正解？顺带一提，这两个人的名字缩写都是 LHF）
大概是心态问题吧，反正我的目的是 S。

晚上教练说要请前年我校参加 GDKOI 的同学去吃寿司，于是我就跟去蹭了下。
曾经吃素的我稍微尝试了下鳗鱼吞拿鱼和牛舌之类的，感觉原来没有想象的那么难吃？
拍了张合照（见本人 QQ 空间）。

回到酒店已经快十点了。
睡得还不错吧。

Day 2:

早上可能心态会好点吧。

T1 稍微扫了一眼就没看了，先去看了后面的题（话说土狼家今天的饭是什么鬼）。
T2 看到分段 + 平方下意识想到斜率优化（虽然正解貌似不是），推了一下发现不会做，于是直接写了个 O(n2) 的 DP。
T3……居然没想到统计贡献？暴力滚粗。
回来看 T1，大概降智了居然没想到最多只会有一个这样的食材？？？
大概是一开题就打算转换模型的后遗症？？？
针对 m=2,3 的数据写了个无聊的暴力。

Day2 64+64+55=183，成功打满自己想要的暴力分。

吃了午饭就返程了呢……
感觉 418 不挂分的话应该一等有戏了？
不枉我停课这么多天啊（逃

事实证明 D1T3 有 25 分假掉了，D2T2 因为空间按着 4×107 开的于是爆零……
（LHF 大佬和我做法一样，但比我少开一个数组，然后就有那 64 分了……）

回到学校先回了下宿舍稍微睡了一会。
然后就去教室了。

他们研学的还没回来，还能再浪两天，哈哈。

既然都到了这一步了，大抵也是稍微释怀了吧。
我对于 OI，目的到底是什么呢？
OI 给我的东西那么多，我却把游记写得跟 AFO 似的，是想干什么呢？
再战吧，大抵我也没有发挥出巅峰实力。

Day 5:

暂时回归文化课了啊。
我的 OI 路还很长啊。

班主任问我考得怎么样……
我说我 J 炸 S 海星……
他愣了一下……

题解

格雷码

要么用某著名结论，要么分治。
这题代码就不贴了（其实是不想找）。

括号树

我的做法怎么这么奇异？目前似乎没找到和我一样的……
也是 DP，但是和大多数人的思路不大一样。

首先考虑把 ( 看做 1，) 看做 −1，再来考虑一个串合法的充要条件： 1. 和为 0，即 (,) 个数相等。 2. 任意位置的前缀和非负。

考虑一个序列上的弱化版问题，则易想到设状态 fi,j 表示以 i 结尾，和为 j，任意位置的前缀和非负的子串个数。
若设 ai 表示字符串第 i 位的字符，则有转移 fi,j={0,ai=(∧j=0fi−1,0+1,ai=(∧j=1fi−1,j−1,ai=(∧j≥2fi−1,j+1,ai=)

注意到若缩掉第一维，转移相当于将整个状态平移 1 或 −1 位，并修改部分状态。
由于修改的状态很少，所以可以直接暴力修改。

转回树上，发现只需要支持一个回溯操作。
容易发现只需要记下被修改为 0 的状态原来如何即可。

复杂度是 O(n) 的。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
using namespace std;
const int N = 5e5;
int n,a[N + 5];
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int _f[N * 3 + 5],*f = _f + N,rot,temp[N + 5];
long long cur,ans;
void dfs(int p)
{
    rot += a[p];
    a[p] == 1 && (temp[p] = f[-rot],f[-rot] = 0,++f[1 - rot]);
    ans ^= p * (cur += f[-rot]);
    for(register int i = first[p];i;i = pre[i])
        dfs(to[i]);
    cur -= f[-rot];
    a[p] == 1 && (--f[1 - rot],f[-rot] = temp[p]);
    rot -= a[p];
}
int main()
{
    scanf("%d",&n);
    char ch;
    for(register int i = 1;i <= n;++i)
        scanf(" %c",&ch),a[i] = ch == '(' ? 1 : -1;
    int u;
    for(register int i = 2;i <= n;++i)
        scanf("%d",&u),add(u,i);
    dfs(1);
    printf("%lld\n",ans);
}

树上的数

咕咕咕。

Emiya 家今天的饭

注意到出现次数过半的主要食材至多有一种，容斥即可。
枚举这种主要食材为 s，并设 fi,j 表示做完了前 i 种烹饪方式，s 的出现次数与其它食材的总出现次数的差为 j 的方案数。
则 fi,j=fi−1,j+fi−1,j−1ai,s+fi−1,j+1∑1≤k≤nk≠sai,k

复杂度 O(n2m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100;
const int M = 2000;
const int mod = 998244353;
int n,m;
int a[N + 5][M + 5],sum[N + 5];
int f_[N + 5][N * 2 + 5],*f[N + 5];
int ans = 1;
int main()
{
    for(register int i = 0;i < N + 5;++i)
        f[i] = f_[i] + N;
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
    {
        for(register int j = 1;j <= m;++j)
            scanf("%d",a[i] + j),sum[i] = (sum[i] + a[i][j]) % mod;
        ans = (long long)ans * (sum[i] + 1) % mod;
    }
    ans = (ans - 1 + mod) % mod;
    for(register int i = 1;i <= m;++i)
    {
        memset(f_,0,sizeof f_),f[0][0] = 1;
        for(register int j = 1;j <= n;++j)
            for(register int k = -j;k <= j;++k)
                f[j][k] = ((f[j - 1][k] + (long long)f[j - 1][k - 1] * a[j][i] % mod) + (long long)f[j - 1][k + 1] * (sum[j] - a[j][i] + mod) % mod) % mod;
        for(register int j = 1;j <= n;++j)
            ans = (ans - f[n][j] + mod) % mod;
    }
    printf("%d\n",ans);
}

划分

注意到显然分的越多越好。
故设 fi 表示所有 [1,i] 的最优方案中，i 所在块的可能最大左端点减一。
再令 si=i∑j=1aj。
则 fi=max0≤j<isi−sj≥sj−sfjj

故显然 fi 有单调性（因为 fi−1 一定也满足 fi 的条件）。
用单调队列维护即可。
压位高精 / 手写 __int128 统计答案（出题人手写了个 __int116）。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 4e7;
const int M = 1e5;
int n,type;
int x,y,z,b[N + 5],m;
int p[M + 5],l[M + 5],r[M + 5];
int f[N + 5],q[N + 5],head,tail;
long long sum[N + 5];
struct Bigint
{
    static const int w = 1e4;
    static const int len = 8;
    int a[len];
    inline Bigint()
	{
        memset(a,0,sizeof a);
    }
    inline Bigint(long long x)
	{
        memset(a,0,sizeof a);
        for(register int i = 0;i < len && x;++i)
            a[i] = x % w,x /= w;
    }
    inline Bigint &operator+=(const Bigint &o)
    {
        for(register int i = 0,k = 0;i < len;++i)
            a[i] += o.a[i] + k,k = a[i] / w,a[i] %= w;
        return *this;
    }
    inline Bigint operator*(const Bigint &o) const
    {
        Bigint ret;
        for(register int i = 0;i < len;++i)
            for(register int j = 0,k = 0;j < len;++j)
                ret.a[i + j] += a[i] * o.a[j] + k,k = ret.a[i + j] / w,ret.a[i + j] %= w;
        return ret;
    }
    inline void output() const
	{
        int i = len - 1;
        for(;~i && !a[i];--i);
        printf("%d",a[i]);
        for(--i;~i;--i)
            printf("%04d",a[i]);
    }
} ans;
int main()
{
    scanf("%d%d",&n,&type);
    if(!type)
        for(register int i = 1;i <= n;++i)
            scanf("%lld",sum + i),sum[i] += sum[i - 1];
    else
    {
        scanf("%d%d%d%d%d%d",&x,&y,&z,b + 1,b + 2,&m);
        for(register int i = 3;i <= n;++i)
            b[i] = x * b[i - 1] + y * b[i - 2] + z & (1 << 30) - 1;
        for(register int i = 1;i <= m;++i)
            scanf("%d%d%d",p + i,l + i,r + i);
        for(register int j = 1;j <= m;++j)
            for(register int i = p[j - 1] + 1;i <= p[j];++i)
                sum[i] = sum[i - 1] + b[i] % (r[j] - l[j] + 1) + l[j];
    }
    for(register int i = 1;i <= n;++i)
    {
        for(;head < tail && 2 * sum[q[head + 1]] - sum[f[q[head + 1]]] <= sum[i];++head);
        f[i] = q[head];
        for(;head < tail && 2 * sum[q[tail]] - sum[f[q[tail]]] >= 2 * sum[i] - sum[f[i]];--tail);
        q[++tail] = i;
    }
    for(register int i = n;i;i = f[i])
        ans += Bigint(sum[i] - sum[f[i]]) * Bigint(sum[i] - sum[f[i]]);
    ans.output();
}

树的重心

首先显然可以考虑每个点作为重心的贡献（然鹅我考场没想到）。
则一个点 p 的贡献应为以 p 为根时在以 p 的某个儿子为根的子树中删去一棵子树并使得 p 仍为整棵树的重心的方案数。
故我们只需要考虑这样的子树个数。

注意到若 p 为重心，则以 p 为根时 p 的重儿子的子树大小不超过 n2。
设 sizex 表示以 p 为根时以 x 为根的子树大小。
再设删去的子树的根为 s，p 的重儿子为 wson，p 的次重儿子为 wson′。

若 s 不在以 p 的重儿子为根的子树内，则 p 的重儿子不会改变。
故应满足 sizewson≤n−sizes2。
解得 sizes≤n−2sizewson。

若 s 在以 p 的重儿子为根的子树内，则 p 的重儿子可能不变，可能会变成原来的次重儿子。
故应满足 sizewson−sizes≤n−sizes2,sizewson′≤n−sizes2。
解得 2sizewson−n≤sizes≤n−2sizewson′。

于是枚举根结点做就做完了（逃

肯定是需要各种奇怪的换根操作的，也就是说要维护以每个点为根时所有子树大小的出现次数。
随便钦定一个根然后就是要分别维护每个点向下的和向上的。
向下的线段树合并。
向上的？可以用总共的减掉向下的。
总共的话，考虑沿一条边从 u 到 v，则会减少 sizev 的贡献，增加 n−sizev 的贡献。

然后就做完了。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 299995;
int T;
int n;
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5],edge_tot;
inline void add(int u,int v)
{
    int &tot = edge_tot;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int c[N + 5];
inline void update(int x,int k)
{
    for(;x <= n;x += lowbit(x))
        c[x] += k;
}
inline int query(int x)
{
    if(x < 0)
        return 0;
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret += c[x];
    return ret;
}
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5],seg_tot;
void update(int x,int k,int &p,int tl,int tr)
{
    int &tot = seg_tot;
    !p && (p = ++tot,seg[p].sum = seg[p].ls = seg[p].rs = 0),seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? update(x,k,seg[p].ls,tl,mid) : update(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(l > r)
        return 0;
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
    r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
    return ret;
}
int merge(int x,int y)
{
    if(!x || !y)
        return x | y;
    seg[x].sum += seg[y].sum;
    seg[x].ls = merge(seg[x].ls,seg[y].ls),seg[x].rs = merge(seg[x].rs,seg[y].rs);
    return x;
}
int fa[N + 5],sz[N + 5],son[N + 5],son1[N + 5];
long long ans;
void dfs1(int p)
{
    sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dfs1(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[to[i]] > sz[son[p]])
                son[p] = to[i];
        }
    for(register int i = first[p];i;i = pre[i])
        if((to[i] ^ fa[p]) && (to[i] ^ son[p]))
            if(!son1[p] || sz[to[i]] > sz[son1[p]])
                son1[p] = to[i];
    update(sz[p],1);
}
void dfs2(int p)
{
    update(sz[p],-1);
    int cur = 0;
    if(n - sz[p] >= sz[son[p]])
    {
        cur += query(n - 2 * (n - sz[p]));
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p])
                update(n - sz[to[i]],1),dfs2(to[i]),update(n - sz[to[i]],-1),rt[p] = merge(rt[p],rt[to[i]]);
        cur -= query(n - 2 * (n - sz[p])) - query(1,n - 2 * (n - sz[p]),rt[p],1,n),
        cur += (query(n - 2 * sz[son[p]]) - query(2 * (n - sz[p]) - n - 1)) - query(2 * (n - sz[p]) - n,n - 2 * sz[son[p]],rt[p],1,n);
    }
    else
    {
        cur += query(n - 2 * sz[son[p]]);
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p])
            {
                update(n - sz[to[i]],1),dfs2(to[i]),update(n - sz[to[i]],-1);
                if(to[i] == son[p])
                    cur -= query(1,n - 2 * sz[son[p]],rt[to[i]],1,n),
                    cur += query(2 * sz[son[p]] - n,n - 2 * max(sz[son1[p]],n - sz[p]),rt[to[i]],1,n);
                rt[p] = merge(rt[p],rt[to[i]]);
            }
    }
    ans += (long long)p * cur;
    update(sz[p],1,rt[p],1,n);
    update(sz[p],1);
}
int main()
{
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%d",&n),edge_tot = seg_tot = ans = 0,memset(first,0,sizeof first),memset(c,0,sizeof c),memset(son,0,sizeof son),memset(son1,0,sizeof son1),memset(rt,0,sizeof rt);
        int u,v;
        for(register int i = 1;i < n;++i)
            scanf("%d%d",&u,&v),add(u,v),add(v,u);
        dfs1(1),dfs2(1);
        printf("%lld\n",ans);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment