第二场感觉好多了，没那么唐了，三个签到题出的没那么快但是都是一发过，在三题队中排名非常靠前；后期想出了一个有点复杂的 $I$ ，做出四个题，排名还不错。这次智力还可以。

A

题意：给定两个大小为 $1\times 1$ 的瓷砖花纹 $A,B$，现在要排一个 $n\times m$ 的瓷砖矩阵，使连续的条纹数量为 $K$ 。

一个找规律题，并不是很难，但似乎榜歪了，都没怎么考虑这个题。

将整个图案分成很多个 $2\times 2$ 的小区域，当每个区域排列都为 $ABBA$ 时会构成很多个圆，这样子的条纹数是最多的，而且每换掉一块瓷砖，花纹数量减少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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>

using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second

template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}
int n,m,k,x,y,p;
int	mx,tot; 
char s;
void solve(){
	int x,y;
	rd(n),rd(m),rd(k);
	rd(x),rd(y);cin>>s;
	p=(s=='A')^((x+y)&1);
	if(p)	mx=n+m+(((n-1)*(m-1)+1)/2);
	else mx=n+m+(n-1)*(m-1)/2;
	if(k<n+m||k>mx)	{
		puts("No");
		return;
	}
	puts("Yes");
	tot=mx-k;
	if(p&&s=='A'){
		for(int i=1;i<=n;++i){
			if(i&1)	printf("A");
			else printf("B");
			for(int j=2;j<=m;++j){
				if((i+j)&1){
					if(!tot)	printf("B");
					else {
						--tot;
						printf("A");
					}	
				}
				else printf("A");
			}
			puts("");
		}		
	}
	else if(p&&s=='B'){
		for(int i=1;i<=n;++i){
			for(int j=1;j<m;++j){
				if(!((i+j)&1)){
					if(!tot)	printf("A");
					else {
						--tot;
						printf("B");
					}	
				}
				else printf("B");
			}
			if((i+m)&1)	printf("B");
			else printf("A");
			puts("");
		}			
	}
	else if(!p&&s=='A'){
		for(int i=1;i<=n;++i){
			if(i&1)	printf("B");
			else printf("A");
			for(int j=2;j<=m;++j){
				if(!((i+j)&1)){
					if(!tot)	printf("B");
					else {
						--tot;
						printf("A");
					}	
				}
				else printf("A");
			}
			puts("");
		}				
	}
	else {
		for(int i=1;i<=n;++i){
			for(int j=1;j<m;++j){
				if(((i+j)&1)){
					if(!tot)	printf("A");
					else {
						--tot;
						printf("B");
					}	
				}
				else printf("B");
			}
			if((i+m)&1)	printf("A");
			else printf("B");
			puts("");
		}				
	}
}
signed main(){
	int T;
	rd(T);
	while(T--){
		solve();
	}
}

B

题意：给一个含有 $N$ 个点 $M$ 条边的图，有 $q$ 个询问，每次询问给定的点集 $S$ 构成的最小生成树。$q\leq 10^5,|S|\leq 10^5$

好玄学啊这题。

前置知识：根号分治。

注意到 $|S|\leq 10^5$ ，为一个定值，可以用根号分治。确定阈值 $K$ ，当 $|S|<K$ 时暴力枚举每个点对是否有边，再跑Kruskal ；若 $|S|\geq K$ ，$O(m)$ 遍历所有边，找出含在集合里的边再跑Kruskal。当 $K=\sqrt{N}$ 时能把时间复杂度降到 $O(N^{1.5})$ 级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int N=1e5+5;

struct bian
{
    int u,v,w;
}adj[N];

int fa[N];
int check[N];
int n,m,q;
unordered_map<LL,int> mp;

int getfa(int x)
{
    return fa[x] = fa[x]==x?x:getfa(fa[x]);
}

bool cmp(bian x,bian y)
{
    return x.w<y.w;
}

