MinamiMelon
0%

发表于 分类于

这是基于 Hexo 框架和 NexT.Gemini 主题的个人博客简易使用指南。

1. 常用命令概览

在 PowerShell 或终端中执行以下命令进行日常维护：

命令 说明
npx hexo new post "标题" 新建一篇博文（位于 source/_posts/）
npx hexo s 启动本地服务器预览 (http://localhost:4000)
npx hexo clean 清除缓存和已生成的静态文件
npx hexo g 生成静态 HTML 文件
npx hexo d 部署静态文件到 GitHub Pages

2. 推荐发布流程

为了确保部署后的文件是最新的，推荐按顺序执行： 

1
npx hexo clean; npx hexo g -d

3. 环境注意事项

  • Markdown 渲染：由于博客使用了 hexo-renderer-pandoc 插件，系统必须安装 Pandoc 才能正常编译。
  • Git 身份：本地已配置该项目的提交身份为 minamimelon。
  • 资源引用：若需在文章中引用图片，建议在 source/images/ 目录下存放，或启用 post_asset_folder。

4. 常见问题处理

  • 样式未生效：执行 npx hexo clean 后重新生成。
  • 渲染报错：检查 Markdown 语法，尤其是 LaTeX 数学公式或 Pandoc 特有的语法。

祝写作愉快！

发表于 更新于 分类于

像 Nvidia P40、P4、P100 或 M40 等服务器计算卡没有内置风扇，一般在无风道的情况下会外加在尾部的风扇以解决散热。对这个风扇的调速，可以看到手动使用调速线、拆开显卡在核心附近安装热电偶获取温度然后用电路控制风扇转速的方案。

然而，系统可以获取显卡的温度，同时也可以控制PWM输出控制风扇转速。因此一定存在软件的解决方案控制风扇转速。解决方案如下。

首先安装 fancontrol，大部分发行版的包管理工具中有此软件。

其控制温度的脚本如下（省略了硬件信息）。FCTEMPS 处是可以填绝对路径的，这里填/home/gputemp

1
2
3
4
5
6
7
8
9
10
...
FCTEMPS=hwmon4/pwm2=/home/gputemp
FCFANS=hwmon4/pwm2=hwmon4/fan2_input 
MINTEMP=hwmon4/pwm2=35 
MAXTEMP=hwmon4/pwm2=65 
MINSTART=hwmon4/pwm2=120 
MINSTOP=hwmon4/pwm2=20 
MINPWM=hwmon4/pwm2=20 
MAXPWM=hwmon4/pwm2=255 
AVERAGE=hwmon4/pwm2=2

我们接下来用一个service 向/home/gputemp 循环写温度。 其systemd 脚本如下。写好后放置到正确位置，并设置enable 开启启动。

1
2
3
4
5
6
7
8
9
10
[Unit]
Description=Write GPU temperature to file

[Service]
ExecStart=sh -c 'echo $(nvidia-smi --query-gpu=temperature.gpu --format=csv,noheader | tail -n 1)000 > /home/gputemp'
Restart=always
RestartSec=10

[Install]
WantedBy=multi-user.target

另，实际上

1
<(echo $(nvidia-smi --query-gpu=temperature.gpu --format=csv,noheader | tail -n 1)000)

可以将直接转为文件，使用stat 查看其信息如下。但 fancontrol 脚本处并不支持执行命令获得的文件。

1
2
3
4
5
6
7
8
9
 stat <(echo $(nvidia-smi --query-gpu=temperature.gpu --format=csv,noheader | tail -n 1)000)
  File: /dev/fd/63 -> pipe:[20209]
  Size: 64              Blocks: 0          IO Block: 1024   symbolic link
Device: 17h/23d Inode: 401811      Links: 1
Access: (0500/lr-x------)  Uid: ( 1000/     wwq)   Gid: ( 1000/     wwq)
Access: 2023-04-02 22:59:46.287394863 +0800
Modify: 2023-04-02 22:59:46.287394863 +0800
Change: 2023-04-02 22:59:46.287394863 +0800
 Birth: -

发表于 更新于 分类于

参考《汇编语言 基于x86处理器》（Kip Irvine）并使用了其中库。

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
INCLUDE Irvine32.inc
maxn=50
.data
fa DWORD ?
fb DWORD ?
fo DWORD ?
buffer BYTE maxn*maxn*12 DUP(0)
bf BYTE 20 DUP(0)
ma DWORD maxn*maxn DUP(0)
mb DWORD maxn*maxn DUP(0)
mc DWORD maxn*maxn DUP(0)
filehandle DWORD ?
eda DWORD ?
m DWORD ?
n DWORD ?
p DWORD ?
q DWORD ?
ERRSTR BYTE "Invalid Input! Matrix Dim ERR",10,0
NEWLINE BYTE 10,0
divisor DWORD 10
.code
ReadMatrix PROC
	push	ebp
	mov		ebp,esp
	sub		esp,16
	;打开文件
	mov		edx,[ebp+8] ;第一个参数，文件名
	mov		edi,[ebp+12] ;第二个参数，存到内存何处
	call	OpenInputFile ;打开文件过程
	mov		filehandle,eax	;存储handle，供Close用

	;读文件
	mov		edx,OFFSET buffer
	mov		ecx,SIZEOF buffer
	call	ReadFromFile
	mov		eda,eax
	add		eda,OFFSET buffer


	;mov		edx,OFFSET buffer
	;call	WriteString

	;关文件
	mov		eax,filehandle
	call	CloseFile

	;处理字符串
	mov		edx,OFFSET buffer
	mov		esi,OFFSET buffer
	mov		DWORD PTR[ebp-12],0 ;计数器，有多少个数
L3:
	inc		esi
	mov		al,BYTE PTR [esi]
	cmp		al,' '
	jne		L3
	mov		BYTE PTR [esi],0
	mov		ecx,esi
	sub		ecx,edx		;ecx 存即将parse 的字符串长度
	call	ParseInteger32
	mov		[edi],eax

	mov		eax,DWORD PTR[ebp-12]
	inc		eax
	mov		DWORD PTR[ebp-12],eax

	add		edi,4
	inc		esi

	mov		al,BYTE PTR [esi]
	cmp		al,0dh ;0dh 是\r 的ASCII
	jne		BK
	add		esi,2 ;过滤 \r 和 \n
BK:
	mov		edx,esi ;更新edx为下一次要parse 的字符串

	cmp		esi,eda
	jge		fin
	jmp		L3
fin:
	mov		ecx,0
	
	mov		esi,OFFSET buffer
L5:
	inc		esi
	cmp		esi,eda
	jg		F2
	mov		al,BYTE PTR [esi]
	cmp		al,10 ;ASCII '\n' 为10
	jne		L5
	inc		ecx
	jmp		L5
F2:
	mov		DWORD PTR[ebp-4],ecx ;行数 row
	mov		eax,DWORD PTR[ebp-12] ;总数字数量，被除数的低16位
	mov		dx,0 ;被除数的高16位数
	mov		cx,WORD PTR[ebp-4] 
	div		cx
	mov		WORD PTR[ebp-8],ax
	add		esp,16
	pop		ebp
	ret
ReadMatrix ENDP

BufferInt PROC
	cmp		eax,0
	jg		POS
	neg		eax
	mov		BYTE PTR [ecx],'-'
	inc		ecx
POS:
	push	edx
	push	ebx
	mov		ebx,0
CONT:
	mov		edx,0		;高位清零
	div		divisor		;eax/=10,edx=eax%10
	add		edx,48		;ASCII 0 ：48
	mov		BYTE PTR bf[ebx],dl
	inc		ebx
	cmp		eax,0
	jg		CONT
LP:
	dec		ebx
	mov		al,BYTE PTR bf[ebx]
	mov		BYTE PTR [ecx],al
	inc		ecx
	cmp		ebx,0
	jg		LP

	pop		ebx
	pop		edx
	mov		BYTE PTR [ecx],' '
	inc		ecx
	ret
BufferInt ENDP

main PROC
	INVOKE	GetCommandLine
	mov		ebp,esp
	mov		ecx,eax
L1:
	inc		ecx
	mov		al,BYTE PTR[ecx]
	cmp		al,' '
	jne		L1
L0:
	inc		ecx
	mov		al,BYTE PTR[ecx]
	cmp		al,' '
	je		L0
	mov		fa,ecx
L2:
	inc		ecx
	mov		al,BYTE PTR[ecx]
	cmp		al,' '
	jne		L2
	mov		BYTE PTR[ecx],0
	inc		ecx
	mov		fb,ecx
L22:
	inc		ecx
	mov		al,BYTE PTR[ecx]
	cmp		al,' '
	jne		L22
	mov		BYTE PTR[ecx],0
	inc		ecx
	mov		fo,ecx
	
	push	OFFSET ma
	push	fa
	call	 ReadMatrix
	mov		eax,DWORD PTR[esp-16]
	mov		m,eax
	mov		eax,DWORD PTR[esp-12]
	mov		n,eax
	add		esp,8

	push	OFFSET mb
	push	fb
	call	ReadMatrix
	mov		eax,DWORD PTR[esp-16]
	mov		q,eax
	mov		eax,DWORD PTR[esp-12]
	mov		p,eax
	add		esp,8
	
	mov		eax,m
	cmp		eax,p
	jne		ERR
;----------Matrix Multiply---------
	mov		ebx,0 ;i
    jmp		LL2
LL7:
    mov		esi,0 ;j
    jmp		LL3
LL6:
    mov		edi,0 ;k
    jmp		LL4
LL5:
    mov		eax,m
    imul	eax,ebx		;i*m
    add     eax,esi		;i*m+j
    mov     edx,DWORD PTR ma[eax*4]

    mov     eax,DWORD PTR q
    imul    eax,esi		;j*q
    add     eax,edi		;j*q+k
    mov     eax,DWORD PTR mb[eax*4]

    imul    edx,eax		;val=ma[i*m+j]*mb[j*q+k]

	mov		eax,q
    imul	eax,ebx		;i*q
    add		eax,edi		;i*q+k
    mov		ecx,DWORD PTR mc[eax*4]

    add     edx,ecx		;mc[i*q+k]+=val
    mov     DWORD PTR mc[eax*4], edx
    add     edi,1		;++k
LL4:
    mov     eax,DWORD PTR q
    cmp     edi,eax
    jl      LL5
    add     esi,1
LL3:
    mov     eax,DWORD PTR m
    cmp     esi,eax
    jl      LL6
    add     ebx,1
LL2:
    mov     eax,DWORD PTR n
    cmp     ebx,eax
    jl      LL7
;----------Matrix OUTPUT-----------	
	mov		ecx,OFFSET buffer
	mov     ebx,0	;i
    jmp     L3
L6:
    mov     esi,0	;j
    jmp     L4
L5:
	mov		eax,q
    imul	eax,ebx		;i*q
    add		eax,esi		;i*q+j
	mov		eax,DWORD PTR mc[eax*4]
	;call	WriteInt
	call	BufferInt
    add     esi,1
L4:
    mov     eax,DWORD PTR q
    cmp     esi,eax
    jl      L5
	;mov		edx,OFFSET NEWLINE
	;call	WriteString
	mov		BYTE PTR [ecx],13	;\r
	inc		ecx
	mov		BYTE PTR [ecx],10	;\n
	inc		ecx 
    add     ebx,1
L3:
    mov     eax,DWORD PTR n
    cmp     ebx,eax
    jl      L6

	mov		BYTE PTR[ecx],0		;\0
	mov		eda,ecx
	mov		edx,fo
	call	CreateOutputFile
	mov		edx,OFFSET buffer	;edx buffer pointer
	call	WriteString
	mov		ecx,eda
	sub		ecx,OFFSET buffer	;ecx buffer_size
	call	WriteToFile
	call	CloseFile
	jmp NOERR
ERR:
	mov edx,OFFSET ERRSTR
	call WriteString
NOERR:
	INVOKE ExitProcess,0
main ENDP
END main

发表于 更新于 分类于

三月第一周

或许总结是一种好的进步方式... ## cf 1268

D1

博弈论。a[i][j], 还进行i此操作，Bob选择加j次的答案(k 归一化）。

显然，a[i][i]=i, a[i][0]=0

Alice 每次的最优决策是(a[i-1][j]+a[i-1][j-1])/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
#include<bits/stdc++.h>
using namespace std;

const int N=2000+5;
const int mod=1e9+7;
typedef long long ll;
ll qpow(ll a,ll p){
	ll ret=1;
	while(p){
		if(p&1) ret=(ret*a)%mod;
		a=(a*a)%mod;
		p>>=1;
	}
	return ret;
}
int a[N][N];

int main(){
	int inv2=qpow(2,mod-2);
	for(int i=1;i<N;++i){
		for(int j=1;j<i;++j){
			a[i][j]=(ll)(a[i-1][j]+a[i-1][j-1])*inv2%mod;
		}
		a[i][i]=i; 
	}
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		printf("%lld\n",(ll)a[n][m]*k%mod);
	}
	return 0;
}

D2

计数优化。

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

const int mod=1e9+7;
typedef long long ll;
ll qpow(ll a,ll p){
	ll ret=1;
	while(p){
		if(p&1) ret=(ret*a)%mod;
		a=(a*a)%mod;
		p>>=1;
	}
	return ret;
}
const int N=4e6+5;
int fact[N];

int C(int n,int m){
	return fact[n]*qpow(fact[m],mod-2)%mod*qpow(fact[n-m],mod-2)%mod;
}
int main(){
	fact[0]=1;
	for(int i=1;i<N;++i){
		fact[i]=((ll)fact[i-1]*i)%mod;
	}
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		if(n==m){
			printf("%lld\n",(ll)n*k%mod);
			continue;
		}
		ll ans=0;
		for(int i=1;i<=m;++i){
			ans=(ans+((ll)i*qpow(2,i-1)%mod)*C(n-i-1,m-i)%mod)%mod;
		}
		ans=ans*qpow(qpow(2,n-1),mod-2)%mod*k%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

Codeforces Round #773 (Div. 2) vp

A

与x轴平行的边的，且有其他顶点在这条变下方。

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

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int x1,x2,x3,y1,y2,y3;
		scanf("%d%d",&x1,&y1);
		scanf("%d%d",&x2,&y2);
		scanf("%d%d",&x3,&y3);
		int ans=0;
		if(y1==y2&&y3<y1){
			ans+=abs(x1-x2);
		}
		if(y2==y3&&y1<y2){
			ans+=abs(x2-x3);
		}
		if(y1==y3&&y2<y1){
			ans+=abs(x1-x3);
		}
		printf("%d\n",ans);
	}
	return 0;
}

