Codeforces Round #479 (Div. 3) 题解

Codeforce官方给的题解 传送门

A. Wrong Subtraction  

交题的传送门：http://codeforces.com/contest/977/problem/A

题意：题意很简单，就是给你一个数，如果能够整除10就直接将该数缩小10倍；否则直接将这个数减一。问k此操作之后，这个数n变为多少？

题解：直接按照题意模拟即可QAQ

代码如下：

//A
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,m,n,k;
    cin>>m>>k;
    int flag=0;
    while(k){
        while(m%10==0){
            m/=10;
            k--;
            if(k==0) {flag =1;break;}
        }
        if(!flag){m--;
        k--;}
    }
    cout<<m<<endl;
    //cin>>j;
    return 0;
}

B. Two-gram 

交题的传送门：http://codeforces.com/contest/977/problem/B

题意：这个题意就是：给你一个字符串，然后这个字符串中任意连续的两个字符组合成的字符串，在原字符串中出现最多次数的字符串给找出来。

题解：直接按照题意模拟，将所截的字符串用map存起来并计数，然后找到最大次数并且将字符串记录，打出来就好了QAQ

代码如下：

//B
#include <iostream>
#include <map>
using namespace std;
map<string, int> mp;
int main()
{
    int i, j, m, n, k;
    string s, p, q;
    cin >> m;
    cin >> s;
    int maxn = -1;
    for (i = 0; i < m-1; i++)
    {
        q=s.substr(i,2);
        //cout<<i<<q<<endl;
        mp[q]++;
        if (mp[q] > maxn)
        {
            maxn = mp[q];
            p = q;
        }
    }
    cout<<p<<endl;
    //cin>>k;
    return 0;
}

C. Less or Equal  

交题的传送门：http://codeforces.com/contest/977/problem/C

题意：给一个整数序列，是否找到一个数x，找到k个数字<=x，找到输出x，不能输出-1。看第二组数据，要找到两个数字，排序后出现1,3,3，会出现三个数字小于等于3，所以不能找到。

           一个坑点，k=0的时候需要分类讨论，如果发现最小的数字是1的话，不能输出0，因为要求输出1~1e9之间的数，否则输出a[0]-1就可以QAQ

题解：排序以后分类判断即可。注意k=0时分类讨论

代码如下：

//C
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
int a[200005];
bool cmp(int x,int y)
{
    return x<y;
}
int main()
{
    int i,j,m,k,n;
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>a[i];
    }

    sort(a,a+n,cmp);
    if(n==k){
        cout<<a[k-1]<<endl;
        return 0;
    }
    if(k==0){
        if(a[0]==1){
            puts("-1");
        }
        else{
            puts("1");
        }

        return 0;
    }
    if(a[k]==a[k-1]){
        puts("-1");
        //cin>>i;
        return 0;
    }
    cout<<a[k-1]<<endl;
    //cin>>i;
    return 0;
}

D. Divide by three, multiply by two 

交题的传送门：http://codeforces.com/contest/977/problem/D

题意：将给出的序列按照题目要求输出。选取一个数，然后通过除以3或者乘以2得到下一个数，然后将这些数按这个顺序直接打出来即可QAQ，数据保证有解

题解：将所有可以除以3的数全部记录次数存到数组里，按照从大到小的顺序直接排，将这个原来的数与这个新数组对应，从而输出来所有的数组。

其实一开始我用DFS去写，发现写不出来，结束了看大神代码，恍然大悟了。还是自己太菜了QAQ

代码如下：

//D
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int count3(LL x)
{
    int ret=0;
    while(x % 3 == 0)
    {
        ret++;
        x /= 3;
    }
    return ret;
}
int n;
vector<pair<int,LL>> v;
int main()
{
    cin>>n;
    v.resize(n);
    for(int i=0; i<n; i++)
    {
        cin>>v[i].second;
        v[i].first=-count3(v[i].second);
        //cout<<v[i].first<<endl;
    }
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++)
        printf("%lld%c", v[i].second, " 
"[i + 1 == n]);
}