void solve()
{
    int cnt;
    int dian[N];
    
    // cin>>cnt;
    scanf("%d",&cnt);
    for(int i=1;i<=cnt;i++)
    {
        // cin>>dian[i];
        scanf("%d",&dian[i]);
        check[dian[i]]=1;
        fa[dian[i]]=dian[i];
    }

    bian tmp[N];
    int tot=0;

    if(1LL*cnt<1LL*n/cnt)
    {
        for(int i=1;i<=cnt;i++)
        {
            for(int j=i+1;j<=cnt;j++)
            {
                LL hash1=1LL*dian[i]*N+dian[j];
                int w=mp[hash1];
                if(w!=0)
                {
                    ++tot;
                    tmp[tot].u=dian[i];
                    tmp[tot].v=dian[j];
                    tmp[tot].w=w;
                }
            }
        }
        sort(tmp+1,tmp+tot+1,cmp);
    }

    else
    {
        for(int i=1;i<=m;i++)
        {
            int u=adj[i].u;
            int v=adj[i].v;
            if(check[u] && check[v])
            {
                tmp[++tot]=adj[i];
            }
        }
    }

    int sum=0;
    LL ans=0;
    for(int i=1;i<=tot;i++)
    {
        int u=tmp[i].u;
        int v=tmp[i].v;

        int fu=getfa(u);
        int fv=getfa(v);

        if(fu==fv)continue;
        sum++;
        ans+=1LL*tmp[i].w;
        fa[fv]=fu;
    }

    if(sum!=cnt-1)puts("-1");
    else printf("%lld\n",ans);

    for(int i=1;i<=cnt;i++)check[dian[i]]=0;

}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
        cin>>adj[i].u>>adj[i].v>>adj[i].w;
        LL hash1=1LL*adj[i].u*N+adj[i].v;
        LL hash2=1LL*adj[i].v*N+adj[i].u;
        mp[hash1]=mp[hash2]=adj[i].w;
    }

    sort(adj+1,adj+m+1,cmp);
    for(int i=1;i<=q;i++)solve();
}

C

题意：有一个 $2\times n$ 的包含红白格子的网格图。从红格子开始走，只能走红格子，且不能走回头路，求能走过的最大红格子数。

$$
dp[i][1]=max(dp[i-1][1]+1,dp[i-1][2]+2)
$$

$$
dp[i][2]=max(dp[i-1][2]+1,dp[i-1][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
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second

template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}
const int N=1e6+10;
int n;
int f[N][3],ans;
char s[3][N];
void solve(){
	rd(n);
	for(int i=1;i<=2;++i)	scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i){
		if(s[1][i]=='R'){
			if(s[1][i-1]=='R'){
				f[i][1]=f[i-1][1]+1;
				if(s[2][i-1]=='R')	f[i][1]=max(f[i][1],f[i-1][2]+2);
			}
		}
		if(s[2][i]=='R'){
			if(s[2][i-1]=='R'){
				f[i][2]=f[i-1][2]+1;
				if(s[1][i-1]=='R')	f[i][2]=max(f[i][2],f[i-1][1]+2);
			}
		}
	}
	for(int i=1;i<=n;++i){
		ans=max(ans,max(f[i][1],f[i][2]));
		if(s[1][i]=='R'&&s[2][i]=='R')	ans=max(ans,max(f[i][1],f[i][2])+1);
	}
	printf("%d",ans);
}
signed main(){
	solve();
}

E

题意：给定 $x$ ，求比 $x$ 小的 $y$ 使得 $x\oplus y=gcd(x,y)$ 。

答案即 $x-lowbit(x)$ 。

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

using namespace std;
typedef long long LL;
LL lowbit(LL x)
{
	return x & -x;
}

int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		long long x;
		cin >> x;
		if(x == lowbit(x)) cout << -1 << endl;
		else cout << x - lowbit(x) << endl;
	}
	return 0;
}

G

