• 两个数异或最值 \to Trie 上跑跑

  • 一堆数异或最值 \to 线性基


都是高二的老狗了,心态能不能像老狗一样平稳一点,tmd 被小朋友交几发暴力就吓炸了?!
想起了省选被隔壁老哥支配的恐惧
还是太重结果了,但这种心态会极大程度影响我的过程
这 TM 是老毛病了吧,中考时考数学做到压轴就一直在想 zhy,zzm 他们一定都切穿了导致我后面做的跟屎一样,好在是做到压轴才开始自闭的,要不可能雅礼都进不了
离 CSP 就两次(?)考试了,一定不能再跟别人比较了

耶耶耶今天是保龄 day~

TMD,T1 不会,T2 不会,T3 不会,T4 不会,我这场在干嘛

T1 遇到沟通困难的时候为什么不重新看一遍题?

T2 构造题你写了个啥?没拍过的乱搞活该保灵好吧

T3 为什么不认真读懂题想一想?线性基写脸上了?

T4 是真的不会。

TMD

# Solutions:

# a

nn 页的日记本,写过的页不能再写,第一天可任意写一页,记昨天写的一页为 tt ,那今天只能写 [1,t][1,t] ,求与给定数组 qq 趋势相同的方案数,支持交换 qq 中两个元素。
要求做到 $$O (n\log n)$$.

cnm,看错题了,看错的题到现在还不会做。

那既然我们今天只能写 [1,t][1,t] 的,记还能写的页码为一个集合,我们一定是写一个递减的东西且以当前集合中最小页码结尾。

然后就是大力推组合数的柿子,由于要与给定 qiq_i 趋势相同,那我们找到每个 qi<qi+1q_i<q_{i+1} 的位置拿出来做一个数组 aia_i 咋计数捏?为了方便处理一些奇怪的情况,我们把 0,n0,n 也放进序列。

每个 aia_i 其实是代表了一个递减段的,做每个递减段时,我们剩余数字集合大小是知道的,而我们是并不关注究竟还剩了什么数字的,毕竟是一个排列,放上去会自动排好序,但此时集合中最小的元素是必须被选的,我们可以得出柿子:

Ans=i=2k(nai11aiai11)Ans=\prod\limits_{i=2}^k\binom{n-a_{i-1}-1}{a_i-a_{i-1}-1}

这里就可以做不带修的情况了,带修咋做,上面这个形式不好维护,我们把组合数拆开,乘一乘,发现好多约掉了。

Ans=(na11)!×k=2n1(aiai1)!×1(nai)Ans=(n-a_1-1)!\times \prod\limits_{k=2}^n{1\over (a_i-a_{i-1})!}\times {1\over (n-a_i)}

我们钦定了 a1=0a_1=0 那上面那个东西前面就是 (n1)!(n-1)!

