【LGR-073】洛谷 7 月月赛

AP6687 论如何玩转 Excel 表格

考虑我们一个数是要去一个固定的位置的,而且我们同一列的数无论怎么交换都无法分离

而且还有一个性质是如果现在行与目标行差的奇偶性为奇数我们就要不在同一列才有解

于是判断合法条件的条件就是这些了qwq

然后求最小步数其实就是一个归并排序求逆序对的问题

目标位置的第一列为1,第二列为2....再把给定位置的对应列填上相应数字,然后求逆序对即可

BP6688 可重集

题面让我们维护一个区间排序判相同

而且还要支持值域平移....

所以考虑hash,我们可以用sin,cos神仙hash

具体就是每个数hash值就是他的sin,cos值

然后我们值域平移相当于所有数+k,sin,cos可以用对应的诱导公式加上k

sin(x+k),cos(x+k)的那个

除非卡精度否则永不冲突

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define db double 
using std::max;
const db eps = 1e-6;
const int MAXN = 1e6 + 7;
const int MAXT = 2e6 + 7;
int n, q, a[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;

struct rec {
	double sum1, sum2;
	int maxx;
	rec(): sum1(0), sum2(0), maxx(0) {};
	rec(double a, double b, int c) : sum1(a), sum2(b), maxx(c) {};
	rec operator+(const rec &x) {
		return rec(sum1 + x.sum1, sum2 + x.sum2, max(maxx, x.maxx));
	}
} tr[MAXT];

struct rec1 {
	int root, T, ls[MAXT], rs[MAXT];
#define mid ((l+r)>>1)
	inline void pushup(int x) {
		tr[x].sum1 = tr[ls[x]].sum1 + tr[rs[x]].sum1 ;
		tr[x].sum2 = tr[ls[x]].sum2 + tr[rs[x]].sum2;
		tr[x].maxx = max(tr[ls[x]].maxx, tr[rs[x]].maxx);
	}
	inline void build(int &k, int l, int r) {
		if(!k)k = ++T;
		if(l == r) {
			tr[k].sum1 = sin(a[l]);
			tr[k].sum2 = cos(a[l]);
			tr[k].maxx = a[l];
			return ;
		}
		build(ls[k], l, mid);
		build(rs[k], mid + 1, r);
		pushup(k);
	}
	inline void modify(int k, int l, int r, int pos, int V) {
		if(l == r) {
			tr[k].sum1 = sin(V);
			tr[k].sum2 = cos(V);
			tr[k].maxx = V;
			return ;
		}
		if(pos <= mid)modify(ls[k], l, mid, pos, V);
		else modify(rs[k], mid + 1, r, pos, V);
		pushup(k);
	}
	inline rec query(int k, int l, int r, int L, int R) {
		if(l >= L && r <= R) {
			return tr[k];
		}
		if(R <= mid)return query(ls[k], l, mid, L, R);
		else if(L > mid)return query(rs[k], mid + 1, r, L, R);
		else return query(ls[k], l, mid, L, R) + query(rs[k], mid + 1, r, L, R);
	}
} T1;

int main() {
	n = read();
	q = read();
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	T1.build(T1.root, 1, n);
	for(int i = 1, opt, l1, l2, r1, r2; i <= q; ++i) {
		opt = read();
		if(opt) {
			l1 = read();
			r1 = read();
			l2 = read();
			r2 = read();
			rec tmp1 = T1.query(T1.root, 1, n, l1, r1);
			rec tmp2 = T1.query(T1.root, 1, n, l2, r2);
			int k = tmp2.maxx - tmp1.maxx;
			// printf("%d?\n", k);
			db Sk = sin(k), Ck = cos(k);
			// printf("%lf %lf\n", Sk, Ck);
			// printf("%lf %lf %lf %lf %lf %lf\n", Sk, Ck, tmp1.sum1, tmp2.sum1, tmp1.sum2, tmp2.sum2);
			if((fabs(tmp1.sum1 * Ck + tmp1.sum2 * Sk - tmp2.sum1) <= eps) && (fabs(tmp1.sum2 * Ck - tmp1.sum1 * Sk - tmp2.sum2) <= eps)) 	{
				puts("YES");
			} else puts("NO");
		} else {
			l1 = read();
			r1 = read();
			T1.modify(T1.root, 1, n, l1, r1);
		}

	}
	return 0;

}

这份代码换成zkw线段树就过掉了

CP6689 序列

N=1答案是0

N=2答案是1/2,因为我们第一次操作操作位置1就没有合法,否则就有一个合法

还有%5的数据可以搜索

一个显然的结论是:右括号数目相同的括号序列出现概率相同

$f_{i,j}$ 表示当前参数为i,S中右括号数目为j

f_{i-1,j}=\frac{N-j}{N}\sum_{k}^{j-1}f_{i,k}\prod_{l=j}^k\frac{l}{N}

首先 $f_{i,j-1}$ 可以O1计算,后面那个参数相当于没有,对于k>=j

相当于j增加1,我们的后面那一项集体减少j/N

所以我们可以处理出每个数*后面前缀积,然后j增加一就整体除掉

这样可以前缀和 $O(nk)$

然后我们能求出有d个右括号的括号序列的概率,然后除以个数,我们就能的到每一种有d个右括号的括号序列的概率

然后考虑对于一个有d个右括号的括号序列的最长合法括号子序列计数

结论:对于 $sum_i$ 表示(为1)为-1的前缀和,那么最长的为 $ans=N-sum_n+2minsum_i$

这个证明考虑不匹配的,sum_i前面有最长的右括号没法匹配, $sum_n-sum_i$ 是最长的左括号他们不能匹配

然后n-不合法的就是答案了....

显然 $sum_n$ 在知道总的右括号序列d后很好算

那么就是最小前缀和不能超过某个值的长度为N的+1序列计数....

我们把它放到数轴上,就是相当于不能到达某个点的方案数....

这个可以考虑总的减去不和法的,就是用从x=0出发的方案数 $\binom{n}{x}$

减去x=-k的方案数 $\binom{n}{x-k}$ (先走k步)

做完了 $O(nk+n^2)$

夏晓光(loveJY)的博客

SDSCDay5