首页 > 其他分享 >P8908 [USACO22DEC] Palindromes P 题解

P8908 [USACO22DEC] Palindromes P 题解

时间:2024-09-26 21:01:25浏览次数:8  
标签:Palindromes P8908 int 题解 texttt tree mid ans

P8908 [USACO22DEC] Palindromes P 题解

算是好题,虽然没什么人做(

简单地,我们考虑如何将一个字符串改变为回文串。显然如果我们判定所有 \(\texttt{G}\) 组成的是回文串,那么整个串一定是回文的。于是我们只考虑改变 \(\texttt{G}\) 的位置。

那么由这类题的套路不难知道最优的变换一定不改变 \(\texttt{G}\) 的先后顺序。于是我们只考虑改变后一半的 \(\texttt{G}\),让这些个 \(\texttt{G}\) 和前一半的 \(\texttt{G}\) 相对应。

具体地,对于一个长度为 \(n\) 的串 \([l,r]\) 有 \(m\) 个 \(\texttt{G}\),记这 \(m\) 个 \(\texttt{G}\) 的位置分别为 \(a_1,a_2,\cdots,a_m\),那么对于 \(a_i(i> \dfrac{m}{2})\),它变换后的对应位置就是 \(r-a_{n-i+1}\)。那么它走过的路径就是 \(|r-(a_{n-i+1}-l)-a_i|=|l+r-a_{i}-a_{n-i+1}|\)。那么我们可以 \(O(m)\) 地求出一个串的最优决策。这样复杂度是 \(O(n^3)\) 的。

考虑优化这个过程。我们发现 \(i\) 和 \(n-i+1\) 相搭配的形式意味着可以向两边递推扩展,具体地,我们枚举 \(i\) 作为序列的中点(中点唯一或不唯一均可),从 \(i\) 分别向 \(1\) 和 \(n\) 扩展,枚举当前范围内的每个区间 \((l,r)\),将 \(l+r\) 加入树状数组就可以方便地维护 \(<l+r\) 和 \(>l+r\) 的数了。

实现的时候注意中点唯一时中点位置固定且不计入 \(l+r\) 的贡献。时间复杂度 \(O(n^2\log n)\)。

题目的关键是发现 \(|l+r-a_i-a_{n-i+1}|\) 的式子和扩展的转移方式。

代码:

#include <bits/stdc++.h>
#define N 7505
using namespace std;
int n;
string s;
int a[N];
struct BIT {
	int lowbit(int x) {
		return x & (-x);
	}
	#define M 15005
	int tree[M];
	void add(int x, int v) {
		while (x < M) {
			tree[x] += v;
			x += lowbit(x);
		}
	}
	int ask(int x) {
		int ans = 0;
		while (x) {
			ans += tree[x];
			x -= lowbit(x);
		}
		return ans;
	}
	void clear() {
		memset(tree, 0, sizeof tree);
	}
} A, B;
int g[N], cnt;
int sum[N], sm[N];
long long ans;

int main() {
	cin >> s;
	n = s.size();
	s = " " + s;
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'G') {
			a[i] = 1;
			g[++cnt] = i;
		}
		else
			++sm[i];
		sm[i] += sm[i - 1];
		sum[i] = sum[i - 1] + a[i];
	}
	g[cnt + 1] = n + 1;
	
	for (int mid = 1; mid <= cnt; mid++) {  
		for (int j = 0; mid - j >= 1 && mid + j <= cnt; j++) {
			int L = g[mid - j - 1] + 1, R = g[mid + j + 1] - 1;
			int tmp = g[mid - j] + g[mid + j];
			if (j) {
				A.add(tmp, tmp);
				B.add(tmp, 1);
			}
			for (int l = L; l <= g[mid - j]; l++)
				for (int r = g[mid + j]; r <= R; r++) {
					if ((r - l + 1) % 2 == 0) 
						continue;
					int tmp = l + r;
					int num = B.ask(tmp), as = A.ask(tmp);
					ans += tmp * num - as
					num = B.ask(M - 1) - B.ask(tmp), as = A.ask(M - 1) -  A.ask(tmp);
					ans += as - tmp * num;
					ans += abs((tmp >> 1) - g[mid]);
				}
		}
		A.clear();
		B.clear();
	} 
    
	for (int mid = 1; mid <= cnt; mid++) {
		for (int j = 0; mid - j >= 1 && mid + 1 + j <= cnt; j++) {
			int L = g[mid - j - 1] + 1, R = g[mid + j + 2] - 1;
			int tmp = g[mid - j] + g[mid + j + 1];
			A.add(tmp, tmp);
			B.add(tmp, 1);
			for (int l = L; l <= g[mid - j]; l++)
				for (int r = g[mid + j + 1]; r <= R; r++) {
					int tmp = l + r;
					int num = B.ask(tmp), as = A.ask(tmp);
					ans += tmp * num - as;
					num = B.ask(M - 1) - B.ask(tmp), as = A.ask(M - 1) -  A.ask(tmp);
					ans += as - tmp * num;					
				}
		}
		A.clear();
		B.clear();
	} 
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (((sum[j] - sum[i - 1]) & 1) && ((sm[j] - sm[i - 1]) & 1))
				--ans;
	cout << ans << "\n";
	return 0;
}

