| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 9/10 | Ø | O | O | Ø | O | O | Ø | . | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
Alice 有一个数字 $1\le a\le n\le 2000$ ，Bob 每次猜一个 $x$ ，Alice 回答是否 $x\ge a$。Alice 可以撒谎一次，Alice 第一个回答必须是肯定的，Alice 想要持续时间更久。对于每个 Bob 第一次询问的数 $i$，问最少多少次才能确定 $a$。
解题思路
当 Alice 回答否的时候，就是给 $[1,x]$ 打上了一个“不可能”标签；否则给 $[x+1,n]$ 打一个”不可能“标签。当一个数上的“不可能”标签不少于两个时才能确定这个数是否真正不是 $a$。因此，问题变成：给定 $[1,n]$ 序列，初始全为 $0$，Bob 每次选择一个 $x$，Alice 决定给左/右段区间 $+1$，当仅有一个元素 $<2$ 时，Bob 才能确定该元素是答案。
由于每次都是前缀/后缀加和，最后（除掉 $\ge 2$ 的元素）必定是依次 $a$ 个 $1$，$b$ 个 $0$，$c$ 个 $1$。设 $f_{a,b,c}$ 表示在这种状态下还要至少猜多少次，可以枚举转移点转移：
- 在 $a$ 中选 $x\in [0,a]$，贡献为 $\max(f_{x+b,0,0},f_{a-x,b,c})$
- 在 $b$ 中选 $x\in [0,b]$，贡献为 $\max(f_{x,b-x,c},f_{a,x,b-x})$
- 在 $c$ 中选 $x\in[0,c]$，贡献为 $\max(f_{a,b,x},f_{b+c-x,0,0})$
复杂度 $O(n^4)$ 。显然 $f$ 和 $a,c$ 都是决策单调的，可以优化到 $O(n^3)$。
调换值域和 $c$ 顺序，设 $f_{i,a,b}$ 表示走 $i$ 步最大能覆盖的 $(a,b,c)$ 中 $c$ 是多少。同样，枚举转移点转移：
- 在 $a$ 中选 $x\in [0,a]$，若 $f_{i-1,x,0}\ge b$ 则可以取到 $f_{i-1,a-x,b}$
- 在 $b$ 中选 $x\in [0,b]$，若 $f_{i-1,a,x}\ge b-x$ 则可以取到 $f_{i-1,x,b-x}$
- 在 $c$ 中选 $x\in[0,c]$，若 $f_{i-1,a,b}\ge 0,f_{i-1,b,0}\ge 0$ 则可以取到 $f_{i-1,a,b}+f_{i-1,b,0}$
第三个转移是 $O(1)$ 的，考虑用决策单调性维护前两个转移。当 $a$ 增加时，第一部分显然是取 $x$ 越大越好，因此决策点是单调不减的；第二部分的 $x$ 随着 $a$ 的减小是单调不增的。由于两个部分分别决策单调，分开维护两个决策点即可。
AC代码
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
typedef long long ll;
using namespace std;
int f[M][N][N];
int main(){
int i,j,a,b,x1,x2,n;
scanf("%d",&n);
memset(f,-1,sizeof(f));
f[0][0][0]=1;
f[0][1][0]=f[0][0][1]=0;
for(i=1;i<M;i++){
for(b=0;b<=n;b++){
x1=0,x2=b;
for(a=0;a<=n-b;a++){
int t=-1;
if(f[i-1][x1][0]>=b)t=max(t,f[i-1][a-x1][b]);
while(x2>0&&f[i-1][a][x2]<b-x2)x2--;
if(f[i-1][a][x2]>=b-x2)t=max(t,f[i-1][x2][b-x2]);
if(f[i-1][a][b]>=0&&f[i-1][b][0]>=0)t=max(t,f[i-1][a][b]+f[i-1][b][0]);
f[i][a][b]=t;
if(f[i-1][x1+1][0]>=b)x1++;
}
}
}
for(i=1;i<=n;i++){
a=i-1,b=n-i+1;
for(j=0;f[j][a][b]==-1;j++);
printf("%d ",j);
}
return 0;
}
B
题目描述
给一个 $n\times m(n,m\le 5000)$ 的矩阵 $c_{i,j}$，初始全为白色。每次可以花费 $c_{i,j}$ 将 $(i,j)$ 染黑，同时如果某个矩形的四个顶点有三个被染黑，那第四个也被自动染黑。问最小花费。
解题思路
solved by qxforever
容易想到最后必然染了 $n+m-1$ 个点。再联想一下连通性和从小到大贪心选择的策略，考虑到最小生成树。将每行、每列抽象为一个点，则 $(i,j)$ 通过 $c_{i,j}$ 边权相连，求个最小生成树即可。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 5010;
struct Dsu {
vector<int> f;
int n;
Dsu(int n) : n(n) {
f.resize(n);
iota(f.begin(), f.end(), 0);
}
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
f[x] = y;
return true;
}
return false;
}
};
int n, m, aa, b, c, d, p;
int A;
int sx[maxn], sy[maxn];
using E = tuple<int, int, int>;
vector<pair<short, short>> sss[int(1e5 + 10)];
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
int id(int x, int y) {
return (x - 1) * m + y;
}
int main() {
cin >> n >> m >> aa >> b >> c >> d >> p;
A = aa;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
A = (1ll * A * A * b + 1ll * A * c + d) % p;
sss[A].push_back({i, j});
}
}
ll ans = 0;
int cnt = 0;
Dsu dsu(n * m + 1);
for (int i = 0; i < p; i++) {
auto& ss = sss[i];
for (auto [x, y] : ss) {
int val = i;
auto yy = sx[x];
auto xx = sy[y];
if (yy == 0 && xx == 0) {
sx[x] = y;
sy[y] = x;
ans += val;
}
else if (yy == 0 || xx == 0) {
ans += val;
if (yy != 0)
dsu.unite(id(x, yy), id(x, y));
else
dsu.unite(id(xx, y), id(x, y));
sx[x] = y;
sy[y] = x;
}
else {
if (!dsu.unite(id(x, yy), id(xx, y)))
continue;
else
ans += val;
dsu.unite(id(xx, y), id(x, y));
sx[x] = y;
sy[y] = x;
}
debug(x, y);
cnt++;
if (cnt == n + m - 1) break;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// debug(i, j, dsu.find(id(i, j)));
// }
// }
}
}
cout << ans;
}
C
题目描述
要构造一个 $n\times n(n\le 2000)$ 的非负整数矩阵，满足第 $i$ 行最大值为 $b_i$，第 $i$ 列最大值为 $c_i$，求矩阵元素和的最小值。
解题思路
solved by qxforever & nikkukun
先假设每一个最大值都是由一个格子贡献的，即答案为 $\sum_i b_i+c_i$。在此基础上尽量让行列之间进行匹配，在交点处贡献，这样每次匹配就能减少 $b_i=c_j$ 的答案了。
从大到小考虑每个数，做二分图匹配即可。
AC代码 - by qxforever
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
126
127
128
129
130
131
132
133
134
135
136
137
138
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 2e3 + 10;
const int maxk = 1e6 + 10;
int n, m, k;
int b[maxn], c[maxn];
bool vis[maxn][maxn];
vector<int> q[maxk], w[maxk];
struct Edge {
int from, to, cap, flow;
};
struct Dinic {
static const int maxn = 2e4 + 23, inf = 2e9 + 23;
int n, m, s, t;
vector<Edge> e;
vector<int> g[maxn];
bool vis[maxn];
int d[maxn], cur[maxn];
void init(int n) {
for (int i = 0; i <= n; i++) g[i].clear();
e.clear();
}
void AddEdge(int from, int to, int cap) {
e.pb((Edge){from, to, cap, 0});
e.pb((Edge){to, from, 0, 0});
m = e.size();
g[from].pb(m - 2);
g[to].pb(m - 1);
}
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(s);
d[s] = 0, vis[s] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i : g[x]) {
Edge& t = e[i];
if (!vis[t.to] && t.cap > t.flow) {
vis[t.to] = 1;
d[t.to] = d[x] + 1;
q.push(t.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < (int)g[x].size(); i++) {
Edge& t = e[g[x][i]];
if (d[x] + 1 == d[t.to] && (f = dfs(t.to, min(a, t.cap - t.flow))) > 0) {
t.flow += f;
e[g[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s, this->t = t;
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, inf);
}
return flow;
}
};
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
int main() {
Dinic dinic;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
scanf("%d", &b[i]);
q[b[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
scanf("%d", &c[i]);
w[c[i]].push_back(i);
}
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
vis[x - 1][y - 1] = 1;
}
ll ans = 0;
for (int i = k; i; i--) {
if (q[i].size() == 0 || w[i].size() == 0) {
ans += 1ll * (q[i].size() + w[i].size()) * i;
}
else {
int l = q[i].size(), r = w[i].size(), S = l + r + 1, T = l + r + 2;
dinic.init(T + 3);
int cntx = 1, cnty = l + 1;
for (int j : q[i]) {
cnty = l + 1;
for (int k : w[i]) {
if (vis[j][k]) {
dinic.AddEdge(cntx, cnty, 1);
}
cnty++;
}
cntx++;
}
for (int j = 1; j <= l; j++) dinic.AddEdge(S, j, 1);
for (int k = l + 1; k <= l + r; k++) dinic.AddEdge(k, T, 1);
int match = dinic.Maxflow(S, T);
ans += 1ll * (l + r - match) * i;
debug(i, match, ans);
}
}
printf("%lld\n", ans);
}
D
题目描述
$n\times n(n\le 32)$ 的棋盘，有 $k\le 7$ 个地方不能放棋子。问满足每行、每列、每对角线至少有一个棋子，总共有 $C$ 个棋子的方案数。
解题思路
超级大容斥。
考虑容斥掉不能放棋子的地方：钦定某几个点必须放，这是一个 $2^k$ 的容斥。问题转化成确定了 $cnt$ 个点必须放，满足条件的方案数。
就是要求满足 $\{行1,行2,…,行n,列1,列2,…,列n,对角线1,对角线2 \}$ 均至少有一个点的方案数。这不好直接求，再考虑容斥掉对角线的限制：钦定某些对角线不能放元素，这又是一个 $2^2$ 的容斥。于是问题转化为：确定了两条对角线分别能/不能放元素，每行每列至少有一个点的方案数。
这时候只剩下行列了，我们同样使用容斥的思想进行处理。但由于要求某些对角线不能放元素，于是枚举 $A$ 行 $B$ 列的同时还要记录有多少点 $X$ 因为对角线被钦定不能放元素而无法选择，设状态为 $(A,B,X)$。这个状态代表选定了要在 $A$ 行 $B$ 列的元素里随便选，但其中的 $X$ 个点因为对角线限制不能选。如果直接容斥，那么仍然太大，考虑将容斥系数与方案数一同计算。
于是 $dp$ 一下能到达这个状态的、带容斥系数的方案数 $f_{A,B,X}$，则该状态对于答案的贡献就是 $f_{A,B,X}\binom{AB-X-cnt}{C-cnt}$。转移的时候“回”字形向内枚举行列，即同时处理 $i,n-i+1$ 行和列四个维度，枚举每一维度（行或者列）是否选择进行类似背包的转移。这里的 $(A,B,X)$ 状态数是 $2n^3$，转移是 $n\times 2^4$ 的。因此总复杂度 $O(2^{k+6}n^4)$，因为转移时可以通过限制一下状态上界，常数非常非常小。
AC代码
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
typedef long long ll;
using namespace std;
const int mod=10007;
int x[K],y[K],C[N][N];
int fixx[M],fixy[M];
int f[M][M][M<<1],g[M][M][M<<1];
int n,k,c;
int main(){
int i,j;
scanf("%d%d%d",&n,&k,&c);
C[0][0]=1;
for(i=1;i<N;i++){
C[i][0]=1;
for(j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for(i=0;i<k;i++)scanf("%d%d",&x[i],&y[i]),x[i]--,y[i]--;
int ans=0;
// Inclusion-Exclusion of K points
for(i=0;i<(1<<k);i++){
int diag1=0,diag2=0,cnt=0,sign=1;
memset(fixx,0,sizeof(fixx));
memset(fixy,0,sizeof(fixy));
for(j=0;j<k;j++){
if(i>>j&1){
fixx[x[j]]=fixy[y[j]]=1;
if(x[j]==y[j])diag1=1;
if(x[j]+y[j]==n-1)diag2=1;
cnt++,sign=-sign;
}
}
// Inclusion-Exclusion of 2 diagonals (1 stands for can't put items on the diagonal)
int d1,d2;
for(d1=0;d1<=1;d1++){
if(diag1&&d1)continue;
for(d2=0;d2<=1;d2++){
if(diag2&&d2)continue;
int sign_in=d1^d2?-1:1;
// Inclusion-Exclusion of rows / columns
// f[A][B][X]: the ways to choose rows & columns such that
// A rows, B columns must chosen, and X elements cant
// be chosen due to diagonal restrictions
// contribute to ans:
// \sum f[A][B][X] * C(AB-X-cnt, k-cnt)
memset(f,0,sizeof(f));
f[0][0][0]=1;
int l,r,a,b,x,tot=0;
for(l=0,r=n-1;l<=r;l++,r--,tot+=2){
memset(g,0,sizeof(g));
for(a=0;a<=tot;a++)
for(b=0;b<=tot;b++)
for(x=0;x<=tot+tot;x++){
if(!f[a][b][x])continue;
int ur,dr,lc,rc; // up/down row, left/right column
if(l==r){
for(ur=fixx[l];ur<=1;ur++)
for(lc=fixy[l];lc<=1;lc++){
int na=a+ur,nb=b+lc,nx=x+(d1|d2)*(ur*lc);
if(ur^lc)(g[na][nb][nx]-=f[a][b][x])%=mod;
else (g[na][nb][nx]+=f[a][b][x])%=mod;
}
}else{
for(ur=fixx[l];ur<=1;ur++)
for(dr=fixx[r];dr<=1;dr++)
for(lc=fixy[l];lc<=1;lc++)
for(rc=fixy[r];rc<=1;rc++){
int na=a+ur+dr,nb=b+lc+rc,nx=x+d1*(ur*lc+dr*rc)+d2*(ur*rc+dr*lc);
if(ur^dr^lc^rc)(g[na][nb][nx]-=f[a][b][x])%=mod;
else (g[na][nb][nx]+=f[a][b][x])%=mod;
}
}
}
swap(f,g);
}
int tmp=0;
for(a=0;a<=n;a++)
for(b=0;b<=n;b++)
for(x=0;x<=2*n;x++)
if(a*b>=x+cnt)
(tmp+=sign_in*sign*C[a*b-x-cnt][c-cnt]*f[a][b][x])%=mod;
(ans+=tmp)%=mod;
}
}
}
printf("%d",(ans%mod+mod)%mod);
return 0;
}
E
题目描述
$t\le 1e5$ 组询问，给定 $n\le 1e18$，问有多少对 $(x,y)$ 满足 $xy+1|x^2+y^2,1\le x\le y\le n$。
解题思路
$x^2-kxy+y^2-k=0$，首先找到特解 $p,p^3$，其中 $k=p^2$。由韦达定理，则 $x_1+x_2=ky$，即如果 $(x,y)$ 是解，则 $(ky-x,y)$ 也是解。于是可以预处理出来所有解，询问时二分即可。
AC代码
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
typedef long long ll;
using namespace std;
int jud(ll x,ll y){
return (x*x+y*y)%(x*y+1)==0;
}
vector<ll>p;
int main(){
int i,t;
ll n;
scanf("%d",&t);
p.pb(1);
for(i=2;i<=1000000;i++){
ll cur=1LL*i*i*i,pre=i;
while(cur<=1e18+10){
p.pb(cur);
if(cur>4e18/i/i)break;
ll nxt=(ll)cur*i*i-pre;
pre=cur;
cur=nxt;
}
}
sort(p.begin(),p.end());
//for(auto x:p)printf("%lld ",x);
while(t--){
ll i;
scanf("%lld",&n);
printf("%d\n",upper_bound(p.begin(),p.end(),n)-p.begin());
}
return 0;
}
F
题目描述
玩使用加减乘除括号的 24 点游戏，且必须存在中间答案不为整数（使用了不能整除的除法），问由 $1$ 到 $13$ 共 $n\le 4$ 张牌有多少种方案拼出来 $m$。
解题思路
暴搜。但是细节比较多。
AC代码 - by nikkukun & Potassium
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<ll, ll> pll;
const int N = 5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
int n, m;
void simplify(pll &x) {
auto &a = x.fi;
auto &b = x.se;
if (b < 0) {
a = -a;
b = -b;
}
int g = __gcd(abs(a), abs(b));
if (g != 0)
a /= g, b /= g;
}
pll add(pll a, pll b) {
pll ret = make_pair(a.fi * b.se + a.se * b.fi, a.se * b.se);
simplify(ret);
return ret;
}
pll sub(pll a, pll b) {
pll ret = make_pair(a.fi * b.se - a.se * b.fi, a.se * b.se);
simplify(ret);
return ret;
}
pll mul(pll a, pll b) {
pll ret = make_pair(a.fi * b.fi, a.se * b.se);
simplify(ret);
return ret;
}
pll div(pll a, pll b) {
pll ret = make_pair(a.fi * b.se, a.se * b.fi);
simplify(ret);
return ret;
}
bool vst[N];
bool hasSol;
vector<int> now;
vector<vector<int>> ans;
pll cal(pll a, pll b, int op, bool &flag) {
if (op == 1) return add(a, b);
if (op == 2) return sub(a, b);
if (op == 3) return mul(a, b);
if (op == 4) {
pll res = div(a,b);
if(res.second!=1)flag=1;
return res;
}
}
bool check(int dep, pll pre, bool flag) {
if (dep > n) {
if (pre == make_pair(1LL * m, 1LL)) {
hasSol = 1;
return flag;
} else
return 1;
}
for (int i = 0; i < n; i++) {
if (vst[i]) continue;
int o = now[i];
vst[i] = 1;
bool ret;
// +
ret = check(dep + 1, add(pre, make_pair(1LL * o, 1LL)), flag);
if (!ret) return 0;
if (dep != 1) {
// -
ret = check(dep + 1, sub(pre, make_pair(1LL * o, 1LL)), flag);
if (!ret) return 0;
ret = check(dep + 1, sub(make_pair(1LL * o, 1LL), pre), flag);
if (!ret) return 0;
// *
ret = check(dep + 1, mul(pre, make_pair(1LL * o, 1LL)), flag);
if (!ret) return 0;
// /
bool f1 = 0, f2 = 0;
pll tmp1 = cal(pre, make_pair(1LL * o, 1LL), 4, f1);
ret = check(dep + 1, tmp1, flag || f1);
if (!ret) return 0;
pll tmp2 = cal(make_pair(1LL * o, 1LL), pre, 4, f2);
ret = check(dep + 1, tmp2, flag || f2);
if (!ret) return 0;
}
vst[i] = 0;
}
return 1;
}
bool cc() {
hasSol=0;
memset(vst, 0, sizeof(vst));
vector<int> tmp = now;
do {
int a=tmp[0],b=tmp[1],c=tmp[2],d=tmp[3];
int op1,op2,op3;
for(op1=1;op1<=4;op1++){
for(op2=1;op2<=4;op2++){
for(op3=1;op3<=4;op3++){
bool flag=0;
// (a+b)*(c+d)
pll l_half = cal(make_pair(1LL*a,1LL),make_pair(1LL*b,1LL),op1,flag);
pll r_half = cal(make_pair(1LL*c,1LL),make_pair(1LL*d,1LL),op2,flag);
pll merge = cal(l_half,r_half,op3,flag);
if(merge==make_pair(1LL*m,1LL)){
if(!flag)return 0;
hasSol=1;
//printf("%d %d %d %d %d %d %d\n",a,b,c,d,op1,op2,op3);
}
}
}
}
} while (next_permutation(all(tmp)));
// (a+b) op c op d
bool flag = check(1,make_pair(0LL,1LL),0);
return hasSol&&flag;
}
void find(int dep, int pre) {
if (dep > n) {
if (cc()) {
ans.push_back(now);
}
return;
}
for (int o = pre; o <= 13; o++) {
now.push_back(o);
find(dep + 1, o);
now.pop_back();
}
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
find(1, 1);
sort(all(ans));
ans.erase(unique(all(ans)), ans.end());
cout << ans.size() << endl;
for (auto p: ans) {
for (auto x: p)
cout << x << ' ';
cout << endl;
}
return 0;
}
G
题目描述
给一棵 $n\le 1.1e5$ 的树，每个节点有一个颜色，初始时所有节点均没有颜色；每条边有距离权值。$q\le 1.1e5$ 次询问，每次有两种操作：
- 给某个节点 $u$ 染 $x\le n$ 颜色，保证 $u$ 之前没染过色，且没有节点染过 $x$ 色。
- 询问离 $u$ 最近的满足条件的祖先 $v$ ，$dis(u,v)$ 是多少。其中要满足，$v$ 被染过 $[l,r]$ 区间的某个颜色 $y$，且 $y\equiv 0 \bmod x$。
解题思路
因为每个点颜色不重，可以暴力将颜色分配到因数上，逐因数进行求解，总因数和是 $O(n\log n)$ 的。
于是 $y\equiv 0\bmod x$ 的限制没了。对于一个询问，就是要找到根的一条路径上，权值为 $[l,r]$ 区间内的数最近离 $p$ 多近，考虑用 $dfs$ 序维护，轻重链剖分后就是 $O(\log n)$ 段 $dfs$ 序连续的重链，在重链上二分即可求出答案。于是问题转化为求 $dfs$ 序区间 $[ql,qr]$ 上有多少个点满足点权 $\in[l,r]$。树状数组套线段树即可求出。
AC代码
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
typedef long long ll;
using namespace std;
vector<pii>G[N];
vector<int>factors[N];
struct Q{
int op,u,l,r,x;
int time;
};
// hld
int dep[N],fa[N],siz[N],son[N],top[N];
int dfnL[N],dfnR[N],tot,dfnToP[N];
ll dis[N];
void dfs1(int p,int f,int d){
dep[p]=d;
fa[p]=f;
siz[p]=1;
son[p]=0;
for(auto pr:G[p]){
auto q=pr.fi;
if(q==f)continue;
dis[q]=dis[p]+pr.se;
dfs1(q,p,d+1);
siz[p]+=siz[q];
if(siz[q]>siz[son[p]])son[p]=q;
}
}
void dfs2(int p,int Top){
dfnL[p]=++tot;dfnToP[tot]=p;
top[p]=Top;
if(!son[p])return;
dfs2(son[p],Top);
for(auto pr:G[p]){
auto q=pr.fi;
if(q==son[p]||q==fa[p])continue;
dfs2(q,q);
}
dfnR[p]=tot;
}
// bit and segtree
int root[N],n;
int tr[N*M],ls[N*M],rs[N*M],tr_tot;
int newnode(){
tr_tot++;
tr[tr_tot]=ls[tr_tot]=rs[tr_tot]=0;
return tr_tot;
}
void modify(int& p,int l,int r,int qx){
if(!p)p=newnode();
tr[p]++;
if(l==r)return;
int mid=(l+r)>>1;
if(mid>=qx)modify(ls[p],l,mid,qx);
else modify(rs[p],mid+1,r,qx);
}
int query(int& p,int l,int r,int ql,int qr){
if(!p)return 0;
if(ql<=l&&r<=qr)return tr[p];
int ans=0,mid=(l+r)>>1;
if(mid>=ql)ans+=query(ls[p],l,mid,ql,qr);
if(mid+1<=qr)ans+=query(rs[p],mid+1,r,ql,qr);
return ans;
}
int query(int x,int y1,int y2){ // [1,x]*[y1,y2]
int ans=0;assert(y1<=y2);
for(;x;x-=x&(-x))ans+=query(root[x],1,n,y1,y2);
return ans;
}
void insert(int x,int y){
for(;x<N;x+=x&(-x))
modify(root[x],1,n,y);
}
// query
vector<Q>queries[N];
ll ans[N];
void solve(int x){
if(queries[x].size()==0)return;
tr_tot=0;
for(auto q:queries[x]){
if(q.op==0){
insert(dfnL[q.u],q.x);
}else{
int p=q.u,l=q.l,r=q.r,id=q.time;
while(p){
// jump up among hard chain
int sum=query(dfnL[p],l,r); // [1, dfnL_p]
if(sum==query(dfnL[top[p]]-1,l,r))p=fa[top[p]];
else{
int ql=dfnL[top[p]],qr=dfnL[p];
while(ql<qr){
int mid=(ql+qr)>>1;
if(query(mid,l,r)<sum)ql=mid+1;
else qr=mid;
}
p=dfnToP[ql];
break;
}
}
if(!p)ans[id]=-1;
else ans[id]=dis[q.u]-dis[p];
}
}
// clear
for(auto q:queries[x]){
if(q.op==0){
int x=dfnL[q.u];
for(;x<N;x+=x&(-x))root[x]=0;
}
}
}
int main(){
int i,j,q;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)for(j=i;j<=n;j+=i)factors[j].pb(i);
for(i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u].pb(mp(v,w));
G[v].pb(mp(u,w));
}
dis[1]=siz[0]=0;
dfs1(1,0,1);
dfs2(1,1);
int cnt=0;
for(i=1;i<=q;i++){
Q t;int x;
scanf("%d",&t.op);
if(t.op){
scanf("%d%d%d%d",&t.u,&t.l,&t.r,&x);
t.time=++cnt;
queries[x].pb(t);
}
else{
scanf("%d%d",&t.u,&x);
t.x=x;
for(auto y:factors[x])queries[y].pb(t);
}
}
for(i=1;i<=n;i++)solve(i);
for(i=1;i<=cnt;i++)if(ans[i]!=-1)printf("%lld\n",ans[i]);else printf("Impossible!\n");
return 0;
}
H
题目描述
解题思路
AC代码
2
I
题目描述
给一个长度为 $n\le 6e5$ 的序列 $a$，$q\le 4e5$ 次操作，每次有两种操作：
- $[l,r]$ 区间全部异或 $x$
- $[l,r]$ 区间的第 $i$ 个数异或 $x+(i-l)$
所有询问后，求序列。值域 $2^{30}$。
解题思路
操作 $1$ 相当于区间异或，异或差分一下就行。
对于操作 $2$，使用分块思想。将序列根据 $x+i-l$ 的低 $10$ 位分为大小 $1024$ 的块，对于，每个整块中的元素相当于低 $10$ 位分别异或 $0,1,2,\cdots 1023$，因此每个位置 $i$ 记录一下从 $i$ 开始的 $1024$ 个元素是否需要分别异或 $0,1,2,\cdots 1023$，最后统计答案的时候暴力异或一下；对于高位，相当于 $\frac {n}{1024}$ 个块，每一个块异或了一个定值，同样适用异或差分即可。复杂度 $O(\frac{qn}{1024}+1024n)$。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 6e5 + 10;
const int B = (1 << 10);
const int P = (1 << 10) - 1;
int n, q;
int a[maxn], diff[maxn];
bool diff2[maxn];
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
// a[i] = 0;
while (q--) {
int op, l, r, x;
scanf("%d%d%d%d", &op, &l, &r, &x);
if (op == 0)
diff[l] ^= x, diff[r + 1] ^= x;
else {
// x + i - l
int st = -1, ed = -1;
int cur = x;
for (int i = l; i <= r; i++, cur++) {
if ((cur & P) == 0) {
st = i;
break;
}
a[i] ^= cur;
// debug(i, x + i - l);
}
if (st != -1) {
ed = st;
for (int i = st; i + B - 1 <= r; i += B) {
diff2[i] ^= 1;
diff[i] ^= cur;
diff[i + B] ^= cur;
ed = i + B;
cur += B;
}
}
if (ed != -1) for (int i = ed; i <= r; i++) a[i] ^= cur++;
}
}
for (int i = 1; i <= n; i++) {
diff[i] ^= diff[i - 1];
a[i] ^= diff[i];
}
for (int i = 1; i <= n; i++) {
if (diff2[i]) {
for (int j = 0; j < B; j++) a[i + j] ^= j;
}
}
for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
return 0;
}解题思路2
对于操作 $2$，变成两个后缀操作 $[l,n]$ 异或 $(i-l)+x$，以及 $[r+1,n]$ 异或 $(i-r)+r-l+x$。
现在要处理的就是，如何处理一个后缀操作 $[l,n]$ 异或 $(i-l)+x$。将 $[l,n]$ 全部异或上 $x$，那么剩下的就是”找不同“，即对于每一位求一下 $x+(i-l)$ 和 $x$ 的差别（异或值）。
对于第 $k$ 位， $(x+i)\oplus x$ 为类似 $00,1111,0000,1111,0000$ 的串，即先有 $2^k-(x\bmod 2^k)$ 个 $0$，然后是 $2^k$ 个 $0$，$2^k$ 个 $1$，如此往复，可以看作是一个 $00,1000,1000,1000,1000$ 形式的前缀和。但是构造这样的前缀和还是复杂度太高，于是考虑仅通过 $00,1000,0000,0000,0000$ 的串还原出来上述串。于是逐 $2^k$ 位考虑，又是一个前缀和形式。复杂度 $O((n+q)\log V)$。
AC代码
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
typedef long long ll;
using namespace std;
int a[N],xs[N];
bool der[30][N];
int main(){
int i,j,k,n,q;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
while(q--){
int o,l,r,x;
scanf("%d%d%d%d",&o,&l,&r,&x);
if(o==0)xs[l]^=x,xs[r+1]^=x;
else{
int y=x+r-l+1;
xs[l]^=x;
xs[r+1]^=y;
for(i=0;i<30;i++){
int d=(1<<i),p=(1<<i)-1;
if(l+d-(x&p)<=n)der[i][l+d-(x&p)]^=1;
if(r+1+d-(y&p)<=n)der[i][r+1+d-(y&p)]^=1;
}
}
}
for(i=0;i<30;i++)
for(j=1;j<=n;j++)
der[i][j]^=der[i][max(0,j-(1<<i))];
for(i=1;i<=n;i++){
for(j=0;j<30;j++)xs[i]^=der[j][i]<<j;
xs[i]^=xs[i-1];
printf("%d ",xs[i]^a[i]);
}
return 0;
}
J
题目描述
给一张 $n\le 8000$ 的完全图，每个边是黑色或白色。问有多少个三元组满足构成的三角形全为相同颜色的边。
解题思路
solved by nikkukun
这是一个经典问题，在去年春训 CF434E Furukawa Nagisa’s Tree 见过。考虑统计不满足条件的三角形，在连出去黑白边的点上统计，则一个点的贡献为 $\frac{cnt_0\times cnt_1} 2$。于是暴力求即可。
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 8000 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
namespace GenHelper {
unsigned z1, z2, z3, z4, b, u;
unsigned get() {
b = ((z1 << 6) ^ z1) >> 13;
z1 = ((z1 & 4294967294U) << 18) ^ b;
b = ((z2 << 2) ^ z2) >> 27;
z2 = ((z2 & 4294967288U) << 2) ^ b;
b = ((z3 << 13) ^ z3) >> 21;
z3 = ((z3 & 4294967280U) << 7) ^ b;
b = ((z4 << 3) ^ z4) >> 12;
z4 = ((z4 & 4294967168U) << 13) ^ b;
return (z1 ^ z2 ^ z3 ^ z4);
}
bool read() {
while (!u) u = get();
bool res = u & 1;
u >>= 1;
return res;
}
void srand(int x) {
z1 = x;
z2 = (~x) ^ 0x233333333U;
z3 = x ^ 0x1234598766U;
z4 = (~x) + 51;
u = 0;
}
} // namespace GenHelper
using namespace GenHelper;
bool edge[N][N];
int main() {
ios::sync_with_stdio(0);
int n, seed;
cin >> n >> seed;
srand(seed);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
edge[j][i] = edge[i][j] = read();
ll ans = 1LL * n * (n - 1) * (n - 2) / 6;
ll sum = 0;
for (int i = 0; i < n; i++) {
ll cnt = 0;
for (int j = 0; j < n; j++)
cnt += edge[i][j];
sum += 1LL * cnt * (n - 1 - cnt);
}
cout << ans - sum / 2 << endl;
return 0;
}