A if语句判断

如果给定的字符串是 ARC 就输出 ABC，否则输出 ARC。

#include<bits/stdc++.h>
using namespace std;
string s; 
int main(){
    cin>>s;
    if(s=="ABC")puts("ARC");
    else puts("ABC");
    return 0;
}

B 数组记录+循环

遍历 $A_1,A_2\dots,A_K$ 这些序列，如果出现了数字 $i$，就用 $num$ 数组记录下来。

最后遍历一遍 $num$ 数组，输出有多少个数没出现过。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,cnt;
int num[MAXN];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&cnt);
        for(int j=1;j<=cnt;j++){
            int a;
            scanf("%d",&a);
            num[a]++;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(num[i]==0)cnt++;
    }
    printf("%d",cnt);
    return 0;
}

C 简单遍历图/结构体排序

Solution 1

这道题很简单，会图论的同学可以直接建图遍历一遍即可。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*f;
}
const int MAXN=1e5+5,MR=2e5+5;
struct edge{
    int from,to,nxt;//链式前向星，用nxt记录下一条边
}e[MR];
int head[MAXN],a[MAXN],cnt;
void add_edge(int u,int v){
    e[++cnt]={u,v,head[u]};//建边
    head[u]=cnt;
}
int n,m;
bool check(int x){
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;//遍历图
        if(a[v]>=a[x])return false;
    }
    return true;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans+=check(i);
    printf("%d",ans);
    return 0;
}

Solution 2

不会图论，怎么办？

可以把所有的双向边存到结构体里面， $edge(x,y)$ 表示从 $x$ 到 $y$ 的一条边。

按照 $x$ 排序后的结构体数组可以直接判断然后解决答案。

时间复杂度 $O(m\log m)$。

#include<bits/stdc++.h>
using namespace std;
int read(){//快读，入门同学可以忽略此函数
    int s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*f;
}
const int MR=2e5+5,MAXN=1e5+5;
int n,m,cnt,ans;
struct edge{//结构体
    int x,y;
}e[MR];
int a[MAXN],is[MAXN];
bool cmp(edge p,edge q){//结构体排序
    return p.x<q.x;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),is[i]=1;
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        e[++cnt]={u,v};//添加边
        e[++cnt]={v,u};
    }
    sort(e+1,e+cnt+1,cmp);
    int h=0,flag=1;
    for(int i=1;i<=cnt+1;i++){
        if(e[i].x!=h){//某一个元素相邻的节点都遍历完了
//          printf("%d %d\n",h,flag);
            is[h]=flag;
            flag=1;
            h=e[i].x;
        }
        if(a[e[i].y]>=a[h])flag=0;//不符要求，flag=0
    }
    for(int i=1;i<=n;i++)ans+=is[i];//统计个数
    printf("%d",ans);
    return 0;
}

D 简单for循环枚举

有些同学看了题面以后，哇！ $x\le 10^{12}$，没法做了！

其实这个题目很简单，我们可以通过简单的运算得到：$^5\sqrt x \le 200$。

所以我们大胆猜想，从 $-200$ 到 $200$ 肯定有答案啊。

然后就 AC 了。

时间复杂度 $O(400^2)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x;
signed main(){
    scanf("%lld",x);
    for(int i=-200;i<=200;i++){
        for(int j=-200;j<=200;j++){
            if(i*i*i*i*i-j*j*j*j*j==x){//判断条件
                printf("%lld %lld",i,j);
                return 0;
            }
        }
    }
    return 0;
}

E 式子变换

首先根据题目大意，可以列出下面的式子：

$a_i-a_j=j-i$

变换一下得：

$a_i-i=a_j+j$

我们可以枚举 $i$，所以 $i,a_i$ 都是已知的。

此时我们可以用一个 map 在循环过程中把 $a_i-i$ 记录下来，找到与它相等的 $a_i+i$，把它们的数量记录下来。

注意注意！！！必须开 long long！！！

时间复杂度 $O(n\log a_i)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5;
int n,ans,a[MAXN];
map<int,int>num;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)ans+=num[i-a[i]],num[a[i]+i]++;
    printf("%lld",ans);
    return 0;
}

F 贪心+抽屉原理

贪心的思路很好想：每一次选的两个数肯定是大的减少，小的增加。

但是如果现在减了大的，下一次操作可能不够减。

所以我们可以考虑一个时间复杂度 $O(n)$ 的离线做法。

根据抽屉原理可以知道，相邻的两次操作中，必然有一个被操作的元素相同。

在发现两次选择中数相同的时候，进行分类讨论：

若下一次操作与本次相同，就在这一次进行任意一个操作，下一次进行相反的操作，这样就使现在的状态与原来相同。

否则我们就选择与下一次重复的的那个字符这次加，保证下次可以减（即使下一次另一个不是 00 也不会出问题）。

#include<bits/stdc++.h>
using namespace std;
int q,a,b,c;
string k[100005];
char ans[100005];
int main(){
    scanf("%d%d%d%d",&q,&a,&b,&c);
    if(!a&&!b&&!c){//全部为零，直接输出NO
        puts("No");
        return 0;
    }
    for(int i=1;i<=q;i++)cin>>k[i];
    for(int i=1;i<=q;i++){
        if(k[i]=="AB"){//第一种情况，后面两种类似
            if(a>b)a--,b++,ans[i]='B';//贪心地操作
            else if(a==b&&i<q){
                if(!a){//如果全部为0就无法操作下去
                    puts("No");
                    return 0;
                }
                if(k[i+1]=="AB")ans[i]='A',ans[i+1]='B';//连续两次操作的序列相同
                else if(k[i+1]=="AC")b--,c++,ans[i]='A',ans[i+1]='C';//操作AC和AB
                else a--,c++,ans[i]='B',ans[i+1]='C';//操作BC和AB
                i++;
            }
            else b--,a++,ans[i]='A';//最后一种情况
        }
        else if(k[i]=="AC"){
            if(a>c)a--,c++,ans[i]='C';
            else if(a==c&&i<q){
                if(!a){
                    puts("No");
                    return 0;
                }
                if(k[i+1]=="AB")c--,b++,ans[i]='A',ans[i+1]='B';
                else if(k[i+1]=="AC")ans[i]='A',ans[i+1]='C';
                else a--,b++,ans[i]='C',ans[i+1]='B';
                i++;
            }
            else c--,a++,ans[i]='A';
        }
        else{
            if(b>c)b--,c++,ans[i]='C';
            else if(b==c&&i<q){
                if(!b){
                    puts("No");
                    return 0;
                }
                if(k[i+1]=="AB")c--,a++,ans[i]='B',ans[i+1]='A';
                else if(k[i+1]=="AC")b--,a++,ans[i]='C',ans[i+1]='A';
                else ans[i]='B',ans[i+1]='C';
                i++;
            }
            else c--,b++,ans[i]='B';
        }
        if(a<0||b<0||c<0){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    for(int i=1;i<=q;i++)printf("%c\n",ans[i]);
    return 0;
}