B

人数超过power-up 的种数时，每增加一人则必须增加一点总能量。

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

map<int,int> mp;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,t;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&t);
			++mp[t];
		}
		int cnt=mp.size();
		for(int i=1;i<=cnt;++i){
			printf("%d ",cnt);
		}
		for(int i=cnt+1;i<=n;++i){
			printf("%d ",i);
		}
		puts("");
		mp.clear();
	}
	return 0;
}

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
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
map<int,int> mp,c;
vector<int> v[N];
int cnt;
typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,x;
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n;++i){
			++c[a[i]];
			if(c[a[i]]>1) continue;
			if(a[i]%x!=0){
				v[++cnt].push_back(a[i]);
				mp[a[i]]=cnt;
			}else{
				int t=a[i]/x;
				if(mp[t]){
					int pos=mp[t];
					v[pos].push_back(a[i]);
					mp[a[i]]=pos;
				}else{
					v[++cnt].push_back(a[i]);
					mp[a[i]]=cnt;
				}
			}
		}
		int ans=0;
		for(int i=1;i<=cnt;++i){
			for(int j=0;j+1<v[i].size();++j){
				int cp=c[v[i][j]],cn=c[v[i][j+1]];
				if(cp<=cn){
					c[v[i][j+1]]=cn-cp;
				}else{
					ans+=cp-cn;
					c[v[i][j+1]]=0;
				}
			}
			ans+=c[v[i][v[i].size()-1]];
			v[i].clear();
		}
		mp.clear();
		c.clear();
		cnt=0;
		printf("%d\n",ans);
	}
	return 0;
}

D

构造。找到当前处理区间与首个元素\(a[st]\)相等的除了其本身的第二个\(a[pos]\)，在\(a[pos]\)后插入使得其后数字与 \(a[st..pos-1]\)相同，然后同样的方法处理去除相同区间的字符串直到结束。

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<bits/stdc++.h>
using namespace std;