题意：给一个 $multiset$ ，有多少个子集满足元素之积是完全平方数，求这些完全平方数的和。$1\leq a_i\leq 1000$

注意到每一个数都小于1000，于是每个数最多含有1个大于31的质因数。那么考虑将质因数分类，分为小于等于31的小质数和大于31的大质数，把小质数状压为 $S$ ，每一位表示这一位的质数的指数是奇数还是偶数。设计 $dp[i][S]$ 表示前 $i$ 个数涉及的质因数状态为 $S$ 时的答案。有转移方程：
$$
dp[i][S]=\sum dp[i-1][S’]\times \sqrt{x^p}
$$
$x$ 为 $S$ 中某一位表示的质数，且 $a_i$ 分解质因数有 $p$ 个 $x$ ，根据 $p$ 的奇偶判断 $S$ 对应位为0还是1；注意若 $p$ 为奇数，那么乘上的数是 $\sqrt{x^{p-1}}$ ，只不过当 $p$ 为奇数的同时 $S’$ 这一位也是奇数时，多补上一个 $x$ 。

另外，对于大质数的情况，我们只需要在最初的11位状态中多加1位表示大质数，且每到一个新数就清空一次最高位，因为大于31的质数每个数只能出现一次。

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

using namespace std;
typedef long long LL;
const int N = 1010, M = 12, mod = 1e9 + 7;

int f[N][1 << M];
bool st[N];
int a[N], id[N];
int n, cnt;

int primes[N];
vector<int>prime[1000];

