Codeforces Round #479 (Div. 3) 简要题解

题目链接http://codeforces.com/contest/977

A

  • 按题意模拟即可
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1000+10;
int n,k;
int main(){
    cin>>n>>k;
    for (int i=1;i<=k;i++){
        if (n%10==0) n/=10;
        else n--;
    }
    cout<<n<<endl;
    return 0;
}

B

  • 暴力枚举所有子串即可
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1000+10;
int n;
string s;
int main(){
    read(n);
    cin>>s;
    string ans="";
    int res=0;
    for (int i=0;i+1<n;i++){
        string t=s.substr(i,2);
        int cnt=0;
        for (int j=0;j<n;j++){
            if (s.substr(j,2)==t) cnt++;
        }
        if (res==0){
            res=cnt;
            ans=t;
        }
        else if (res<cnt){
            res=cnt;
            ans=t;
        }
    }
    cout<<ans<<endl;
    return 0;
}

C

  • 将数组排序以后二分答案即可
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2e5+10;
int n,i,k,a[N];
int check(int x){
    int cnt=0;
    for (int i=1;i<=n;i++){
        if (a[i]>x) break;
        cnt++;
    }
    return cnt;
}
int main(){
    read(n),read(k);
    for (i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+1+n);
    int l=1,r=(int)1e9,ans=-1;
    while (l<=r){
        int mid=l+((r-l)>>1);
        int num=check(mid);
        if (num==k) return printf("%d\n",mid),0;
        else if (num>k){
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<-1<<endl;
    return 0;
}

D

  • 对于满足条件的数对(a,b),从ab连一条有向边,因为题目保证一定有解,所以直接dfs就好了。
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100+10;
int n,i,j,in[N];
bool vis[N];
ll a[N];
vector<int>G[N];
void dfs(int u){
    vis[u]=1;
    printf("%lld ",a[u]);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (vis[v]) continue;
        dfs(v);
    }
}
int main(){
    read(n);
    for (i=1;i<=n;i++){
        read(a[i]);
    }
    for (i=1;i<=n;i++){
        for (j=i+1;j<=n;j++){
            if (a[i]*2LL==a[j]){
                in[j]++;
                G[i].push_back(j);
            }
            else if (a[i]%3==0&&a[i]==a[j]*3LL){
                in[j]++;
                G[i].push_back(j);
            }
            else if (a[j]*2LL==a[i]){
                in[i]++;
                G[j].push_back(i);
            }
            else if (a[j]%3==0&&a[j]==a[i]*3LL){
                in[i]++;
                G[j].push_back(i);
            }
        }
    }
    for (i=1;i<=n;i++){
        if (in[i]==0){
            dfs(i);
            break;
        }
    }
    return 0;
}

E

  • 考虑到环上每个点的度数都为2,所以从这里下手即可,用并查集维护连通性,然后check每个连通块内所有点点数是否为2
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2e5+10;
int n,m,u,v,i,deg[N],fa[N];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
map<int,bool>vis;
int main(){
    read(n),read(m);
    int tmp=n;
    for (i=1;i<=n;i++) fa[i]=i;
    for (i=1;i<=m;i++){
        read(u),read(v);
        deg[u]++,deg[v]++;
        u=Find(u),v=Find(v);
        if (u^v){
            fa[u]=v;
            n--;
        }
    }
    // printf("%d\n",n);
    for (i=1;i<=tmp;i++){
        int f=Find(i);
        if (vis[f]==1) continue;
        if (deg[i]!=2){
            vis[f]=1;
            n--;
        }
    }
    printf("%d\n",n);
    return 0;
}

F

  • 可以得到一个很显然的dp方程,即dp[i]表示以数字i结尾的最大连续子序列的长度,然后因为值域范围很大所以用map动态开点。
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2e5+10;
int n,mx,i,e=-1,a[N];
map<int,int>dp;
int main(){
    read(n);
    for (i=1;i<=n;i++){
        read(a[i]);
        if (dp.find(a[i])==dp.end()){
            dp[a[i]]=1;
            if (dp.find(a[i]-1)==dp.end());
            else dp[a[i]]+=dp[a[i]-1];
        }
        else{
            if (dp.find(a[i]-1)==dp.end());
            else dp[a[i]]=max(dp[a[i]-1]+1,dp[a[i]]);
        }
        int num=dp[a[i]];
        if (e==-1){
            e=a[i];
            mx=num;
        }
        else if (mx<num){
            mx=num;
            e=a[i];
        }
    }
    printf("%d\n",mx);
    int s=e-mx+1;
    for (i=1;i<=n;i++){
        if (a[i]==s){
            printf("%d ",i);
            s++;
        }
        if (s==e+1) break;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注