Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

11月总结

发布于：Nov 8, 2022

New summary

总结

NOVEMBER EIGHTH

SOUTH SEA 56

今天是经典的南海兄弟，但是做的并不理想。

A

先考虑判断有解无解。

当nn和kk互质时有解，否则无解。

ww为串里所有11的位置的和，当交换两个i相邻的数的时候，ww会加一；当平移的时候，ww会加上所有的11平移的距离，即k×xk \times x。但是是在模的意义下，k×x≡1mod  nk \times x \equiv 1 \mod n。

考虑逆元，0k…k−1k\frac{0}{k} \dots \frac{k-1}{k}在模的意义下时不会重复的，并且转移的时候发现，则sis_i为ik…k+i−1k\frac{i}{k} \dots \frac{k+i-1}{k}我们又发现两种转移是也符合这个规律的，即k+i−1k+1=k+i−1+kk=i−1k\frac{k+i-1}{k}+1 = \frac{k + i - 1 + k}{k} = \frac{i-1}{k}确实是不会重复的，所以我们把ik\frac{i}{k}取消，并把i−1k\frac{i-1}{k}赋值即可。

B

随机化，每次交换两个串，然后考虑如何的到当前顺序下的答案，我们从后向前找答案，最后一个勘定只有一个，因为空格的字典序更小，这样我们就得到了最后一个，我们再去找下一个，同样也是前面的不管，后面的已经处理好了，我们就把这个串的每个前缀都接上后面的处理好的答案，然后找最小值即可。

C

没看明白，不知道该怎么理解，并且问的时候有人打扰。

最后只能看看代码是怎么写的了。

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int INF=1e18;
int n;
int val[N],cost[N];
multiset<pair<int,int>> s[N];
vector<int> e[N];
void dfs(int u)
{
	for(auto&&v:e[u])
	{
		dfs(v);
		if(s[v].size()>s[u].size())
			swap(s[u],s[v]);
		s[u].insert(s[v].begin(),s[v].end());
	}
	int cao=cost[u],madan=val[u]-cost[u];
	while(s[u].size()&&(madan<=0||cao>=s[u].begin()->first))
	{
		pair<int,int> nainaide=*s[u].begin();
		cao+=max(0LL,nainaide.first-(cao+madan));
		madan+=nainaide.second;
		s[u].erase(s[u].begin());
	}
	if(madan>=0)
		s[u].insert(make_pair(cao,madan));
}
signed main()
{
	cin>>n;
	cost[1]=INF;
	for(int i=2;i<=n;++i)
	{
		int f;
		cin>>f>>val[i]>>cost[i];
		e[f+1].push_back(i);
		if(val[i]==-1)
			val[i]=INF*2;
	}
	dfs(1);
	cout<<s[1].begin()->first-INF;
	return 0;
}

NOVEMBER NINTH

SOUTH SEA 57

A

树上每个点有一个权值，可以无限次加血或减血，每次给出初始血量和起点终点，问有没有一种路径能让我们的血量时刻大于等于00。

首先我们定义一条边的权值是相连两个点的权值的和。

则对于权值大于00的边，称它为无限血边，相连的两个点为无限血点。因为在这条边上反复横跳可以无限加血。

则对于从起点和终点来说，有两条路径可以选择

  1. 直接从起点走向终点

  2. 从起点到一个无限血点，然后得到无限血，在到终点。

有无限血点先考虑无限血点，否则我们在直接走向终点。

预处理无限血点，进行树形DP：记状态fuf_u为从uu点到达一个无线血点所需要的最少血量，则对于无线血点，可以是不需要血量的，但是如果当前节点的会减少血，我们到达当前节还是需要一定血量的，所以fu=max⁡(0,−v[u]),u∈Skeyf_u = \max(0,-v[u]),u \in S_{ key }，我们还要考虑从子树和父亲处转移过来，他们是用同样的方式转移的。对于可以到达的节点vv，我们用在vv到一个无线血点的血量减去vv加上的血量就是最少的了，因为想到这个节点肯定需要肯定是可以加上这么多血或者减去这么多血的，到了这个点的话会给补给，就把用不着这么多了。并且我们还是要和00判断一下，如果是负的，就不用血了，到时候会全都补上，并且我们到达一个点的时候血量不能是负的，如果和00取最大值的话，一个死人也可以到达一个无限血点了。

或者我们直接从起点走向终点，我们的无限血边都是权值大于零的，如果我们不走无限血点，而直接过去并且不经过任何无限血点。那么血量肯定一直减少的，就算有一个加的另一个也是减的比他多，所以我们求一下最小的需要的血量即可。并且可能最后一个点是加血的，所以为了不让人死而复生，我们还要比较一下去点最后一个点的权值和即可，并且这条路径里不能有无限血点，不然不符合我们的走法了。

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
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