标签:Palindromes,P8908,int,题解,texttt,tree,mid,ans
From: https://www.cnblogs.com/Rock-N-Roll/p/18434360

相关文章

  • 【洛谷】P1168 中位数 的题解
    【洛谷】P1168中位数的题解题目传送门题解不懂就问,这是什么标签啊,《线段树》《二分》《堆》《树状数组》qaq谔谔,教练讲的这是一题线段树,看半天看不出来,也不会做,只好去看题解。其他的题解讲什么主席树,平衡树,分块,结果看完第一篇人都傻了。什么东西嘛qaq(恼vector直接一......
  • CF1063E Lasers and Mirrors题解
    一道很好的手玩题,被薄纱了。首先判掉\(\foralli,p_i=i\)的情况(显然是\(n\))然后考虑按照\(p_i\)连边,先构造每一个环的方案。发现可以简单放置两面镜子使得\(i\)射到\(p_i\),而且只要从高到底构造,一定不会产生影响。但是每一个环的最后一个点很特殊,因为第1个点下面放置了让第1个......
  • LOJ 6241. 性能优化 I 题解
    题给代码意为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\sum\limits_{k=1}^j[\gcd(j,k)=1]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\varphi(j)\\......
  • P8475 「GLR-R3」雨水 题解
    关于这道题目卡\(O(n\logn)\)但是放\(O(n^2)\)我也是很疑惑。我们发现,题目要求的是字典序最小的序列。但凡涉及了字典序最小,答案或多或少的都会带点贪心思想。那我们也来贪一贪。考虑当前枚举到第\(i\)个点,如果后面有比它更小的数,那显然把它们交换过来是更优的。如果有多......
  • P8474 「GLR-R3」立春 题解
    俗话说的好:“打表出奇迹”,所以我们这一题打表计算。其实确实可以打表来找规律。通过打表,我们可以获得如下的结果:1 12 33 214 3155 9765…… ……然后观察可得:\[1\times3=1\times(2^2-1)=3\]\[3\times7=3\times(2^3-1)=21\]\[21\times15=21\t......
  • Codeforces Round 971 (Div. 4)题解记录(G3待补)
    A.Minimize!暴力模拟一遍即可#include<iostream>#include<queue>#include<deque>#include<map>#include<set>#include<stack>#include<vector>#include<bitset>#include<math.h>#include<random>#include&l......
  • P8563 Magenta Potion 题解
    前排警告这是较为通用,不需要脑子,但是代码量巨大的题解,请谨慎食用解题思路不知道大家做没做过带修改的区间最大连续子段和,这一题其实就是带修改的区间最大连续子段积。那么其实做法是类似的。我们用线段树维护五个量:当前区间答案,区间前缀最小值,区间前缀最大值,区间后缀最小值,区......
  • P8564 ρars/ey 题解
    显然树上背包。首先一眼会想到的状态:\(dp_{i,j}\)表示\(i\)的子树最后剩下\(j\)个结点的最小代价。然而开始写会发现这并不好DP。于是我们换一个想法:\(dp_{i,j}\)表示\(i\)的子树删去\(j\)个结点的最小代价。则有转移方程:\[dp_{i,j}=\min_{v\inson(i)}\{dp_{i......
  • 题解:UVA1456 Cellular Network
    UVA1456CellularNetwork题解夭寿了!30行写完紫题了!更新:已联系管理员修改难度,现在是绿题题意很简单,不再赘述。首先一个小贪心,将概率\(u​\)进行从大到小的排序,优先查看概率大的区域,显然这样能够保证访问数量期望最小。接着考虑如何将区域分组。一个显而易见的思路是动态......
  • 题解:CF437B The Child and Set
    CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)?\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\),其中最低位的\(1\)在第二位,表示\((2)_{10}\),即\(\operatorname{lo......