const int N=500+5;
int a[N*N];
map<int,int> mp;
typedef pair<int,int> pii;
vector<pii> ans;
vector<int> ct;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			++mp[a[i]];
		}
		bool f=0;
		for(int i=1;i<=n;++i){
			if(mp[a[i]]&1){
				f=1;
				break;
			}
		}
		if(f){
			puts("-1");
		}else{
			ct.push_back(1);
			int len=n,st=1;
			while(st<=len){
				int fd=a[st],pos=-1;
				for(int i=st+1;i<=len;++i){
					if(a[i]==fd){
						pos=i;
						break;
					}
				}
				int p=pos+1;
				for(int i=st+1;i<pos;++i,++p){
					if(a[i]!=a[p]){
						ans.emplace_back(p-1,a[i]);
						for(int j=len+2;j>=p+2;--j){
							a[j]=a[j-2];
						}
						a[p]=a[p+1]=a[i];
						len+=2;
					}
				}
				st=p;
				ct.push_back(p);
			}
			printf("%d\n",ans.size());
			for(auto t:ans){
				printf("%d %d\n",t.first,t.second);
			}
			printf("%d\n",ct.size()-1);
			for(int i=1;i<ct.size();++i){
				printf("%d ",ct[i]-ct[i-1]);
			}
			puts("");
			
			for(int i=1;i<=len;++i){
				//printf("%d ",a[i]);
				a[i]=0;
			}
		//	puts("------------------------");
			ans.clear();
			ct.clear();
		}
		mp.clear();
	}
	return 0;
}

3.4 Codeforces Round #774 (Div. 2)

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,s;
		scanf("%lld%lld",&n,&s);
		printf("%lld\n",s/(n*n));
	}
	return 0;
}

B

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

typedef long long ll;
const int N=2e5+5;
ll a[N],sum[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%lld",&a[i]);
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n;++i){
			sum[i]=sum[i-1]+a[i];
		}
		bool f=0;
		for(int i=1;i+i+1<=n;++i){
			if(sum[n]-sum[n-i]>sum[i+1]){
				f=1;
				break;
			}
		}
		puts(f?"YES":"NO");
	}
	return 0;
}

C

\(15! > 10^9\)，分解成二的幂次即有多少个二进制位为1（popcount）。枚举分解成阶乘的什么（注意1!, 2!也是二的幂次不要枚举），popcount统计分成二的幂次部分，取最小值即可。

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

typedef long long ll;
ll fact[16];

int main(){
	fact[0]=1;
	for(int i=1;i<=15;++i){
		fact[i]=fact[i-1]*i;
	}
	int T;
	scanf("%d",&T);
	while(T--){
		ll x;
		scanf("%lld",&x);
		ll rg=(1<<14);
		int ans=__builtin_popcountll(x);
		for(int i=0;i<rg;++i){
			ll t=x;
			int cnt=0;
			for(int j=0;j<13;++j){
				if((i>>j)&1){
					++cnt;
					t-=fact[j+3];
					if(t<0){
						cnt=-1;
						break;
					}
				}
			}
			if(cnt!=-1){
				ans=min(ans,cnt+__builtin_popcountll(t));
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

3.5 Atcoder Beginer

C

DP

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

const int mod=998244353;
typedef long long ll;
ll cnt[10];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=9;++i) cnt[i]=1;
	for(int i=2;i<=n;++i){
		ll nc[10];
		nc[1]=(cnt[1]+cnt[2])%mod;
		for(int i=2;i<=8;++i){
			nc[i]=(cnt[i-1]+cnt[i]+cnt[i+1])%mod;
		}
		nc[9]=(cnt[8]+cnt[9])%mod;
		memcpy(cnt,nc,sizeof cnt);
	}
	ll ans=0;
	for(int i=1;i<=9;++i){
		ans=(ans+cnt[i])%mod;
	}
	cout<<ans;
	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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
char s[N];
typedef long long ll;

char g(char c,ll t){
	return 'A'+(c-'A'+t)%3;
}

char f(ll t,ll k){
	if(k==0) return g(s[0],t);
	if(t==0) return s[k];
	return g(f(t-1,k/2),k%2+1);
}

int main(){
	scanf("%s",s);
	int T;
	scanf("%d",&T);
	while(T--){
		ll t,k;
		scanf("%lld%lld",&t,&k);
		printf("%c\n",f(t,k-1));
	}
	return 0;
}

Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)

A

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=100+5;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		int f0=-1,l0=-1;
		for(int i=1;i<=n;++i){
			int t;
			scanf("%d",&t);
			if(t==0){
				l0=i;
				if(f0==-1){
					f0=i;
				}
			}	
		}
		if(l0==-1){
			puts("0");
		}else{
			printf("%d\n",l0-f0+2);
		}
	}
	return 0;
}

B

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

const int N=1e5+5;
typedef long long ll;
int a[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		ll sum=0,mx=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			sum=sum+a[i];
			mx=max(mx,1ll*a[i]);
		}
		if(mx==0){
			puts("0");
		}else{
			printf("%lld\n",sum-mx+1>=mx?1:mx-(sum-mx));
		}
	}
	return 0;
}

C

