前言
就只做出了 \(A,B,C,D\) 是不是很弱？
A.Chess For Three
A，B，C 三人下棋，A和B先下，每次下完棋之后由现在观战的人（例如第一局就由C）代替下输的人。 每次输入一个数表示谁赢了（A是1，B是2，C是3），如果每一次输入的赢家都不是当时旁观者，则输出 “YES”，否则输出“NO”。
预计难度普及-。
直接模拟即可。
#include <bits/stdc++.h>
using namespace std;
int n;
int ret=0;
signed main(){
cin>>n;
ret=3;
for(int i=1;i<=n;i++){
int v;
cin>>v;if(v==ret){
cout<<"NO";
return 0;
}
if(ret==1){
ret=5-v;
}
else if(ret==2){
ret=4-v;
}
else{
ret=3-v;
}
}
cout<<"YES";
return 0;
}
B.Beautiful Divisors
给定n，求n最大的因数s，使s能表示成 \((2^k-1)*(2^{k-1})\) 的形式
预计难度普及-。
暴力枚举 \(O(n\log n)\) 可过。
#include <bits/stdc++.h>
using namespace std;
int n;
int ret=1;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
if(!(n%i)){
for(int k=1;(pow(2,k)-1)*(pow(2,k-1))<=i;k++){
if((pow(2,k)-1)*(pow(2,k-1))==i){
ret=i;
break;
}
}
}
}
cout<<ret;
}
C.Rumor
有n个人，其中有m对朋友，现在你有一个秘密你想告诉所有人，第i个人愿意出价a[i]买你的秘密，获得秘密的人会免费告诉它的所有朋友（他朋友的朋友也会免费知道），现在他们想出最少的价钱买秘密，那么你最少能得到多少钱？
预计难度普及。（洛谷难度提高+，有点虚高）
考虑并查集。显然，如果谁的秘密低，就当作并查集的根节点，朋友和朋友之间连边，这样子只要买根节点就可以了。
时间复杂度 \(O(n+m\log n)\)。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005];
namespace UnionFind{
int fa[1000005];
int find(int x){
if(fa[x]==x)return fa[x];
else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
if(a[find(x)]>a[find(y)]){
fa[find(x)]=find(y);
}
else{
fa[find(y)]=fa[find(x)];
}
}
}
int n,m;
int isroot[1000005];
int ret=0;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
UnionFind::fa[i]=i;
}
for(int i=1,liwenx,daniel2020;i<=m;i++){
cin>>liwenx>>daniel2020;
UnionFind::merge(liwenx,daniel2020);
}
for(int i=1;i<=n;i++){
int rt=UnionFind::find(i);
if(!isroot[rt]){
ret+=a[rt];
isroot[rt]=1;
}
}
cout<<ret;
return 0;
}
D.Credit Card
Recenlty Luba有一张信用卡可用，一开始金额为0，每天早上可以去充任意数量的钱。到了晚上，银行会对信用卡进行一次操作，操作有三种操作。 1.如果a[i]>0，银行会给卡充入a[i]元。 2.如果a[i]<0 银行从卡中扣除a[i]元。 3.如果a[i]=0 银行会查询卡里的金额。 有两条规则，如果违背信用卡就会被冻结。 1.信用卡里的金额不能大于d。 2.当银行查询卡里的金额时，金额不能为负。 Recenlty Luba想知道最少去充多少次钱，可以使她在接下来的n天里信用卡不被冻结。
预计难度提高。
这道题考虑贪心。维护最大和最小，如果最小的都大于 \(t\) 显然无解。如果最大都要充钱那么计数器++，最后输出计数器。
时间复杂度 \(O(n)\)。
代码：
#include <bits/stdc++.h>
#define NO_SOLVE cout<<-1;return 0
using namespace std;
int n,d;
int least,most;
int now;
int ans;
signed main(){
cin>>n>>d;
for(int i=1;i<=n;i++){
cin>>now;
if(now!=0){
least+=now;
most+=now;
if(least>d){
NO_SOLVE;
}
most=min(most,d);
}
else{
least=max(least,0);
if(most<0){
ans++;
most=d;
}
}
}
cout<<ans<<'\n';
return 0;
}