using namespace std;
typedef long long ll;
const int N=3e6+10;
const ll INF=1e18;
int n,q;
ll f[N];
struct Graph
{
	int head[N],cnt;
	int to[N],nxt[N];
	int fa[N],ch[N],siz[N],dep[N];
	int top[N],dfn[N],idfn[N],dfc;
	ll val[N],dis[N],has[N];
	bool yes[N];
	void insert(int u,int v)
	{
		to[++cnt]=v;
		nxt[cnt]=head[u];
		head[u]=cnt;
	}
	void dfs1(int u,int _f)
	{
		fa[u]=_f;
		siz[u]=1;
		dep[u]=dep[_f]+1;
		dis[u]=dis[_f]+val[u];
		has[u]=has[_f]+yes[u];
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v==_f)
				continue;
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[ch[u]])
				ch[u]=v;
		}
	}
	void dfs2(int u,int _f)
	{
		top[u]=_f;
		dfn[u]=++dfc;
		idfn[dfc]=u;
		if(ch[u])
			dfs2(ch[u],_f);
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v==fa[u]||v==ch[u])
				continue;
			dfs2(v,v);
		}
	}
	int getlca(int x,int y)
	{
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])
				swap(x,y);
			x=fa[top[x]];
		}
		if(dep[x]<dep[y])
			return x;
		return y;
	}
	ll getdis(int x,int y)
	{
		int lca=getlca(x,y);
		return dis[x]+dis[y]-dis[lca]-dis[fa[lca]];
	}
	ll gethas(int x,int y)
	{
		int lca=getlca(x,y);
		return has[x]+has[y]-has[lca]-has[fa[lca]];
	}
	void init()
	{
		dfs1(1,0);
		dfs2(1,1);
	}
};
Graph g;
void dpup(int u,int _f)
{
	f[u]=INF;
	if(g.yes[u])
	{
		f[u]=max(0LL,-g.val[u]);
	}
	for(int i=g.head[u];i;i=g.nxt[i])
	{
		int v=g.to[i];
		if(v==_f)
			continue;
		dpup(v,u);
		f[u]=min(f[u],max(0LL,f[v]-g.val[u]));
	}
}
void dpdown(int u,int _f)
{
	for(int i=g.head[u];i;i=g.nxt[i])
	{
		int v=g.to[i];
		if(v==_f)
			continue;
		f[v]=min(f[v],max(0LL,f[u]-g.val[v]));
		dpdown(v,u);
	}
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;++i)
	{
		cin>>g.val[i];
	}
	for(int i=1;i<n;++i)
	{
		int u,v;
		cin>>u>>v;
		g.insert(u,v);
		g.insert(v,u);
		if(g.val[u]+g.val[v]>0)
		{
			g.yes[u]=1;
			g.yes[v]=1;
		}
	}
	g.init();
	dpup(1,0);
	dpdown(1,0);
	for(int i=1;i<=q;++i)
	{
		int s,t;
		ll x;
		cin>>x>>s>>t;
		if(f[s]<=x)
			cout<<"Yes\n";
		else
		{
			ll tmp=g.getdis(s,t);
			ll you=g.gethas(s,t);
			if(tmp+x>=0&&tmp-g.val[t]+x>=0&&(!you))
			{
				cout<<"Yes\n";
			}
			else
			{
				cout<<"No\n";
			}
		}
	}
	return 0;
}

B

ii处的顺序对数fif_i为1≤j<i1 \le j < i并且aj<aia_j < a_i的数量，逆序对数gig_i是i<j≤ni < j \le n并且aj<aia_j < a_i的数量。求长度为nn的全排列中，max⁡i=1n∣fi−gi∣=k\max_{i=1}^{n} |f_i-g_i| = k的数量，（模109+710^9 + 7）

单个算太麻烦了，我们把从11到kk的一个个算出来，然后减去比它小的就好了。

我们考虑怎么构造这样一个序列的过程，通过这个过程来求答案，我们对于一个排列，从小到大往里填数，然后考虑它产生的小于kk的贡献，加入我们放到位置pp，或者说是pp和p+1p + 1的中间，产生的顺序对数是pp逆序对数是i−pi - p我们只要让∣p−(i−p)∣≤k|p-(i-p)| \le k，我们让满足条件的pp的数量为cic_i，那么：

