比赛链接：Dashboard - Codeforces Round 934 (Div. 2) - Codeforces
B
题意：有长度为 $2n$ 的数组 $a$ ，由 $1-n$ 的每个整数组成，每个整数出现两次。需要找出两个长度为 $2k$ 的数组 $l$ ，$r$ ，使得 $l$ 是 $[a_1,a_2,…,a_n]$ 的子集， $r$ 是 $[a_{n+1},a_{n+2},…,a_{2n}]$ 的子集，且 $l_1\bigoplus l_2\bigoplus …\bigoplus l_{2k}=r_1\bigoplus r_2\bigoplus …\bigoplus r_{2k}$ 。
将前 $n$ 个元素和后 $n$ 个元素分别排序，先考虑数组 $l$ ，即前 $n$ 个元素：若有连续的相同元素，那么都选，且数组 $r$ 需要选的两个相同元素的数量+1；然后再考虑单个的元素，那么必然是两个元素一个在 $l$ ，一个在 $r$ ，都统计上即可。
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;
void solve()
{
int n,k;
cin>>n>>k;
int a1[n+5]={0},a2[n+5]={0};
for(int i=1;i<=n;i++)cin>>a1[i];
for(int i=1;i<=n;i++)cin>>a2[i];
sort(a1+1,a1+n+1);
sort(a2+1,a2+n+1);
int ans1[n+5]={0},ans2[n+5]={0};
int cnt1=0,cnt2=0,tot=0;
for(int i=1;i<=n;i++)
{
if(cnt1==2*k)break;
if(a1[i]==a1[i+1] && cnt1+2<=k*2)
{
ans1[++cnt1]=a1[i];
ans1[++cnt1]=a1[++i];
tot++;
}
}
for(int i=1;i<=n;i++)
{
if(cnt1==2*k)break;
if(a1[i]!=a1[i+1])
{
ans1[++cnt1]=a1[i];
ans2[++cnt2]=a1[i];
}
else i++;
}
int sum=0;
for(int i=1;i<=n;i++)
{
if(sum==tot)break;
if(a2[i]==a2[i+1])
{
ans2[++cnt2]=a2[i];
ans2[++cnt2]=a2[++i];
sum++;
}
}
for(int i=1;i<=2*k;i++)cout<<ans1[i]<<" ";cout<<endl;
for(int i=1;i<=2*k;i++)cout<<ans2[i]<<" ";cout<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
C
题意：A和B博弈，A先行动。有一个长为 $n$ 的数组，A每次选一个数并将其移动到一个初始为空的数组 $c$ 中，B每次删除一个数，A想要使 $c$ 的 $mex$ 最大，B与其相反。求最后 $c$ 的 $mex$ 。
将 $n$ 个数排序后，最后的答案不会超过第一个没有出现的数。在这些数中，若有出现过2次及以上的数，那么A不需要主动拿它，当B拿这个数的时候再拿这个数。因此策略是：A第一次拿掉第一个只出现过一次的数，B第一次拿掉第二个只出现过一次的数。因此答案就是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;
void solve()
{
int n;
cin>>n;
int a[n+5]={0};
int num[n+5]={0};
for(int i=1;i<=n;i++)cin>>a[i],num[a[i]]++;
int ans=-1;
int tot=0;
for(int i=0;i<=n;i++)
{
if(num[i]==0)
{
if(ans==-1)ans=i;
break;
}
if(num[i]==1 && tot==0)
{
tot++;
continue;
}
if(num[i]==1 && tot==1)
{
ans=i;
break;
}
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
D
题意：对于一个字符串 $t$ ，若存在一个长度为 $k$ 的子串不为回文串，那么称字符串 $t$ 为 $k-good$ 。定义 $f(t)$ 表示所有 $k$ 值只和。先给出字符串 $s$ ，给出 $q$ 个询问，每次给出 $l,r$ 求 $f(s_ls_{l+1}…s_r)$ 。
前置知识：http://aaaarnoldddd.github.io/2024/03/19/ACM/模板/manacher/
考虑什么样的字符串不为 $k-good$ 。
对于字符串长度为 $n$ ， $1<k< n$ ，
- 当 $k$ 为偶数时，需要所有字符都相等。
- 当 $k $ 为奇数时，需要所有奇数位置相等，偶数位置相等。
可以通过预处理来实现。
当 $k=1$ ，不存在。
当 $k=n$ ，需要判断整个字符串是否回文。使用manacher算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> manacher(string s)
{
string t;
for(auto c:s)
{
t+=string("#")+c;
}
t+=string("#");
int n=t.length();
vector<int>p(n+2);
t="$"+t+"%";
int l=1,r=1;
for(int i=1;i<=n;i++)
{
p[i]=max((int)0,min(r-i,p[l+r-i]));
while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++;
if(i+p[i]>r)
{
r=i+p[i];
l=i-p[i];
}
}
return vector<int>(begin(p)+2,end(p)-2);
}
void solve()
{
int n,q;
cin>>n>>q;
string s;
cin>>s;
int nxt1[n+5]={0},nxt2[n+5]={0};
for(int i=n-2;i>=0;i--)
{
if(s[i]==s[i+1])nxt1[i]=nxt1[i+1];
if(s[i]!=s[i+1])nxt1[i]=i+1;
if(i+2<n && s[i]==s[i+2])nxt2[i]=nxt2[i+2];
if(i+2<n && s[i]!=s[i+2])nxt2[i]=i+2;
}
auto v=manacher(s);
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
int ans=0;
int len=r-l+1;
if(nxt1[l-1]<=r-1 && nxt1[l-1]!=0)
{
if(len%2==1)ans+=(2+len/2*2)*(len/2)/2;
else ans+=(2+len/2*2)*(len/2)/2-len;
}
if(nxt2[l-1]<=r-1 && nxt2[l-1]!=0 || nxt2[l]<=r-1 && nxt2[l]!=0)
{
if(len%2==0)ans+=(1+(len-1)/2*2+1)*((len+1)/2)/2-1;
else ans+=(1+(len-1)/2*2+1)*((len+1)/2)/2-len-1;
}
if(v[l+r-2]<len)ans+=len;
cout<<ans<<endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
微信
支付宝
