202199 CF question brushing training

Hits: 0

A – Three Friends
topic link
Ideas: 3 numbers can be selected as +1 or -1 or unchanged. Finally, the absolute value of the difference between the three is required to be the smallest after one operation. Two ideas:
1. From a mathematical point of view, consider 2 large and 1 small , 2 small and 1 large, etc. are considered.
2. The simplest idea: 3 loops 6 times to [traverse] all situations and take the minimum value.

# include  <bits/stdc++.h>
 using  namespace  std ;
 typedef  long  long ll;
 const  long  long inf= 233333333333333 ; //open enough 0x3f3f3f3f is not big enough 
int  main () {
    ll q, a, b, c;
    cin >> q;
    while(q--){
        ll ans=inf;
        scanf("%lld%lld%lld",&a,&b,&c);
        for(ll i=a-1; i<=a+1; i++){
            for(ll j=b-1; j<=b+1; j++){
                for(ll k=c-1; k<=c+1; k++){
                    if(ans>fabs(i-j)+fabs(j-k)+fabs(i-k)){
                        ans=abs(i-j)+abs(j-k)+abs(i-k);
                    }
                }
            }
        }
        printf("%lld\n",ans);   
    }
    return 0;
}

B – Polycarp Training
topic link
topic To the effect: an acmer can solve k questions on the k day, and he has a series of games. If there is no question in the remaining games on a day that is greater than the number of questions he can solve on that day, then he stops brushing the questions. Maximum number of days to ask questions

Idea: Sort the number of input game questions first, and then we traverse, because k is constantly refreshed, as long as we can’t find a larger k than the current one (the reason is that the order is sorted from small to large, and you don’t need to think about it anymore. Considered)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    int sum=0,k=1;
    for(int i=0;i<n;i++)
    {
        if(a[i]>=k)
        {
            sum++;
            k++;
        }
    }
    printf("%d\n",sum);
    return 0;
}

C – Yet Another Broken Keyboard question
link Idea: We can traverse it directly to find the continuity, but we must pay attention to the one that is directly connected to the end to be dealt with separately (this is a kind of idea that can be used for many questions).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[26];
int main(){
    int n, k;
    string s;
    char ch;
    cin >> n >> k;
    cin >> s;
    for(int i=0; i<k; i++){
        cin >> ch;
        vis[ch-'a']=true;
    }
    ll sum=0, ans=0;
    for(int i=0; i<s.size(); i++){
        if(vis[s[i]-'a']) ans++;
        else{
            sum+=((1+ans)*ans/2);
            ans=0;
        }
        if(vis[s[i]-'a']&&i==n-1){
            sum+=((1+ans)*ans/2);
            ans=0;
        }
    }
    cout << sum;
    return 0;
}

D – Snow Walking Robot question
link
It means not to let the robot go the same way, that is to say, the robot goes back to the origin in a circle.
Idea: We need to take the minimum of L and R and the minimum of U and D as the final number of steps to take. If it only contains L and R or U and D, then output 2.

#include <bits/stdc++.h>
using namespace std;
int l, r, u, d;
int q;
string s;
int main(){
    cin >> q;
    while(q--){
        cin >> s;
        l=0, r=0, u=0, d=0;
        for(int i=0; i<s.size(); i++){
            if(s[i]=='L') l++;
            if(s[i]=='R') r++;
            if(s[i]=='U') u++;
            if(s[i]=='D') d++;
        }
        int m=min(l,r), n=min(u,d);
        if(m>0&&n>0){
            printf("%d\n",m*2+n*2);
            for(int i=1; i<=m; i++) printf("L");
            for(int i=1; i<=n; i++) printf("U");
            for(int i=1; i<=m; i++) printf("R");
            for(int i=1; i<=n; i++) printf("D");
        }
        else{
            if(m>0) printf("2\nLR");
            else if(n>0) printf("2\nUD");
            else printf("0");
        }
        puts("");
    }
    return 0;
}

G – Cow and Snacks
topic link
Ideas: And search for ideas, constantly refresh the root node of each food with the find function, so as to find the smallest number of depressed people.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int fa[maxn];
int x, y;
int find(int u){
    if(fa[u]==u) return u;
    return fa[u]=find(fa[u]);
}
int main(){
    int n, k;
    cin >> n >> k;
    int sum=0;
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=k; i++){
        cin >> x >> y;
        x=find(x), y=find(y);
        if(x!=y) fa[x]=y;
        else sum++;
    }
    cout << sum;
    return 0;
}

F – Coffee Break
topic link
Idea: Priority queue simulation, let the smallest always be in the front, and use a structure, including the second rest, the rest day, and the position of the input itself

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, num, pos;
};
vector <node> v;
priority_queue <int,vector<int>,greater<int> > g;
bool cmp1(node a, node b){
    return a.x<b.x;
}
bool cmp2(node a, node b){
    return a.pos<b.pos;
}
int n, m, d;
int a;
int main(){
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1; i<=n; i++){
        scanf("%d",&a);
        v.push_back({a,0,i});
    }
    sort(v.begin(),v.end(),cmp1);
    int day=1;
    int ans=0;
    g.push(v[0].x);
    v[0].num=1;
    for(int i=1; i<v.size(); i++){
        int cnt=g.top();
        if(cnt+d>=v[i].x){
            day++;
            v[i].num=day;
            g.push(v[i].x);
        }
        else{
            g.push(v[i].x);
            v[i].num=v[ans].num;
            ans++;
            g.pop();
        }
    }
    sort(v.begin(),v.end(),cmp2);
    printf("%d\n%d",day,v[0].num);
    for(int i=1; i<v.size(); i++){
        printf(" %d",v[i].num);
    }
    return 0;
}

Leave a Reply

Your email address will not be published.