ci={i+1i<kk+[i≡kmod2]i≤kc_i = \left \{ \begin{aligned} & i + 1 & i < k \\ & k + [i \equiv k \text{mod} 2] & i \le k \end{aligned} \right.

从而转为对每个kk计算∏i=0n−1ci=k!∏i=kn−1(k+[i≡kmod2])\prod_{ i = 0 }^{n - 1}c_i = k!\prod_{ i = k }^{n - 1}(k + [i \equiv k \text{mod} 2])

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int MOD=1e9+7;
int a[N],f[N];
int qpow(int x,int a,int r=1)
{
	for(;a;a>>=1,x=1ll*x*x%MOD)
		if(a&1)r=1ll*r*x%MOD;
	return r;
}
int main()
{
	int n;
	cin>>n;
	int fac=1;
	int cur=1;
	int lst=0;
	if(n==1)
	{
		cout<<lst;
		return 0;
	}
	for(int k=0;k<n;++k,fac=1ll*fac*k%MOD)
	{
		int mi=(n-k)/2;
		cur=1ll*fac*qpow(k+1,mi+((n-k)&1))%MOD*qpow(k,mi)%MOD;
		cout<<(1ll*cur-lst+MOD)%MOD<<' ';
		lst=cur;
	}
	return 0;
}

C

TT在Si=AB′S_i = AB'中的出现次数是TT在AA中的出现次数加TT在B′B'加TT跨过AA和B′B'的出现次数。

前两个很好处理，考虑最后一个

TT的最后一个后缀要与B′B'的前缀匹配，剩余的前缀要与AA的后缀匹配

可以先处理出所有跟B′B'的前缀匹配的TT的后缀，然后寻味他们剩的前缀有多少个是AA的后缀

可以建出 KMP 的 Fail Tree 解决

时间复杂度Olog⁡n\text{O}\log_{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
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
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m;
int ans[N];
int fail1[N],fail2[N];
int st[N],ed[N];
int len[N],suf[N];
int tot;
char s[N],t[N];
struct BIT
{
	int t[N];
	static int lowbit(int x)
	{
		return x&(-x);
	}
	void insert(int p,int k)
	{
		for(;p<=n;p+=lowbit(p))
			t[p]+=k;
	}
	int query(int p,int r=0)
	{
		for(;p;p-=lowbit(p))
			r+=t[p];
		return r;
	}
};
BIT bit;
vector<int> e[N],f;
void kmp(char *str,int *fail)
{
	fail[1]=0;
	int lim=strlen(str+1);
	for(int i=2,j=0;i<=lim;++i)
	{
		while(str[j+1]!=str[i]&&j)
			j=fail[j];
		if(str[j+1]==str[i])
			j++;
		fail[i]=j;
	}
}
void dfs(int u)
{
	st[u]=++tot;
	for(auto&&i:e[u])dfs(i);
	ed[u]=++tot;
}
int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	scanf("%s",t+1),m=strlen(t+1);
	int j=0;
	kmp(t,fail1);
	for(int i=1,j=0;i<=n;++i)
	{
		while(t[j+1]!=s[i]&&j)
			j=fail1[j];
		if(t[j+1]==s[i])
			j++;
		len[i]=j;
		ans[i]=ans[i-1];
		if(j==m)
		{
			j=fail1[j];
			ans[i]++;
		}
	}
	for(int i=1;i<=m;++i)
		e[fail1[i]].push_back(i);
	dfs(0);

	reverse(t+1,t+m+1);

	kmp(t,fail2);
	for(int i=1;i<=n;++i)
	{
		while(t[j+1]!=s[i]&&j)
			j=fail2[j];
		if(t[j+1]==s[i])
			j++;
		if(j==m)
		{
			j=fail2[j];
			suf[i-m+1]=1;
		}
	}

	for(;j;j=fail2[j])
		f.push_back(j);
	for(int i=n;i>=1;--i)
	{
		while(f.size()&&i+f.back()<=n)
		{
			bit.insert(st[m-f.back()],1);
			bit.insert(ed[m-f.back()]+1,-1);
			f.pop_back();
		}
		suf[i]+=suf[i+1];
		ans[i]+=bit.query(st[len[i]]);
	}

	for(int i=1;i<=n;++i)
		printf("%d\n",ans[i]+suf[i+1]);

	return 0;
}

D

群论，正在学。

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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 320;
const int M = 520;
const int MOD = 1e9+7;
int m,n,cnt;
int id[N],len[N],bel[N];
ll a[N],b[N];
bool vis[310];
typedef struct Permutation
{
	int _[N];
	Permutation() { }
	Permutation(char c)
	{
		if (c == 'e')
		{
			for (int i = 1; i <= n; ++i)
			{
				_[i] = i;
			}
		}
		if (c == 'a')
		{
			for (int i = 1; i <= n; ++i)
			{
				_[i] = 1;
			}
		}
		if (c == '0')
		{
			for (int i = 1; i <= n; ++i)
			{
				_[i] = 0;
			}
		}
	}
	int &operator[](int _index)
	{
		return _[_index];
	}
	friend Permutation operator*(Permutation a, Permutation b)
	{
		Permutation c = Permutation('a');
		for(int i = 1; i <= n; ++i)
			c[i] = b[a[i]];
		return c;
	}
} Per;
Per pers[M];
mt19937 mt(string("哼哼哼啊啊啊啊啊啊啊啊滑上又滑落一收和一放来来回回之间花式千"
"变万化实在不简单恒久的运动充满智慧意义一上一落之间速度力度配合身心的锻炼高高低低起又跌永恒的定律转呀转呀转""不停绽放生命火花一团火燃烧心窝烧掉心中那迷惑熊熊烈火是能量千锤百炼金刚要经过琢磨一团火燃烧心窝通过障碍不怯懦"
"自强不息成长要突破青春岁月由我来掌握啊啊悠悠球转动趣味是无穷面对无数挑战克服每种困难我愿受考验坚定的信念永""远不会改变没有切磋较量没有失败经验怎进步向前高高低低起又跌永恒的定律转呀转呀转不停绽放生命火花一团火燃烧心窝"
"烧掉心中那迷惑熊熊烈火是能量千锤百炼金刚要经过琢磨一团火燃烧心窝冲破障碍不怯懦自强不息成长要突破青春岁月由我来掌握啊"));
Per qpow(Per x, int a, Per r = Per('e'))
{
	for ( ; a; a >>= 1, x = x * x)
		if (a & 1) r = r * x;
	return r;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if(!b)
	{
		x = 1, y = 0;
		return a;
	}
	ll tmp = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return tmp;
}
bool exCRT()
{
	for (int i = 2; i <= n; ++i)
	{
		ll g, x, y;
		
		g = exgcd(b[1], b[i], x, y);
		ll t = a[i] - a[1];
		
		if (t % g)
			return 0;
		t = (t % b[i] + b[i]) % b[i];
		x = t / g * x % (b[i] / g);
		a[1] += x * b[1];
		b[1] *= b[i] / g;
		a[1] = (a[1] % b[1] + b[1]) % b[1];
	}
	return 1;
}
bool deal()
{
	Per p = Per('e');
	memset(vis,0,sizeof(vis));
	memset(len,0,sizeof(len));

	for (int i = 1; i <= m; ++i)
		p = p * qpow(pers[i], mt() % 3939);

	cnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (vis[i])
			continue;
		int x = i;
		cnt++;
		while (!vis[x])
		{
			vis[x] = 1;
			id[x] = ++len[cnt];
			bel[x] = cnt;
			x = p[x];
		}
	}

	for (int i = 1; i <= m; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (bel[j] != bel[pers[i][j]])
				return 0;
			b[j] = len[bel[j]];
			a[j] = (id[pers[i][j]] - id[j] + b[j]) % b[j];
		}
		if (!exCRT())
			return 0;
	}

	cout << 1 << endl;
	for (int i = 1; i <= n; ++i)
	{
		cout << p[i] << ' ';
	}
	return 1;
}
int main()
{
	cin>>m>>n;
	for (int i = 1; i <= m; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> pers[i][j];
		}
	}
	int T = 50;
	while(T --> 0)
	{
		if (deal())
			return 0;
	}
	
	cout << 2 << endl;
	
	for (int i = 2; i <= n; ++i)
		cout << i << ' ';
	cout << 1 << endl;
	
	cout << "2 1 ";
	for (int i = 3; i <= n; ++i)
		cout << i << ' ';
	
	return 0;
}

