CF 题解

Codeforces Round #579 (Div. 3)

链接：https://codeforces.com/contest/1203

2019年8月17日23:44:37

A. Circle of Students

题意：给你一个数组问你里面的值，如果是顺时针或逆时针连续，就输出YES，不连续输出NO
思路：很明显连续要n个才行，不连续只要有1个不满足就行。扫两遍，一遍判断顺时针，一遍判断逆时针。唯一一个跳跃的地方就是1到n，或者n到1的地方，处理好这个位置就好
细节：将数组从下标0开始存数，在取前后元素的时候，方便取模

#include <iostream>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
using namespace std;int q,n,a[205];int main()
{cin>>q;while(q--){cin>>n;rep(i,0,n-1)cin>>a[i];bool valid=true;rep(i,0,n-1){if((a[i%n]+1)%n!=a[(i+1)%n]%n){valid=false;break;}}if(valid){cout<<"YES\n";continue;}valid=true;rep(i,0,n-1){if(a[i]-1!=a[(i+1)%n]%n){valid=false;break;}}if(valid)cout<<"YES\n";elsecout<<"NO\n";	}  return 0;
}

B. Equal Rectangles

题意：给你4n根木棍，问能不能组成面积相等的n个矩形面积

思路：很明显，将木棍排完序后，先判断一下木棍是不是两两相等，然后再一前一后的取木棍组成矩形，判断面积是否相同即可

#include <iostream>
#include <algorithm>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
using namespace std;
const int maxn=1000+5,INF=0x3f3f3f3f;int q,n,a[maxn];int main()
{cin>>q;while(q--){cin>>n;rep(i,1,4*n)cin>>a[i];	sort(a+1,a+1+4*n);	bool valid=true;rep(i,1,2*n)if(a[i*2]!=a[i*2-1])valid=false;if(!valid){cout<<"NO\n";continue;}int l=1,r=4*n-1;int area=a[1]*a[4*n-1];while(l<r){if(area!=a[l]*a[r]){valid=false;break;}l+=2;r-=2;}if(valid)cout<<"YES\n";elsecout<<"NO\n";		} return 0;
}

C. Common Divisors

题意：给你n个整数，请你求出所有整除这n个整数的正整数的数量

思路：很明显就是让你求出n个数的最大公约数，然后求最大公约数的因子数，根据算数基本定理分解质因数，然后计算一下次数就好

细节：又被ll坑了

#include <iostream>
#include <algorithm>
#include <cstdio>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
const int maxn=4e5+5,INF=0x3f3f3f3f;int n;
ll a[maxn];
pair<ll,int> p[maxn];ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}int main()
{scanf("%d",&n);rep(i,1,n)scanf("%lld",&a[i]);ll GCD=a[1];rep(i,1,n)GCD=gcd(a[i],GCD);int k=0;for(ll i=2;i*i<=GCD;++i){if(GCD%i==0){	p[++k].first=i;while(GCD%i==0){			p[k].second++;GCD/=i;}}}if(GCD>1){p[++k].first=GCD;p[k].second=1;}ll ans=1;for(int i=1;i<=k;++i)ans*=(p[i].second+1);printf("%lld\n",ans);return 0;
}

D1. D2. Remove the Substring

题意：给定两个字符串S、T，其中T是S的子序列，问你在S中最长能够删除多长的子串，使得T仍然是S的子序列，输出这个S的长度

思路：答案就两种情况，一种是在序列T开头或者结尾的一串连续子串，还有一种是在序列T的前后两个字符之间。我们想要使得两个相邻的字符尽量远，其实就是一个是在S中从左往右第一次匹配，另一个是在S中从右往左第一次匹配。这样$R[i]-L[i-1]$就是两个相邻字符的最远距离了

#include <iostream>
using namespace std;
const int maxn=2e5+5,;string s,t;
int L[maxn],R[maxn];int main()
{cin>>s>>t;int n=s.size(),m=t.size();s='0'+s,t='0'+t;int k=1;for(int i=1;i<=n;++i){if(k<=m&&s[i]==t[k])L[k++]=i;}k=m;for(int i=n;i>=1;--i){if(k>=1&&s[i]==t[k])R[k--]=i;}int ans=max(L[1]-1,n-L[m]);ans=max(max(R[1]-1,n-R[m]),ans);for(int i=2;i<=m;++i)ans=max(R[i]-L[i-1]-1,ans);cout<<ans<<"\n";return 0;
}

