MinamiMelon
0%

发表于

像 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;
}

发表于 更新于

向量空间:给定域\(F\)，\(F\)上的向量空间\(V\)是一个集合，其上定义加法和数乘运算且这两个运算满足八个公理。

线性无关:对于向量空间中\(V\)上\(n\)个元素的向量组\((\mathbf{v}_1, \ldots, \mathbf{v}_n)\),若存在不全为\(0\)的数\(a_i \in F\)满足 \[ a_{1}\mathbf{v}_{1}+a_{2}\mathbf {v}_{2}+\ldots +a_{n}\mathbf{v}_{n} = 0 \]

则称这\(n\)个向量线性相关（linearly dependent），否则称为线性无关（linearly independent）。

线性组合:对于向量空间中 V 上 nn 个元素的向量组\((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其线性组合（linear combination）是如下形式的向量

\[ a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} \] ​​ 其中\(a_1, \ldots, a_n \in F\)

一组向量线性无关 \(\Leftrightarrow\)没有向量可用有限个其他向量的线性组合所表示

张成:对于向量空间中 \(V\) 上 \(n\) 个元素的向量组 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其所有线性组合所构成的集合称为 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)的张成（span），记为 \(\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)\)

基:若向量空间 \(V\) 中向量组 \(\mathfrak{B}\) 既是线性无关的又可以张成 \(V\)，则称其为\(V\) 的基（basis）。

\(\mathfrak{B}\)中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

设 \(\mathfrak {B}\) 是向量空间 \(V\) 的基。则\(\mathfrak {B}\)具有以下性质：

1.\(V\) 是 \(\mathfrak {B}\)的极小生成集，就是说只有\(\mathfrak {B}\)能张成\(V\)，而它的任何真子集都不张成全部的向量空间。

2.\(\mathfrak {B}\) 是 \(V\) 中线性无关向量的极大集合，就是说 \(\mathfrak {B}\) 在\(V\) 中是线性无关集合，而且\(V\) 中没有其他线性无关集合包含它作为真子集。

3.\(V\) 中所有的向量都可以按唯一的方式表达为\(\mathfrak {B}\) 中向量的线性组合。

异或运算下的基} $

对于数 \(a_0, a_1, \ldots, a_n\)，将 \(a_i\)的二进制表示$ (b_{m}b_0)_2$​ 看作一个向量。向量组 \(\mathbf{a}_1, \ldots, \mathbf{a}_n\)可以张成一个向量集合 \(\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)\)，加上我们的异或运算和乘法运算（显然满足 8 条公理），即可形成一个向量空间 \(V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)\)

设集合\(S\)中最大的数在二进制意义下有\(L\)位，我们使用一个 \([0\dots L]\)的数组\(a\)来储存线性基。

这种线性基的构造方法保证了一个特殊性质，对于每一个\(i\),\(a_i\)有以下两种可能：

  • \(a_i=0\)，并且 只有} \(满足\)j<i\(的\)a_j\(（即\)a_i\(前面所有数）的第\)i$个二进制位一定为\(0\)。

  • \(a_i\neq0\),并且

  1. 整个\(a\)数组只有\(a_i\)的第\(i\)个二进制位为\(1\)；
  2. \(a_i\)更高的二进制位一定为1

（如果排成矩阵，形成一个下三角矩阵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
const int MAXL=60;
ll a[MAXL+1];int lbsiz;
void insert(ll t){//高斯消元解出的对角矩阵的非零行构成的向量组 
    for(int j=MAXL;j>=0;--j){// 逆序枚举二进制位
        if(!((t>>j)&1)) continue;// 如果 t 的第 j 位为 0，则跳过
        if(a[j]) t^=a[j];
        else{// 找到可以插入 a[j] 的位置
            // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
// 如果某一个a[k]=0也无须担心，因为这时候第k位不存在于线性基中，不需要保证t的第k位为 0	
            for(int k=0;k<j;++k) if((t>>k)&1) t^=a[k];
            // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
            for(int k=j+1;k<=MAXL;++k) if((a[k]>>j)&1) a[k]^=t;
                // 插入到 a[j] 的位置上
            a[j]=t;++lbsiz;
            return;// 不要忘记，结束插入过程
        }
    }
}

最大异或和：将线性基中所有向量异或起来得到的向量所对应的数。

1
2
3
4
5
ll querymax(){
    ll res=0;
    for(int i=0;i<=MAXL;++i) res^=a[i];
    return res;
}