注意，一个数组两两之间的积的和，排序后扫一遍可以\(O(n \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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5+5;
vector<int> x[N],y[N];

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			int t;
			scanf("%d",&t);
			x[t].emplace_back(i);
			y[t].emplace_back(j);
		}
	}
	long long ans=0;
	for(int i=1;i<N;++i){
		sort(x[i].begin(),x[i].end());
		long long sum=0,cnt=0;
		for(auto p:x[i]){
			ans+=p*cnt-sum;
			sum+=p;
			++cnt;
		}
		sort(y[i].begin(),y[i].end());
		sum=0,cnt=0;
		for(auto p:y[i]){
			ans+=p*cnt-sum;
			sum+=p;
			++cnt;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

D

枚举倍数。时间复杂度 \(\sum\limits^{n}_{i=1}\frac{n}{i}=O(n \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
#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;
int sum[N],cnt[N];
typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,c;
		scanf("%d%d",&n,&c);
		for(int i=1;i<=c*2;++i){
			sum[i]=cnt[i]=0;
		}
		for(int i=1;i<=n;++i){
			int t;
			scanf("%d",&t);
			sum[t]=cnt[t]=1;
		}
		for(int i=2;i<=c*2;++i){
			sum[i]+=sum[i-1];
		}
		bool f=1;
		for(int i=1;i<=c;++i){
			if(cnt[i]){
				for(int j=1;(ll)j*i<=c;++j){
					ll l=(ll)i*j,r=(ll)i*(j+1)-1;
					if(sum[r]-sum[l-1]&&!cnt[j]){
						f=0;
						break;
					}					
				}
				if(!f){
					break;
				}
			}
		}
		puts(f?"Yes":"No");
	}
	return 0;
}

三月第四周

odeforces Round #779 (Div. 2)

A

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

const int N=1e4+4;
char s[N];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d%s",&n,s+1);
		int ans=0;
		for(int i=2;i<=n;++i){
			if(s[i]=='0'){
				if(s[i-1]=='0'){
					ans+=2;
				}else if(s[i-2]=='0'){
					ans+=1;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

B

\(\gcd\) 的最大值是2。

\(n\)奇数时不存在。

\(n\)偶数时，\(1\dots n\) 中的偶（奇）数与\(p\)中的奇（偶）数匹配，答案\(\left(\left(\frac{n}{2}\right)!\right)^2\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n;
		scanf("%lld",&n);
		ll cnt=1,ans=1;
		for(int i=4;i<=n;++i){
			if(!(i&1)){
				++cnt;
				ans*=(cnt*cnt)%mod;
				ans%=mod;
			}
		}
		cout<<((n&1)?0:ans)<<"\n";
	}
	return 0;
}

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
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		bool f=1;
		int c1=0,p1=-1;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			if(a[i]==1){
				++c1;
				p1=i;
			}
		}
		if(c1!=1){
			f=0;
		}else{
			for(int i=2;i<p1;++i){
				if(a[i-1]+1<a[i]){
					f=0;
					break;
				}
			}
			if(f){
				for(int i=p1+1;i<=n;++i){
					if(a[i-1]+1<a[i]){
						f=0;
						break;
					}
				}
			}
			if(p1!=1){
				if(a[1]-a[n]>1){
					f=0;
				}
			}
		}
		if(f){
			puts("YES");
		}else{
			puts("NO");
		}
	}
	return 0;
}

D1

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt[65],cc[65];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll l,r;
		scanf("%lld%lld",&l,&r);
		memset(cnt,0,sizeof cnt);
		for(ll k=l;k<=r;++k){
			for(int i=0;i<63;++i){
				if((k>>i)&1ll){
					++cnt[i];
				}
			}
		}
		ll len=r-l+1;
		
		memset(cc,0,sizeof cc);
		for(int i=0;i<=r;++i){
			ll k;
			scanf("%lld",&k);
			for(int i=0;i<63;++i){
				if((k>>i)&1ll){
					++cc[i];
				}
			}
		}
		ll ans=0;
		for(int i=0;i<63;++i){
			if(cnt[i]!=cc[i]){
				ans|=(1ll<<i);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D2

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,B=62;
int t[2][N*B];
ll val[N*B];
int cnt,root;
void insert(ll x){
    bool b;int u=root;
    for(int i=B;~i;--i){
        b=x>>i&1ll;
        if(!t[b][u]) 
            t[b][u]=++cnt;
        u=t[b][u];
    }
    val[u]=x;
}
ll xormax(ll x){
	bool b;int u=root;
	for(int i=B;~i;--i){
		b=x>>i&1ll;
		if(t[!b][u]) u=t[!b][u];
		else u=t[b][u];
	}
	return x^val[u];
}
ll xormin(ll x){
	bool b;int u=root;
	for(int i=B;~i;--i){
		b=x>>i&1ll;
		if(t[b][u]) u=t[b][u];
		else u=t[!b][u];
	}
	return x^val[u];
}
ll a[N];
int main(){
 	int T;scanf("%d",&T);
	while(T--){
		root=++cnt;
		ll L,R;
		scanf("%lld%lld",&L,&R);
		for(ll i=L;i<=R;++i){
			ll t;
			scanf("%lld",&t);
			a[i-L+1]=t;
			insert(t);
		}
		int len=R-L+1;
		for(ll i=1;i<=len;++i){
			ll x=a[i]^L;
			//printf("%lld %lld %lld ???\n",x,xormin(x),xormax(x));
			if(xormin(x)==L&&xormax(x)==R){
				printf("%lld\n",x);
				break;
			}
		}
		for(int i=1;i<=cnt;++i){
			val[i]=0;
			t[0][i]=t[1][i]=0;
		}
		cnt=0;
	}   
    return 0;
}

发表于 更新于 分类于

\(O(n\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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
set<int> st,stt;
int n;
typedef pair<int,int> pii;
const int N=1e6+5;
pii a[N];

void getint(int &x){
	char c=getchar();
	for(;c>'9'||c<'0';c=getchar());
	for(x=0;c>='0'&&c<='9';c=getchar()){
		x=(x<<1)+(x<<3)+c-'0';
	}
}

int main(){
	getint(n);
	st.insert(0);
	st.insert(n+1);
	for(register int i=1;i<=n;++i){
		getint(a[i].first);
		a[i].second=i;
	}
	sort(a+1,a+n+1);
	ll ans=0;
	for(register int i=1;i<=n;++i){
		int t=a[i].second;
		auto p=st.lower_bound(t);
		int r=*p;
		--p;
		ans-=(ll)(r-t)*(t-*p)*a[i].first;
		st.insert(t);	
	}
	stt.insert(0);
	stt.insert(n+1);
	for(register int i=n;i>=0;--i){
		int t=a[i].second;
		auto p=stt.lower_bound(t);
		int r=*p;
		--p;
		ans+=(ll)(r-t)*(t-*p)*a[i].first;
		stt.insert(t);	
	}
	printf("%lld",ans);
	return 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
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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
typedef pair<int,int> pii;
const int N=1e6+5;
pii a[N];

void getint(int &x){
	char c=getchar();
	for(;c>'9'||c<'0';c=getchar());
	for(x=0;c>='0'&&c<='9';c=getchar()){
		x=(x<<1)+(x<<3)+c-'0';
	}
}
int bl[N],br[N],sl[N],sr[N];
pii st[N];
int tp=0;

int main(){
	getint(n);
	for(int i=1;i<=n;++i){
		getint(a[i].first);
		a[i].second=i;
	}
	for(int i=1;i<=n;++i){
		while(tp&&st[tp]<a[i]){
			st[tp--]=pii(0,0);
		}
		bl[i]=st[tp].second;
		st[++tp]=a[i];
	}
	while(tp){
		st[tp--]=pii(0,0);
	}
	for(int i=1;i<=n;++i){
		while(tp&&st[tp]>a[i]){
			st[tp--]=pii(0,0);
		}
		sl[i]=st[tp].second;
		st[++tp]=a[i];
	}
	while(tp){
		st[tp--]=pii(0,0);
	}
	st[0].second=n+1;
	for(int i=n;i>0;--i){
		while(tp&&st[tp]<a[i]){
			st[tp--]=pii(0,0);
		}
		br[i]=st[tp].second;
		st[++tp]=a[i];
	}
	while(tp){
		st[tp--]=pii(0,0);
	}
	for(int i=n;i>0;--i){
		while(tp&&st[tp]>a[i]){
			st[tp--]=pii(0,0);
		}
		sr[i]=st[tp].second;
		st[++tp]=a[i];
	}
	while(tp){
		st[tp--]=pii(0,0);
	}
//	for(int i=1;i<=n;++i){
//		printf("%d %d %d %d\n",bl[i],sl[i],br[i],sr[i]);
//	}
	ll ans=0;
	for(int i=1;i<=n;++i){
		ans+=(ll)((ll)(br[i]-i)*(i-bl[i])-(ll)(sr[i]-i)*(i-sl[i]))*a[i].first;
	}
	printf("%lld",ans);
	return 0;
}

发表于 更新于 分类于

A

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

typedef long long ll;
const int mod=998244353;
ll f[2][15];
int a[100005];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		a[i]%=9;
	}
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=9;++j){
			f[i&1][j]=(f[1-(i&1)][j]+f[1-(i&1)][(j-a[i]+9)%9])%mod;
		}
	}
	for(int i=1;i<=9;++i){
		printf("%d ",f[n&1][i]);
	}
	return 0;
}

B

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

const int N=2e5+5;
char s[N];
int ST[3][20][N];

int main(){
	int n,T;
	scanf("%d%d%s",&n,&T,s+1);
	for(int i=1;i<=n;++i){
		if(s[i]=='W'){
			ST[0][0][i]=1;
			ST[1][0][i]=1;
			ST[2][0][i]=1;
		}else if(s[i]=='L'){
			ST[0][0][i]=0;
			ST[1][0][i]=-1;
			ST[2][0][i]=-1;
		}
	}
	for(int i=1;i<20;++i){
		for(int j=1;j+(1<<i)-1<=n;++j){
			for(int k=0;k<3;++k){
				ST[k][i][j]=ST[k][i-1][j]+ST[(k+ST[k][i-1][j]+3)%3][i-1][j+(1<<i-1)];
			}
		}
	}
	while(T--){
		int l,r,s;
		scanf("%d%d%d",&l,&r,&s);
		int dd=r-l+1;
		for(int i=19;i>=0;--i){
			if((dd>>i)&1){
				s+=ST[s%3][i][l];
				l+=(1<<i);
			}
		}
		printf("%d\n",s);
	}	
	return 0;
}

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

const int N=100+5;
int f[N];

int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a==1){
			f[i]=3;
		}else if(b==1){
			if(!f[i-1]){
				f[i]=2;
			}else if(f[i-1]==1){
				f[i]=1;
			}
		}else if(c){
			if(!f[i-1]&&!f[i-2]){
				f[i]=1;
			}
		}
		ans+=f[i];
	}
	printf("%d",ans);
	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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e5,M=1e5; 
ll prime[M],cnt;
bool nisp[N];

