TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) ABCD

A

题意：

• 有一个开关，每天s点开，t点关（可能在第2天或第n天），判断x点时开着还是关着。

思路：

• 按照是否需要隔夜分个类。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int s, t, x;
    cin>>s>>t>>x;
    if(s<t){
        if(x>=s&&x<t)cout<<"Yes\n";
        else cout<<"No\n";
    }else{
        if(x>=t&&x<s)cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}

B、

题意：

• 高桥有n个朋友，每个朋友会向a[i]分享秘密，最开始s知道了秘密，求最后多少人会知道秘密。

思路：

• 开个set维护知道秘密的人，链式遍历即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
int main(){
    int n, s;
    cin>>n>>s;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    set<int>se;
    int now = s;
    for(int i = 1; i <= n; i++){
        if(i!=1 && now==s)break;
        se.insert(now);
        now = a[now];
    }
    cout<<se.size()<<"\n";
    return 0;
}

C、

题意：

• n个学生参加为期4天的考试，每天300分，已知前三天分数。
• 求最后一天考完第i个学生能否到达前k名，名次定义为比他分数高的人数+1。

思路：

• 贪心策略是第i个学生最后一天300分，其他人都0分。
• 把前三天的总分从大到小排个序，每次去二分第i个学生的排名位置，判断是否在k名内。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn];
bool cmp(int x, int y){return x>y;}
int main(){
    int n, k;  cin>>n>>k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 3; j++){
            int x;  cin>>x;  a[i] += x;
        }
        b[i] = a[i];
    }
    sort(b+1,b+n+1,cmp);
    for(int i = 1; i <= n; i++){
        int p = lower_bound(b+1,b+n+1,a[i]+300,greater<int>())-b;
        if(p<=k || a[i]+300>=1200)cout<<"Yes\n";
        else cout<<"No\n";
        // if(a[i]+300>=b[k])cout<<"Yes\n";
        // else cout<<"No\n";
    }
    return 0;
}

D、

题意：

• 初始一个空序列 a[0]到a[2^20]，默认都是-1。
• Q个操作，操作1找到a[x]往后第一个不是-1的位置，改成时间戳。操作2询问a[x]的值。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (1<<20)-1;

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}

LL v[maxn+10];

int main(){
    init(maxn);
    memset(v,-1,sizeof(v));
    int q;  cin>>q;
    while(q--){
        LL op, x;  cin>>op>>x;
        if(op==1){
            int i = find(x&maxn);
            v[i] = x;
            fa[i] = find((i+1)&maxn);
        }else{
            cout<<v[x&maxn]<<"\n";
        }
    }
    return 0;
}