Reincarnation

正因为梦易碎，才格外美好。

ZROI - 2023csp七连测day7 - 送你上路

发表于 分类于 ，
本文字数： 8k 阅读时长 ≈ 7 分钟

打得最爽的一集。

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

签到题

题目简介

存在 个单位，其中每两个相邻的单位换算都是 ，现在给定 个最小单位，求进位之后每一位的和。

数据范围：

名副其实签到，求 的 进制下每一位的和。

不会还需要我贴代码吧。

过了个过

题目简介

给定一个长度为 的 串，每次操作可以删除一个任意长度的 交替的子串，删除后两端合并。求出删掉整个串需要的最小次数。

数据范围：

发现所有会对答案进行额外的贡献的情况仅有 相邻的情况，也就是 和 。

我们设 表示 和 的个数，这些显然要么从中间断开，要么一个一个被删除，然后你发现无论如何删除这个子串的操作数都是 ，所以最后答案是 。

不会还需要我贴代码吧。

河了个河

题目简介

给定一个 阶排列 ，维护 次操作：

  • 循环左移，即将 变成 ，将 移到 ；
  • 翻转，即对于 ，交换 。

每次操作结束后求出逆序对数，以 。对 取模。

数据范围：

考虑这个经典的问题，那么性质一定出在操作上。

对于操作一，你发现除了 之外，其它逆序对不会有任何改变，更具体地说，将 移到 ，逆序对数减少 ，增加 。总体来说，也就是 。这个可以 维护。

然后考虑翻转操作，这个更经典了，那就是逆序对数和顺序对数交换，那么对于操作一我们再维护一个顺序对数，然后直接交换即可。也可以 。

我的做法是，直接维护 的值和位置，然后将以 起头的排列直接处理出来（顺序和逆序都处理），然后对于 找到答案即可。

当然也可以操作 的时候动态维护当前答案，这个没什么影响。

刚开始写了个大常数两棵主席树，后来才找到操作一的性质，就可以从 转移变成 了。

时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// ----- Eternally question-----
// Problem: C. [2023CSP七连 Day7]河了个河
// Contest: ZROI - 23csp7连测day7之送你上路
// URL: http://zhengruioi.com/contest/1469/problem/2742
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-14 18:34:43
// ----- 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; }
const int MAXN=1e6+10;
const int Mod=998244353;
int N,Q,p[MAXN];
ll realans,Pw[MAXN],ans[MAXN];
char Oper[MAXN];
struct BIT
{
	int Tre[MAXN],Siz;
	inline void build(int n){ Siz=n;for(int i=1;i<=n;++i) Tre[i]=0; }
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline int get(int l,int r){ return l>r?0:query(r)-query(l-1); }
}Tre;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q),Pw[0]=1;Tre.build(N);
	for(int i=1;i<=Q;++i) Pw[i]=Pw[i-1]*233%Mod;
	for(int i=1;i<=N;++i) read(p[i]),p[i+N]=p[i];
	scanf("%s",Oper+1);
	for(int i=1;i<=N;++i)
	{
		ans[1]+=Tre.get(p[i]+1,N);
		ans[N+N]+=Tre.query(p[i]-1);
		Tre.add(p[i],1);
	}
	for(int i=2;i<=N;++i) ans[i]=ans[i-1]-(p[i-1]-1)+(N-p[i-1]);
	for(int i=N+N-1;i>=N+1;--i) ans[i]=ans[i+1]-(p[i+1]-1)+(N-p[i+1]);
	for(int i=1;i<=N+N;++i) ans[i]%=Mod;
	int posfir=1,possec=1,delta=1,ansflag=1;
	for(int i=1;i<=Q;++i)
	{
		if(Oper[i]=='0')
		{
			if(delta==1)
			{
				posfir=posfir%N+1;
				possec=(possec+N-2)%N+1;
			}
			else
			{
				posfir=(posfir+N-2)%N+1;
				possec=possec%N+1;
			}
		}
		else delta*=-1,ansflag^=1;
		// write(delta,' ',ansflag,' ',posfir,' ',possec,'\n');
		// write(ansflag?ans[posfir]:ans[N+N-possec+1],'\n');
		ll lastans=ansflag?ans[posfir]:ans[N+N-possec+1];
		realans=(realans+lastans*Pw[Q-i]%Mod)%Mod;
	}
	write(realans);
	return 0;
}
/*

*/

