Codeforces Round #479 (Div. 3)（A-F)题解

传送门

A. Wrong Subtraction

思路：签到题，根据题意模拟即可。

时间复杂度：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++){
        if(n%10!=0) n--;
        else n/=10;
    }
    cout<<n<<endl;
    return 0;
}

B. Two-gram

思路：暴力，因为所要求的子串长度为，所以可以枚举长度为2的字符串。

时间复杂度：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int a[26][26];
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n-1;i++){
        a[s[i]-'A'][s[i+1]-'A']++;
    }
    int mx=0,x,y;
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++){
            if(a[i][j]>mx){
                mx=a[i][j],x=i,y=j;
            }
        }
    printf("%c%c\n",x+'A',y+'A');
    return 0;
}

C. Less or Equal

思路：

我的解法：二分枚举答案，即最大值最小化。时间复杂度：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int a[N],n,k;
int check(int x){
    int  p=upper_bound(a+1,a+n+1,x)-a;
    p--;
    return p;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int l=1,r=a[n];
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)>=k) r=mid-1;
        else l=mid+1;
    }
    if(check(l)!=k) puts("-1");
    else printf("%d\n",l); 
    return 0;
}

实际上是我想多了，没必要这么麻烦，直接排序选第小的数即可，注意特判数的范围是否则属于。
时间复杂度： 。
这里就不放代码了。

D. Divide by three, multiply by two

思路：贪心+排序，因为只有两种操作：除以和乘以，所以含因子3越多的个数要越靠前，又因为有乘2的操作，所以当的个数相同的时候，就取因子越少的数即可。

时间复杂度：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105+10,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
ll a[N];
pair<int,PII>b[N];
bool cmp(pair<int,PII> a,pair<int,PII> b){
    return a.se.se==b.se.se?a.se.fi<b.se.fi:a.se.se>b.se.se;
}
int main(){    
    int n; 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        ll x=a[i];
        b[i].fi=i;
        for(int j=2;j<=3;j++)
            while(x%j==0){
                if(j==2) b[i].se.fi++;
                else b[i].se.se++;
                x/=j;
            }    
    }

    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
        printf("%lld ",a[b[i].fi]);
    return 0;
}

E. Cyclic Components

题意：求给定无向图的所有环(这里的环是每个结点度数都为2的环)个数。

思路：显然使用，因为题目不保证图是连通的，所以用一个标记结点是否被访问过，可能需要多次，每次若遍历到已经标记过的结点而且所有结点度数都为，则。

时间复杂度：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
vector<int>e[N];
int vis[N],d[N],ans,f;
void dfs(int u,int fa){
    for(auto v:e[u]){
        if(v==fa||d[v]!=2) continue;    
        //printf("%d->%d",u,v);
        if(!vis[v]&&d[v]==2) vis[v]=1,dfs(v,u);
        else if(vis[v]&&d[v]==2){
            if(!f)
            ans++,f=1;
            else return;
        }
    }
} 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v),e[v].push_back(u);
        d[u]++,d[v]++;
    } 
    for(int i=1;i<=n;i++){
        if(!vis[i]&&d[i]==2) f=0,vis[i]=1,dfs(i,-1);
    }
    printf("%d\n",ans);
    return 0;
}

F. Consecutive Subsequence

题意：求最长(连续递增)子序列。

思路：这里的连续递增指得是子序列的数为的相连的数相差1的形式。

根据题目显然考虑解决此题，我们可以子序列的末尾的数，即最大值为下标，令表示以元素结尾的最大长度。

因为，所以考虑离散化，用储存。

即。

因为是顺序遍历，所以可以一边输入一遍更新。

对于输出下标，则可以找到起始点.

然后顺序扫一遍即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+100;
#define mst(a) memset(a,0,sizeof a)
int a[N];
map<int,int>mp;
int main(){
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mp[a[i]]=mp[a[i]-1]+1;
        if(mp[a[i]]>mp[ans]) ans=a[i];
    }
    printf("%d\n",mp[ans]);
    int st=ans-mp[ans]+1;
    for(int i=1;i<=n;i++)
        if(a[i]==st) printf("%d ",i),st++;
    return 0;
}

此题有个坑点是用会 ，大概是哈希表建立的时间耗费较长？，不知道希望有人能说说。