Articles12
Tags2
Categories0

CodeForces Round 615(Div.3)


第一场AK的div3,写一篇题解纪念一下。

传送门

注:题解比较简单,没有题意,大家笑一笑就好^^_

整体难度 A<B<C<D<F<E(大概吧

A. Collecting Coins

先把A,B,C填平了,再看看剩下的n能否整除3.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
ll a[3];
void solve(){
    ll n;scanf("%lld%lld%lld%lld",&a[0],&a[1],&a[2],&n);
    sort(a,a+3);
    ll k=a[2]-a[0]+a[2]-a[1];
    if(n<k||(n-k)%3){
        printf("NO\n");
    }else printf("YES\n");
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
}

B. Collecting Packages

根据题意可知,能先往右边走就先往右边走,然后再上去,根据高度从低到高排序然后模拟即可.

如果排完序还出现往左下走的情况就说明不合法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
struct node{
    int x,y;
}a[1010];
int cmp(node p,node q){
    return p.x<q.x||p.x==q.x&&p.y<q.y;
}
vector<int>v;
void solve(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }sort(a+1,a+n+1,cmp);
    v.clear();int x=0,y=0;
    for(int i=1;i<=n;i++){
        if(a[i].x<x||a[i].y<y){
            printf("NO\n");return;
        }for(int j=1;j<=a[i].x-x;j++){
            v.push_back(1);
        }for(int j=1;j<=a[i].y-y;j++){
            v.push_back(2);
        }x=a[i].x;y=a[i].y;
    }printf("YES\n");
    for(int i=0;i<v.size();i++){
        if(v[i]==1) printf("R");
        else printf("U");
    }printf("\n");
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
} 

C. Product of Three Numbers

没啥好说的,能判断3个是不同的就好了,乱搞题。

这里推荐施老师的代码(@syh0313 简洁清楚 我的就比较丢人

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int T,n,a,b;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n); a=-1; b=-1;
        for (int i=2;1ll*i*i<=n;i++) if (n%i==0) {a=i; n/=i; break;}
        for (int i=2;1ll*i*i<=n;i++) if (n%i==0 && i!=a && i!=n/i) {b=i; n/=i; break;}
        if (a==-1 || b==-1) printf("NO\n");
        else printf("YES\n%d %d %d\n",a,b,n);
    }
    return 0;
}

D. MEX maximizing

这道题看起来比较吓人,代码其实就10行.可以发现答案是单调递增的,我们可以把所有数先减到不能再减,即取模:a[i]=a[i]%x;再把当前答案也取个模,就能轻松模拟了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+50;
int vis[maxn];
int main(){
    int now=0;memset(vis,0,sizeof(vis));
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){int x;
        scanf("%d",&x);vis[x%k]++;
        int y=now/k;
        while(vis[now%k]>=y+1){
            now++;y=now/k;
        }printf("%d\n",now);
    }
} 

E. Obtain a Permutation

卡了很久的一道构造题,能发现移动的方式其实很有限,所以可以每列单独考虑,对每一列来说,要么全部替换,要么先移位再替换,移位的思路:对于每一个符合当列要求(即v [i] [j] %m==j%m)的数,算出离它应该呆的位置的距离x,然后用一个数组记录下来,即vis[x]++;最后答案就是ans[j]=min(ans[j],i+(n-vis[i]));

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
vector<int>v[maxn];
int ans[maxn];int vis[maxn];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        v[i].push_back(0);
        for(int j=1;j<=m;j++){int x;
            scanf("%d",&x);v[i].push_back(x);
        }
    }int res=0;
    for(int j=1;j<=m;j++){
        ans[j]=0;
        for(int i=1;i<=n;i++){
            if(v[i][j]!=(i-1)*m+j){
                ans[j]++;
            }
        }
        for(int i=0;i<n;i++) vis[i]=0;
        for(int i=1;i<=n;i++){
            if(v[i][j]%m==j%m){
                int now=(v[i][j]-j)/m;now++;
                if(now>n) continue;
                vis[(i-now+n)%n]++; 
            }
        }for(int i=0;i<n;i++){
            ans[j]=min(ans[j],i+(n-vis[i]));
        }res+=ans[j];
    } printf("%d\n",res);
} 

F. Three Paths on a Tree

先找出一条直径,直径的两端点就是第一二个点。再在直径经过的每一个点上深搜,搜到的那个最远的点就是第三个点

又是4个dfs(

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
vector<int>g[maxn];
int vis[maxn];int ss,tt,mxpos;
int ans=0,th;
void dfs1(int now,int fa,int pos){
    if(pos>=mxpos){
        ss=now;mxpos=pos;
    }for(int i=0;i<g[now].size();i++){
        int e=g[now][i];
        if(e==fa) continue;dfs1(e,now,pos+1);
    }
}void dfs2(int now,int fa,int pos){
    if(pos>=mxpos){
        tt=now;mxpos=pos;
    }for(int i=0;i<g[now].size();i++){
        int e=g[now][i];
        if(e==fa) continue;dfs2(e,now,pos+1);
    }
}int dfs3(int now,int fa){
    int flag=0;
    if(now==tt) flag=1;
    for(int i=0;i<g[now].size();i++){
        int e=g[now][i];
        if(e==fa) continue;if(dfs3(e,now)){
            vis[now]=1;flag=1;
        }
    }
    return flag;
}void dfs4(int now,int fa,int pos){
    if(pos>ans){
        ans=pos;th=now;
    }for(int i=0;i<g[now].size();i++){
        int e=g[now][i];
        if(e==fa||vis[e]) continue;
        dfs4(e,now,pos+1);
    }
}
int main(){
    int n;scanf("%d",&n);memset(vis,0,sizeof(vis));
    for(int i=1;i<=n-1;i++){
        int a,b;scanf("%d%d",&a,&b);
        g[a].push_back(b);g[b].push_back(a);
    }mxpos=0;dfs1(1,-1,0);mxpos=0;dfs2(ss,-1,0);vis[ss]=vis[tt]=1;
    dfs3(ss,-1);
    for(int i=1;i<=n;i++){
        if(vis[i]&&i!=ss&&i!=tt){
            th=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i]){
            dfs4(i,-1,0);
        }
    }printf("%d\n%d %d %d",mxpos+ans,ss,tt,th);
} 

还要继续努力 qwq

Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2020/01/23/CodeForces%20Round%20615(Div.3)/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可