ZROI - 2023noip十连测day4

倍权重掉大分。

比赛链接：http://zhengruioi.com/contest/1445

A. 富贵竹

题目简介

从 延 发射一颗小球，边界为 ，每单位时间移动 ，当然，碰到边界就会反弹，左右边界则左右反，上下亦之。求多少单位时间后回到 。多次询问。

数据范围：

考虑 静态桌面时出现的泡泡，只有当碰到某个角时会原路返回（ 显然就不需要了）。

我们设 ，以 为例，我们列出所有与边界相关的位置：。

用 表示：。

然后你发现当 时后面为 ，所以我们考虑 的形式。

手玩一下发现每次碰边界的地方是 ，所以最后的答案为 ，当然，只有 会出现第一次的角是 ，这个时候 显然。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: A. 23zr提高day4富贵竹
// Contest: ZROI - 23noip十连测day4
// URL: http://zhengruioi.com/contest/1445/problem/2670
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-17 08:35:54
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
int Q;
ll N,M;
ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Q);
	while(Q--)
	{
		read(N,M);
		ll gc=gcd(N,M);
		write(M*N/gc*2,'\n');
	}
	return 0;
}
/*

*/

---

B. 柳穿鱼

题目简介

给定一个有 个结点 条边的无向图，现在需要给所有边染色（有黑色和白色），求出所有保留黑边后所有结点度数为偶数的方案，并输出这个方案中黑边个数平方的和。不保证重边，自环，连通。对 取模。

数据范围：

首先不考虑平方，对每个连通块建立 树。然后考虑树边和非树边。容易发现非树边约束了树边，如果所有非树边都被决定了，那么树边的选择是唯一的。这个可以直接遍历 树自下而上的决定，得到答案 ，其中 是连通块个数。

然后考虑变成平方贡献。

考虑枚举其中的两条边，指定其为黑色后计算贡献，然后根据连通性分类讨论：

• 如果这两条边中存在一条割边（设为 ），那么断掉 后该连通块会被分割成两部分，我们考虑没有 的那部分，这个连通块中有一个结点度数 （连接了 ），所以，当没有 前，连通块度数和为奇数，否则无解。
• 当两条边共同组成了一个割边（删掉后连通块 ），那么方案数为 。
• 否则连通块个数不变，方案数为 。

然后考虑统计点对，这是一个 的做法，显然不优美。所以考虑对所有非树边随机权值 ，树边对应所有覆盖非树边的异或和。

为什么可以这么做

参考了一道古老题 （ 上的，暂无链接），通过分讨树边和非树边，随机权值异或，那么当异或和为 时，尽可能存在一条树边以及其对应环的所有边，可以用来判断连通性。

那么对于 的边一定是割边，而 的边对则对应第二种情况，否则第三种。这个可以直接用哈希维护做到 。

AC Code

官方题解 我的代码

#include <bits/stdc++.h>
using u64 = unsigned long long;
constexpr int mod = 1e9 + 7, inv4 = (mod + 1)/ 4;
int main() {
	// freopen("in.txt", "r", stdin);
	std::ios::sync_with_stdio(false), std::cin.tie(0);
	int n, m;
	std::mt19937_64 hua(time(0));
	std::cin >> n >> m;
	std::vector<std::vector<std::pair<int, int>>> G(n);
	for(int i = 0; i < m; i ++) {
		int u, v;
		std::cin >> u >> v;
		u --, v --;
		G[u].emplace_back(v, i);
		if(u != v) G[v].emplace_back(u, i);
	}
	std::unordered_map<u64, int> cnt;
	std::vector<u64> val(n);
	std::vector<int> vis(n), instack(n);
	int way = 1;
	std::function<void(int, int)> dfs = [&] (int u, int par) {
		vis[u] = instack[u] = 1;
		for(auto edge : G[u]) {
			int v, eid;
			std::tie(v, eid) = edge;
			if(eid == par) continue;
			if(vis[v]) {
				if(instack[v]) {
					u64 tmp = hua();
					val[u] ^= tmp;
					val[v] ^= tmp;
					cnt[tmp] ++;
					way = 2 * way % mod;
				}
			} else {
				dfs(v, eid);
				val[u] ^= val[v];
			}
		}
		instack[u] = 0;
	};
	for(int i = 0; i < n; i ++) {
		if(!vis[i]) {
			dfs(i, -1);
			assert(val[i] == 0);
		}
	}
	for(int i = 0; i < n; i ++) {
		if(val[i]) {
			cnt[val[i]] ++;
		}
	}
	int all = 0;
	int pair = 0;
	for(auto ele : cnt) {
		int cnt = ele.second;
		all += cnt;
		pair = (pair + 1ll * cnt * cnt) % mod;
	}
	all = 1ll * all * all % mod;
	std::cout << 1ll * way * (all + pair) % mod * inv4 % mod << '\n';
	return 0;
}

