[C++知识库]2020 江苏省赛 - H(dp) C(构造) D(思维转化 二分)

H. Happy Morse Code

题意：
给定 m 个字符，每个字符对应一个 01 串 t。
问，一个长度为 n 的 01 串有多少种字符对应方案？
答案对 128 取模。
$(1\le T\le 10^5,1\le n\le 10^5,1\le m\le 26,1\le |t|\le 5)$

思路
定义状态 f[i] 表示前 i 个位置的字符对应方案。
初始状态赋值为0，0位置赋值为1。
因为 0 状态也可能更新其他点，但是不应该更新，所以需要额外用 ff[i] 标记每个点是否可以转移，是否已经被取模。
如果是像背包一样求最大价值，不可更新时可将初始状态设为负无穷。

• 如果最后一个位置可以被转移，并且没有被取模，并且前 n 个位置的方案数 f[n] 为 1 的话，说明方案唯一。
• 如果最后一个位置不可以被转移，说明方案为 0；
• 否则方案不唯一。

Code

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

#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
string a[N];
int f[N], ff[N];
char s[N];

bool get(int l, int r, int j)
{
	int flag = 1;
	for(int i=l;i<=r;i++)
	{
		if(s[i] != a[j][i-l]) flag=0;
	}
	return flag;
}

signed main(){
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		char c;
		for(int i=1;i<=m;i++) cin >> c >> a[i];
		
		for(int i=0;i<=n;i++) f[i] = ff[i] = 0;
		f[0] = 1;
		ff[0] = 1;
 		
		int cnt = 0;
		
		cin >> s+1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(i < a[j].size() || !get(i-a[j].size()+1, i, j)) continue;
				
				if(ff[i-a[j].size()])
				{
					if(!ff[i]) ff[i] = 1;
					if(f[i] + f[i-a[j].size()] >= 128) ff[i] = 2;
					f[i] = (f[i] + f[i-a[j].size()]) % 128;
				}
			}
		}
		
		if(ff[n]==1 && f[n] == 1) cout << "happymorsecode\n";
		else if(!ff[n]) cout << "nonono\n";
		else cout << "puppymousecat " << f[n] << "\n"; 
	}
	
	return 0;
}

C. Cats

题意
一共 n 个位置，每个位置可以填 $1?20$ 中的一个数。
构造一个数列，使得任意两个相同的数 $x$ 满足：

• 位置不相邻；
• 他们中间数的最小值要大于x。

思路
因为中间的最小数要大于其本身，所以数1只能出现1次，数2只能出现两次，而且要保证在1的一左一右。
那么3就可以在2的一左一右，在1的一左一右，可以出现4次。
4就可以在3的一左一右，2的，1的，为了尽可能插入的多，就放到其相邻位置。
这样，20个数最多能够构造出长度为 $2^{20}$ 的数列。

Code

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

#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];

signed main(){
	cin >> n;
	a[1]  = b[1] = 1;
	
	int cnt = 1, x = 1;
	while(cnt < n)
	{
		cnt = cnt*2 + 1;
		x ++;
		
		for(int i=1;i<=cnt;i++)
		{
			if(i%2) a[i] = x;
			else a[i] = b[i/2];
		}
		
		for(int i=1;i<=cnt;i++) b[i] = a[i];
	}
	
	for(int i=1;i<=n;i++) cout << a[i] << ' ';
	
	
	return 0;
}

Delete Prime

题意
有 n 个球排成一排，球 $i$ 上有标记 $i$，每个球按照排列顺序编号为 1~n。
对于每一次操作：

• 删除编号为 1 或 质数 的球，将其标记依次加入数组 $d[]$；
• 然后将剩余的球按照原来顺序从 1 开始重新编号；
• 重复上述操作，直到所有球都被删除。

$T$ 次询问，每次询问给出 $t,n,k$ 分别表示询问类型，球的个数，询问数。

• t = 1 时，求把 n 个球加入数组后，标记为 k 的球的下标；
• t = 2 时，求把 n 个球加入数组后，下标为 k 的球的标记。

$(1\le T\le 2?10^5,1\le k\le n\le 10^6)$

思路
直接模拟的话显然超时。
因为每次删除的球都是固定的，询问的时候只是有的球没有达到。1e6 个球最多删除 80 次。
所以可以先预处理把 1e6 个球分到每次删除的 vector 中，然后每次询问的时候二分查找 1-n 个球中，每次删除了多少个即可。

• 找第 k 个位置上的数就是直接每一层二分 1-n 个数一共多少个，总数超过 k 了就停止。
• 找数 x 的位置就是找每次层第一个大于等于 x 的数，判断是不是 x。

Code

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

#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl '\n'

const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N];
int prim[N], f[N];
int cnt, b[N], k;
vector<int> v[N];

void Prim()
{
	n = 1e6;
	for(int i=2;i<=n;i++)
	{
		if(!f[i]) prim[++cnt] = i;
		for(int j=1;prim[j] <= n/i;j++)
		{
			f[prim[j]*i] = 1;
			if(i % prim[j] == 0) break;
		}
	}
}

void pre()
{
	int t = n;
	
	for(int i=1;i<=n;i++) a[i] = i;
	
	while(1)
	{	
		cnt++;
		int r = t;
		t = 0;
		
		for(int i=1;i<=r;i++)
		{
			if(!f[i]) v[cnt].pb(a[i]);
			else b[++t] = a[i];
		}
		v[cnt].pb(1e7);
		
		for(int i=1;i<=t;i++) a[i] = b[i];
		if(!t) break;
	}
}

int solve1(int x, int n)
{
	int sum = 0, ans;
	for(int i=1;i<=cnt;i++)
	{
		auto p = lower_bound(v[i].begin(), v[i].end(), x);
		if(*p == x)
		{
			return sum + lower_bound(v[i].begin(), v[i].end(), x) - v[i].begin() + 1;
		}
		int pos = upper_bound(v[i].begin(), v[i].end(), n) - v[i].begin();
		sum += pos;
	}
}

int solve2(int k, int n)
{
	int sum = 0, ans;
	for(int i=1;i<=cnt;i++)
	{
		int pos = upper_bound(v[i].begin(), v[i].end(), n) - v[i].begin();
		
		if(sum + pos >= k){
			ans = i;
			break;
		}
		else sum += pos;
	}
	
	return v[ans][k-sum-1];
}

signed main(){
	Prim();
	
	cnt = 0;
	pre();
	
	cin >> T;
	while(T--)
	{
		int t;
		cin >> t >> n >> k;
		if(t == 1) cout << solve1(k, n) << endl;
		else cout << solve2(k, n) << endl;
	}
	
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