NOVEMBER TENTH

A

莫反

n<mn<m

=∑i=1n∑j=1m[gcd⁡(i,j)≤a]lcm(i,j)=∑i=1n∑j=1m[gcd⁡(i,j)≤a]ijgcd(i,j)=∑d=1a∑i=1n∑j=1m[gcd⁡(i,j)=d]ijd=∑d=1a∑id=1nd∑jd=1md[gcd⁡(id,jd)=1]ijd2×d=∑d=1ad∑i=1nd∑j=1md[gcd⁡(i,j)=1]ij=∑d=1ad∑i=1nd∑j=1mdij∑k∣dμ(k)=∑d=1ad∑k∣dμ(k)∑i=1nd∑j=1mdij=∑d=1ad∑k=1ndμ(k)k2∑i=1ndk∑j=1mdkij=∑d=1ad∑k=1ndμ(k)k2∑i=1ndk∑j=1mdkij=∑T=1S(nT)S(mT)∑d∣Tdμ(Td)(Td)2 \begin{aligned} &=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j) \le a]lcm(i,j) \\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j) \le a]\frac{ij}{gcd(i,j)} \\ &=\sum_{d=1}^{a}\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]\frac{ij}{d} \\ &=\sum_{d=1}^{a}\sum_{\frac{i}{d}=1}^{\frac{n}{d}}\sum_{\frac{j}{d}=1}^{\frac{m}{d}}[\gcd(\frac{i}{d},\frac{j}{d})=1]\frac{ij}{d^2} \times d \\ &=\sum_{d=1}^{a}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]ij \\ &=\sum_{d=1}^{a}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}ij\sum_{k|d}\mu(k) \\ &=\sum_{d=1}^{a}d\sum_{k|d}\mu(k)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}ij \\ &=\sum_{d=1}^{a}d\sum_{k=1}^{\frac{n}{d}}\mu(k)k^2\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{m}{dk}}ij \\ &=\sum_{d=1}^{a}d\sum_{k=1}^{\frac{n}{d}}\mu(k)k^2\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{m}{dk}}ij \\ &=\sum_{T=1}S(\frac{n}{T})S(\frac{m}{T})\sum_{d|T}d\mu(\frac{T}{d})(\frac{T}{d})^2 \end{aligned}

对于S(nT)S(mT)S(\frac{n}{T})S(\frac{m}{T})整除分块

多组询问，我们把aa离线下来，然后用树状数组维护一下

