比赛链接
我服了做得太烂了。。。
还差36分变绿，死一会儿。。。
题解
A. Maximize?
典，暴力枚举即可
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;
int t,x;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>x;
int mx=0,id=0;
for(int i=1;i<x;i++)
{
if(__gcd(x,i)+i>mx)
{
mx=__gcd(x,i)+i;
id=i;
}
}
cout<<id<<"\n";
}
return 0;
}
|
B. Prefiquence
双指针，也很典
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
| #include<bits/stdc++.h>
using namespace std;
int t,n,m;
string a,b;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>m>>a>>b;
int cn1=b.size(),cn2=a.size();
int i=0,j=0;
while(i<cn1&&j<cn2)
{
if(a[j]==b[i])
{
j++;
}
if(j==cn2)
{
break;
}
i++;
}
cout<<j<<"\n";
}
return 0;
}
|
C. Assembly via Remainders
比较简单的构造，保证每个$a[i-1]>x[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
| #include<bits/stdc++.h>
using namespace std;
int t;
int n;
long long x[505],a[505];
long long pre;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(int i=2;i<=n;i++)
{
cin>>x[i];
}
a[1]=x[2]+1;
for(int i=2;i<=n;i++)
{
a[i]=a[i-1]+x[i];
while(a[i]<=x[i+1])
{
a[i]+=a[i-1];
}
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
}
return 0;
}
|
D. Permutation Game
与zhy女士讨论的思路甚至是对的。
大概是一个类似于线性dp的思路，以min(循环节长度, $k$ )为循环，这样循环大小不会超过 $2×10^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
| #include<bits/stdc++.h>
using namespace std;
long long t;
long long n,k,pb,ps;
long long a[200005],p[200005];
bool vis[200005];
long long score(long long x,long long k)
{
memset(vis,0,sizeof vis);
long long mx=0,sum=0;
while(!vis[x]&&k>0)
{
vis[x]=1;
mx=max(mx,sum+k*a[x]);
sum+=a[x];
k--;
x=p[x];
}
return mx;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
long long n,k,pb,ps;
cin>>n>>k>>pb>>ps;
for(long long i=1;i<=n;i++)
{
cin>>p[i];
}
for(long long i=1;i<=n;i++)
{
cin>>a[i];
}
long long A=score(pb,k),B=score(ps,k);
if(A>B)
{
cout<<"Bodya\n";
}
else if(A<B)
{
cout<<"Sasha\n";
}
else
{
cout<<"Draw\n";
}
}
return 0;
}
|
E. Cells Arrangement
烂透构造题hmm，你知道我看到代码时有多崩溃吗=(
oh，原来读题读错了，人家让我求max，我搁这儿求min。。。（笑不出来
虽然有很多别的构造方式但是这里介绍一下官方题解的最短方法
注意到：
$n=2$ 时，随便放即可
$n=3$ 时，在上一个的基础上最外圈的上面填一个点，与剩下两个的距离不相等且不等于1
$n=4$ 同理
在一张 $n×n$ 的图里，我们一共可以得到 $1$ ~ $2(n-1)$ 的 $2(n-1)$ 个不同曼哈顿距离对角线上的点与右下产生所有偶数距离，与右下上一个点产生所有奇数距离
其实也没有很难qwq，代码不需要注释了吧…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
int t,n;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n-2;i++)
{
cout<<i<<" "<<i<<"\n";
}
cout<<n-1<<" "<<n<<"\n"<<n<<" "<<n<<"\n";
}
return 0;
}
|
F.Equal XOR Segments
感觉这次的题都有点浓厚数学的成分
本题我借鉴了一下题解，发现 $k>3$ 是没有必要的，因为我们可以把任意连续三个异或和相同的序列合并成一个，即 $x⊕x⊕x=x$，这样就可以减少两个子序列
同时 $k=2$ 时， $x⊕x=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
| #include<bits/stdc++.h>
using namespace std;
long long t;
long long n,q;
long long a[200005];
map<long long,vector<long long> > id;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>q;
for(auto &i:id)
{
i.second.clear();
}
id[0].push_back(0);
for(long long i=1;i<=n;i++)
{
cin>>a[i];
a[i]^=a[i-1];
id[a[i]].push_back(i);
}
while(q--)
{
long long l,r;
cin>>l>>r;
if(a[r]==a[l-1])
{
cout<<"YES\n";
continue;
}
long long t= *--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r);
long long s= *lower_bound(id[a[r]].begin(),id[a[r]].end(),l);
if(t>s)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
cout<<"\n";
}
}
|
G&H.Division + LCP
一个简化版一个强化版，合一起做
这题似乎需要一种名字叫做 Z函数(扩展kmp) 的东西
【模板】扩展 KMP/exKMP（Z 函数）
然后这个题目说让我们求把这个字符串分成k段的LCP最大值，其中有一个子段一定是原字符串的前缀，所以最后得到的k个子段也肯定是原字符串的前缀
如果 $k$ 不大于 $\sqrt{n}$ ，那么只需要枚举不超过 $\sqrt{n}$ 次；否则用二分算答案即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include<bits/stdc++.h>
using namespace std;
int t,n;
int z[200005];
int ans[200005];
void Z(string s)
{
int l=0,r=0;
for(int i=1;i<n;i++)
{
if(i<=r&&z[i-l]<r-i+1)
{
z[i]=z[i-l];
}
else
{
z[i]=max(0,r-i+1);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]])
{
z[i]++;
}
}
if(i+z[i]-1>r)
{
l=i,r=i+z[i]-1;
}
}
}
int f(int len)
{
int cnt=1;
for(int i=len;i<n;)
{
if(z[i]>=len)
{
cnt++,i+=len;
}
else
{
i++;
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
memset(z,0,sizeof z);
memset(ans,0,sizeof ans);
int l,r;
string s;
cin>>n>>l>>r;
cin>>s;
Z(s);
int sq=ceil(sqrt(n));
for(int i=sq;i>0;i--)
{
int cn=f(i);
ans[cn]=max(ans[cn],i);
}
for(int i=n-1;i>0;i--)
{
ans[i]=max(ans[i],ans[i+1]);
}
for(int i=1;i<=sq;i++)
{
int L=0,R=n/i;
while(L<R)
{
int mid=(L+R+1)/2;
if(f(mid)>=i)
{
L=mid;
}
else
{
R=mid-1;
}
}
ans[i]=L;
}
for(int i=l;i<=r;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
}
return 0;
}
|
Finished.