集合任选大于1个元素异或出的第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
vector<ll> v;
bool zero;int n;//zero: 是否能异或出0
void init(){
    lbsiz=0;
    v.clear();
    memset(a,0,sizeof a);
}
void prepare(){
    zero=(lbsiz!=n);
    for(int i=0;i<=MAXL;++i){
        if(a[i]) v.push_back(a[i]);
    }
}
ll query(ll k){
    if(zero) --k;
    if(k>=(1ll<<v.size())) return -1;
    ll res=0;
    for(int i=MAXL;i>=0;--i) if((k>>i)&1) res^=v[i];
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int ttt=1;ttt<=T;++ttt){
        init();
        scanf("%d",&n);ll t;
        for(int i=1;i<=n;++i){
            scanf("%lld",&t);
            insert(t);
        }
        prepare();
        printf("Case #%d:\n",ttt);
        int q;scanf("%d",&q);
        while(q--){
            scanf("%lld",&t);
            printf("%lld\n",query(t));
        }
    }
    return 0;
}

P4151 [WC2011]最大XOR和路径

异或路径问题：转化成任意一条路径，和任意个圈的异或。

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

typedef long long ll;
const int M=200000+5,N=50000+5,MAXL=60;
struct Edge{
	int t,n;
	ll v;
}e[M];
int hd[N],cnt;
inline void build(int f,int t,ll v){
	e[++cnt]=(Edge){t,hd[f],v};
	hd[f]=cnt;
}
ll a[MAXL+3],dis[N];
bool vis[N];
void insert(ll t){
	for(int j=MAXL;j>=0;--j){
		if(!((t>>j)&1)) continue;
		if(a[j]) t^=a[j];
		else{
			for(int k=0;k<j;++k){
				if((t>>k)&1) t^=a[k];
			}
			for(int k=j+1;k<=MAXL;++k){
				if((a[k]>>j)&1){
					a[k]^=t;
				}
			}
			a[j]=t;
			return;
		}
	}
}
int n,m;
void dfs(int u,ll now){
	dis[u]=now;vis[u]=1;
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(!vis[v]){
			dfs(v,now^e[i].v);
		}else{
			insert(now^e[i].v^dis[v]);
		}
	}
}
ll query(ll x){
	for(int i=MAXL;i>=0;--i){
		if((x^a[i])>x){
			x^=a[i];
		}
	}
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b;ll d;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&a,&b,&d);
		build(a,b,d);
		build(b,a,d);
	}
	dfs(1,0);
	printf("%lld",query(dis[n]));
	return 0;
}

P4301 [CQOI2013] 新Nim游戏

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=105;
int a[40],d[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
	}
	sort(d+1,d+n+1,greater<int>());
	long long ans=0;
	for(int i=1;i<=n;++i){
		int t=d[i];
		for(int j=31;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				a[j]=t;
				break;
			}
		}
		if(!t) ans+=d[i];
	}
	printf("%lld",ans);
	return 0;
}

P3292 [SCOI2016]幸运数字

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;

typedef long long ll;
const int N=20000+5,MAXL=61;
struct Edge{
	int t,n;
}e[N<<1];
int hd[N],cnt;
inline void build(int f,int t){
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
}
struct Lbasis{//Linear Basis 
	ll a[MAXL+1];
	Lbasis(){memset(a,0,sizeof a);}
	Lbasis(const Lbasis& b){memcpy(a,b.a,sizeof a);} 
	void insert(ll t){
		for(int j=MAXL;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				for(int k=0;k<j;++k){
					if((t>>k)&1) t^=a[k];
				}
				for(int k=j+1;k<=MAXL;++k){
					if((a[k]>>j)&1){
						a[k]^=t;
					}
				}
				a[j]=t;
				return;
			}
		}
	}
	void merge(const Lbasis &b){
		for(int i=MAXL;i>=0;--i){
			if(b.a[i]){
				insert(b.a[i]);
			}
		}
	}
	ll max(){
		ll res=0;
		for(int i=0;i<=MAXL;++i){
			res^=a[i];
		}
		return res;
	}
}b[20][N];
int dep[N],anc[20][N];
ll val[N];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	anc[0][u]=f;
	b[0][u].insert(val[u]);
	for(int i=1;anc[i-1][u];++i){
		anc[i][u]=anc[i-1][anc[i-1][u]];
		b[i][u]=b[i-1][u];
		b[i][u].merge(b[i-1][anc[i-1][u]]);
	}
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(v==f) continue;
		dfs(v,u);
	}
}
ll ask(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dd=dep[x]-dep[y];
	Lbasis res;
	for(int i=19;i>=0;--i){
		if(dd&(1<<i)){
			res.merge(b[i][x]);
			x=anc[i][x];
		}
	}
	if(x==y){
		res.insert(val[x]);
		return res.max();
	}
	for(int i=19;i>=0;--i){
		if(anc[i][x]!=anc[i][y]){
			res.merge(b[i][x]);res.merge(b[i][y]);
			x=anc[i][x];y=anc[i][y];
		}
	}
	res.insert(val[x]);res.insert(val[y]);res.insert(val[anc[0][x]]);
	return res.max();
}
int n;
int main(){
	int q;
	scanf("%d%d",&n,&q);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		build(a,b);build(b,a);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",ask(x,y));
	}
	return 0;
}