void findp(ll n){
	for(ll i=2;i<=n;++i){
		if(!nisp[i]){
			prime[++cnt]=i;
		}
		for(ll j=1;j<=cnt&&i*prime[j]<=n;++j){
			nisp[i*prime[j]]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
}

bool isprime(ll n){
	int r=sqrt(n);
	for(int i=2;i<=r;++i){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

int main(){
	findp(1000);
	int T;
	scanf("%d",&T);
	while(T--){
		ll n;
		scanf("%lld",&n);
		if(n==1){
			puts("-1");
			continue;
		}
		ll ans=1;
		for(int i=1;i<=cnt;++i){
			if(ans*prime[i]>n){
				break;
			}
			ans*=prime[i];
		}
		printf("%lld ",ans);
		for(ll i=n;i>0;--i){
			if(isprime(i)){
				printf("%lld\n",i);
				break;
			}
		}
	}
	return 0;
}

E

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

typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,m;
		scanf("%lld%lld",&n,&m);
		if(m==1){
			if(n==1){
				puts("1");
			}else
				puts("-1");
		}else{
			ll ans=n/(m-1)*2;
			if(n%(m-1)==1||n%(m-1)==0){
				--ans;
			}else{
				++ans;
			}
			printf("%lld\n",ans-(m==2?2:0));
		}
	}
	return 0;
}

F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,t,cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i){
			scanf("%d",&t);
			if(t<m){
				++cnt;
			}
		}
		printf("%d\n",n-cnt*2>0?n-cnt*2:-1);
	}
	return 0;
}

G

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

const int N=1e5+5;
int a[N];
typedef pair<int,int> pii;
vector<pii> v;


int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		int res=0;
		for(int i=2;i<=n-1;++i){
			if(a[i-1]==a[i]||a[i+1]==a[i]) continue;
			int l=0,r=2e9;
			if(a[i-1]>a[i]){
				r=min(r,(a[i-1]+a[i]-1)/2);
			}else{
				l=max(l,(a[i-1]+a[i])/2+1);
			}
			if(a[i+1]>a[i]){
				r=min(r,(a[i+1]+a[i]-1)/2);
			}else{
				l=max(l,(a[i+1]+a[i])/2+1);
			}
			if(l>r) continue;
			if(l==0){
				++res;
			}else{
				v.emplace_back(l,1);
			}
			if(r<2e9){
				v.emplace_back(r+1,-1);
			}
		}
		sort(v.begin(),v.end(),[](pii x,pii y){
			if(x.first==y.first){
				return x.second>y.second;
			}
			return x.first<y.first;
		});
		int t=res;
		for(auto x:v){
			t+=x.second;
			res=min(res,t);
		}
		printf("%d\n",res);
		v.clear();
	}
	return 0;
}

H

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

typedef long long ll;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define sz(x) (t[x].r-t[x].l+1)
#define mid(x) (t[x].l+t[x].r>>1)
struct Node{
	int l,r,c;
	ll v;
}t[10005];
inline void upd(int o){
    t[o].v=(t[L(o)].v+t[R(o)].v);
    t[o].c=(t[L(o)].c+t[R(o)].c);
}
void buildt(int o,int L,int R){
    t[o].l=L,t[o].r=R;
    if(L==R){
    	t[o].c=t[o].v=0;
        return;
    }
    int M=L+R>>1;
    buildt(L(o),L,M);
    buildt(R(o),M+1,R);
    upd(o);
}
void add(int o,int p,int v){
	if(p<=t[o].l&&t[o].r<=p){
		++t[o].c;
		t[o].v+=v;
		return;
	}
	int M=mid(o);
	if(p<=M){
		add(L(o),p,v);
	}else{
		add(R(o),p,v);
	}
	upd(o);
}
ll ask(int o,int L,int R){
	if(R<L){
		return 0;
	}
    if(L<=t[o].l&&t[o].r<=R){
        return t[o].v;
    }
    int M=mid(o);
    ll ret=0;
    if(L<=M)
        ret=(ret+ask(L(o),L,R));
    if(M<R)
        ret=(ret+ask(R(o),L,R));
    return ret;
}
int asc(int o,int L,int R){
	if(R<L){
		return 0;
	}
    if(L<=t[o].l&&t[o].r<=R){
        return t[o].c;
    }
    int M=mid(o);
    ll ret=0;
    if(L<=M)
        ret=(ret+asc(L(o),L,R));
    if(M<R)
        ret=(ret+asc(R(o),L,R));
    return ret;
}

int main(){
	buildt(1,0,1000);
	int n;
	scanf("%d",&n);
	int tt;
	ll ans=0;
	scanf("%d",&tt);
	ans+=abs(tt+tt-1000);
	add(1,tt,tt);
	for(int i=2;i<=n;++i){
		scanf("%d",&tt);
		ans+=abs(tt+tt-1000);
		ll nv=ask(1,0,1000-tt-1),nc=asc(1,0,1000-tt-1);
		ans+=nc*1000-nv-tt*nc;
		nv=ask(1,1000-tt,1000),nc=asc(1,1000-tt,1000);
		ans+=nv+nc*tt-nc*1000;
		add(1,tt,tt);
	}
	printf("%lld",ans);
	return 0;
}

I

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

typedef long long ll;
const ll M=1e9+7;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
	    x=1,y=0;return;
	}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
ll qpow(ll a,ll p,ll mod){
    ll ans=1;
    a%=mod;
    while(p){
        if(p&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        p>>=1;
    }
    return ans%mod;
}


int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,m;
		scanf("%lld%lld",&n,&m);
		if(n==1){
			puts("0");
		}else{
			ll val=inv(2,M);
			printf("%lld\n",(1-qpow(val,n-1,M)+M)%M*m%M);
		}
	}
	return 0;
}

J

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