E. Boxers

题意：有n个体重，每个人可以使自己的体重-1、不变、+1，当然体重不能为0。问最多能够选多少个体重不同的人

思路：一个体重可以放3个位置，从小到大遍历的话，优先放在前面的位置。如果3个位置都放满了，那么这个体重就得舍弃

细节：一开始题目读错了，读成了最大的体重连续的人数，服了

#include <iostream>
#include <algorithm>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
using namespace std;
const int maxn=150005;int n,a[maxn];
bool b[maxn];int main()
{cin>>n;b[0]=true;int ans=n;rep(i,1,n)cin>>a[i];sort(a+1,a+1+n);rep(i,1,n){int x=a[i];if(b[x-1]==false)b[x-1]=true;else if(b[x]==false)b[x]=true;else if(b[x+1]==false)b[x+1]=true;elseans--;			}cout<<ans<<"\n";return 0;
}

F2. Complete the Projects (hard version)

题意：给定 $n$ 个任务和初始能力值 $r$，每个任务需要达到 $a_i$ 的能力值。做完之后会获得 $b_i$ 的能力值（可以为负数）。问在能力值不出现负数的情况下，最多能够完成多少个任务。

思路：先分成两部分，$b_i\ge 0$的分在一起，按 $a_i$ 从小到大排序，不能取的时候就可以结束了。 $b_i$ 小于 $0$ 的那部分，按照 $a_i+b_i$ 从大到小排序。然后每次都取和最高的任务，把 $b_i$ 放入堆中，当后面能力值不足时，就把扣的最多的那个任务（$b_i$ 最小）的 $b_i$ 取消掉。

分析：为什么这样是成立的呢？因为 $b_i$ 小又比当前的任务，先进到队列中，说明了那个任务的门槛 $a_i$ 高，当时那么高的 $a_i$ 都进队了，那么我现在把那个任务替换成一个低门槛的也是成立的。这样反而可以有更大的能力值 $r$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define mp make_pair
#define ll long long
#define pb push_back
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define isZero(d)  (abs(d) < 1e-8)
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
const int mod=1e9+7;int n,r;
vector<pair<int,int> > a,b; int main()
{scanf("%d%d",&n,&r);rep(i,1,n){int x,y;scanf("%d %d",&x,&y);if(y>=0)a.pb(mp(x,y));elseb.pb(mp(x,y));}sort(a.begin(),a.end());int ans=0;for(auto it: a){if(r>=it.first){r+=it.second;ans++;}}sort(b.begin(),b.end(),[](pair<int,int> a,pair<int,int> b){return a.first+a.second>b.first+b.second;	});priority_queue<ll,vector<ll>,greater<ll> > pq;for(auto it: b){pq.push(it.second);if(r<it.first||r+it.second<0){r+=it.second;r-=pq.top();pq.pop();}			else r+=it.second;			}printf("%d\n",ans+(int)pq.size());return 0;
}

Codeforces Round #578 (Div. 2)

链接：https://codeforces.com/contest/1200

2019年8月12日16:13:27

A. Hotelier

细节：一共10个位置，L往右，R往左扫即可。一开始错误地维护了一个 l 、r ，服了

#include <iostream>
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
const int mod=1e9+7;
int n;
string s;int main()
{int d[15]={0};cin>>n>>s;for(int i=0;i<n;++i){if(s[i]=='L'){int j=0;while(d[j]==1)j++;d[j]=1;}else if(s[i]=='R'){int j=9;while(d[j]==1)j--;d[j]=1;}elsed[s[i]-'0']=0;}for(int i=0;i<=9;++i)cout<<d[i];cout<<"\n";return 0;
}

B. Block Adventure

思路：贪心、模拟，背包是无限大的，很明显，尽量把石头放在包，可以有更多的石头用来铺放。当前点，h[cur]的基准线就是$h[cur+1]-k$，高于基准线的都可以放到背包里面，低于基准线的需要从背包里面补。

细节：很明显，基准线不能低于0。比赛的时候，被这个点，坑了好久~~