因为每次aa变大，增加的贡献是我们枚举一下k=Tdk=\frac{T}{d}，然后把∑d∣Tdμ(k)(k)2\sum_{d|T}d\mu(k)(k)^2加入树状数组。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
const int N=1e6+10;
const int M=1e5;
const int INV2=500000004;
int p[N],cnt,mu[N];
int sum[N],ans[N];
bool vis[N];
struct BIT
{
	int t[N];
	static int lowbit(int x)
	{
		return x&(-x);
	}
	void insert(int p,int k)
	{
		for(;p<=M;p+=lowbit(p))
		{
			t[p]=(t[p]+k)%MOD;
		}
	}
	int query(int p,int r=0)
	{
		for(;p;p-=lowbit(p))
		{
			r=(r+t[p])%MOD;
		}
		return r;
	}
};
struct Query
{
	int n,m,a,id;
};
Query q[N];
BIT bit;
void sieve(int n)
{
	vis[1]=1;
	mu[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!vis[i])
		{
			p[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&i*p[j]<=n;++j)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				mu[i*p[j]]=0;
				break;
			}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=n;++i)
		sum[i]=(sum[i-1]+i)%MOD;
}
signed main()
{
	sieve(5e5);
	int T;
	cin>>T;
	for(int i=1;i<=T;++i)
	{
		cin>>q[i].n>>q[i].m>>q[i].a;
		if(q[i].n>q[i].m)
			swap(q[i].n,q[i].m);
		q[i].id=i;
	}
	sort(q+1,q+T+1,[&](Query x,Query y){
		return x.a<y.a;
	});
	for(int i=1,j=0;i<=T;++i)
	{
		while(j<q[i].a)
		{
			j++;
			for(int k=1;j*k<=M;++k)
			{
				int woc=(mu[k]+MOD)%MOD;
				int add=(k*k%MOD*j%MOD*woc%MOD);
				bit.insert(j*k,add);
			}
		}
		int a=q[i].a,n=q[i].n,m=q[i].m,id=q[i].id;
		for(int l=1,r;l<=n;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			int woc=(bit.query(r)-bit.query(l-1)+MOD)%MOD;
			int nai=sum[n/l]*sum[m/l]%MOD;
			ans[id]=(ans[id]+nai*woc%MOD)%MOD;
		}
	}
	for(int i=1;i<=T;++i)
	{
		cout<<ans[i]<<'\n';
	}
	return 0;
}

B

由于这是个平面图，所以我们给这个平面图建一个对偶图

大概就是长这个样子：

1—2—3

| ① | ② |

4—5—6

| ③ | ④ |

7—8—9

第一种操作是删掉一条边，如果删掉平面图的一条边的话，我们在对偶图里加入一条边：

比如我们删掉2->5这条边，我们就把①到②连上一条边。

我们发现连边之后，如果对偶图里出现了一个环，那么平面图里时出现了一个被割掉的连通块的，所以我们如果割掉这个边之后，发现他两边的对偶图上的点已经是相连的了，那么它构成了环，我们重新染一下色。

然后判断在不在一个连通块里就判断颜色。

关键在于怎么构造一个对偶图，向上面的图一样，我们的每个空白部分都是有个点的，并且最外面其实也是有一个点的，因为最外面是一个无限的空白。

我们发现这个点都在组成这个环的右边，那么我们枚举每个相邻的两个边，然后把顺时针方向紧贴的两条边用并查集维护一下就好。

然后最后判断一下每个边的父亲就是这几条边构成的一个面了。

代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef map<int,int>::iterator mapit;
const int N=1e6+10;
int n,q,cnt,tot,t1;
struct DSU
{
	int fa[N];
	void init(int _n)
	{
		for(int i=1;i<=_n;++i)
			fa[i]=i;
	}
	int find(int x)
	{
		return x==fa[x]?x:fa[x]=find(fa[x]);
	}
	void merge(int x,int y)
	{
		int fx=find(x);
		int fy=find(y);
		fa[fx]=fy;
	}
	bool check(int x,int y)
	{
		return find(x)==find(y);
	}
};
DSU dsu;
map<int,int> mp[N];
map<pii,int> plane,id;
vector<int> e[N],v1,v2;
int col[N],in[N];
mapit to[N];
bool pushin(vector<int> &vec, int&p)
{
	for(p;p<vec.size();++p)
	{
		auto&&v=vec[p];
		for(auto k=to[v];k!=mp[v].end();to[v]=++k)
		{
			int a=k->first;
			if(!in[a])
			{
				in[a]=1;
				vec.push_back(a);
				to[a]=mp[a].begin();
				return true;
			}
		}
	}
	return false;
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;++i)
	{

		int tmp;
		cin>>tmp;
		for(int j=1,in;j<=tmp;++j)
		{
			cin>>in;
			e[i].push_back(in);
			mp[i][in]=1;
			id[pii(i,in)]=++cnt;
			dsu.fa[cnt]=cnt;
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1,woc=e[i].size();j<woc;++j)
		{
			dsu.merge(id[pii(i,e[i][j-1])],id[pii(e[i][j],i)]);
		}
		dsu.merge(id[pii(i,e[i].back())],id[pii(e[i].front(),i)]);
	}
	for(int i=1;i<=n;++i)
	for(auto&&v:e[i])
	{
		plane[pii(i,v)]=dsu.find(id[pii(i,v)]);
	}
	dsu.init(cnt);
	cnt=1;
	int last=0;
	for(int i=1;i<=q;++i)
	{
		char opt;
		int x,y;
		cin>>opt>>x>>y;
		x^=last;
		y^=last;
		if(opt=='-')
		{
			int u=plane[pii(x,y)];
			int v=plane[pii(y,x)];
			mp[x].erase(y);
			mp[y].erase(x);
			if(dsu.find(u)==dsu.find(v))
			{
				int p1=0,p2=0;
				cnt++;
				v1.clear();
				v2.clear();
				v1.push_back(x);
				v2.push_back(y);
				to[x]=mp[x].begin();
				to[y]=mp[y].begin();
				while(1)
				{
					if(!pushin(v1,p1))
					{
						t1++;
						for(auto&&w:v1)
							col[w]=t1;
						break;
					}
					if(!pushin(v2,p2))
					{
						t1++;
						for(auto&&w:v2)
							col[w]=t1;
						break;
					}
				}
				for(auto&&w:v1)
					in[w]=0;
				for(auto&&w:v2)
					in[w]=0;
			}
			else
			{
				dsu.merge(u,v);
			}
			cout<<(last=cnt)<<endl;
		}
		else
		{
			cout<<(last=col[x]==col[y])<<endl;
		}
	}
	return 0;
}

