Codeforces Round #660 (Div. 2) 题解

A - Captain Flint and Crew Recruitment

题意：定义一个近似素数，是由两素数相乘得来，现在得定n，要求判断是否是由至少含三个近似素数的四个不同正整数组成。
思路：其实样例给的很清楚了，因为是至少三个，所以最小的三个近似素数是6,10,14，那么所组成的和最小就是31，小于31的都不能组成，另外因为不能重复，所以，36,40,44，都要特判一下，把14换成15就行了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<unordered_map>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
vector<int>prime;
int vis[MAX_N];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int n;
        scanf("%d",&n);
        if(n<=30)
        {
   
            cout<<"NO"<<endl;
        }
        else
        {
   
            cout<<"YES"<<endl;
            if(n==36)
            {
   
                cout<<5<<' '<<6<<' '<<10<<' '<<15<<endl;
            }
            else if(n==40)
            {
   
                cout<<6<<' '<<10<<' '<<15<<' '<<9<<endl;
            }
            else if(n==44)
            {
   
                cout<<6<<' '<<7<<' '<<10<<' '<<21<<endl;
            }
            else
            {
   
 
                cout<<6<<' '<<10<<' '<<14<<' '<<n-30<<endl;
            }
 
        }
 
    }
}

B - Captain Flint and a Long Voyage

题意：对于一个n长度的正整数x，我们定义一个k，是他们的每一位的数的二进制数组合而成，比如x=729，k=111101001，将k的后n位抹掉形成新的数r也就是111101，现在给定n，要求算出最小的x，使他所形成的的r最大。
思路：因为只要抹除后n位，所以前面毫无疑问越大越好，即每位都是9，然后只需要考虑最后被抹除的那几位即可。由于8是1000,9是1001，而7是111，只有三位，所以如果有7会让整体变小，所以只考虑8和9。这里我们考虑999，即100110011001，这时我们发现抹除后三位也就是001被抹除，这个1是浪费，最优的情况应是抹除000，即998，也就是说每当抹除的数会抹到9所对应的数，就应当改为8，也就是每4个为一周期。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<unordered_map>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
vector<int>prime;
int vis[MAX_N];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int n;
        scanf("%d",&n);
        int p=n/4;
        if(n%4)
            p++;
        int i;
        for(i=1;i<=n-p;i++)
            cout<<9;
        for(i=1;i<=p;i++)
            cout<<8;
        cout<<endl;
 
    }
}

C - Uncle Bogdan and Country Happiness

题意：给定一个树形图，每个节点代表一个城市，现在有m个人要从节点1回家，在回家的过程中会有人从开心转变为不开心，而且不能变回来，现在每个城市统计路过的人中开心的人数-不开心的人数的值，并给定回每个城市的人数，现在要求判断每个城市统计的是否正确。
思路：我们定义经过每个城市的人开心人数是hap[i]，不开心人数是unhap[i]，所以每个城市的统计值就是hap[i]-unhap[i]，而经过每个城市的总人数是hap[i]+unhap[i]，通过这两个城市就可以直接算出经过每个城市的开心人数和不开心人数，那么要计算经过每个城市的总人口，只需要将该城市和这个城市之后的所有城市的定居人数之和加起来即可。另外通过递归我们也可以得到每个城市的儿子城市的开心人数之和以及不开心人数之和，我们设为h和u。有了这些数据我们考虑统计的合理性。首先hap[i]=（经过总人数+统计值）/2，那么如果括号里是奇数那么就无法得到hap[i]，即不合理。而unhap[i]是总人数-hap[i]，如果是负数也不合理。另外，理论上u+h=hap[i]+unhap[i]-i的定居人数，那么如果不符合这个条件，也不合理。
最后我们考虑开心人数转变为不开心人数的情况。因为只能由开心转为不开心，所以开心人数必然越来越少，如果变多即不合理。考虑不开心人数，因为开心的人和不开心的人经过城市会留下一部分，所以要让u最小，应该是尽量让不开心人留下，然后没有发生转变，而要u最大，就是在留下一部分人后，让所有开心的人转变为不开心的人，所以u必须在这个区间呢。

Codeforces Round #660 (Div. 2) 题解

A - Captain Flint and Crew Recruitment

B - Captain Flint and a Long Voyage

C - Uncle Bogdan and Country Happiness

全站热榜