还有两个dalao的骚操作，大家可以看下

//D
#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
typedef long long int ll;
ll a[N],b[N];
map<ll,ll>m;
int main()
{
    int n;
    scanf("%d",&n);
    m.clear();
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",a+i);
        m[a[i]]=1;
    }
    sort(a+1,a+1+n);
    int l=100,r=100;
    b[l]=a[1];
    while(r-l<n-1)
    {
        //cout<<l<<' '<<r<<endl;
        if(m[b[r]*2]==1)
        {
            m[b[r]*2]=0;
            r++;
            b[r]=b[r-1]*2;
        }
        else if(b[r]%3==0&&m[b[r]/3]==1)
        {
            m[b[r]/3]=0;
            r++;
            b[r]=b[r-1]/3;
        }
        else if(m[b[l]*3]==1)
        {
            m[b[l]*3]=0;
            l--;
            b[l]=b[l+1]*3;
        }
        else if(b[l]%2==0&&m[b[l]/2]==1)
        {
            m[b[l]/2]=0;
            l--;
            b[l]=b[l+1]/2;
        }
    }
    for(int i=l; i<=r; i++)
    {
        printf("%lld ",b[i]);
    }
    return 0;
}

//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int highest_power(ll n,int k)   //k is 3 or 2
{
    int count=0;
    while(n%k==0)
    {
        count++;
        n=n/k;
    }
    return(count);
}
bool ispresent(ll num,ll n,ll a[])
{
    for(int i=0; i<n; i++)
    {
        if(a[i]==num)
            return(1);
    }
    return(0);
}
int main()
{
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0; i<n; i++)cin>>a[i];
    pair <int,int> start;
    int index=-1;
    start= {-999999,999999};
    for(int i=0; i<n; i++)
    {
        int temp3=highest_power(a[i],3);
        int temp2=highest_power(a[i],2);
        //cout<<temp3<<" "<<temp2<<endl;
        if((temp3>=start.first)&&(temp2<=start.second))
        {
            start= {temp3,temp2};
            index=i;
        }
        //cout<<"start: "<<start.first<<" "<<start.second<<endl;
    }
    cout<<a[index]<<" ";
    ll curr=a[index];
    for(int i=2; i<=n; i++)
    {
        if(curr%3==0)
        {
            if(ispresent(curr/3,n,a))
            {
                curr=curr/3;
                cout<<curr<<" ";
            }
            else
            {
                curr=2*curr;
                cout<<curr<<" ";
            }
        }
        else
        {
            curr=2*curr;
            cout<<curr<<" ";
        }
    }
}

E. Cyclic Components 

交题的传送门：http://codeforces.com/contest/977/problem/E

题意：给你一些点与点直接的连通情况，这个是无向图，算出这个图中有几个圈。注意：圈中所有的节点的度为2

题解：用并查集直接统计，若两个节点的父亲节点是同一个，那么增加一个圈。算出圈的个数QAQ

代码如下：

//E
#include<bits/stdc++.h>
using namespace std;

struct node
{
    int u;
    int v;
}e[200005];
int du[200005],coun;
int father[200005];

void init(int x)
{
    memset(du,0,sizeof(du));
    for(int i=1;i<=x;i++)
    {
        father[i]=i;
    }
}
int Find(int x)
{
    if(x==father[x]) return x;
    return father[x]=Find(father[x]);
}

void Union(int x,int y)
{
    int dx=Find(x);
    int dy=Find(y);
    if(dx==dy) coun++;
    else father[dx]=dy;
}

int main()
{
    int i,j,m,n,k,x,y;
    cin>>m>>n;
    init(m);
    for(i=1;i<=n;i++)
    {
        cin>>e[i].u>>e[i].v;
        du[e[i].u]++;
        du[e[i].v]++;
    }
    coun=0;
    for(i=1;i<=n;i++)
    {
        if(du[e[i].u]==2&&du[e[i].v]==2){
            Union(e[i].u,e[i].v);
        }
    }
    cout<<coun<<endl;
    return 0;
}