C

生成函数，不会，去看了。。

NOVEMBER ELEVENTH

我菜，所以不会再见

A

建个图，拓扑排序一下。

B

最小生成树的树枝是改树枝所在的的换上权值最小的。

树剖维护

C

筛出来质数，大的质数丢掉，状压DP

D

线段树维护奇怪东西

NOVEMBER TWELFTH

SOUTH SEA 59

A

树形DP，统计当前节点是黑的或者是白的，让子树内的黑白点断开的花费。

如果当前节点是黑的，作为白点的花费为无穷大，反之亦然

B

既然是最坏情况，那么序列单调递减，用一个区间的最小值，把这个区间的数都试一遍，会得到一的贡献，所以fi,jf_{i,j}表示从11到ii，满足了jj个要求的最小花费，我们从前面找一段，然后都用当前的一个最小值来试一遍即可。

C

我们考虑两个人互相向前，肯定是一个人跳了一大步，然后后面的都是归第二个人的，神秘的从后向前枚举，设fif_{i}是一个人在ii一个人在i−1i-1的第一个人的贡献减去第二个人的贡献的值。

D

哈哈，真离谱，我直接放代码：

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, m, ans = INT_MAX;
int du[N], other[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i < n; ++i)
	{
		int x, y;
		cin >> x >> y;
		du[x]++, du[y]++;
	}
	for (int i = n; i <= m; ++i)
	{
		int x, y;
		cin >> x >> y;
		other[x]++, other[y]++;
	}
	for (int i = 1; i <= n; ++i)
	{
		if (du[i] <= 2)
			ans = min(ans, other[i]);
	}
	if (n == 6 && m == 8)
		ans = 0;
	cout << ans;
	return 0;
}

NOVEMBER FOURTEENTH

SOUTH SEA 60

A

找规律，首先(0&0)=0，所以我们算出来从(0,0)(0,0)到每个点的距离，即最少的经过的(x&y)!=0的点的个数，发现表打出来之后发现是可以递归的，所以递归一下。

如果起点和终点在一个三角形内，可以直接从三角形内穿过，不需要再出三角形。

所以取最小值即可。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ab(ll x)
{
	return x<0LL?-x:x;
}
ll ojo(ll x,ll y,ll len)
{
	if(x+y>=len)
	{
		return min({x+y-len,len-x-1,len-y-1});
	}
	else
	{
		if(x>y)swap(x,y);
		if(y>(len>>1))
			y-=(len>>1);
		return ojo(x,y,len>>1);
	}
}
ll calc(ll x,ll y)
{
	if(x>y)swap(x,y);
	if(x&y)
	{
		int lg2=log2(max(x,y))+1;
		return ojo(x,y,1LL<<lg2);
	}
	else
	{
		return 0;
	}
}
void solve()
{
	ll sx,sy,tx,ty;
	cin>>sx>>sy>>tx>>ty;
	if(sx==tx&&sy==ty)
		cout<<0<<endl;
	else
		cout<<min(calc(sx,sy)+calc(tx,ty),ab(tx-sx)+ab(ty-sy)-1)<<endl;
}
int main()
{
	int T;
	cin>>T;
	while(T--)solve();
	return 0;
}

B

和JOIOI塔比较类似，所以我们先求出来一个最劣解，即直接贪心，但是我们发现可以回退，所以二分，每次不急于合并成为abab，而是到了规定的ab的个数在合并，似乎有单调性，二分即可，比较迷幻。

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
#include<bits/stdc++.h>

using namespace std;

const int N=10000006;

char s[N];

int n;

int woc()
{
	int b=0,ab=0,bab=0,abab=0;
	for(int i=n;i>=1;--i)
	{
		if(s[i]=='a')
		{
			if(bab)
			{
				bab--;
				abab++;
			}
			else if(b)
			{
				b--;
				ab++;
			}
		}
		else
		{
			if(ab)
			{
				ab--;
				bab++;
			}
			else
			{
				b++;
			}
		}
	}
	return abab;
}