#include <iostream>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
using namespace std;int n,m,k,t,h[150];int main()
{cin>>t;while(t--){cin>>n>>m>>k;rep(i,1,n)cin>>h[i];int cur=1;while(cur<n){int height=h[cur+1]-k;if(height<0)height=0;if(h[cur]+m<height)break;if(h[cur]>height)m+=h[cur]-height;if(h[cur]<height)m-=height-h[cur];cur++;}if(cur==n)cout<<"YES\n";elsecout<<"NO\n";}  return 0;
}

C. Round Corridor

思路：找到最大公约数GCD，意思是内圈和外圈都分成GCD份，每份的长度分别是n/GCD，m/GCD。然后计算两个点是不是落在同一份内，在同一份内就是共通的。

细节：比赛的时候采用的是一种找最小公倍数的方法，成功地WA在了39。原因是，两个1e18的数，找不到最小公倍数。很明显这种会爆longlong的做法，绝对是错的

#include <iostream>
#include <algorithm>
#include <cstdio>
#define ll long long
using namespace std;ll n,m,q,sx,sy,ex,ey;ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}int main()
{scanf("%lld %lld %lld",&n,&m,&q);ll GCD=gcd(n,m);ll x=n/GCD,y=m/GCD;while(q--){scanf("%lld %lld %lld %lld",&sx,&sy,&ex,&ey);if(sx==1)sy=(sy-1)/x;elsesy=(sy-1)/y;if(ex==1)ey=(ey-1)/x;elseey=(ey-1)/y;if(sy==ey)puts("YES");elseputs("NO");}return 0;
}

Educational Codeforces Round 70 (Rated for Div. 2)

链接：https://codeforces.com/contest/1202

A. You Are Given Two Binary Strings…

题意：给定A、B两个01字符串，B串可以左移k位，问最小的k几位，使得$A+B\times 2^k$翻转之后的字段序最小，A串的长度严格大于B串

思路：想要相加使得翻转之后的字典序最小，就是尽量用B串去消除A越低位的1，这样翻转后的字段序最小。也就是用B串最后一位的1，尽量去消除A中低位的1

#include <iostream>
using namespace std;
string A,B;int main()
{int T;cin>>T;while(T--){		cin>>A>>B;int pos=B.size()-1;int cnt=1;while(B[pos]=='0'){pos--;cnt++;}int ans=0;pos=A.size()-1;while(A[pos-cnt+1]=='0'){ans++;pos--;}	cout<<ans<<"\n";	}  return 0;
}

Codeforces Round #575 (Div. 3)

链接：https://codeforces.com/contest/1196

D2. RGB Substring (hard version)

题意：给定一个长度为n的字符串S，截出一个长度为k的字符串a，使a改变最少的字符数量，成为"RGBRGBRGB$\cdots$"的子串，问这个最少数量是多少？

写法一：分别用三个串"RGBRGBRGB$\cdots$"，“GBRGBRGBR$\cdots$”，"BRGBRGBRG$\cdots$"去做匹配，维护不同个数的前缀和，遍历统计答案

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn=2e5+5,INF=0x3f3f3f3f;
const int mod=1e9+7;int q,n,k,pref[3][maxn];
string s;
string a="RGB";int main()
{		cin>>q;while(q--){			cin>>n>>k>>s;				s="0"+s;for(int i=0;i<3;++i){for(int j=1;j<s.size();++j){if(s[j]!=a[(i+j)%3])pref[i][j]=1;elsepref[i][j]=0;pref[i][j]+=pref[i][j-1];}}int ans=INF;for(int i=0;i<3;++i)for(int j=1;j+k-1<s.size();++j)ans=min(ans,pref[i][j+k-1]-pref[i][j-1]);cout<<ans<<"\n";}  return 0;
}

写法二：在字符串S上维护一个长度为k的区间，推动区间往右移，更新答案

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn=2e5+5,INF=0x3f3f3f3f;
const int mod=1e9+7;int q,n,k;
string s;int solve(string a)
{int cnt=0;for(int i=0;i<k;++i)if(s[i]!=a[i%3])cnt++;int ans=cnt;for(int i=k;i<n;++i){if(s[i-k]!=a[(i-k)%3])cnt--;if(s[i]!=a[i%3])cnt++;ans=min(ans,cnt);}return ans;
}int main()
{		cin>>q;while(q--){			cin>>n>>k>>s;				cout<<min(min(solve("RGB"),solve("GBR")),solve("BRG"))<<"\n";}  return 0;
}