const int N=2e5+5;
int a[N],b[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=m;++i){
			scanf("%d",&b[i]);
		}
		if(n<(k+1)/2){
			puts("-1");
		}else{
			sort(a+1,a+n+1,greater<int>());
			sort(b+1,b+m+1,greater<int>());
			int pa=(k+1)/2+1,ans=0,pb=1,now=(k+1)/2;
			for(int i=1;i<pa;++i){
				ans+=a[i];
			}
			while(now<k){
				if(pa<=n&&pb<=m){
					if(a[pa]>b[pb]){
						ans+=a[pa++];
					}else{
						ans+=b[pb++];
					}
				}else if(pb<=m){
					ans+=b[pb++];
				}else{
					ans+=a[pa++];
				}
				++now;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

K

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

const int N=1e5+5;
char s[N];
int f[N][3][3][3];

inline char get(int j,int k,int l)
{
	int green=(j==0)+(k==0)+(l==0),red=(j==1)+(k==1)+(l==1);
	if(green>red)return 'G';
	if(green<red)return 'R';
	return 'B';
}

int main(){
	int n;
	scanf("%d%s",&n,s+1);
	for(int i=0;i<=n;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				for(int l=0;l<=2;++l){
					f[i][j][k][l]=-1e9;
				}
			}
		}
	}
	for(int i=0;i<=2;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				if(get(i,j,k)==s[3]){
					f[3][i][j][k]=(i==0)+(j==0)+(k==0);
				}
			}
		}
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				for(int l=0;l<=2;++l){
					if(get(j,k,l)==s[i]){
						for(int t=0;t<=2;++t)
							f[i][j][k][l]=max(f[i][j][k][l],f[i-1][t][j][k]+(l==0));
					}
				}
			}
		}
	}
	int ans=-1;
	for(int i=0;i<=2;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				if(get(i,j,k)==s[n]){
					ans=max(ans,f[n][i][j][k]);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

L

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

const int N=1e5;
char s[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,x=0,y=0;
		double ans=0;
		scanf("%d%s",&n,s+1);
		for(int i=1;i<=n;++i){
			if(s[i]=='L'){
				x++;
			}else if(s[i]=='R'){
				x--;
			}else if(s[i]=='U'){
				y++;
			}else{
				y--;
			}
			ans=max(ans,sqrt(x*x+y*y));
		}
		printf("%.12lf\n",ans);
	}
	return 0;
}

发表于 更新于 分类于

BioDBSystem

基于林奈生物分类法的生物信息管理系统（数据库课程设计作业）

建立了生物信息数据库，其中涵盖了生物的分类信息，域、界、门、纲、目、科、属和种，以及生物的栖息地和别名等附加信息。

在其基础上建立了信息管理系统，能够在图形界面上进行注册和登录，权限控制，对生物信息的各种增删查改，以及对插入和修改时间的登记。

管理员登录时，提供了SQL的接口和基本表的展示，对于单表支持在图形化界面上删改。另外还分为研究者和管理者两个角色作为系统的使用者，此时隐藏管理员后台的内容，前者能进行查询插入删除和修改，而后者只支持查询。同时支持统计功能，对部分数据进行可视化展示。

管理员界面如下

而非管理员界面如下

详细报告以及技术支持可联系：chwhc0@outlook.com 或 1073486274（QQ，请备注来意）

发表于 更新于 分类于

The 2021 CCPC Guilin B

A Plus B Problem

维护区间后缀0/9的数量。

不用二分+线段树（维护区间0/9的数量）。

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include<bits/stdc++.h>
using namespace std;

const int N=4e6+5;
struct Node{
	int l,r,s0,s9,v;
	bool t0,t9;
}t[N];
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define sz(x) (t[x].r-t[x].l+1)
#define mid(x) (t[x].l+t[x].r>>1)
int a[2][N],c[N];

void upd(int o){
	if(sz(R(o))==t[R(o)].s0){
		t[o].s0=t[L(o)].s0+t[R(o)].s0;
	}else{
		t[o].s0=t[R(o)].s0;
	}
	if(sz(R(o))==t[R(o)].s9){
		t[o].s9=t[L(o)].s9+t[R(o)].s9;
	}else{
		t[o].s9=t[R(o)].s9;
	}
}

void build(int o,int L,int R){
	t[o].l=L;t[o].r=R;
	if(L==R){
		t[o].s0=(c[L]==0);
		t[o].s9=(c[L]==9);
		t[o].v=c[L];
		return;
	}
	int M=L+R>>1;
	build(L(o),L,M);
	build(R(o),M+1,R);
	upd(o);
}

inline void ds9(int o){
	t[o].t9=1;
	t[o].t0=0;
	t[o].s0=0;
	t[o].s9=sz(o);
	t[o].v=9;
}

inline void ds0(int o){
	t[o].t0=1;
	t[o].t9=0;
	t[o].s0=sz(o);
	t[o].s9=0;
	t[o].v=0;
}

void spread(int o){
	if(t[o].t0){
		ds0(L(o));
		ds0(R(o));
		t[o].t0=0;
	}
	else if(t[o].t9){
		ds9(L(o));
		ds9(R(o));
		t[o].t9=0;	
	}
}

int ask9(int o,int p){
	if(sz(o)==t[o].s9) return min(p,t[o].r)-t[o].l+1;
	if(t[o].l==t[o].r) return t[o].v==9;
	spread(o);
	int M=mid(o);
	if(p>M){
		int len=ask9(R(o),p);
		if(len==min(t[R(o)].r,p)-t[R(o)].l+1){
			len+=ask9(L(o),p);
		}
		return len;
	}
	return ask9(L(o),p);
}

int ask0(int o,int p){
	if(sz(o)==t[o].s0) return min(p,t[o].r)-t[o].l+1;
	if(t[o].l==t[o].r) return t[o].v==0;
	spread(o);
	int M=mid(o);
	if(p>M){
		int len=ask0(R(o),p);
		if(len==min(t[R(o)].r,p)-t[R(o)].l+1){
			len+=ask0(L(o),p);
		}
		return len;
	}
	return ask0(L(o),p);
}

int ask(int o,int p){
	if(p==t[o].l&&t[o].r==p){
		return t[o].v;
	}
	spread(o);
	int M=mid(o);
	if(p<=M){
		return ask(L(o),p);
	}else{
		return ask(R(o),p);
	}
}

void change(int o,int L,int R,int v){
	if(L<=t[o].l&&t[o].r<=R){
		t[o].v=v;
		if(v==0){
			ds0(o);
		}else if(v==9){
			ds9(o);
		}else{
			t[o].t0=0;
			t[o].t9=0;
			t[o].s0=0;
			t[o].s9=0;
		}
		return;
	}
	int M=mid(o);
	spread(o);
	if(L<=M){
		change(L(o),L,R,v);
	}
	if(M<R){
		change(R(o),L,R,v);
	}
	upd(o);
}

char s[2][N];

int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	scanf("%s%s",s[0]+1,s[1]+1);
	for(int i=1;i<=n;++i){
		a[0][i]=s[0][i]-'0';
		a[1][i]=s[1][i]-'0';
	}
	int jin=0;
	for(int i=n;i>0;--i){
		c[i]=a[0][i]+a[1][i]+jin;
		jin=c[i]/10;
		c[i]%=10;
	}
	build(1,1,n);
	while(q--){
		int r,x,v;
		scanf("%d%d%d",&r,&x,&v);
		--r;
		int d=v-a[r][x];
		a[r][x]=v;
		if(d==0){
			printf("%d 0\n",ask(1,x));
			continue;
		}
		int tmp=ask(1,x);
		int val=tmp+d;
		if(val>=0&&val<=9){
			change(1,x,x,val);
			printf("%d 2\n",val);
		}else{
			if(val>=10){
				change(1,x,x,val-10);
				int len=ask9(1,x-1);
				if(len){
					change(1,x-len,x-1,0);
				}
				if(x-len-1>=1){
					printf("%d %d\n",val-10,3+len);
					change(1,x-len-1,x-len-1,ask(1,x-len-1)+1);
				}else{
					printf("%d %d\n",val-10,2+len);
				}
			}else{
				change(1,x,x,val+10);
				int len=ask0(1,x-1);
				if(len){
					change(1,x-len,x-1,9);
				}
				if(x-len-1>=1){
					printf("%d %d\n",val+10,3+len);
					change(1,x-len-1,x-len-1,ask(1,x-len-1)-1);
				}else{
					printf("%d %d\n",val+10,2+len);
				}
			} 
			
		}
	}
	return 0;
}

UVA11992 Fast Matrix Operations

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

