首页 > 其他分享 >P3604 美好的每一天题解

P3604 美好的每一天题解

时间:2023-09-03 10:23:40浏览次数:43  
标签:奇偶 字符 题解 ll t2 t1 异或 美好 P3604

传送门

好题!

首先说这道题的时间复杂度:\(O(26n\sqrt n)\)。因为转移是的常数是 \(O(26)\) 并非 \(O(1)\),这启示我们,看数据范围,不要被O(1)给限制了,O(1)是一般情况,有些题不一般

首先,回文串能出现的条件是所有的字符都出现偶数次 \(or\) 仅有一个字符出现奇数次,所以我们并不关心每个字符出现多少次,只关注他们的奇偶

因为只有 \(26\) 个字符,所以考虑状压,对于每个字符:\(1\) 表示出现奇数次,\(0\) 表示出现偶数次,对于新加入的字符,使用异或就好了。

考虑前缀和,令 \(a_i\) 表示 \([1,i]\) 这个区间内每个字符的奇偶次数,那么就有区间 \([l,r]\) 每个字符出现的奇偶次数为 \(a_r \oplus a_{l-1}\)

最后,对于这道题,我们考虑使用莫队,假设我们已经知道了 \([l,r]\) 的答案,那么求 \([l,r+1]\) 的答案时候就可以只加入 \(a_{r+1}\) ,然后判断区间 \([l,r]\) 中与 \(a_{r+1}\)异或为 \(0\) 的 \(a_x\) 个数和与其异或为 \(2^i\) 的 \(a_x\) 个数。

上代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=60050;
ll n,m,a[N],b[N],sq;
char sr[N];
struct jgt
{
	ll l,r,id;
}q[N];
ll ans[N];
bool cmp(jgt t1,jgt t2)
{
	return (b[t1.l]^b[t2.l])?b[t1.l]<b[t2.l]:((b[t1.l]&1)?t1.r<t2.r:t1.r>t2.r);
}
ll now;
ll cnt[(1<<26)+50];
void add(ll wz)
{
	now+=cnt[a[wz]];
	cnt[a[wz]]++;
	for(ll i=0;i<26;i++)
		now+=cnt[a[wz]^(1<<i)];
}
void del(ll wz)
{
	cnt[a[wz]]--;
	now-=cnt[a[wz]];
	for(ll i=0;i<26;i++)
		now-=cnt[a[wz]^(1<<i)];
}
int main()
{
	scanf("%lld %lld",&n,&m);
	scanf("%s",sr+1);
	sq=sqrt(n);
	for(ll i=1;i<=n;i++)
	{
		a[i]=1<<(sr[i]-'a');
		a[i]^=a[i-1];
	}
	for(ll i=0;i<=n;i++)
	b[i]=i/sq+1;
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld %lld",&q[i].l,&q[i].r);
		q[i].l--;
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	ll le=0,ri=0;
	cnt[0]++;
	for(ll i=1;i<=m;i++)
	{
		while(ri<q[i].r) add(++ri);
		while(le>q[i].l) add(--le);
		while(ri>q[i].r) del(ri--);
		while(le<q[i].l) del(le++);
		ans[q[i].id]=now;
	}
	for(ll i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

标签:奇偶,字符,题解,ll,t2,t1,异或,美好,P3604
From: https://www.cnblogs.com/pengchujie/p/17674663.html

相关文章

  • 【题解】AtCoder Beginner Contest 318(D - Ex)
    赛时过了A-G,Ex仿佛猜到了结论但是完全不懂多项式科技,就炸了。大家好像都秒了A,B,C就不写了。D.GeneralWeightedMaxMatching题目描述:给你一个加权无向完全图,图中有\(N\)个顶点,编号从\(1\)到\(N\)。连接顶点\(i\)和\(j\)的\((i<j)\)的权重为\(D_{i,j}\)。在......
  • P4198 楼房重建题解
    传送门一眼数据结构。考虑线段树,记录该区间能看到最多的建筑数量\(ans_{wz}\)以及看到区间中最大的斜率(或者说,该区间内最后看到的建筑)\(xl_{wz}\)。很明显,假如我现在的修改操作是\((x,y)\),那么会改变\(\log_n\)个节点,即包含\(x\)的节点,考虑如何修改他们的\(ans\)和\(......
  • AT_abc318_e 题解
    AT_abc318_eSandwiches题解Links洛谷AtCoderDescription给定一个长度为\(n\)的序列\(a\),找到满足以下条件的三元组\((a,b,c)\)的数量。\(i<j<k\);\(a_{i}=a_{k}\);\(a_{i}\neqa_{j}\)。数据范围:\(1\leqn\leq3\times10^{5}\),\(1\leqa_{i}\leqn......
  • ABC317题解报告
    我直接从第三题开始讲了。T3把数组\(A\)从大到小排序。然后从前往后把前\(q\)个数加起来,然后判断这\(q\)个数的和与\(d\)的大小关系,如果大了就变成\(d\)。然后有些细节就看代码吧。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintm......
  • 龙芯平台Hadoop集群搭建问题解决
    这几天一直在困扰我pycurl版本和本机的版本不符合他连接又连接的自己自带的版本与系统不相同低级也会报错 https://blog.csdn.net/u010910682/article/details/89496550/?ops_request_misc=&request_id=&biz_id=102&utm_term=pycurl7.45.2%20%E6%90%AD%E9%85%8Dlibcurl%E6%......
  • 【题解】NOIP2021
    咕咕咕的东西总是要补的。A.报数题目描述:报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数,但如果下一个报的数是\(7\)的倍数,或十进制表示中含有数字\(7\),就必须跳过这个数,否则就输掉了游戏。在一个风和日丽的下午,刚刚结束SPC20nn比赛的小r和......
  • 【题解】Luogu[P7706] 「Wdsr-2.7」文文的摄影布置
    Link一道很有意思的线段树题。第一步分析,我们要求最大的\(a_i+a_k-\min{(b_j)}\),事实上我们可以直接省去这个\(\min\)因为要最大化这个东西,选出来的\(b_j\)必然是最小的,所以原题转化为给定\(l,r\)求\(\max{(a_i-b_j+a_k)}\)其中\(i<j<k\)。第二步分析,我们发现这是一......
  • 【题解】Educational Codeforces Round 153(CF1860)
    每次打都想感叹一句,Educational名不虚传。A.NotaSubstring题目描述:有\(t\)组数据,对于每一组数据,你需要判断能否构造一个只由左右括号组成且长度为已经给定字符串的\(2\)倍且已经给定的字符串不是子串的合法字符串。注:合法的字符串是左右括号能完全匹配的字符串。如果能,......
  • 【题解】Luogu-P2482 SDOI2010 猪国杀
    写了\(358\)行,\(11.94\mathrm{KB}\),有这么几个地方写挂了:反猪决斗一定选主猪。游戏结束判定是主猪死亡或全部反猪死亡。决斗可能被反杀,之后不能再出牌。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intn,m;charCh[3];queue<char>Deck;in......
  • CF1863C 题解
    CF1863CMEXRepetition题解Links洛谷CodeforcesDescription给你一个长度为\(n\)的序列\(a\),满足\(\foralli\in[1,n]\),\(0\leqa_{i}\leqn\)且序列中的数互不相同。定义一次操作为:按照\(i\)从\(1\)到\(n\)的顺序,\(a_{i}\gets\operatorname{MEX}(a_{1}......