Codeforces Round #565 (Div. 3)

• 题意：
• 给出一个数，每次操作，如果可以除以2就除以2，如果可以除以3就除以3再乘2，如果可以除以5就除以5再乘4
• 题解：
• 模拟呗
• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  int main()
  {
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        ll k1=0,k2=0,k3=0;
        while(n%2 == 0){
            n/=2;
            k1++;
        }
        while(n%3 == 0){
            n/=3;
            k2++;
        }
        while(n%5 == 0){
            n/=5;
            k3++;
        }
        if(n == 1){
            cout<<k1+2*k2+3*k3<<endl;
            continue;
        }
        cout<<"-1"<<endl;
    }
    return 0;
  }

题意：
给出一段数组，问你最少减少多少个数可以使得这个数组成为[4,8,15,16,23,42]组成的数组。
题解：
从4开始，如果有4就往后看又没有8，然后看有没有15.16.....
总共看有多少个
代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<int,int> mp;
int n,k;
int ans[100]={0};
int main()
{
    mp[4]=1,mp[8]=2,mp[15]=3,mp[16]=4,mp[23]=5,mp[42]=6;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&k);
        if(mp[k] == 1){
            ans[1]++;
        }
        else if(ans[mp[k]-1] > 0){
            ans[mp[k]-1]--;
            ans[mp[k]]++;
        }
    }
    //cout<<ans[6]<<endl;
    cout<<n-6*ans[6]<<endl;
    return 0;
}

题意：
给出一个无向图，n个点和m条边，问你最多选择n/2个点使得每个没有被选到的点都能连着被选到的点，输出选择的点。
题解：
直接染色就行了呗，染白色和黑色，颜色少的肯定小于等于n/2
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 2e5+10;
vector<int> v[maxx];
int n,k,cnt0=0,cnt1=0;
int color[maxx],flag[maxx];
void dfs(int x,int sign)
{
    if(sign){
        cnt1++;
    }else{
        cnt0++;
    }
    color[x] = sign;
    for(int i=0;i<v[x].size();i++){
        if(!flag[v[x][i]]){
            flag[v[x][i]] = 1;
            dfs(v[x][i],sign^1);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

        int n,m,x,y;
        cnt0 = cnt1 = 0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            flag[x] = flag[y] = 0;
            v[x].push_back(y),v[y].push_back(x);
        }
        flag[1] = 1;
        dfs(1,0);
        if(cnt0 > cnt1){
            cout<<cnt1<<endl;
            for(int i=1;i<=n;i++){
                if(color[i]){
                    cout<<i<<" ";
                }
            }
            cout<<endl;
        }else{
            cout<<cnt0<<endl;
            for(int i=1;i<=n;i++){
                if(!color[i]){
                    cout<<i<<" ";
                }
            }
            cout<<endl;
        }
    }
    return 0;
}