int qp(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

void init()
{
	for(int i = 2; i < N; i++)
    {
        if(!st[i]) primes[cnt++] = i, id[i] = cnt - 1;
        for(int j = 0; primes[j] < N / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	init();
	
	for(int i = 1; i <= n; i ++)
	{
		int m = a[i];
		if(m == 1)
		{
			prime[2].push_back(1);
			continue;
		}
		int max_prime = 0;
		for(int j = 2; j <= m / j; j ++)
        {
            if(m % j ==0)
            {
            	max_prime = max(max_prime, j);
                int s = 0;
                while(m % j == 0)
                {
                    m /= j;
                    s ++;
                }
            }
        }
        if(m > 1) max_prime = max(max_prime, m);
        prime[max_prime].push_back(a[i]);
	}

	int ct = 0;
	f[0][0] = 1;
	for(int i = 0; i < cnt; i ++)
	{
		int P = primes[i];

		for(int t = 0; t < prime[P].size(); t ++)
		{
			if(!t) for(int state = 1 << M - 1; state < 1 << M; state ++) f[ct][state] = 0;
			
			for(int state = 0; state < 1 << M; state ++) f[ct + 1][state] = f[ct][state];

			for(int state = 0; state < 1 << M; state ++)
			{
				int c = prime[P][t];
				int n_state = 0;
				int mul = 1;
				for(int j = 2; j <= c / j; j ++)
		        {
		            if(c % j ==0)
		            {
		                int s = 0;
		                while(c % j == 0)
		                {
		                    c /= j;
		                    s ++;
		                }
		                if(s % 2 == 0) mul = (LL)mul * qp(j, s / 2) % mod;
		                else n_state |= (1 << id[j]), mul = (LL)mul * qp(j, s / 2) % mod;
		            }
		        }
		        if(c > 1) n_state |= (1 << min(11, id[c]));
		        for(int k = 0; k < M; k ++)
		        	if((state >> k & 1) && (n_state >> k & 1))
		        		if(k < M - 1)
		        			mul = (LL)mul * primes[k] % mod;
		        		else mul = (LL)mul * primes[i] % mod;
		        		
				int target = state ^ n_state;
				
				//if(!ct && !state) cout << target << ' ' << c << ' ' << P << endl;
				
 		    	f[ct + 1][target] = ((LL)f[ct + 1][target] + (LL)f[ct][state] * mul % mod) % mod;
			}
			ct ++;
		}
	}
	//cout << f[2][1 + (1 << (M - 1))] << endl;
	//cout << f[n][0] << endl;
	printf("%d\n", (f[n][0] - 1 + mod) % mod);
	return 0;
}


H

题意：给定一段包含 $ASDW$ 的指令序列，从 $(0,0)$ 出发，要求经过 $(x,y)$ ，求这样的连续指令段的数量。

首先记录前缀和，当确定某个段的终点后，起点的前缀和的值就可以确定。

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;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second

template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}
const int N=2e5+10;
int n;
int x,y,vx,vy;
int dx[128],dy[128];
LL ans;
char s[N];
map<pair<int,int>, int>mmp;
void solve(){
	dx['W']=0,dx['A']=-1,dx['S']=0,dx['D']=1;
	dy['W']=1,dy['A']=0,dy['S']=-1,dy['D']=0;
	rd(n),rd(vx),rd(vy);
	scanf("%s",s+1);
	if(vx==0&&vy==0){
		printf("%lld",n*(n+1)/2);
		return ;
	}
	mmp[{0,0}]=1;
	for(int i=1;i<=n;++i){
		x+=dx[s[i]];
		y+=dy[s[i]];
		ans+=1ll*mmp[{x-vx,y-vy}]*(n-i+1);
		mmp[{x-vx,y-vy}]=0;
//		cout<<"x="<<x<<" y="<<y<<" mmp="<<mmp[{x-vx,y-vy}]<<" ans="<<ans<<endl;
		mmp[{x,y}]++;
	}
	printf("%lld",ans);
}
signed main(){
	solve();
}

I

题意：给 $2\times n$ 个数的排列， $1-n$ 每个数出现2次，每次能拿走连续一段数，但首尾的数必须相同，此次操作得到的分数为第一个数与这一段数的长度的乘积。求最大分数。$n\leq3000$

首先将所有区间排序，从小区间处理大区间的分数。有一个小技巧是最开始和末尾添加两个0，那么最后的答案就是 $d[0]$ 。

对于一个区间 $[l,r]$，要把它拿走最少的分数就是 $a[l]\times (r-l+1)$ ，但是如果其中有包含的区间 $[l’,r’]$ 且 $a[l’]>a[l]$ ，那么先拿走中间小区间会更优。此时有可能就会出现冲突，如：$l,…,l_1,…l_2,…,r_1,…,r_2,…,r$ ，选择中间哪个区间就转化为了区间覆盖问题：在一个区间内选择若干个不重合的区间，那个区间有一个价值，使总价值最大，用 $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
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
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second
#define int long long
template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}

const int N=6e3+10;
int n,m,q;
int a[N],L[N],R[N],mxx[N],f[N];

struct node{
	int l,r;
	bool operator<(node b){
		return r-l<b.r-b.l;
	}
}b[N];


void solve(){
	rd(n);
	for(int i=1;i<=2*n;++i)	rd(a[i]);
	for(int i=1;i<=2*n;++i){
		if(!L[a[i]])	L[a[i]]=b[a[i]].l=i;
		else R[a[i]]=b[a[i]].r=i;	
	}
	L[0]=0,R[0]=2*n+1;
	b[0]={0,2*n+1};
	sort(b,b+n+1);
	for(int i=0;i<=n;++i){
		int x=a[b[i].l];
		mxx[L[x]]=2*x;
//		cout<<"x="<<x<<" L="<<L[x]<<" R="<<R[x]<<endl;
		for(int j=L[x]+1;j<R[x];++j){
			int y=a[j];
			mxx[j]=mxx[j-1]+x;
//			if(y<x||L[y]<L[x]||L[y]==j)	continue;
			if(R[y]==j&&L[y]>L[x])		mxx[j]=max(mxx[j],mxx[L[y]-1]+f[y]);
		}
		f[x]=mxx[R[x]-1];
//		cout<<"x="<<x<<" f="<<f[x]<<endl;
	}
	printf("%lld",f[0]);
}

signed main(){
	solve();
}