A . Three swimmers
题解
找p离a,b,c倍数最近的那个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
long long mod=1000000007;
long long ans,a,b,c,p;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld%lld",&p,&a,&b,&c);
ans=a-((p-1)%a+1);
ans=min(ans,b-((p-1)%b+1));
ans=min(ans,c-((p-1)%c+1));
printf("%lld\n",ans);
}
return 0;
}
|
B . Card Deck
题解：
使值大的尽量在底下，每次取都取到当前剩的最大的一个
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
| #include<bits/stdc++.h>
using namespace std;
long long mod=1000000007;
int const maxn=1e5+7;
typedef long long ll;
ll n,a[maxn],ne[maxn],ans;
int p[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
p[1]=1;
for(int i=2;i<=n;i++){
if(a[i]>a[p[i-1]])p[i]=i;
else p[i]=p[i-1];
}
int qwq=n,tot=0;
while(qwq>0){
for(int i=p[qwq];i<=qwq;i++){
ne[++tot]=a[i];
}
qwq=p[qwq]-1;
}
for(int i=1;i<n;i++){
printf("%lld ",ne[i]);
}
printf("%lld\n",ne[n]);
}
return 0;
}
|
C . Maximum width
题意：
给出长度为n的字符串s，长度为m的字符串t
求构造一个长度m递增数列p， \[1 \leq p_{1} \le p_{2} \le \ldots \le p_{m} \leq n\] 满足 \(s_{pi} = t_i\) , p的宽度定义为 \(\max _{1 \leq i<m}\left(p_{i+1}-p_{i}\right)\)，即最大的相 邻的差
保证一定能构造出一组p，求p的最大宽度
数据范围：
\[\left( 2 \leq m \leq n \leq 2 \cdot 10^{5}\right)\]
题解：
使相邻的pi 和 pi+1 差最大，就要使pi取尽量靠左的s中的位置，pi+1取尽量靠右的s中的位置
为了维护p递增，先从左向右扫一遍维护出最小值pl，再从右向左扫一遍维护出最大值pr，再扫一遍枚举分界点 \[ans=max \left( pr[i+1]-pl[i] \right)\]
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 const maxn2=2e5+7;
int l[maxn2],r[maxn2],n,m;
string s1,s2;
int main(){
scanf("%d%d",&n,&m);
cin>>s1>>s2;
int ans=-maxn2;
int qwq=0;
for(int j=0;j<m;j++){
while(s1[qwq]!=s2[j])qwq++;
l[j]=qwq;
qwq++;
}
qwq=n-1;
for(int j=m-1;j>=0;j--){
while(s1[qwq]!=s2[j])qwq--;
r[j]=qwq;
qwq--;
}
for(int i=0;i<m-1;i++){
ans=max(r[i+1]-l[i],ans);
}
printf("%d\n",ans);
return 0;
}
|
比赛时：
我居然忘记了p是递增的，直接求了pi+1在s中的最右减去，pi在s中的最左。。。。
假题意代师。。。
D . Genius's Gambit
题意：
构造两个含a个0，b个1的二进制数x,y(x>=y)，两者之差的二进制数含k个1。
数据范围：\[(0≤a, 1≤b; 0≤k≤a+b≤2⋅10^5)\]
题解：
两个错位的1和0，中间全部相同，能减出一组1，例如：
\[11110000-\\01110001=\\01111111\]
利用这个规律可以构造出所有a+b-2>=k （k,a>=1,b>=2）的情况
特判：只有0个0的，或者1个1（因为不允许前导零），不能构造出1。k=0时一定能满足。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| a,b,k=map(int,input().split())
if(k==0):
s='1'*b+'0'*a
print("Yes\n"+s+"\n"+s)
elif(a==0):
print("No");
else:
if a+b-2<k or b==1:
print("No")
else:
s='1'*(b-1)+'0'*(a-1)
print("Yes")
print(s[:a+b-k-1]+'1'+s[a+b-k-1:]+'0')
print(s[:a+b-k-1]+'0'+s[a+b-k-1:]+'1')
|
比赛时：
没有想到只要错位中间一样就可以了。。以为要分0和1讨论
没有想到k=0一定满足
没有注意到1个1，或者0个0都不能构造出来。
比完赛简直是面向样例编程。。。
E . Almost Fault-Tolerant Database
题意：
n个m长的数组，
构造一个数组，满足它改变最多两个值可以得到任意一个给出的n个数组
不存在输出no
数据范围：
\[(2 \leq n ; 1 \leq m ; n \cdot m \leq 250000)\]
题解：
网上看到的。枚举构造
假设以第一个数组为模板，跟后面的作对比
有数组跟它>4个不同，则无解
所有的<=两个不同，则直接输出第一个数组
有4个不同，则第一个数组至少要改2位，枚举改的两位和改的值
有3个不同，如果有一位所有3个的都有且为同一个值，则改这一位，否则等同于第三种情况，枚举改哪两位哪个值，