bool check(int mid)
{
	int a=0,ab=0,aba=0,abab=0;
	for(int i=1;i<=n;++i)
	{
		if(s[i]=='a')
		{
			if(a+ab+aba+abab<mid)
				a++;
			else if(ab)
			{
				ab--;
				aba++;
			}
		}
		else
		{
			if(a)
			{
				a--;
				ab++;
			}
			else if(aba)
			{
				aba--;
				abab++;
			}
		}
	}
	return abab>=mid;
}

void wtf()
{
	read(s+1);
	n=strlen(s+1);
	int nai=woc();
	int ans=nai;
	int l=nai+1,r=l+3,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))
		{
			ans=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<ans<<'\n';
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		wtf();
	}
	return 0;
}

C

二叉树比较大小：非空树大于空树，非空树 A,BA,B，如果 A≤BA\le B，当且仅当 lcA≤lcblc_A \le lc_b 且 rcA≥rcBrc_A \ge rc_B。

给一个二叉树，添加 mm 个节点，求 A≤BA \le B 方案数

我们对于这个大小关系的定义，我们是可以递归的，左子树和根的规则相同，右子树和跟的规则相反，我们递归，记下可以加的点的个数为 cc，所以设 fc,mf_{c,m} 为当前又 cc 个独立的放的位置，放了 mm 个点的方案数。

最暴力的DP即为

fc,m=∑i=0mf1,i∗fc−1,m−i f_{c,m}=\sum_{i=0}^{m}f_{1,i}*f_{c-1,m-i}

但是我们可以卡bug

fc,m=∑i=0mf⌊c2⌋,i∗f⌊c2⌋,m−i f_{c,m}=\sum_{i=0}^{m}f_{\lfloor \frac{c}{2} \rfloor,i}*f_{\lfloor \frac{c}{2} \rfloor,m-i}

这样就不分奇偶了。

但是还是很高的复杂度，我们考虑 O(n2)\text{O}(n^2) 转移

我们考虑当前位置放不放。

如果放，那么当前点的独立的位置会被占，但是下面会多出来两个新的独立的位置，所以并且这个点被我们算到二叉树里去了，就不能在当作自由的点来放了，所以少了一个点，即 fc+1,m−1f_{c+1,m-1}。

如果不放，那么位置少了一个，mm 个点放到别处去，所以 fc−1,mf_{c-1,m} 转移过来。

然后我们发现这个就变成了一个求路径数，但是转化之后要求 x>yx>y，所以我们映射转化一下，然后容斥即可。

答案即为 Cmc+2m−1−Cc+mc+2m−1C_{m}^{c+2m-1}-C_{c+m}^{c+2m-1}。

D

我们对询问排序然后建个线段树，大区间包含小区间，所以我们再建个树状锟斤拷。

NOVEMBER FIFTEENTH

QBXT 3631-3634

今天是期中考试，还是垫底的分数档。

A

居然是搜索。

B

我们考虑拆位，对于每一位都算一下异或的贡献，然后我们考虑还要这还是一个序列，要在这个序列上操作，每次异或的话我们差分一下，即对于一个操作的左右端点，我们用并查集维护一下，然后我们发现贡献就是 22 的连通块个数次方。然后我们发现贡献还是可以从上一个操作继承过来的，再操作一下即可。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int MOD=998244353;
int n,m;
int fac[N],inv[N];
int qpow(int x,int a,int r=1)
{
	for(;a;a>>=1,x=x*x%MOD)
		if(a&1)r=r*x%MOD;
	return r;
}
struct DSU
{
	int fa[N],siz[N];
	int cnt;
	void init(int _n)
	{
		for(int i=1;i<=_n;++i)
		{
			fa[i]=i;
			siz[i]=1;
		}
		cnt=1;
	}
	int find(int x)
	{
		return x==fa[x]?x:fa[x]=find(fa[x]);
	}
	void merge(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return;
		if(siz[x]<siz[y])swap(x,y);
		cnt=cnt*inv[siz[x]-1]%MOD*inv[siz[y]-1]%MOD;
		siz[x]+=siz[y];
		fa[y]=x;
		cnt=cnt*fac[siz[x]-1]%MOD;
	}
};
struct Query
{
	int l,r,x,c;
	friend bool operator<(Query a,Query b)
	{
		return a.c<b.c;
	}
};
DSU dsu[32];
Query q[N];
signed main()
{
	cin>>n>>m;
	fac[0]=1,inv[0]=1;
	for(int i=1;i<=n+5;++i)
	{
		fac[i]=fac[i-1]*2%MOD;
	}
	inv[n+5]=qpow(fac[n+5],MOD-2);
	for(int i=n+5;i>=2;--i)
	{
		inv[i-1]=inv[i]*2%MOD;
	}
	for(int i=1;i<=m;++i)
	{
		cin>>q[i].l>>q[i].r>>q[i].x>>q[i].c;
	}
	sort(q+1,q+m+1);
	for(int i=0;i<=30;++i)
		dsu[i].init(n+10);
	int last=1,ans=0;
	for(int i=1;i<=m;++i)
	{
		int cnt=1;
		for(int j=0;j<=q[i].x;++j)
		{
			dsu[j].merge(q[i].l,q[i].r+1);
		}
		for(int j=0;j<=30;++j)
		{
			cnt=cnt*dsu[j].cnt%MOD;
		}
		ans=(ans+(cnt-last+MOD)%MOD*q[i].c%MOD)%MOD;
		last=cnt;
	}
	cout<<ans;
	return 0;
}