还有位dalao写的，参考一下

//E
#include<iostream>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<map>
#include<string>
#include<stdio.h>
#include<vector>
#include<stack>
#include<set>
using namespace std;
#define INIT ios::sync_with_stdio(false)
#define LL long long int

struct node {
    int id;
    int count;
};
int dp[2 * 100005];
vector<int>mm[200005];
void init() {
    for (int i = 0;i < 2 * 100005;i++) {
        dp[i] = i;
    }
}

int _find(int x) {
    if (dp[x] != x) {
        return dp[x] = _find(dp[x]);
    }
    return dp[x];
}

void _union(int  x, int y) {
    int xx = _find(x);
    int yy = _find(y);
    if (xx < yy) {
        dp[xx]= yy;
    }
    else {
        dp[yy] = xx;
    }
}

int main() {
    int n, m;
    map<int, int>mp;//存每个节点的度
    while (cin >> n >> m)
    {
        mp.clear();
        init();
        int a, b;
        int ans = 0;
        for (int i = 0;i < m;i++) {
            cin >> a >> b;
            mp[a]++;
            mp[b]++;
            if (_find(a) != _find(b)) {
                _union(a, b);
            }
        }
        //通过父节点把连通图存进一个vector数组
        for (int i = 1;i <= n;i++) {
            mm[_find(i)].push_back(i);
        }
        for (int i = 1;i <= n;i++) {
            //连通图至少要有3个点
            if (mm[i].size() > 2) {
                int flag = 1;
                for (int j = 0;j < mm[i].size()&&flag;j++) {
                    //只要有一个度不为2就跳出
                    if (mp[mm[i][j]] != 2) {
                        flag = 0;
                    }
                }
                if (flag)ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

F. Consecutive Subsequence

交题的传送门：http://codeforces.com/contest/977/problem/F

题意：给出一个n和n个数的序列，然后让你找到满足两个数之间相差为1的存在的最长的序列，让你输出他们的下标。

题解：

跟最长递增子序列差不多，但是他的数据有给的还是挺大的，两种方法，离散化一下，或者map搞一下，map比较好写，所以直接map存一下。接着你只需要保存最长的序列最后一个数的位置和数就可以，那么怎么保存呢？

因为我们需要顺序的从这个序列里找，可以每次把进来的数标记由前面一个数 + 1得到，即可以得到到这个数为止的最长序列的长度。

比如 3 3 4 7 5 6 8 

3 的时候 我们就以m【2】 + 1 得到这个m【3】，但是因为m【2】没出现过，所以直接就是1，然后下一个3也是如此，4的时候就由m【3】 + 1 ，所以m【4】 = 2，然后依次到8，就可以在m【8】的位置保存到从0到8中，最长的序列长度。

边赋值，边找到最大值的下标和数，然后找到以后，有个最大值，用最大值减去长度 + 1是不是就可以得到他的起始数字了，然后再遍历一遍序列，找每个数就可以了，输出下标。

由于这道题目不知道如何表达，参考了这位大佬的题解QAQ，（实际上就是自己太菜了555555555

参考了这位dalao的题解：https://blog.csdn.net/qq_38185591/article/details/80256487

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
    int i,j,m,n,k,x;
    cin>>m;
    map<int,int> dp;
    vector<int> ve;
    for(i=0;i<m;i++)
    {
        cin>>a[i];
    }
    int ans=0;
    int last=0;
    for(i=0;i<m;i++)
    {
        x=a[i];
        dp[x]=dp[x-1]+1;
        if(ans<dp[x]){
            ans=dp[x];
            last=x;
        }
    }
    cout<<ans<<endl;
    for(i=m-1;i>=0;i--){
        if(a[i]==last){
            ve.push_back(i+1);
            last--;
        }
    }
    reverse(ve.begin(),ve.end());
    for(i=0;i<ve.size();i++){
        if(i==ve.size()-1){cout<<ve[i]<<endl;break;}
        cout<<ve[i]<<' ';
    }
    return 0;
}