卒了个卒

题目简介

给定 个不可重集 ，其中最大元素不超过 。

定义一个下标对 是合法的，当且仅当：

  • ；
  • 将 抽象为数轴上的小球，每个小球从 开始向右滚动；
  • 将 抽象为数轴上的无穷大的洞，可以接纳所有 的小球。
  • 每个小球会掉入其向右滚动时第一个到达的洞（即最小的 满足 ）。如果不存在这个 ，则视为这个小球不会掉入洞。
  • 记有 个有球的洞，若 ，那么这个集合对合法。

求合法集合对的个数。

数据范围：

本场最大捡漏。

考虑直接枚举 ，我们首先对所有集合做前缀和 表示集合 值域在 中有多少个数，然后每次枚举 的元素，然后直接求 是否非零。

然后用逻辑表达式代替条件语句，代码简洁点，时间复杂度 就直接过了。

正解是维护两个 std::bitset ，表示当前球和有球的洞的状态，然后枚举遇到球就将 置为 ；遇到洞就将 异或上 ，并清空 。

上述过程用 std::bitset 维护，时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// ----- Eternally question-----
// Problem: D. [2023CSP七连 Day7]卒了个卒
// Contest: ZROI - 23csp7连测day7之送你上路
// URL: http://zhengruioi.com/contest/1469/problem/2743
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-14 20:53: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; }
const int MAXN=7.5e3+10,MAXM=60;
int N,M,K[MAXN],a[MAXN][MAXM];
int pre[MAXN][MAXM];
namespace AnotherSolve
{
	const int MAXS=1<<10|10;
	int tmp1[MAXM],tmp2[MAXM],K1,K2;
	bool ans[MAXS][MAXS];
	int Sta[MAXN];
	inline bool main()
	{
		for(int s1=0;s1<(1<<M);++s1)
			for(int s2=0;s2<(1<<M);++s2)
			{
				K1=K2=0;
				for(int i=1;i<=M;++i)
				{
					if(s1>>(i-1)&1) tmp1[++K1]=i;
					if(s2>>(i-1)&1) tmp2[++K2]=i;
				}
				int cur1=1,cur2=1,cnt=0,cnthole=0;
				while(cur1<=K1&&cur2<=K2)
				{
					if(tmp1[cur1]<=tmp2[cur2]) ++cnt,++cur1;
					else cnthole+=(!!cnt),++cur2,cnt=0;
				}
				cnthole+=(!!cnt),ans[s1][s2]=cnthole&1;
			}
		for(int i=1;i<=N;++i)
			for(int j=1;j<=K[i];++j) Sta[i]|=1<<(a[i][j]-1);
		int res=0;
		for(int i=1;i<=N;++i)
			for(int j=i+1;j<=N;++j)
				res+=ans[Sta[i]][Sta[j]];
		write(res,'\n');
		return 0;
	}
};
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i)
	{
		read(K[i]);
		for(int j=1;j<=K[i];++j) read(a[i][j]),pre[i][a[i][j]]=1;
		std::sort(a[i]+1,a[i]+K[i]+1);
		for(int j=1;j<=M;++j) pre[i][j]+=pre[i][j-1];
	}
	if(M<=10) return AnotherSolve::main();
	int ans=0;
	for(int i=2;i<=N;++i)
		for(int j=1;j<i;++j)
		{
			int cnt=0;
			for(int k=1;k<=K[i];++k) cnt+=(pre[j][a[i][k]]>pre[j][a[i][k-1]]);
			ans+=cnt&1;
		}
	write(ans);
	return 0;
}
/*

*/
相关文章