// ----- Eternally question-----
// Problem: B. 23zr提高day4柳穿鱼
// Contest: ZROI - 23noip十连测day4
// URL: http://zhengruioi.com/contest/1445/problem/2671
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-17 08:51:07
// ----- Endless solution-------

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=1e6+10;
const int Mod=1e9+7;
template<class T>
inline void add(T &x,T y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M,C,Num,Pw[MAXN];
ll val[MAXN],rd[MAXN],ans;
bool Vis[MAXN];
std::vector<Pir>Edges[MAXN];
std::mt19937_64 rnd((ll)new char);
std::unordered_map<ll,int>Hash;
void dfsTree(int x,int fe)
{
	Vis[x]=1;
	for(auto p:Edges[x])
	{
		int v=p.fir,id=p.sec;
		if(id==fe) continue;
		if(!Vis[v]) dfsTree(v,id),val[id]=rd[v],rd[x]^=rd[v];
		else if(!val[id]) val[id]=rnd(),rd[x]^=val[id],rd[v]^=val[id];
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M),Pw[0]=1;Hash.clear();
	for(int i=1,u,v;i<=M;++i)
	{
		read(u,v);Pw[i]=(Pw[i-1]<<1)%Mod;
		Edges[u].push_back(Mkr(v,i));
		Edges[v].push_back(Mkr(u,i));
	}
	for(int x=1;x<=N;++x) if(!Vis[x]) dfsTree(x,0),++C;
	for(int i=1;i<=M;++i) if(val[i]) ++Num,++Hash[val[i]];
	for(auto p:Hash)
	{
		add(ans,(ll)p.sec*p.sec%Mod*Pw[(M-2)-N+(C+1)]%Mod);
		add(ans,(ll)p.sec*(Num-p.sec)%Mod*Pw[(M-2)-N+C]%Mod);
	}
	write(ans);
	return 0;
}
/*

*/

---

C. 雁河菊

题目简介

给定一个长度为 的序列 ，并构造一个 ，保证 。也就是 序列中包含所有 （同一个数可以出现多次），并重排 ，最小化：

$$\sum_{i=1}^{n}|a_i-b_i|$$

多测。保证

数据范围：

考虑一个朴素的 ，设状态为 表示前 （排序后）中出现了 ，发现只能向 ，其它的都不优或者不合法。

考虑现在新加入的 ，我们进行分类讨论：

• ，那么直接向 更新，如果 一定不优。
• ，那么可以向 转移。
• 如果 ，显然也只有 更优。

所以我们发现只有一种情况会转移 ，其余都是 。

考虑维护 ，所以只有四种操作：

• 全局平移 ；
• 全局加绝对值一次函数；
• 单点修改；
• 单点查询。

对操作一打标记，对操作二左右拆分，那么这就是一个可以通过线段树很好维护的操作。可以 做，通过 的点。

考虑到全局平移量为 级，考虑直接维护指针 ，然后在右侧直接维护一次函数加前后缀的标记，在枚举的时候统一计算，这样可以做到线性， 通过本题。

AC Code

官方题解 我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1e18;

template <int T>
struct fast_io {
	char p[T], *p1, *p2;
	fast_io() {
		p1 = p2 = p;
		fread(p, 1, T, stdin);	
	}
	char gc() {
		return *p1++;
	}

};
fast_io<110'000'000> io;
int read() {
	int r = 0, neg = 1;
	char ch;
	do ch = io.gc();while (ch < 48 || ch > 57);
	do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return r;
}

struct func {
	i64 k, b;
	func(i64 k, i64 b) : k(k), b(b) {}
	func() : b(0), k(0) {}
	friend func operator + (func x, func y) {
		return func(x.k + y.k, x.b + y.b);
	}
	friend func operator - (func x, func y) {
		return func(x.k - y.k, x.b - y.b);
	}
};
i64 operator + (i64 x, func y) {
	return x * y.k + y.b;
}
int main() {
//	freopen("in.txt", "r", stdin);
	for(int T = read(); T; T --) {
		int n = read(), m = read();
		std::vector<int> a(n);
		std::vector<int> tot(m + 1);
		for(auto &x : a) tot[x = read()] ++;
		int mxlen = n + m + 1;
		std::vector<func> pre(mxlen + 2), suf(mxlen + 2);
		std::vector<i64> f(mxlen + 2, inf);
		int cur = n + 1, cnt = - n - 1;
		auto inc = [&] {
			suf[cur + 1] = suf[cur + 1] + suf[cur];
			f[cur] += cur + suf[cur];
			suf[cur] = func();
			cur ++;
		};
		auto dec = [&] {
			pre[cur - 2] = pre[cur - 2] + pre[cur - 1];
			f[cur - 1] += (cur - 1) + pre[cur - 1];
			pre[cur - 1] = func();
			cur --;
		};
		auto query = [&] (int x) {
			while(cur > x) dec();
			while(cur < x + 1) inc();
			return f[x];
		};
		auto add = [&] (int x, func ltag, func rtag) {
			while(cur > x) dec();
			while(cur < x) inc();
			pre[x - 1] = pre[x - 1] + ltag;
			suf[x] = suf[x] + rtag;
		};
		auto update = [&] (int x, i64 val) {
			while(cur > x) dec();
			while(cur < x + 1) inc();
			f[x] = std::min(f[x], val);
		};
		f[cur] = 0;
		for(int i = 1; i <= m; i ++) {
			for(int j = 0; j < tot[i]; j ++) {
				int x = i;
				x -= cnt ++;
				i64 val = query(x);
				add(x, func(-1, x - 1), func(1, -x + 1));
				update(x - 1, val);	
			}
		}
		int last = cur;
		while(cur <= mxlen) inc();
		cur = last;
		while(cur > 1) dec();
		std::cout << *std::min_element(f.begin(), f.end()) << '\n';
	}
	std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
	return 0;
}

// ----- Eternally question-----
// Problem: C. 23zr提高day4雁河菊
// Contest: ZROI - 23noip十连测day4
// URL: http://zhengruioi.com/contest/1445/problem/2672
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-17 08:56:02
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<int T>
struct fast_io
{
    char p[T],*p1,*p2;
    fast_io(){ p1=p2=p;fread(p,1,T,stdin); }
    char gc(){ return *p1++; }
};
fast_io<110'000'000>io;
inline int read()
{
    int r=0;
    char ch;
    do ch=io.gc();while(ch<48||ch>57);
    do r=(r<<3)+(r<<1)+ch-48,ch=io.gc();while(ch>=48&&ch<=57);
    return r;
}
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
template<class T>
inline T abs(T x){ return x<0?-x:x; }
const int MAXN=1e7+10;
const int Inf=0x3f3f3f3f;
int Test,N,M;
int Hash[MAXN],val[MAXN];
namespace Brute
{
	const int MAXBr=3e3+10;
	int Dp[MAXBr][MAXBr],a[MAXBr];
	inline void solve()
	{
		for(int i=1,cnt=0;i<=M;++i)
			if(Hash[i])
			{
				for(int j=1;j<=Hash[i];++j) a[++cnt]=i;
				Hash[i]=0;
			}
		for(int i=0;i<=N;++i)
			for(int j=0;j<=M;++j)
				Dp[i][j]=Inf;
		std::sort(a+1,a+N+1);
		Dp[0][0]=0;
		for(int i=1;i<=N;++i)
			for(int j=1;j<=i;++j)
				checkMin(Dp[i][j],std::min(Dp[i-1][j],Dp[i-1][j-1])+abs(a[i]-j));
		int ans=Inf;
		for(int i=1;i<=M;++i) checkMin(ans,Dp[N][i]);
		write(ans,'\n');
		return ;
	}
};
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	Test=read();
	while(Test--)
	{
		N=read(),M=read();
		for(int i=1;i<=N;++i) ++Hash[read()];
		// if(N<=3000){ Brute::solve();continue; }
		ll ans=0;N=0;
		for(int i=1;i<=M;++i) while(Hash[i]) Hash[val[++N]=i]--;
		for(int i=1;i<=N;++i) if(val[i]>i) ans+=val[i]-i,val[i]=i;
		for(int i=1,cur=0;i<=N;++i)
		{
			++Hash[val[i]=i-val[i]],++cur;
			while(!Hash[cur]) --cur;
			if(val[i]<cur) ans+=cur-val[i],--Hash[cur],++Hash[val[i]];
		}
		for(int i=1;i<=N;++i) Hash[val[i]]=0;
		write(ans,'\n');
	}
	return 0;
}
/*

*/

---