牛客挑战赛53题解

A题

题意：进行最少操作从原点走到x处，第k次操作可以选择向右走k步或者向左走1步。

解：先用最少的次数到达>=x,即求出最小的r，r*(r+1)/2 >= x，

此时，可能多走了0-(r-2)步，

考虑在前面的操作中选择一个变成往左走。

比如第1步往左走，最终对答案的影响是-2，以此类推，第i步变成往左走会让答案-（i+1），所以除非r*(r+1)/2 - x == 1，其余的x都可以在r步得到。

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

typedef long long ll;
ll x;
int t;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>x;
		ll k = 1LL * (long long)sqrt(x * 2);
		if(k * (k + 1) / 2 < x) k++;
		ll r = k * (k + 1) / 2 - x;
		if(r == 1) k++;
		cout<<k<<'\n';
	}
	return 0;
}

B题

题意：给出s，要求构造一个只包含0，1和质数的序列使得序列的和为s，要求序列长度尽可能小。

解：先来背诵哥德巴赫猜想qaq。

如果本身这个数不是质数。

根据关于偶数的哥德巴赫猜想，任意一个大于2的偶数都可以写成两个素数之和。

然后对于奇数x来说，有两种思路，变成2+(x-2)，这样序列就有最多2个数，只需要检查x-2是不是质数就可以，或者变成1+(x-1)，因为x-1是偶数，所以序列最多3个数。

因为n只有1e7，预处理出质数暴力查找即可。

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

const int N = 1e7;
int p[N + 10];
bool vis[N + 10];
int tot,t,n;

void init()
{
	for(int i = 2;i <= N; ++i)
	{
		if(!vis[i]) p[++tot] = i;
		for(int j = 1;j <= tot && p[j] * i <= N; ++j)
		{
			vis[i * p[j]] = 1;
			if(i % p[j] == 0) break;
		}
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	init();
	cin>>t;
	while(t--)
	{
		cin>>n;
		if(n <= 2 || !vis[n])
		{
			cout<<"1\n"<<n<<" = "<<n<<'\n';
			continue;
		}
		if(n % 2 == 0)
		{
			for(int i = 1;i <= tot && p[i] <= n; ++i)
				if(!vis[n - p[i]])
				{
					cout<<"2\n"<<p[i]<<" + "<<n - p[i]<<" = "<<n<<'\n';
					break;
				}
            continue;
		}
		if(!vis[n - 2]) 
        {
            cout<<"2\n2 + "<<n - 2<<" = "<<n<<'\n';
            continue;
        }
		for(int i = 1;i <= tot && p[i] <= n - 1; ++i)
			if(!vis[n - p[i] - 1])
			{
				cout<<"3\n1 + "<<p[i]<<" + "<<n - p[i] - 1<<" = "<<n<<'\n';
				break;
			}
	}
	return 0;
}

C题

题意：给出n个点m条边的无向图，求每个集合中有多少个子集是独立集（独立集是指集合中任意两点之间都没有边）。

解：n只有26。dp[i]表示编号为i的集合中有多少子集是独立集，我们设x为i的二进制为1的最低位（即lowbit(i))。

如果选择x不冲突，dp[i]可以由dp[i^(1<<x)]转移过来，

如果选择x冲突，dp[i]可以由dp[i^(i & pw[x)]转移过来，pw记录的是所有x的互斥的点。

最后，又卡时间又卡空间太难受了，被迫写的特别丑才过，复杂度是O(2^n)

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

typedef long long ll;
const int p = 1e9 + 7;
int pw[26];
int dp[(1 << 26) + 10];
int pe[(1 << 25) + 10];
int n,m,x,y;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i = 0;i < n; ++i) 
        pw[i] = (1 << i),pe[(1 << i)] = i;
	while(m--)
	{
		cin>>x>>y;
		pw[x] |= (1 << y);
		pw[y] |= (1 << x);
	}
	dp[0] = 1;
	for(int i = 1;i < (1 << n); ++i)
	{
		int id = pe[i&(-i)];
		dp[i] = dp[i ^ (1 << id)] + dp[i ^ (i & pw[id])];
        if(dp[i] >= p) dp[i] -= p;
	}
    ll ans = 0;
    for(int i = (1 << n) - 1;i >= 0; --i) 
        ans = (233LL * ans + dp[i]) % p;
	cout<<ans<<'\n';
	return 0;
}