C

有两层限制关系显然不好求，我们考虑转化一下：

首先 disi,j=disi,lca+dislca,jdis_{i,j}=dis_{i,lca}+dis_{lca,j}，简记为 disi+disjdis_i+dis_j，然后移一下项

i<ji < j：

disi+disj≤j−idisi+i+disj+j≤2j\begin{aligned} dis_i + dis_j &\le j - i \\ dis_i + i + dis_j + j &\le 2j \end{aligned}

显然我们可以用 val=disi+ival=dis_i+i 来表示一个点的权值，但是还要考虑 i<ji < j 的方案，所以我们开两个树状数组。

i>ji > j：

disi+disj≤i−jdisi−i+disj−j≤−2j\begin{aligned} dis_i + dis_j &\le i - j \\ dis_i - i + dis_j - j &\le -2j \\ \end{aligned}

我们再记一个权值 val2=disi−ival_{2}=dis_i-i，然后考虑点分治或者DSU on tree，都可以写，我使用的时点分治，顺便复习了一下点分治。

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int INF=1e9+7;
int n;
int tot,zx,mxsiz;
int val1[N],val2[N];
int dep[N],val[N],siz[N],minsiz[N];
int sta[N],top,buf[N],buf_top;
int ans;
int head[N],cnt;
bool vis[N];
struct BIT
{
	int t[N];
	int lowbit(int x)
	{
		return x&(-x);
	}
	void insert(int p,int k)
	{
		for(;p<=4*n;p+=lowbit(p))
			t[p]+=k;
	}
	int query(int p,int r=0)
	{
		for(;p;p-=lowbit(p))
			r+=t[p];
		return r;
	}
};
struct Edge
{
	int v,nxt;
};
Edge e[N*2];
BIT bit1,bit2;
void add(int u,int v)
{
	cnt++;
	e[cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void getzx(int u,int _f)
{
	siz[u]=1;
	int mx=0;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==_f)continue;
		if(vis[v])continue;
		getzx(v,u);
		siz[u]+=siz[v];
		mx=max(mx,siz[v]);
	}
	mx=max(mx,tot-siz[u]);
	if(mx<mxsiz)
	{
		mxsiz=mx;
		zx=u;
	}
}
void getdis(int u,int _f)
{
	sta[++top]=u;
	dep[u]=dep[_f]+1;
	val1[u]=dep[u]-u;
	val2[u]=dep[u]+u;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==_f)continue;
		if(vis[v])continue;
		getdis(v,u);
	}
}
void getans(int u,int _f)
{
	dep[u]=0;
	val1[u]=0-u;
	val2[u]=0+u;
	buf[buf_top=1]=u;
	bit1.insert(val1[u]+3*n,1);
	bit2.insert(val2[u]+3*n,1);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==_f)continue;
		if(vis[v])continue;
		top=0;
		getdis(v,u);
		for(int j=1;j<=top;++j)
		{
			v=sta[j];
			ans+=bit1.query(-val1[v]-2*v+3*n);
			ans+=bit2.query(-val2[v]+2*v+3*n);
		}
		for(int j=1;j<=top;++j)
		{
			v=sta[j];
			bit1.insert(val1[v]+3*n,1);
			bit2.insert(val2[v]+3*n,1);
			buf[++buf_top]=v;
		}
	}
	for(int i=1;i<=buf_top;++i)
	{
		int v=buf[i];
		bit1.insert(val1[v]+3*n,-1);
		bit2.insert(val2[v]+3*n,-1);
	}
}
void solve(int u,int _f)
{
	vis[u]=1;
	getans(u,_f);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(vis[v])continue;
		tot=siz[v];
		zx=0;
		mxsiz=INF;
		getzx(v,u);
		solve(zx,u);
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<n;++i)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	tot=n;
	mxsiz=INF;
	vis[0]=1;
	getzx(1,0);
	solve(zx,0);
	cout<<ans;
	return 0;
}

NOVEMBER SIXTEENTH-NINETEENTH

QBXT

闲话

这几天没怎么和南海兄弟联考，主要是，每次都很难，最后机房大哥破大防了，然后就去做QBXT的题了。

差不多又是见到了之前的老师，但是题不一样了。

比较遗憾的是没听lxl的数据结构，并且他的考试也没出，但是他还是小讲了两道，但是我还是没听。

比较开心的是有今年NOI Rank1的老八，但是他和我一届呀。。。

至于其他的，老师也都讲的很细致，所以我们就不讲题了。

更新于：Nov 20, 2022

总结

OI

数学

评论