CF1464C Poman Numbers

给出一个序列\(a_i\)代表\(2^{a_i}\)，你需要按照如下方式决定\(a_i\)的正负号，问是否可以使和等于\(T\)：建一棵线段树（\(mid\)不一定为中点），每个位置的符号由根到它对应的叶子结点经过的左儿子边数决定，如果是奇数就是\(-1\)。

\(n\le 10^5,T\le10^{15}\)

结论：\(a_n\)系数为\(1\)，\(a_{n-1}\)系数为\(-1\)，前面的符号可以任意钦定。

证明考虑归纳：考虑现在要构造一个符号序列\(\{s_i\}\)，记\(query(\{s_i\})\)。如果\(s_1=-1\)则可以分成子问题\(query({-1})\)和\(query(\{s_2,\dots,s_n\})\)。否则找到\(i\)满足\(s_{i-1}=+1,s_i=-1\)，问题拆分成了\(query(\{-s_1,\dots,-s_i\})\)和\(query(\{s_{i+1},\dots,s_n\}\)。

最后直接贪心判定即可。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
#define ll long long
int n;
ll T;
char str[N];
ll pw[27];
int c[27];
int main(){
	freopen("in.txt","r",stdin);
	scanf("%d%lld%s",&n,&T,str+1);
	pw[0]=1;
	for (int i=1;i<=26;++i)
		pw[i]=pw[i-1]*2;
	T=T-pw[str[n]-‘a‘]+pw[str[n-1]-‘a‘];
	for (int i=1;i<=n-2;++i){
		T=T+pw[str[i]-‘a‘];
		c[str[i]-‘a‘+1]++;
	}
	for (int i=26;i>=1;--i){
		while (c[i] && pw[i]<=T){
			c[i]--;
			T-=pw[i];
		}
	}
	if (T==0)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

CF1464C Poman Numbers

原文：https://www.cnblogs.com/jz-597/p/14170193.html