Codeforces Round #828 (Div. 3)-赛后总结
Dashboard - Codeforces Round #828 (Div. 3) - Codeforces
打完比赛的晚上美滋滋的看着解出来的六道题，心想着能够加上一百多分。一觉醒来眼睁睁看着E1E2被hack掉，排名从前一百掉到快两千，落差感是很大的。但不管怎么说也算是有些收获。
总结就是
1. CF的原始数据仅仅是全部数据的冰山一角，赛时过不代表一定过。
2. 不要去想算法，不要去想算法，否则一定会被牵制住思维！
Problem - A - Codeforces
给定n个数字，n位字符串，原始操作是给一种数字涂上相同的字符。
判断是否数字相同时对应的字母也是相同。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[100];
string s;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>s;
s=" "+s;
int flag=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i]==a[j])
{
if(s[i]!=s[j])
{
flag=1;
}
}
}
}
if(flag)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
return 0;
}Problem - B - Codeforces
B. Even-Odd Increments
给定0 1操作，0代表给全部偶数加上 y 1代表给全部奇数加上y
是一道模拟题，只需要维护奇数个数，偶数个数，奇数和，偶数和即可，y的奇偶使得数列中的奇数偶数性质得到不断变换或者不变。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[100000+10];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n>>q;
ll cntji=0,cntou=0,sumji=0,sumou=0;
for(int i=1; i<=n; i++)
{
cin>>a[i];
if(a[i]&1)
{
cntji++;
sumji+=a[i];
}
else
{
cntou++;
sumou+=a[i];
}
}
while(q--)
{
ll x,y;
cin>>x>>y;
if(x==0)
{
if(y&1)
{
sumou+=cntou*y;
sumji+=sumou;
sumou=0;
cntji+=cntou;
cntou=0;
}
else
{
sumou+=cntou*y;
}
}
else
{
if(y&1)
{
sumji+=cntji*y;
sumou+=sumji;
sumji=0;
cntou+=cntji;
cntji=0;
}
else
{
sumji+=cntji*y;
}
}
cout<<sumji+sumou<<endl;
}
}
return 0;
}
Problem - C - Codeforces
C. Traffic Light
给定红绿灯与灯的字符串序列（可以循环），找到给定颜色最远的绿灯。首先绿灯一定是0
红黄的话只需要将字符串扩大一倍，开启后缀DP，倒叙遍历求出距离位置i的最近绿灯即可。然后我们统计最大值。
不少人赛后被HACK，是因为赛时数据极水，暴力n2都能过，然而赛时数据仅仅是冰山一角
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int dp[200000*2+2];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
char r;
cin>>n>>r;
string s;
cin>>s;
if(r=='g')
{
cout<<0<<endl;
}
else
{
s=s+s;
dp[2*n]=1e9;
for(int i=2*n-1;i>=0;i--)
{
if(s[i]=='g')
{
dp[i]=i;
}
else
{
dp[i]=dp[i+1];
}
}
int ans=0;
for(int i=0;i<n;i++)
{
if(s[i]==r)
{
ans=max(ans,dp[i]-i);
}
}
cout<<ans<<'\n';
}
}
return 0;
}Problem - D - Codeforces
原序列乘积能被2^n整除的数学表示就是原序列包含了超过n个2，如果原序列已经包含了超过n个2，那么一定可以且耗费是0,。接下来就是需要我们人工添加下标的操作了，既然要求次数最少，干脆on遍历全部下标，求出来其中含有2的个数。排序贪心取即可
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll a[100000*2+10];
int tempfuck[100000*2+10];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int cnt=0;
for(int i=1; i<=n; i++)
{
cin>>a[i];
ll tempx=a[i];
while(tempx&&tempx%2==0)
{
cnt++;
tempx/=2;
}
}
if(cnt>=n)
{
cout<<0<<endl;
}
else
{
int temp=0,fuck=0,ans=0;
for(int i=n; i>=1; i--)
{
tempfuck[i]=0;
temp=0;
if(i%2)
continue;
int tempx=i;
while(tempx&&tempx%2==0)
{
temp++;
tempx/=2;
}
tempfuck[i]=temp;
}
sort(tempfuck+1,tempfuck+1+n,cmp);
temp=0;
for(int i=1; i<=n; i++)
{
temp+=tempfuck[i];
if(temp+cnt>=n)
{
ans=i;
break;
}
}
if(temp+cnt>=n)
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
}
}
return 0;
}Problem - E1 - Codeforces
对a*b进行因数拆分，我们求出来一个 i 一个 a*b/i 。只需要包含这两个部分，我们的x,y就一定能够满足对a*b的整除。而我们根据 a b可以直接定位出来第一个大于a且整除i的数，作为x.另一个配对的因数作为y即可。时间复杂度也就 sqrt(a*b)，是一定不会被卡掉的。
赛时看到4秒还以为可以胡搞，于是就敲了一个枚举倍数的暴力。。。数据很水跑了31ms...赛后被卡到4s+...
# include<iostream>
using namespace std;
typedef long long int ll;
ll a,b,c,d,ans1,ans2;
bool check(ll x, ll y)
{
ll tempans1=(a+x)/x*x;
ll tempans2=(b+y)/y*y;
if(a<tempans1&&tempans1<=c&&tempans2>b&&tempans2<=d)
{
ans1=tempans1;
ans2=tempans2;
return 1;
}
return 0;
}
int main ()
{
int t;
cin>>t;
while(t--)
{
cin>>a>>b>>c>>d;
ans1=-1,ans2=-1;
int flag=0;
for(ll i=1;i*i<=a*b;i++)
{
if(a*b%i==0)
{
if(check(i,a*b/i))
{
flag=1;
break;
}
if(check(a*b/i,i))
{
flag=1;
break;
}
}
}
if(flag)
{
if(ans1>a&&ans1<=c&&ans2>b&&ans2<=d)
{
cout<<ans1<<" "<<ans2<<endl;
}
else
{
cout<<ans2<<" "<<ans1<<endl;
}
}
else
{
cout<<-1<<" "<<-1<<endl;
}
}
return 0;
}Problem - E2 - Codeforces
E1是对ab进行了因数分解，如果E2再进行分解可以发现明显的超时。这时完全可以对a,b单独进行分解，然后我们不难发现因数其实是很少的，暴力枚举两个因数的组合当做x的基底，另外一个只需要除以这个基底。这个暴力枚举的过程其实就等价于我们对a*b拆分因数的过程。时间复杂度很低，不会被卡。
赛时我想到了一个类似的，那就是枚举a,b的全部质因子，枚举每种搭配，枚举倍数，然而这种方法一旦倍数很多时是很容易被卡掉的。
# include<iostream>
# include<vector>
using namespace std;
typedef long long int ll;
vector<ll>x,y;
int main ()
{
int t;
cin>>t;
while(t--)
{
ll a,b,c,d;
cin>>a>>b>>c>>d;
x.clear();
y.clear();
ll tempx=a,tempy=b;
for(ll i=1;i*i<=a;i++)
{
if(a%i==0)
{
x.push_back(i);
x.push_back(a/i);
}
}
for(ll i=1;i*i<=b;i++)
{
if(b%i==0)
{
y.push_back(i);
y.push_back(b/i);
}
}
ll ans1=-1,ans2=-1;
int flag=0;
for(auto it1:x)
{
for(auto it2:y)
{
ll now=it1*it2;
ll temp=a*b/now;
tempx=(a+now)/now*now;
tempy=(b+temp)/temp*temp;
if(tempx>a&&tempx<=c&&tempy>b&&tempy<=d)
{
ans1=tempx;
ans2=tempy;
flag=1;
break;
}
tempy=(b+now)/now*now;
tempx=(a+temp)/temp*temp;
if(tempx>a&&tempx<=c&&tempy>b&&tempy<=d)
{
ans1=tempx;
ans2=tempy;
flag=1;
break;
}
}
if(flag)
break;
}
if(flag)
{
if(a<ans1&&ans1<=c&&ans2>b&&ans2<=d)
{
cout<<ans1<<" "<<ans2<<endl;
}
else
{
cout<<ans2<<" "<<ans1<<endl;
}
}
else
{
cout<<-1<<" "<<-1<<endl;
}
}
return 0;
}