Codeforces Round #565(Div.3) 解题报告

发布于 2020-01-24  27 次阅读



A - Divide it!
能除以2就除以2,不能除以2再乘以一个$\frac{2}{3}$或$\frac{4}{5}$,再除以2就行

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        cin>>n;
        int ans=0;
        while(n>1)
        {
            if((
            while(
            if(
            while(
            if(
            while(
        }
        printf(
    }
    return 0;
}

B - Merge it!
直接看除以3的余数:余数为0就不管,就看余数为1和2的怎么凑可以凑出最多的余数为0的数。
发现一个1和一个2就可以,剩下的1(或2)需要3个来凑。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
int n;
int a[105];
int cnt[5];
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        cin>>n;mem(cnt,0);int ans=0;
        for(int i=1;i<=n;++i)scanf(
        for(int i=1;i<=n;++i)cnt[a[i]]++;
        int tmp=min(cnt[1],cnt[2]);
        ans+=min(cnt[1],cnt[2])+cnt[0];
        cnt[1]-=tmp;
        cnt[2]-=tmp;
        ans+=cnt[1]/3+cnt[2]/3;
        printf(
    }
    return 0;
}

C - Lose it!
贪心就行......就像拦截导弹第二问那样......

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
int n;
const int N=500050;
int a[N];
int num[]={0,4,8,15,16,23,42};
queue <int> q[10];
int ans;
bool Exit(int i,int j)
{
    while(q[i].front()>q[j].front()&&!q[j].empty())q[j].pop();
    return q[j].empty();
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)scanf(
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=6;++j)
            if(a[i]==num[j])q[j].push(i);
    }
    while(true)
    {
        if(Exit(1,2))break;
        if(Exit(2,3))break;
        if(Exit(3,4))break;
        if(Exit(4,5))break;
        if(Exit(5,6))break;
        ans++;
        for(int i=1;i<=6;++i)q[i].pop();
    }
    printf(
    return 0;
}

D - Recover it!
这题题意还看了半天......愣是没理解append啥意思
我们把b从大到小排序,发现只需要扫一遍就行。
一个数无非就两种情况:是质数和不是质数。
是质数的话说明肯定是由一个更小的质数生成而来,更小的那个质数就在后面,并且是a中的数;
不是质数的话这个数就肯定是a中的数,并且生成了一个更小的数。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=300050;
int n;
int b[N<<1];
bool vis[N*20];
int cnt[N*20];
int pri[N];
int no[N*20],tot;
vector <int> a;
bool cmp(const int &x,const int &y){return x>y;}
bool isprime(int x)
{
    for(int i=2;i<=sqrt(x);++i)if(
    return true;
}
void init()
{
    for(int i=2;i<=3000000;++i)
    {
        if(!vis[i]){pri[++tot]=i;no[i]=tot;}
        for(int j=1;j<=tot&&i*pri[j]<=3000000;++j)
        {
            vis[i*pri[j]]=1;
            if(
        }
    }
}
int main()
{
    init();
    cin>>n;
    for(int i=1;i<=n*2;++i)scanf(
    sort(b+1,b+2*n+1,cmp);
    for(int i=1;i<=n*2;++i)
    {
        if(cnt[b[i]]==0)continue;
        if(isprime(b[i]))
        {
            cnt[b[i]]--;
            cnt[no[b[i]]]--;
            a.push_back(no[b[i]]);
        }
        else
        {
            int num=0;
            for(int j=2;j<=sqrt(b[i]);++j)
            {
                if(b[i
            }
            a.push_back(b[i]);
            cnt[num]--;
            cnt[b[i]]--;
        }
    }
    for(int i=0;i<a.size();++i)printf(
    puts("");
    return 0;
}

E - Cover it!
对整张图黑白染色就行......

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=200050;
int n,m;
struct edge
{
    int v,nxt;
}e[N<<1];
int head[N],ecnt;
inline void ad(int u,int v)
{
    e[++ecnt].v=v;e[ecnt].nxt=head[u];head[u]=ecnt;
}
int c[N];
bool vis[N];
int cnt1,cnt2;
void dfs(int u,int fa)
{
    if(vis[u])return;
    vis[u]=1;
    if(!c[fa])c[u]=1;
    else if(c[fa]==1)c[u]=2;
    else if(c[fa]==2)c[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
    }
}
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        scanf(
        cnt1=cnt2=0;
        memset(head,0,(n+5)*sizeof(int));
        memset(vis,0,(n+5)*sizeof(int));
        memset(e,0,(m*2+5)*sizeof(int));
        memset(c,0,(n+5)*sizeof(int));
        for(int i=1;i<=m;++i)
        {
            int x,y;
            scanf(
            ad(x,y),ad(y,x);
        }
        c[1]=1;
        dfs(1,1);
        for(int i=1;i<=n;++i)
        {
            if(c[i]==1)cnt1++;
            else cnt2++;
        }
        if(cnt1<=cnt2)
        {
            printf(
            for(int i=1;i<=n;++i)
            {
                if(c[i]==1)printf(
            }
        }
        else
        {
            printf(
            for(int i=1;i<=n;++i)
            {
                if(c[i]==2)printf(
            }
        }
        puts("");
    }
    return 0;
}

F - Destroy it!
一道还算不错的dp题。
首先,对于每一轮,我们可以只选择其中五张牌:花费为1的伤害最高的3张,花费为2伤害最高的1张,花费为三伤害最高的1张。为什么呢?因为限定每一轮花费不超过3,所以组合一下发现花费为1的最多用三张,其他同理。
然后因为还有一个双倍伤害的设定,那么dp数组需要再开一维表示现在是用到的第几张牌。
然后决策最多有6种:对用一张、两张、三张讨论可得6种决策。
然后就可以上dp了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node
{
	int c1,c2,c3;
	ll x1[4],x2,x3;
}a[N];
bool cmp(ll x,ll y)
{
	return x>y;
}
ll dp[10],temp[10];
int main()
{
	int T;
	scanf(
	int n;
	int t=1;
	while(T--)
	{
		scanf(
		vector<ll>tmp;
		tmp.clear();
		for(int i=1;i<=n;i++)
		{
			ll c,d;
			scanf(
			if(c==1)
			{
				tmp.push_back(d);
				a[t].c1++;
			}
			else if(c==2)
			{
				a[t].c2++;
				a[t].x2=max(a[t].x2,d);
			}
			else
			{
				a[t].c3++;
				a[t].x3=max(a[t].x3,d);
			}
		}
		sort(tmp.begin(),tmp.end(),cmp);
		for(int i=0;i<3&&i<a[t].c1;i++)
		{
			//cout<<tmp[i]<<endl;
			a[t].x1[i+1]=tmp[i];
		}
		t++;
	}
	memset(dp,-1,sizeof dp);
	dp[0]=0;
	//cout<<t<<endl;
	for(int i=1;i<t;i++)
	{
		ll *x1=a[i].x1,x2=a[i].x2,x3=a[i].x3;
		//cout<<x1[0]<<endl;
		int c1=a[i].c1,c2=a[i].c2,c3=a[i].c3;
		memcpy(temp,dp,sizeof dp);
		for(int j=0;j<10;j++)
		{
			if(temp[j]==-1)
				continue;
			//选1张
			if(j<9)
			{
				if(c1)
					dp[j+1]=max(dp[j+1],temp[j]+x1[1]);
				if(c2)
					dp[j+1]=max(dp[j+1],temp[j]+x2);
				if(c3)
					dp[j+1]=max(dp[j+1],temp[j]+x3);
			}
			else
			{
				if(c1)
					dp[0]=max(dp[0],temp[j]+2*x1[1]);
				if(c2)
					dp[0]=max(dp[0],temp[j]+2*x2);
				if(c3)
					dp[0]=max(dp[0],temp[j]+2*x3);
			}
			//选2张
			if(j<8)
			{
				if(c1>=2)
					dp[j+2]=max(dp[j+2],temp[j]+x1[1]+x1[2]);
				if(c2&&c1)
					dp[j+2]=max(dp[j+2],temp[j]+x2+x1[1]);
			}
			else
			{
				if(c1>=2)
					dp[j-8]=max(dp[j-8],temp[j]+2*x1[1]+x1[2]);
				if(c2&&c1)
				{
					ll maxx=max(x2,x1[1]);
					dp[j-8]=max(dp[j-8],temp[j]+x2+x1[1]+maxx);
				}
			}
			//选3张
			if(j<7)
			{
				if(c1>=3)
				{
					dp[j+3]=max(dp[j+3],temp[j]+x1[1]+x1[2]+x1[3]);
				}
			}
			else
			{
				if(c1>=3)
				{
					dp[j-7]=max(dp[j-7],temp[j]+x1[1]*2+x1[2]+x1[3]);
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=9;i++)
	{
		ans=max(ans,dp[i]);
	}
	printf(
	return 0;
}