这个显然可以 setset 维护交换。

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
/* ==============================
* Author : Odalys
*
* Blog : Odalys.xyz
*
* Mail : minyuenu@gmail.com
* =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define ins insert
#define era erase
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 3e5 + 10;
const int Mod = 1e9 + 7;
inline int Mul (int x, int y) {
return 1ll * x * y >= Mod ? (1ll * x * y % Mod) : (x * y);
}
inline int Add (int x, int y) {
return (x + y >= Mod) ? (x + y - Mod) : x + y;
}
inline int Sub (int x, int y) {
return (x - y < 0) ? (x - y + Mod) : (x - y);
}
int qpow (int a, int b) {
int ans = 1, base = a;
while (b) {
if (b & 1) ans = Mul(ans, base);
base = Mul(base, base);
b >>= 1;
}
return ans;
}
int fac[N], ifac[N];
void Init (int M) {
fac[0] = ifac[0] = 1;
For (i, 1, M) fac[i] = Mul(fac[i - 1], i);
ifac[M] = qpow(fac[M], Mod - 2);
foR (i, M - 1, 1) ifac[i] = Mul(ifac[i + 1], i + 1);
}
int bin (int a, int b) {
if (a < b || a < 0 || b < 0) return 0;
return Mul(fac[a], Mul(ifac[a - b], ifac[b]));
}
int Inv (int s) {
int a = qpow(s, Mod - 2);
return (a ? a : 1);
}
set <int> mck;
int a[N], s[N], tot;
int Ans;
int n, m;
int eps(int x) { return x ? x : 1; }
inline void Era (int x) {
auto it1 = mck.lower_bound(x); it1--; int pre = *it1;
Ans = Mul(Ans, Mul(eps(n - x), fac[x - pre - 1]));
auto it2 = mck.upper_bound(x); int nxt = *it2;
Ans = Mul(Ans, Mul(eps(n - nxt), fac[nxt - x - 1]));
mck.erase(x);
Ans = Mul(Ans, Mul(Inv(n - nxt), ifac[nxt - pre - 1]));
}
inline void Ins (int x) {
auto it1 = mck.lower_bound(x), it2 = mck.upper_bound(x);
it1--;
int pre = *it1, nxt = *it2;
Ans = Mul(Ans, Mul(eps(n - nxt), fac[nxt - pre - 1]));
Ans = Mul(Ans, Mul(Inv(n - x), ifac[x - pre - 1]));
Ans = Mul(Ans, Mul(Inv(n - nxt), ifac[nxt - x - 1]));
mck.insert(x);
}

int del[N];

int main() {
Init(N - 10);
read(n); read(m);
For (i, 1, n) read(a[i]);
s[++tot] = 0; mck.ins(0);
For (i, 1, n - 1) if (a[i] < a[i + 1]) s[++tot] = i, mck.ins(i);
s[++tot] = n; mck.ins(n);
Ans = 1;
For (i, 2, tot) Ans = Mul(Ans, Mul(Inv(n - s[i]), ifac[s[i] - s[i - 1] - 1]));
printf ("%d\n", Mul(Ans, fac[n - 1]));
For (i, 1, m) {
int x, y; read(x); read(y);

if (y < n && !del[y]) if (a[y] < a[y + 1]) Era(y), del[y] = 1;
if (y > 1 && !del[y - 1]) if (a[y - 1] < a[y]) Era(y - 1), del[y - 1] = 1;
if (x < n && !del[x]) if (a[x] < a[x + 1]) Era(x), del[x] = 1;
if (x > 1 && !del[x - 1]) if (a[x - 1] < a[x]) Era(x - 1), del[x - 1] = 1;
swap(a[x], a[y]);
del[x] = del[y] = del[x - 1] = del[y - 1] = 0;
if (y < n && !del[y]) if (a[y] < a[y + 1]) Ins(y), del[y] = 1;
if (y > 1 && !del[y - 1]) if (a[y - 1] < a[y]) Ins(y - 1), del[y - 1] = 1;
if (x < n && !del[x]) if (a[x] < a[x + 1]) Ins(x), del[x] = 1;
if (x > 1 && !del[x - 1]) if (a[x - 1] < a[x]) Ins(x - 1), del[x - 1] = 1;
printf ("%d\n", Mul(Ans, fac[n - 1]));
del[x] = del[y] = del[x - 1] = del[y - 1] = 0;
}
}

# b

一张无向图,可能重边,每条路可黑白染色,构造方案使得每座城市连出的黑白差绝对值最大为 11

每个点度数为偶数的包暗示我们欧拉路

那对于一张所有点度数为偶数的图,拉一条欧拉路,路上点黑白染色,那不难发现起点是唯一可能破戒的,因为其他点度数为偶数,进来一次出去一次差为 00 ,而若欧拉路上有奇数条边,那我们起点就 GG 了,这种不能构造

若有奇数度数的点,新建虚点连上去,一样做就好,推荐一种好写的写法,使用了类似当前弧一样的东西。

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
/* ==============================
* Author : Odalys
*
* Blog : Odalys.xyz
*
* Mail : minyuenu@gmail.com
* =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 4e6 + 10;
struct edge {
int to, nxt, id;
} e[N << 1];
int head[N], cnt = 1;
inline void add (int u, int v, int Id) {
e[++cnt].to = v; e[cnt].nxt = head[u]; e[cnt].id = Id; head[u] = cnt;
}
int du[N];
int n, m;
int Ans[N << 1], vis[N << 1], edges;
void dfs (int u) {
for (int &i = head[u]; i; i = e[i].nxt) { // !
int v = e[i].to, j = i / 2;
if (vis[j]) continue;
vis[j] = 1; dfs(v); Ans[j]= (++edges) & 1;
}
}
int main() {
read(n); read(m);
For (i, 1, m) {
int u, v; read(u); read(v); add(u, v, i), add(v, u, i);
du[u]++, du[v]++;
}
int id = m;
For (i, 1, n) if (du[i] & 1) add(0, i, ++id), add(i, 0, id);
For (u, 0, n) {
edges = 0;
dfs(u);
if ( (edges & 1) && u ) return puts("-1"), 0;
}
For (u, 1, m) printf ("%d ", Ans[u]);
}



# c

一棵树,每个点带权,求每个点不在他到父亲的链上以及他子树内的所以点异或和最大值。

本场考试最简单的题了把,看懂就能切。

两个数异或最值 \to Trie 上跑跑

一堆数异或最值 \to 线性基

然后树上 dfsdfs ,跑到一个点时的线性基就是一边的答案,跑完一个点子树再将这个点加入线性基,正反都跑一遍即可。

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
/* ==============================
* Author : Odalys
*
* Blog : Odalys.xyz
*
* Mail : minyuenu@gmail.com
* =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
#define int long long
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
#define ll long long
const int N = 4e5 + 10;
const int L = 62;
vi to[N];
struct Linear_Basic {
ll a[L | 1];
inline void clear () {
memset (a, 0, sizeof a);
}
bool ins (ll t) {
foR (i, L, 0) {
if (t & (1ll << i)) {
if (a[i]) {t ^= a[i]; continue;}
For (j, 0, i - 1) if (t & (1ll << j) ) t ^= a[j];
For (j, i + 1, L) if ( a[j] & (1ll << j) ) a[j] ^= t;
a[i] = t;
return true;
}
}
return false;
}
} cur, l[100], r[100];
int ltot, rtot;
int n, qy, v[N];
ll Ans[100][100];
int idl[N], idr[N];
void dfs (int u, int fa) {
idl[u] = ltot;
int sz = to[u].size();
For (i, 0, sz - 1) {
int v = to[u][i];
if (v == fa) continue;
dfs(v, u);
}
if (cur.ins(v[u])) l[++ltot] = cur;
}


void sfd (int u, int fa) {
idr[u] = rtot;
int sz = to[u].size();
foR (i, sz - 1, 0) {
int v = to[u][i];
if (v == fa) continue;
sfd(v, u);
}
if (cur.ins(v[u])) r[++rtot] = cur;
}

signed main() {
read(n); For (i, 1, n) read(qy);
For (i, 1, n) read(v[i]);
For (i, 1, n - 1) {
int u, v; read(u); read(v);
to[u].pb(v), to[v].pb(u);
}
dfs(1, 0);
cur.clear();
sfd(1, 0);
For (i, 0, ltot) For (j, 0, rtot) {
cur.clear();
For (k, 0, L) cur.ins(l[i].a[k]), cur.ins(r[j].a[k]);
foR (k, L, 0) {
ll val = Ans[i][j] ^ cur.a[k];
ckmax(Ans[i][j], val);
}
}
For (i, 1, n) printf ("%lld\n", Ans[idl[i]][idr[i]]);
}

# D

会了

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