Codeforces Round 474 A-D 题解
960A Check the string
字符串满足abc按顺序排列且a的数量与c相同或者b的数量与c相同时候输出yes。
首先特判字符串首部肯定为a，后面每个字符的ascii值一定要大于等于前一个字符（不然不符合abc的顺序），扫描时记录下abc的个数，判断输出即可
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
| #include <iostream>
using namespace std;
int main()
{
string s;
int a=1,b=0,c=0,ans=0;
cin>>s;
int len = s.length();
if(s[0]!='a')
{
cout<<"NO"<<endl;
return 0;
}
for(int i=1; i<len; i++)
{
if(s[i]<s[i-1])
{
cout<<"NO"<<endl;
return 0;
}
if(s[i]=='a')
a++;
else if(s[i]=='b')
b++;
else if(s[i]=='c')
c++;
}
if(a==0''b==0''c==0)
cout<<"NO"<<endl;
else if(a==c''b==c)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}
|
960B Minimize the error
要使得上下两个数列差的平方和最小，而上下两个数组的操作可以相当于合并，所以K1和K2可以相加为同一个数。
我们使用一个优先队列维护上下两个数组的差，这样保证每次减去的都是数列中差值最大的。
只有让每个数平均的减小才能实现最后平方和最小，所以每次给队列首部最大的一个数减去1。
维护有限队列时，不能让其出现负数，负数的平方是大于0的但是负数会排在0之后，所以当优先队列顶部出现0的时候将其值改为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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1000+10;
long long x[maxn],y[maxn];
priority_queue<long long> q;
int main(){
int n,k1,k2;
cin >> n >> k1 >> k2;
while(!q.empty()) q.pop();
for(int i=0;i<n;i++)
cin >> x[i];
for(int i=0;i<n;i++){
cin >> y[i];
q.push(abs(x[i]-y[i]));
}
long long k = k1 + k2,temp;
while(k > 0){
if(q.top()>0)
temp = q.top() - 1;
else
temp = 1;
q.pop();
q.push(temp);
k--;
}
long long sum = 0;
while(!q.empty()){
sum += q.top() * q.top();
q.pop();
}
cout << sum << endl;
return 0;
}
|
960C Subsequence Counting
一个字符串有X个子串的最大值间区最小值大差一定小于等于D。
一个串有2^n-1个子串，我们就需要保证每个连续的字串差值尽可能的小，不难想到从1开始取，每次出现连续mid个相同的数，就会有2^mid-1个子串,每次减少mid值找到满足X剩余数量的mid值，构造即可，此题是special judge，所有有很多种构造方式。
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;
const int N = 10000+5;
long long x,d;
long long a[N];
int main()
{
cin>>x>>d;
long long l=0,i=0;
int mid=30;
while(x)
{
int t=pow(2,mid)-1;
while(t>x)
{
mid--;
t=pow(2,mid)-1;
}
x-=t;
for(int j=0; j<mid; j++)
a[l++]=d+i*d;
i++;
}
cout << l << endl;
for(int i=0; i<l-1; i++)
cout<<a[i]<<" ";
cout<<a[l-1]<<endl;
return 0;
}
|
960D Full Binary Trr Queries
使用数组维护每次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
44
45
46
47
48
49
50
51
52
53
54
| #include <bits/stdc++.h>
using namespace std;
const int N = 62;
long long a[N],b[N];
long long mod[N];
int main()
{
mod[0]=1;
for(int i=1;i<N;i++){
mod[i]=mod[i-1]*2;
}
int n,type;
cin>>n;
while(n--){
scanf("%d",&type);
if(type==1){
long long x,k;
scanf("%lld%lld",&x,&k);
int layer=log2(x);
a[layer]=(a[layer]+k+mod[N-1])%mod[layer];
}
if(type==2){
long long x,k;
scanf("%lld%lld",&x,&k);
int layer=log2(x);
k=(k+mod[N-1])%mod[layer];
for(int i=layer;i<62;i++){
a[i]=(a[i]+k*mod[i-layer])%mod[i];
}
}
if(type==3){
long long x;
scanf("%lld",&x);
int layer=log2(x);
if(x==1) {
printf("%lld\n",x);
continue;
}
printf("%lld ",x);
b[layer]=x+a[layer]-mod[layer];
for(int i=layer-1;i>=1;i--){
b[i]=(b[layer]/mod[layer-i]-a[i]+mod[i])%mod[i];
}
for(int i=layer-1;i>=1;i--){
printf("%lld ",mod[i]+b[i]);
}
printf("%lld\n",1+b[0]);
}
}
return 0;
}
|