const int R=21,C=1e6+500;
struct Node{
	int l,r,sum,max,min,add,set;
	bool f;
}t[R][C*2];
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define sz(i,x) (t[i][x].r-t[i][x].l+1)
#define mid(i,x) (t[i][x].l+t[i][x].r>>1)
inline void upd(int i,int o){
    t[i][o].sum=t[i][L(o)].sum+t[i][R(o)].sum;
    t[i][o].max=max(t[i][L(o)].max,t[i][R(o)].max);
    t[i][o].min=min(t[i][L(o)].min,t[i][R(o)].min);
}
void buildt(int i,int o,int L,int R){
    t[i][o].l=L,t[i][o].r=R;
    t[i][o].sum=t[i][o].max=t[i][o].min=t[i][o].add=t[i][o].set=t[i][o].f=0;
    if(L==R){
        return;
    }
    int M=L+R>>1;
    buildt(i,L(o),L,M);
    buildt(i,R(o),M+1,R);
    upd(i,o);
}
inline void stx(int i,int o,int v){
	t[i][o].f=1;
	t[i][o].max=t[i][o].min=t[i][o].set=v;
	t[i][o].sum=sz(i,o)*v;
	t[i][o].add=0;//set会清除add标记 
}
inline void adx(int i,int o,int v){
	t[i][o].add+=v;
	t[i][o].sum+=sz(i,o)*v;
	t[i][o].max+=v;
	t[i][o].min+=v;
}
void spread(int i,int o){
    if(t[i][o].f){ //先set再add 
    	int &v=t[i][o].set;
    	stx(i,L(o),v);
    	stx(i,R(o),v);
    	t[i][o].f=0;
    	v=0;
    }
    if(t[i][o].add){
    	int &v=t[i][o].add;
    	adx(i,L(o),v);
    	adx(i,R(o),v);
    	v=0;
    	t[i][o].add=0;
    }
}
void add(int i,int o,int L,int R,int v){
	if(L<=t[i][o].l&&t[i][o].r<=R){
		adx(i,o,v);
		return;
	}
	spread(i,o);
	int M=mid(i,o);
	if(L<=M){
		add(i,L(o),L,R,v);
	}
	if(M<R){
		add(i,R(o),L,R,v);
	}
	upd(i,o);
}
void change(int i,int o,int L,int R,int v){
	if(L<=t[i][o].l&&t[i][o].r<=R){
		stx(i,o,v);
		return;
	}
	spread(i,o);
	int M=mid(i,o);
	if(L<=M){
		change(i,L(o),L,R,v);
	}
	if(M<R){
		change(i,R(o),L,R,v);
	}
	upd(i,o);
}
int _min=2e9,_max=-2e9,_sum=0;
void ask(int i,int o,int L,int R){
	if(L<=t[i][o].l&&t[i][o].r<=R){
		_min=min(_min,t[i][o].min);
		_max=max(_max,t[i][o].max);
		_sum+=t[i][o].sum;
		return;
	}
	int M=mid(i,o);
	spread(i,o);
	if(L<=M){
		ask(i,L(o),L,R);
	}
	if(M<R){
		ask(i,R(o),L,R);
	}
}
int main(){
  	int op,x1,y1,x2,y2,r,c,q;
  	while(~scanf("%d%d%d",&r,&c,&q)){
	  	for(int i=1;i<=r;++i){
	  		buildt(i,1,1,c);
	  	}
		while(q--){
			scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
			if(op==1){
				int v;scanf("%d",&v);
				for(int i=x1;i<=x2;++i){
					add(i,1,y1,y2,v);
				}
			}else if(op==2){
				int v;scanf("%d",&v);
				for(int i=x1;i<=x2;++i){
					change(i,1,y1,y2,v);
				}
			}else{
				_min=2e9,_max=-2e9,_sum=0;
				for(int i=x1;i<=x2;++i){
					ask(i,1,y1,y2);
				}
				printf("%d %d %d\n",_sum,_min,_max);
			}
		}
	}
  	return 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
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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include<bits/stdc++.h>
using namespace std;

typedef unsigned char uc;
uc m[0xffff+10]; 
char prog[105][50];
int totl,now=2,ca=-1,cb=-1;

inline int getrg(char c){
	//if(ss[1]<'A'||ss[1]>'D') return -1;
	return ((c-'A')<<1)+0xffff+1;
}

int getad(char *ss){
	int ad;
	if(ss[2]=='X'){
		int rd=getrg(ss[1]);
		ad=((int)m[rd+1]<<8)+m[rd];
	}else{
		sscanf(ss,"T%X",&ad);
	}
	if(ad<0x3000||ad+1>=0xB000){
		puts("ACCESS_VIOLATION");
		return -1;	
	}
	return ad;
}

bool run(char *s){
	if(!strncmp(s,"ECHO",4)){
		char a[10];
		sscanf(s,"ECHO %s",a);
		if(a[0]=='T'||a[1]=='X'){
			int ad;
			if(a[0]=='T') ad=getad(a);
			else ad=getrg(a[0]);
			if(ad>0){
				printf("%02X%02X\n",m[ad+1],m[ad]);
			}else{
				return 0;
			}
		}else{
			puts(a);
		}
		++now;
	}else if(!strncmp(s,"ADD",3)){
		char a[10],b[10];
		sscanf(s,"ADD %s %s",a,b);
		int va,vb;
		int ad;
		if(a[0]=='T') ad=getad(a);
		else ad=getrg(a[0]);
		if(ad>0){
			va=((int)m[ad+1]<<8)+m[ad];
		}else{
			return 0;
		}
		if(b[0]=='T'||b[1]=='X'){
			int bd;
			if(b[0]=='T') bd=getad(b);
			else bd=getrg(b[0]);
			if(bd>0){
				vb=((int)m[bd+1]<<8)+m[bd];
			}
			else{
				return 0;
			}
		}else{
			sscanf(b,"%X",&vb);
		}
		int vc=va+vb;
		m[ad+1]=((vc>>8)&0xff);
		m[ad]=(vc&0xff);
		++now;
	}else if(!strncmp(s,"INC",3)){
		char a[10];
		sscanf(s,"INC %s",a);
		int ad;
		if(a[0]=='T') ad=getad(a);
		else ad=getrg(a[0]);
		if(ad>0){
			int va=((int)m[ad+1]<<8)+m[ad];
			++va;
			m[ad+1]=((va>>8)&0xff);
			m[ad]=(va&0xff);
		}else{
			return 0;
		}
		++now;
	}else if(!strncmp(s,"MOV",3)){
		char a[10],b[10];
		sscanf(s,"MOV %s %s",a,b);
		int va,vb;
		int ad;
		if(a[0]=='T') ad=getad(a);
		else ad=getrg(a[0]);
		if(ad>0){
			va=((int)m[ad+1]<<8)+m[ad];
		}else{
			return 0;
		}
		if(b[0]=='T'||b[1]=='X'){
			int bd;
			if(b[0]=='T') bd=getad(b);
			else bd=getrg(b[0]);
			if(bd>0){
				vb=((int)m[bd+1]<<8)+m[bd];
			}
			else{
				return 0;
			}
		}else{
			sscanf(b,"%X",&vb);
		}
		m[ad+1]=((vb>>8)&0xff);
		m[ad]=(vb&0xff);
		++now;
	}else if(!strncmp(s,"CMP",3)){
		char a[10],b[10];
		sscanf(s,"CMP %s %s",a,b);
		if(a[0]=='T'||a[1]=='X'){
			int ad;
			if(a[0]=='T') ad=getad(a);
			else ad=getrg(a[0]);
			if(ad>0){
				ca=((int)m[ad+1]<<8)+m[ad];
			}else{
				return 0;
			}
		}else{
			sscanf(a,"%X",&ca);
		}
		if(b[0]=='T'||b[1]=='X'){
			int bd;
			if(b[0]=='T') bd=getad(b);
			else bd=getrg(b[0]);
			if(bd>0){
				cb=((int)m[bd+1]<<8)+m[bd];
			}
			else{
				return 0;
			}
		}else{
			sscanf(b,"%X",&cb);
		}
		++now;
	}else if(s[0]=='J'){
		if(s[1]=='M'){
			sscanf(s,"JMP %X",&now);
		}
		else{
			if(ca==-1&&cb==-1){
				puts("CMP_MISSING");
				return 0;
			}
			bool f=0;
			switch(s[1]){
				case 'M':f=1;break;
				case 'G':f=(ca>cb);break;
				case 'L':f=(ca<cb);break;
				case 'E':f=(ca==cb);break;
				case 'N':
					switch(s[2]){
							case 'G':f=!(ca>cb);break;
							case 'L':f=!(ca<cb);break;
							case 'E':f=(ca!=cb);break;
					}
				break;
			}
			if(f){
				int lin;
				s[0]=' ',s[1]=' ';
				sscanf(s,"J %X",&lin);
				if(lin<2||lin>totl){
					puts("RUNTIME_ERROR");
					return 0;
				}
				now=lin;
			}else{
				now++;
			}
		}
	}else if(!strncmp(s,"STOP",4)){
		return 0;
	}
	return 1;
}

int main(){
	while(gets(prog[++totl]));
	int cnt=1;
	while(run(prog[now])){
		++cnt;
		if(cnt>=1000000){
			puts("TLE");
			break;
		}
	}
	return 0;
}

发表于 更新于 分类于

Borůvka’s algorithm

最初每个点是孤立点。从所有当前的连通块向其他连通块扩展出最小边，直到只剩一个连通块。

时间复杂度\(O(E\log V)\) 

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
const int N=5005,M=2e5+5;
struct Edge{
	int f,t,v;
}e[M];
int fa[N],lk[N],cpt[N],n,m; //cpt cheapest 子树中最小的边权 
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);};

int Boruvka(){
	int ans=0;
	for(int i=1;i<=n;++i) fa[i]=i;
	int t=n;
	while(t>1){
		for(int i=1;i<=n;++i) lk[i]=0;
		int cnt=0;
		for(int i=1;i<=m;++i){
			int x=find(e[i].f),y=find(e[i].t);
			if(x!=y){
				++cnt;
				if(!lk[x]||cpt[x]>e[i].v) lk[x]=y,cpt[x]=e[i].v;
				if(!lk[y]||cpt[y]>e[i].v) lk[y]=x,cpt[y]=e[i].v;
				//lk[i]: 在本轮连边中 i子树连向哪棵子树 
			}
		}
		if(!cnt) return -1;//图不联通 
		for(int i=1;i<=n;++i){
			if(fa[i]==i){
				fa[find(lk[i])]=i;
				ans+=cpt[i];
				--t;
			}
		}
	}
	return ans;
}

异或最小生成树

给每一个点一个点权，连接两个点\(i,j\)的边的边权为\(a_i\) xor \(a_j\)，求这张图上的最小生成树。

我们怎么快速找到连通块外的最近点（异或值最小的点）呢，这时我们就需要0/1字典树了。

