Day 1
没有题解 全是数论 T1 类欧几里得 T2 积函数 T3 容斥原理 T4 仙人掌拆分
Day 2
上午纯坐牢
T1
题目描述
盒子里有 \(n\) 个球，球的颜色有黑白两种，但是不知道初始状态
一共进行 \(m\) 操作，每次会从盒子中取出一个球，然后放入黑白各一个球，然后再取出一个球
取出的 \(2m\)个球会形成一个序列，你需要对所有初始状态计算本质不同的序列对
\(p\) 取模的结果
两个序列不同当且仅当存在一个位置，其所代表的球的颜色在两个序列中不同
这里的初始状态指的是盒子中两种颜色的球的个数
输入格式
一行三个数 \(n, m, p\)
输出格式
一行一个数表示答案
样例输入
1 2 114514
样例输出
8
数据范围
$ 1 \le n, m \le 3 * 10^{3}, 1 \le p \le 10^{9}$
题解
Code
T2
题目描述
定义一个可重集 \(S\) 的众数 \(f(S)\) 为集合中出现次数最多且编号最小的数字。例如 \(f(1,2,2,3) = 2,f(2,2,3,3) = 2\)。
定义一个可重集 \(S\) 的价值为\(2^{f(S)}\) 。
现在你有一个长度为 \(n\) 的序列 \(a_{1},a_{2},...,a_{n}\)，其中数字 \(a_{x}\) 表示可重集 \(S\) 中正整数 \(x\) 出现了 \(a_{x}\) 次。你需要将这个可重集 \(S\) 不重、不漏地划分成若干个可重集，使得这些可重集的价值之和最小。
你只需要输出这个数值在模 \(998244353\) 意义下的结果。
接下来，会有 \(q\) 次修改，每次修改会将 \(a_{x}\) 改为 \(y\) 。每次修改后你都要重新输出上面所描述的数值。
输入格式
第一行一个正整数 \(n\) ，表示序列的长度。
接下来一行 \(n\) 个正整数，分别表示$a_{1}, a_{2}, ..., a_{n} $。
接下来一个正整数 \(q\) ，表示修改次数。
接下来 \(q\) 行，每行两个正整数 \(x, y\)，表示将 \(a_{x}\) 改为 \(y\)。
输出格式
答案对 \(9982444353\) 取模。
在修改之前，先输出一个数值表示答案。
每次修改之后，都要输出一个数值表示答案。
样例输入
0
4
4 1 2 3
2
1 1
1 2
样例输出
2
10
6
数据范围
\(1 \le n \le 2 * 10^{5}, 0 \le q \le 2 * 10^{5}, 1 \le a_{i}, y \le 2 * 10^{5}, 1 \le x \le n\) 。
题解
Code
T3
题目描述
有一棵 \(n\) 个节点的树，一条树边可以记为 $(u_{i}, v_{i}, w_{i}),表示连接点 \(u_{i}\) 和点 \(v_{i}\) 权为 \(w_{i}\)。
对于边 \(i\) , \(a_{i,j}\) 的定义如下：令 \(c_{j,i}\) 为点 \(j\) 与其他 \(n - 1\) 个点之间的简单路径中经过边 \(i\) 的路径数，那么 \(a_{i,j} = c_{j,i} * w_{i}\) 。
一条边 \(i\) 在点 \(j\) 是优的，当且仅当不存在有另一条边 \(k\) 使得 \(a_{k,i} > a_{i,j}\)（可能有多条边在同一个点是优的）。
令 \(f(i)\) 表示边 \(i\) 在多少个点上是优的，现在要求 \(f(i)\) 。
输入格式
第一行，一个正整数 \(n\) 。
接下来 \(n - 1\) 行，每行三个正整数 \(u_{i}, v_{i}, w_{i}\) 表示一条边的信息。
输出格式
为减少输出量，共输出一行，一个整数，表示所有 \(f(i)\) 的异或和。
样例输入
5
1 2 3
2 3 1
3 4 1
3 5 1
样例输出
2
数据范围
\(n \le 10^{7}, w_{i} \le 10^{10}\)
题解
Code
T4
题目描述
GreenDuck 买到了最新的扫地机器人——RobotDuck。为了更高效地清扫房间，GreenDuck 决定分析一下房间的布局和 RobotDuck 的清扫机制。
GreenDuck 的房间可以看成是
行 列的网格，每个格子中要么是空的，要么放了一件家具。同时他惊奇地发现，每个家具都很薄(可以看成是一条线段)，两个端点分别占据了一个格子的西北角和东南角！
RobotDuck 在清扫时会采取这样一种机制：刚开始，可以给它设定一个方向(向南或向东)，接着它将一直沿着直线行进。如果碰到一个家具，那么会反弹。具体方式如下图所示。
GreenDuck 一开始得知，在自己的房间里有 \(k\) 件家具，第 \(i\) 件家具在第 \(x_{i}\)行，\(y_{i}\) 列。接下来，他会进行 \(Q\)次测试。
第一种测试，是在一个没有家具的格子上放上一件家具(方向保持一致)。这种测试后，他不会拿走任何家具。
第二种测试，是将 RobotDuck 贴着墙壁然后释放。具体来说，如果 RobotDuck 放在北面(对应了图中矩形的上边界)，那么它会从第一行某个格子的上边界的中心出发，面向南面行进。如果 RobotDuck 放在西面(对应了图中矩形的左边界)，那么它会从第一列某个格子的左边界的中心出发，面向东面行进。在行进过程中，它遵守清扫的机制。
GreenDuck 想知道，在每次第二种测试时，RobotDuck 在反弹恰好 \(q\) 次后会在哪个格子里。请你告诉他。
输入格式
第一行四个数字，\(type, n, m, k\), 分别表示数据类型(你可能不需要)，行数，列数，一开始有的家具件数。
接下来 \(k\)行，每行两个整数\(x_{i}, y_{i}\)，分别表示这件家具的行数和列数。
接下来一行一个整数 \(Q\) ，表示测试的次数。
接下来 \(Q\) 行，首先输入一个数字 \(w\)。
若 \(w\) 为 \(1\) ，则会有两个数字 \(x,y\)，分别表示新添的家具的行数和；列数。
若 \(w\) 为 \(2\)，则会有三个数字 \(x, y\)。若 \(x = 0\)，表示RobotDuck 从第一行第 \(y\)列格子的上边界的中心面向南行进。否则 \(y = 0\)，表示 RobotDuck 从第一列第 \(x\) 行格子的左边界的中心面向东行进。 \(q\) 表示反弹的次数。
输出格式
对于每个 \(w = 2\) 的操作，输出一行两个数字 \(x\) 和 \(y\)分别表示所在格子的行数和列数。
特别地，若 RobotDuck 在第 \(q\) 次反弹之前就碰到了墙壁，若墙壁是第 \(n\) 行格子的下边界，输出" \(n + 1\)列数"，否则输出"行数 $ m + 1$ "。
样例输入
0 4 4 1
2 2
5
2 2 0 3
1 3 2
2 2 0 2
2 2 0 3
2 2 0 4
样例输出
5 2
3 2
3 5
3 5
样例解释
数据范围
对于所有数据，家具的坐标不会重复，每次第二种操作要么 \(x=0\) 要么 \(y=0\)。 \(1 \le q \le 200000\)。
题解
对于每一个格子来说建立两个点，分为上半部分和下半部分。然后分别对外连边。于是每一次查询就是相当于查询弹了 \(q\) 次后所到达的地方。
在这里的路径要记录弹了的次数。方便之后的查询。
关于加家具的操作可以考虑上面所说的上下两部分， 然后交换连一下， 还是很好处理的。
本来一个点的 上半部分由别人上部分向右连的， 加了家具之后就是从别人的下部分向下连， 另外半边也是一样。
涉及到单点交换修改， 且每一条路径都是链的情况下我们可以考虑使用链表经行处理。
不过要么修改时间复杂度高达 $ O(n) $, 要么查询的时间复杂度高达 $ O(n) $
于是考虑分块， 再结合基本不等式可以得出最优的分块数在 \(300\) 左右。
然后注意点细节什么的就好了。
Code
Day 3
上午的题目还可以， T1 拓扑排序但是写挂了 T2 数据结构还是挂了 T3 网络流 但是好像还是寄了 T4看都没看
T1
题目描述
对于计数问题和期望问题，你们⼀定都不陌⽣。
给定⼀个 \(n\)个点 \(m\) 条边的有向⽆环图，第 \(i\) 条边有\(p_{i}\) 的概率存在，另外 \(1-p_{i}\) 的概率不存
在，求从 \(1\) ⾛到 \(n\) 的路径条数的期望。
输入格式
第⼀⾏两个正整数 \(n\) 和 \(m\)，表示点数和边数。
之后m⾏，每⾏三个数 \(u_{i},v_{i},p_{i}\)，表示每条边的起点，终点和出现的概率。
输出格式
⼀个⼩数，表示路径条数的期望，保留2位⼩数。
样例输入
3 3
1 2 0.5
2 3 0.5
1 3 0.5
样例输出
0.75
数据范围
\(n,m<=10^{5}\)，对所有 \(1<=i<=m\) ，满⾜ \(0<pi<1\) ，\(p_{i}\)⾄多两位⼩数。
保证给定的有向图不存在环，保证答案不超过100（不需要考虑精度问题）
题解
拓扑排序， 直接搞就可以， 转移就是每个点的期望到达值再乘上边的存在值。
最后用加法原理合并。
记得一开始拓扑的时候要把所有入度为零的点加进去。
虽然除了1以外其他点的贡献为零， 但是他们可以帮助别的点减少入度。（我在考试时就在这里寄了。）
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 +100;
double ans[N];
struct T{
int v;
double val;
};
vector <T> tu[N];
int ru[N];
int n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++){
int u, v;
double val;
cin >> u >> v >> val;
tu[u].push_back({v, val});
ru[v] ++;
}
queue <int> q;
for(int i = 1; i <= n; i ++)
if(!ru[i]) q.push(i);
ans[1] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = 0; i < tu[u].size(); i ++){
int v = tu[u][i].v;
double val = tu[u][i].val;
ans[v] += (ans[u] * val);
ru[v] --;
if(!ru[v])
q.push(v);
}
}
cout << fixed<< setprecision(2) << ans[n];
return 0;
}
T2
题目描述
给定⼀个 \(n\) 个点堆（不⼀定是⼆叉堆）的结构，每个点的值构成 \(1 \sim n\) 的排列，即每个点的
值都是 \(1 \sim n\) 之间的整数，且任意不同的两点的值不同。根据堆的定义，每个点的值⼤于它的
所有⼦节点。
现在已知其中 \(k\) 个点的值，你需要回答是否存在这样的堆，即是否可能填上剩下 \(n-k\) 个点
的值，使得每个点的值是 \(1 \sim n\)的排列，并且满⾜每个点的值⼤于⼦节点。
你需要分别判定 \(T\) 棵堆。
输入格式
第⼀⾏⼀个正整数 \(T\) 。接下来有 \(T\) 组数据。
每组数据第⼀⾏两个正整数 \(n\)
第⼆⾏ \(n\) 个整数，表示这个堆上每个节点的⽗亲 \(f\)，如果 \(f_{i}=0\) 表示根是 \(i\)
第三⾏ \(n\) 个整数，表示每个节点的值 \(v_{i}\)，如果 \(v_{i}=0\) 表示该节点的值未知
输出格式
\(T\) ⾏，第 \(i\) ⾏表示第 \(i\) 组数据是否存在这样的堆，如果存在，输出 \(1\) ，如果不存在，输出0。
数据范围
\(T<=100,n<=10^4\)
样例输入
2
5
0 1 2 3 4
5 4 3 1 2
13
0 1 1 1 2 2 2 3 3 4 4 8 8
13 7 9 0 0 0 0 3 0 0 0 0 0
样例输出
0
1
题解
Code
T3
题意描述
⼤学⾥总共有 \(c\) ⻔课，\(t\) 个时间段。每⻔课会在很多时间段开课，且不同时间段开的同⼀
⻔课可能容纳的⼈数不同，具体地，第 \(j\) 个时间段的第 \(i\) ⻔课的⼈数上限是 \(a[i,j]\)，如果\(a[i,j]=0\) 则表示该时间段不开放该课程。教室可以容纳的的⼈数最⼤值是 \(N\) ，保证所有的 $ a[i,j]<=N$ 。
每个学⽣每⻔课可以选择在任何⼀个时间段上，但不能在同⼀个时间段上超过⼀⻔课。求⼤
学⾥学⽣⼈数的上限，使得存在⼀种选课的⽅式，每位学⽣的每⻔课都能选上。
输入格式
第⼀⾏三个正整数 \(N\)，\(c\) 和 \(t\)，分别表示教室⼤⼩，课程数量和时间段数量。
之后 \(c\) ⾏，每⾏ \(t\) 个⾮负整数，第 \(i\) ⾏第 \(j\)个整数 \(a[i,j]\) 表示第 \(i\) ⻔课在第 \(j\) 个时间段的⼈数上限。
输出格式
⼀个⾮负整数，表示⼤学⾥学⽣⼈数的上限。
数据范围
$ N,c,t<=50 $
样例输入
3 2 3
3 1 0
3 1 0
样例输出
2
题解
Code
T4
题意描述
给定⼀张 \(n\) 个点 \(m\) 条边的⽆向图，求出所有⽣成树中，以 \(1\) 为根的情况下所有节点的深
度之和的最⼤值，其中树上节点的深度表示该节点到根的路径上的节点个数，包括该节点本身和根节点。
输入格式
第⼀⾏两个正整数 \(n\) 和 \(m\) ，表示点数和边数。
之后 \(m\) ⾏，每⾏两个整数 \(u\) 和 \(v\) ，表示每条边的端点。
输出格式
⼀个整数，表示所有节点深度之和的最⼤值。
数据范围
$ n \le 20, m \le n * (n - 1) / 2$
样例输入
3 3
1 2
1 3
2 3
样例输出f
6
题解
Code
下午
下午讲图论
T1 ABC262E
T2 CSP-S2021交通规划
T3 Noi2022 挑战 NPCll （【模板】树同（[BJOI2015]
树的同构））
T4 CCO2022 P5 Phone Plans
T5 ABC261Ex
T6 AGC056C
T7 CF1519F
T8 CF1525F
T9 CF1508C
T10 CF1712F
Day 3
上午
只会T1, 其他的全不会
T1 Doctor
题目描述
给定一棵 \(n\) 个点的树和参数 \(k\)，你需要找到一条起点为 \(1\) 的路径，满足路径上恰好有 \(k\) 个不同的顶点，且路径的长度最短。一条路径的长度定义为路径经过的点数。
注意，你不需要保证路径是一条简单路径，即路径可以经过重复点和重复边。
输入格式
本题有多组数据。
输入的第一行包含一个正整数 \(T\)，分别表示测试数据组数。
对于每一组测试数据：
输入的第一行包含两个正整数 \(n , k\)，分别表示树的顶点数和要求经过的不同的顶点数。
接下来 \(n - 1\) 行，每行两个整数 \(u, v\)，表示树上存在一条连接顶点 \(u\) 和顶点 \(v\) 的边。
输出格式
对于每一组测试数据：
第一行包含一个正整数 \(m\)，表示路径的长度。
第二行包含 \(m\) 个正整数，描述树上的一条路径，其中第 \(i\) 个正整数表示路径上第 \(i\) 个结点的编号。
数据范围
$ 1 \le n, m \le 10^{5} $
样例输入
2
6 4
1 4
2 5
1 6
1 3
1 2
6 4
1 2
5 6
1 4
2 5
1 3
样例输出
5
1 4 1 2 5
4
1 2 5 6
题解
Code
T2 Patriot
题目描述
给定 \(m\) 个集合 $S_1 \sim S_m $，计数长度为 \(n\) 的整数序列 \(a\)的个数，使得对于任意 \(i\)，$ 0 \le a_i \le r $ 且由 \(a\) 导出的长度为 \(m\) 的序列 $ b_i = \bigoplus\limits_{j \in S_i}a_j$ 是一个不降序列（定义空集的 \(b_i\) 为 $ 0 $），即对于 $ 1 \le i < m，b_i \le b_{i + 1} $。其中 $ \oplus$ 表示异或运算。
由于答案可能很大，请输出答案 \(mod\) $998244353 $ 的值。
输入格式
第一行包含两个整数 \(n，m\)表示序列长度和集合的个数。
接下来 \(n\) 行，每行包含一个用二进制形式表示的正整数，其中第 \(i\) 行的正整数表示 \(r_i\) ，含义见题目描述。
接下来 \(m\) 行，每行包含长度为 \(n\) 的 01 串，第 \(i\) 行描述集合 \(S_i\) ，其中第 \(i\) 个序列的第 \(j\) 个字符为 \(1\) 表示 $ j \in S_i$，为 \(0\) 表示 \(j \not\in S_i\)。
输出格式
一行一个整数，表示答案 \(mod\) \(998244353\) 的值。
数据范围
$ 1 \le n, m \le 7, 1 \le r_i \le 2^{500} - 1$
样例输入
3 4
110
101
100
111
101
011
010
样例输入
10
题解
Code
T3 Talulah
题目描述
给定一个长度为 \(n\) 的排列 \(p\) ，定义集合 \(S_i = \{ x | x \ge i \enspace \max\limits_{i \le k < x} p_k < p_x \}\) 。你需要回答一共 \(q\) 组询问，对于第 \(i\) 组询问，给定区间 $ [l_i, r_i] $，你需要求出 $ \sum\limits_{l \le x, y \le r} |S_x \cup S_y|$的值。
输入格式
第一行包含三个正整数 \(n, 1, type\) ，表示排列的长度，询问次数以及 \(p\) 是否随机生成（ \(type = 1\)表示 \(p\) 随机生成）。
第二行包含 \(n\) 个正整数，描述排列 \(p\) ，其中第 \(i\) 个正整数表示 \(p_i\) 的值。
接下来 \(q\) 行，每行包含两个正整数 \(l_i，r_i\) 描述一组询问。
输出格式
共 \(q\) 行，其中第 \(i\) 行包含一个正整数，表示第 \(i\) 组询问的答案。
数据范围
$ 1 \le n, q \le 2,5 * 10^{5} $
样例输入
5 5 0
3 1 4 5 2
1 2
3 5
2 5
1 3
1 5
样例输出
14
18
41
28
72
题解
Code
T4 Rosmontis
题目描述
求有序正整数序列对 \((A,B)\) 的数量，满足 \(A_i，B_i \in [1,k]\) ,$ |A| = |B| = n $且存在方案使得从 \(A\) 中删去至多两个元素， \(B\) 中删去至多两个元素后，满足 \(A=B\)。
由于答案可能很大，请输出答案 \(mod \enspace 10^{9} + 9\)的值。
输入格式
第一行包含两个正整数 \(n, k\)，分别表示序列的长度和序列的值域。
输出格式
一行一个整数，表示答案模 $ 10^9 + 9$ 的值。
数据范围
$ 1 \le n, k \le 10^9 $
样例输入1
3 3
样例输出1
687
样例输入2
4 7
样例输出2
2165779
题解
Code
Day 4
T1 equal
上午一道题目都不会， 题目又没有好好讲的， 感觉最近有点寄。
题目描述
有一个长度为 \(n\) 的序列，你要切三刀，把这个序列分成连续的 \(4\) 段，每段的权值
为这段所有数之和, 你要让这四个权值的极差最小。
输入格式
第一行一个整数 \(n\) 。
第二行 \(n\) 个整数，第 \(i\) 个数为 \(a_i\)。
输出格式
一个整数表示最小的四段的极差。
数据范围
$ 4 \le n \le 200000, \enspace 1 \le a_i \le 10^9 $
样例输入
5
3 2 4 1 2
样例输出
2
题解
其实本题很简单（但是在考试的时候没有想到）。
先枚举中间点， 然后把东西分成两部分， 然后再对两部分进行操作。
显然那两部分的极差最小时整体的极差最小, 可以用二分来做。
然后可以发现， 当中间点向左移动一格时， 左右两边的断电也至多会向右移动一格， 所以可以在线性时间内通过此题。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
int n;
long long a[N];
long long asum[N];
long long get(int l, int r){
long long ll = l, rr = r;
while ( ll < rr){
int mid = (ll + rr) >> 1;
if(asum[mid] - asum[l - 1] < asum[r] - asum[mid])
ll = mid + 1;
else
rr = mid;
}
return ll;
}
long long check(int l, int mid, int r){
long long len[5];
len[1] = asum[l], len[2] = asum[mid] - asum[l], len[3]= asum[r] - asum[mid], len[4]= asum[n] - asum[r];
sort(len + 1,len + 1 + 4);
return len[4] - len[1];
}
int main(){
cin >> n;
asum[0] = 0;
for(int i = 1; i <= n; i ++)
cin >> a[i], asum[i] = asum[i - 1] + a[i];
int mid = 2;
int l, r; // 规定第一段的值为 asum[l] 第二段为 asum[mid] - asum[l] 第三段为 asum[r] - asum[mid] 第四段为 asum[n] - asum[r]
long long ans = 0x3f3f3f3f3f3f3f3f;
for(mid = 2; mid <= n - 1; mid ++){
int ll= get(1, mid), rr = get(mid + 1, n);
for(int i = -1; i <= 1; i ++)
for(int j = -1; j <= 1; j ++){
int cl = ll + i, cr = rr + j;
ans = min(check(cl, mid, cr), ans);
}
}
cout << ans;
return 0;
}
T2 dance
题目描述
有一个长度为 \(n\) 的序列，对于序列中的每一个数你都需要求出，所有包含这个数
且长度在 \(l\) 到 \(r\) 范围内的连续子序列中，最大的连续子序列的权值和。
输入格式
第一行三个整数 \(n\), \(l\), \(r\)。
第二行 \(n\) 个整数，第 \(i\) 个数为 \(a_i\)。
输出格式
一行 \(n\) 个整数，第 \(n\) 个整数表示 \(f_i\)。
数据范围
$ 1 \le l \le r \le n \le 10^5, \enspace 0 \le |a_i| \le 10^5$
样例输入
5 1 3
-1 -6 7 7 -4
样例输出
0 8 14 14 10
题解
Code
T3 practice
题目描述
你有一个数 \(a\)，你想要把它变成 \(b\) ，每次你可以选择一个 \([1, k]\) 范围内的整数 \(x\)，假
设当前的数为 \(p\)，你可以把 \(p\) 变成 \(p - (p \enspace mod \enspace x)\)，特别的，当你选择 \(x = 1\) 时，\(p\) 会变成 \(p - 1\) ，问你至少使用多少次操作才能把 \(a\) 变成 \(b\)。
输入格式
一行一个整数 \(T\)，表示有 \(T\) 组数据。
接下来 \(T\) 行每行 \(3\) 个数 \(a\), \(b\), \(k\)。
输出格式
输出 \(T\) 行每行一个整数表示答案。
数据范围
\(1 ≤ T ≤ 10，\enspace b ≤ a ≤ 10^{18}，\enspace 1 ≤ k ≤ 15\)。
样例输入
3
10 1 4
6 3 10
1000000000000000000 1 3
样例输出
6
2
666666666666666667
题解
Code
T4 subsets
题目描述
给定一个由整数组成的集合，问有多少个非空子集，子集中的数能划分成和相等的
两份。集合中的数是可以重复的。
输入格式
一行一个整数 \(n\)，集合的大小。
接下来 \(n\) 行，第 \(i + 1\) 行的数 \(a_i\) 表示集合里第 \(i\) 个数。
输出格式
行一个数，表示方案数。
数据范围
$ n \le 20, \enspace |a_i| \le 10^8 $
样例输入
4
1
2
3
4
样例输出
3
题解
考试的时候总觉得像背包， 因为看错题目了。
其实只要输出可行的子集， 而我看成了具体的方案数， 导致写了一个很烦的背包然后成功保灵。
其实就是简单的状压加折半搜索。
可以考虑我们要把一个子集分成两个集合 \(A\) 和 \(B\)， 然后记 \(A\) 中元素总和 减去 \(B\) 中元素总和为 \(s\)。
然后考虑一个元素 \(a_i\) , 以及当前状态 \(sta\) ,有三种情况：
- 不选， 对 \(s\) 和 \(sta\) 都没有影响
- 选， 放进 \(A\) , \(s + a_i , sta \enspace | \enspace (1 << (i - 1))\)
- 选， 放进 \(B\) , \(s - a_i , sta \enspace | \enspace (1 << (i - 1))\)
然后就处理出了半部分所有差值为 \(s\) 的状态 然后Hash一下， 后面要用。
思考， 前半部分差值为 \(s\) 后半部分差值为 \(-s\) 的两种分法合并在一起是不是就可以了。
所以在后半段结束时调用出之前Hash进的相应状态， 再取或运算， 这就是合法的状态。
因为每种子集只算一次， 考虑把合法的状态存进一个 \(bool\) 数组。
最后的答案就是把 \(bool\) 数组里的 \(1\) 全部加起来。
记住， 不能有空集。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = (1 << 20) + 114514;
map <int, int> id;
int cnt = 0;
vector <int> Hash[N];
#define ll long long
ll a[23];
bool an[N];
int mid;
void dfsl(int dep, int s, int state){
if(dep == mid + 1){
if(!id[s]) id[s] = ++ cnt;
Hash[id[s]].push_back(state);
return;
}
dfsl(dep + 1, s, state); //不选
dfsl(dep + 1, s + a[dep], state | (1 << (dep - 1)));
dfsl(dep + 1, s - a[dep], state | (1 << (dep - 1)));
}
void dfsr(int dep, int s, int state){
if(dep == n + 1){
if(!id[s]) return ;
int k = id[s];
for(int i = 0; i < Hash[k].size(); i ++)
an[state | Hash[k][i]] = 1;
return;
}
dfsr(dep + 1, s, state); //不选
dfsr(dep + 1, s + a[dep], state | (1 << (dep - 1)));
dfsr(dep + 1, s - a[dep], state | (1 << (dep - 1)));
}
int ans = 0;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%lld", &a[i]);
mid = n / 2;
dfsl (1, 0, 0);
dfsr (mid + 1, 0, 0);
for(int i = 1; i <= (1 << n); i ++)
ans += an[i];
cout << ans;
return 0;
}
Day 5
T1
题目描述
小Q和小王在博弈。
对于所有 $ 1 \le i \le n$，桌子上有 \(a_i\) 个数字 \(i\)。 小Q和小王轮流操作，小Q先手。每次操作可以选任意两个相等的数 \(x\)，从桌子上拿走这两个数，并再放入一个 $ x + 1 $。
无法操作的人就输了。如果两人都采取最优策略，问谁会赢。
一个测试点含有多组数据。
输入格式
第一行一个整数 \(T\)，表示测试组数。
接下来 \(T\) 组每组第一行一个整数 \(n\)，第二行 \(n\) 个整数表示 \(a_1, a_2 , ...a_n\)
输出格式
\(T\) 行，每行一个大写字母表示该组测试的答案。若小Q会赢输出 \(Q\) ，否则输出 \(W\) 。
数据范围
$ T \le 10, /ensapce n \le 10^5, \enspace 0 \le a_i \le 10^9$
输入样例
2
1
2
2
2 1
输出样例
Q
W
题解
这道是个诈骗题， 看上去是博弈论其实不是。
可以发现，这个游戏跟决策没有关系， 因为只要拿两个就可以。只要考虑总的操作次数就可以。
每一次操作会对后面一堆有影响， 所以从前往后做。
再注意 \(n\) 后面的数可能对答案也有贡献， 加上去就可以。
每一次做要将数组清零。
Code
#include <bits/stdc++.h>
using namespace std;
int T;
#define ll long long
const int N = 2e5 + 100000;
ll a[N];
void solve(){
int n;
memset(a, 0, sizeof(a));
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%lld", &a[i]);
ll res = 0;
for(int i = 1; i <= n; i ++){
res += a[i] / 2;
a[i + 1] += a[i] / 2;
res %= 2;
}
int k = n + 1;
while(a[k]){
res += a[k] / 2;
a[k + 1] = a[k] / 2;
k ++;
res %= 2;
}
if(res) printf("Q\n");
else printf("W\n");
}
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d", &T);
while (T --)
solve();
return 0;
}
T2
题目描述
你有一个长度为 \(n\) 的序列 \(a_1, a_2...a_n\) 。
你需要进行 \(m\) 次操作。
- 给定 \(p\)，\(x\) 将 \(a_p\) 赋值为 \(x\)。
- 给定 \(l, r, k\) 将所有 \(l \le i \le r\) 的 \(a_i\) 赋值为 \(a_i \enspace mod \enspace k\)。（ \(mod\) 为取模运算）
- 给定 \(l，r\) 求所有 $l \le i \le r $ 的 \(a_i\) 的最大值。
输入格式
第一行两个整数 \(n, m\)。
第二行 \(n\) 个整数 \(a_1, a_2, ... , a_n\)。
接下来 \(m\) 行每行第一个整数表示操作类型，后面 \(2\) 或 \(3\) 个整数表示这次操作给定的参数。
输出格式
对于所有操作 \(3\)，输出一行一个整数表示这次操作的答案。
数据范围
\(n, m \le 10^5, 1 \le a_i, x, k \le 10^9, 1 \le l \le r \le n\)。
输入样例
3 5
2 3 3
3 1 3
2 2 3 2
3 1 3
1 2 5
3 2 3
输出样例
3
2
5
题解
线段树， 暴力操作。
若子树的最大值小于模数， 就不去修改。
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 1000;
int n, m;
struct Tr{
ll val;
}tr[N * 8];
ll a[N];
void push_up(int rt){
tr[rt].val = max(tr[rt << 1].val, tr[rt << 1 | 1].val);
return;
}
void build(int rt, int l , int r){
if(l == r){
tr[rt].val = a[l];
return;
}
int m = (l + r) >> 1;
build(rt << 1, l, m);
build(rt << 1 | 1, m + 1, r);
push_up(rt);
return ;
}
bool check(int rt, ll p){
if(tr[rt].val < p) return false;
return true;
}
void change(int rt, int l, int r, ll p, ll x){
if(l == r){tr[rt].val = p; return;}
int m = (l + r) >> 1;
if(m >= x) change(rt << 1, l, m, p, x);
else change(rt << 1 | 1, m + 1, r, p, x);
push_up(rt);
}
void update(int rt, int l, int r, int L, int R, ll k){
if(l == r){tr[rt].val %= k; return;}
int m = (l + r) >> 1;
if(L <= m && check(rt << 1, k)) update(rt << 1, l, m, L, R, k);
if(m < R && check(rt << 1 | 1, k)) update(rt << 1 | 1, m + 1, r, L, R, k);
push_up(rt);
}
ll query(int rt, int l, int r, int L, int R){
if(L <= l && r <= R) return tr[rt].val;
int m = (l + r) >> 1;
ll ans = -19090;
if(L <= m){
if(tr[rt << 1].val == 0) ans = max(ans, (ll)0);
else ans = max(ans, query(rt << 1, l, m, L, R));
}
if(m < R){
if(tr[rt << 1 | 1].val == 0) ans = max(ans, (ll)0);
else ans = max(ans, query(rt << 1 | 1, m + 1, r, L, R));
}
return ans;
}
int main(){
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1;i <= n; i ++)
scanf("%lld", &a[i]);
build(1, 1, n);
for(int i = 1; i <= m; i ++){
int pos;
scanf("%d", &pos);
if(pos == 1){
ll p, x;
scanf("%lld%lld", &p, &x);
change(1, 1, n, x, p);
}
if(pos == 2){
int l, r;
ll k;
scanf("%d%d%lld", &l, &r, &k);
update(1, 1, n, l, r, k);
}
if(pos == 3){
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, 1, n, l, r));
}
}
return 0;
}
T3
题目描述
给定 \(n\)，求所有长度为 \(n\) 的错排的逆序对数之和。
一个测试点含有多组数据。
答案对 $998244353 $取模。
输入格式
第一行一个整数 \(T\)，表示测试组数。
接下来 \(T\) 行每行一个整数 \(n\)。
输出格式
\(T\)行， 每行一个整数表示这组数据的答案。
数据范围
$ T \le 2 * 10^5 \enspace n \le 10^7 $
输入样例
3
2
3
114514
输出样例
1
4
556483447
题解
Code
T4（TL = 3s）
题目描述
现在是晚上九点，小王准备为大家献歌一首。
小王要唱的歌的歌词可以抽象成一个长度为 \(n\) 的字符串 \(s\)，其中每个字符可能是大小写字母，数字，下划线。
(注：大小写相同字母视为不同的字符)
现在，小Q会进行以下 \(m\) 次操作，每次操作给定 \(l, r, t\):
- 小Q为了让小王唱的更魔怔，把歌词的第 \(l\) 个字符到第 \(r\)个字符替换为长度为 \(r - l + 1\) 的字符串。
- 小Q想检验小王唱的怎么样，让小王从第 \(l\) 个字符唱到第 \(r\) 个字符。他想知道在这个过程他总共会听到多少次 \(t\) 。即 \(t\) 在 \(s[l,r]\) 中共可重叠出现了多少次。
由于训练小王唱歌不是一件轻松的事，所以小Q请你写一个程序来帮他训练小王并回答每次询问。
输入格式
第一行两个整数 \(n, m\)。
接着一行长度为 \(n\) 的字符串 \(s\)。
下面 \(m\) 行每行开头一个 \(1\) 或 \(2\)表示操作类型，然后是两个正整数 \(l,r\) 和一个字符串 \(t\)。
输出格式
对于每次 \(2\) 操作，输出一行表示答案。
数据范围
\(1 \le n, m \le 10^5, \enspace 1 \le k_1 \le 2 * 10^6, \enspace 1 \le k_2 \le 10^5\)
其中，\(k_1\) 为所有 1 操作中的 \(t\) 长度之和， \(k_2\) 为所有 \(2\) 操作中的 \(t\) 长度之和。
输入样例
34 10
JinWan9Dian_WHQChangGe_BuJianBuSan
2 1 34 an
2 6 33 an
1 1 10 aaaaaaaaaa
2 2 9 aaa
2 1 34 _
1 11 20 abaabaabab
2 1 20 ab
2 1 20 aab
1 1 34 JinWan9Dian_WHQChangGe_BuJianBuSan
2 1 34 JinWan9Dian_WHQChangGe_BuJianBuSan
输出样例
5
3
6
2
4
3
1
题解
Code
Day 6
T1 permutation
题目描述
给两个大小为 \(n\) 的排列 \(p,q\)。
你需要给出另一个大小为 \(n\) 的排列 \(h * p * h^{-1} = q\) 满足 ，或判断不存在这样的排列 \(h\) 。
一些定义：
- \(p\) 是一个大小为 \(n\) 的排列当且仅当 \(p_i \in \{ 1, 2, ..., n \}\)，且 \(p_i\) 两两不同。
对于两个大小为 \(n\) 排列的 \(p，q\) 定义 \(h = p * q\)，其中 $\forall i, h_i, q_{p_i} 。（注意，这里的定义可能与你所了解的定义不同）
对于一个大小为 \(n\) 的排列 ，定义 为 的逆元，其中 满足
学习清单
prufer
树的同