我们可以建立一个全局字典树包含所有的点权，然后对每个连通块都维护一个单独的字典树，每个字典树中包含了这个连通块中的所有点权。

每次查询某个点\(a_i\)的最近点的时候，我们从高位到低位比较，假设当前在第\(i\)位，且\(a_i\)的第\(i\)位上的值为\(b\)，如果连通块外有\(i\)位也为\(b\)的数字（说明\(b\)方向上，全局字典树的size大于当前连通块字典树的size），我们必然选择同为\(b\)的数字，我们在两棵字典树的位置都往\(b\)方向转移。如果没有，我们便在字典树上的位置便要向\(b\) \(xor\) \(1\)的方向转移，结果值就要加上\(2^i\)。

参考：https://zhuanlan.zhihu.com/p/164633727

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

const int N=2e5+5;
int t[2][N*60],siz[N*60],val[N*60],root[N];
int cnd;
typedef pair<int,int> pii;
void insert(int u,int x,int i){
	bool b;
	++siz[u];
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]) t[b][u]=++cnd;
		u=t[b][u];
		++siz[u];
	}
	val[u]=i;
}
pii query(int rt,int lt,int x){
	int ans=0;
	for(int i=30;i>=0;--i){//从高位到低位贪心 
		bool b=x>>i&1;
		int sr=t[b][rt]?siz[t[b][rt]]:0;
		int sl=t[b][lt]?siz[t[b][lt]]:0;
		if(sr>sl){//全局的字典树大于当前的字典树 
			rt=t[b][rt];////可以走与x的第i位相同的 
			lt=t[b][lt];
		}else{//不得不走与x的第i位相异的 
			ans+=(1<<i);//当前位对答案贡献 
			rt=t[b^1][rt];
			lt=t[b^1][lt];
		}
	}
	return pii(ans,val[rt]);
}
void merge(int &x,int y){
	if(x==0||y==0){
		x=x+y;
		return;
	}
	merge(t[0][x],t[0][y]);
	merge(t[1][x],t[1][y]);
	siz[x]+=siz[y];
	val[x]=max(val[x],val[y]);
}
int fa[N],lk[N],cpt[N],n,m,a[N]; //cpt cheapest 子树中最小的边权 
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);};

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		fa[i]=i;
		root[i]=i;
	}
	root[0]=n+1;
	cnd=n+1;
	sort(a+1,a+n+1);
	n=unique(a+1,a+n+1)-a-1;//相同的数可以事先用边权为0的边连起来 
	for(int i=1;i<=n;++i){
		insert(root[0],a[i],i);
		insert(root[i],a[i],i);
	}
	int t=n;
	long long ans=0;
	while(t>1){
		for(int i=1;i<=n;++i) lk[i]=0;
		for(int i=1;i<=n;++i){
			int x=find(i);
			pii tmp=query(root[0],root[x],a[i]);
			int w=tmp.first,y=find(tmp.second);
			if(x!=y){
				if(!lk[x]||cpt[x]>w) lk[x]=y,cpt[x]=w;
				if(!lk[y]||cpt[y]>w) lk[y]=x,cpt[y]=w;
			}
		}
		for(int i=1;i<=n;++i){
			if(fa[i]==i){
				int fi=find(lk[i]);
				fa[fi]=i;
				merge(root[i],root[fi]);
				ans+=cpt[i];
				--t;
			}
		}
	}
	printf("%lld",ans); 
	return 0;
}

The 2020 ICPC Asia Macau Regional Contest

C Club Assignment

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<bits/stdc++.h>
using namespace std;

const int N=500000+5;
int t[2][N*60],siz[N*60],val[N*60],root[N];
int cnd;
typedef pair<int,int> pii;
void insert(int u,int x,int i){
	bool b;
	++siz[u];
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]) t[b][u]=++cnd;
		u=t[b][u];
		++siz[u];
	}
	val[u]=i;
}
pii query(int rt,int lt,int x){
	int ans=0;
	for(int i=30;~i;--i){
		bool b=x>>i&1;
		int sr=t[b][rt]?siz[t[b][rt]]:0;
		int sl=t[b][lt]?siz[t[b][lt]]:0;
		if(sr>sl){
			rt=t[b][rt];
			lt=t[b][lt];
		}else{
			ans+=(1<<i);
			rt=t[b^1][rt];
			lt=t[b^1][lt];
		}
	}
	return pii(ans,val[rt]);
}
void merge(int &x,int y){
	if(x==0||y==0){
		x=x+y;
		return ;
	}
	merge(t[0][x],t[0][y]);
	merge(t[1][x],t[1][y]);
	siz[x]+=siz[y];
	val[x]=max(val[x],val[y]);
}
int fa[N],lk[N],cpt[N],n,m,a[N],ff[N*2],ans[N];
pii b[N],lp[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int ffd(int x){
	return ff[x]==x?x:ff[x]=ffd(ff[x]);
}
void uni(int x,int y){
	x=ffd(x),y=ffd(y);
	if(x!=y){
		ff[x]=y;
	}
}
void init(){
	//init start 
	for(int i=1;i<=cnd;++i){
		siz[i]=0;
		t[0][i]=t[1][i]=0;
		val[i]=0;
	}
	cnd=0;
}

int que(int u,int x){
	if(!siz[u]) return 2e9;
	bool b;
	int ans=0;
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]){
			ans|=(1<<i);
			u=t[b^1][u];
		}else{
			u=t[b][u];
		}
	}
	return ans;
}

void ins(int u,int x){
	bool b;
	++siz[u];
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]) t[b][u]=++cnd;
		u=t[b][u];
		++siz[u];
	}
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			b[i].first=a[i];
			b[i].second=i;
			fa[i]=i;
			root[i]=i;
		}
		root[0]=n+1;
		cnd=n+1;
		sort(a+1,a+n+1);
		int nn=n;
		sort(b+1,b+nn+1);
		n=unique(a+1,a+n+1)-a-1;
		for(int i=1;i<=n;++i){
			insert(root[0],a[i],i);
			insert(root[i],a[i],i);
		}
		int t=n;
		//int as=0;
		for(int i=1;i<=(n<<1);++i){
			ff[i]=i;
		}
		while(t>1){
			for(int i=1;i<=n;++i) lk[i]=0,lp[i]=pii(0,0);
			for(int i=1;i<=n;++i){
				int x=find(i);
				pii tmp=query(root[0],root[x],a[i]);
				int w=tmp.first,y=find(tmp.second);
				if(x!=y){
					if(!lk[x]||cpt[x]>w) lk[x]=y,lp[x]=pii(tmp.second,i),cpt[x]=w;
					if(!lk[x]||cpt[y]>w) lk[y]=x,lp[y]=pii(i,tmp.second),cpt[y]=w;
				}
			}
			for(int i=1;i<=n;++i){
				if(fa[i]==i){
					int fi=find(lk[i]);
					fa[fi]=i;
					merge(root[i],root[fi]);
				//	cout<<lp[i].first<<"to"<<lp[i].second<<' '<<cpt[i]<<endl;
					uni(lp[i].first,lp[i].second+n);
					uni(lp[i].first+n,lp[i].second);
				//	as+=cpt[i];
					--t;
				}
			}
		}
	//	cout<<"!!!"<<as<<endl;
		int p=1,ft=0,nt=0;
		int c1=++cnd,c2=++cnd,a1=2e9,a2=2e9;
		for(int i=1;i<=n;++i){
			int now=ffd(i);
			if(!ft){
				ft=now;
			}else if(!nt){
				nt=now;
			}
			if(now==ft){
				ans[b[p].second]=1;
				a1=min(a1,que(c1,b[p].first));
				ins(c1,b[p++].first);
				while(b[p].first==a[i]){
					ans[b[p].second]=0;
					a2=min(a2,que(c2,b[p].first));
					ins(c2,b[p++].first);
				}
			}else{
				ans[b[p].second]=0;
				a2=min(a2,que(c2,b[p].first));
				ins(c2,b[p++].first);
				while(b[p].first==a[i]){
					ans[b[p].second]=1;
					a1=min(a1,que(c1,b[p].first));
					ins(c1,b[p++].first);
				}
			}
		}
	//	printf("%d %d\n",a1,a2);
		printf("%d\n",min(a1,a2));
		for(int i=1;i<=nn;++i){
			printf("%d",ans[i]+1);
		}
		puts("");
		init();
	}
	return 0;
}