目前仍未更新完成，鸽了。

本篇题解提供 C/C++/Python 代码。

考虑到很多选手写的 C++ 代码都偏向 C 语言风格以及有的同学就只会 C 语言，所以会提供 C 语言程序，在此基础上还会补充较为成熟的新标准 C++ 实现。
注意 Python3（CPython）和 PyPy3 只是执行方式有所不同，都可以看作使用 Python 语言。本文特意区分了牛客上的两类执行方式 Python3 和 PyPy3。
考虑到时间成本，对于用 Java 和其它语言的选手，我只能~~祝你们幸福~~认为你们会上述至少一种语言。

注：不论封闭比赛如何地无法接纳 AIGC，AIGC 都毫无疑问是先进生产力。本题解中的不懂之处，均可拿去询问（文本类）AIGC。

A 酒鬼地图前传

注意到 $7<10$ ，所以输出后者。

以下代码直接提交 PHP 可过。

He never showed up to confess

B 酒鬼地图

考虑在给定 $x$ 时给出最佳策略，注意到可以以到达一个酒馆为一种状态，每个状态下，至多只有两个抉择——喝或是不喝，对于当前状态，喝与不喝都不需要考虑后续的状态（无后效性）。求出每个状态的最佳策略下的酒精度最小值的状态转移方程如下。

$\begin{cases}\mathrm{dp}[i]\gets\mathrm{dp}[i-1]+a_i{\small\color{blue}{\boxed{\text{只能喝}}}},&i=1,2,\cdots,x,\\\mathrm{dp}[i]\gets\min(\mathrm{dp}[i-1]+a_i{\small\color{blue}{\boxed{\text{喝}}}},\mathrm{dp}[i-1-x]+\sum\limits_{j=1}^xa_{i-j}{\small\color{darkgreen}{\boxed{\text{不喝}}}}),&i=x+1,x+2,\cdots,n.\end{cases}$

容易想到 $\sum\limits_{j=1}^xa_{i-j}=\sum\limits_{j=i-x}^{i-1}a_j$ 可以用我们老生常谈的前缀和方法线性处理并调用。

注意到当 $x$ 增加时，取 $\min$ 的机会变少了，这意味着在最佳策略下酒精度必然不会减少，那么就存在一个分界使得对于这个分界之前的 $x$ 都不会醉酒，对于这个分界及之后的 $x$ 则都会醉酒。二分找到这个分界即可。

C/C++:

#include<stdio.h>
typedef long long ll;
#define N 200001
int n;ll m;
int a[N];
ll pre[N],dp[N];
ll min(ll a,ll b){return a<b?a:b;}
int isDrunk(int x)
{
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1]+a[i];//喝
		if(i>=x+1)
			dp[i]=min(dp[i],dp[i-x-1]+pre[i-1]-pre[i-x-1]);
	}
	return dp[n]>m;//醉了
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d%lld",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			pre[i]=pre[i-1]+a[i];
		}
		int left=1,right=n+1;
		//在[left,right)中找到第一个True的位置，若没有找到，则有left=right
		// 注意：如果x=n≠1时才会醉，那么不能输出-1
		// 因为这说明x=n-1到x=n也会有变化，不是一定不会醉
		// 只有x≥n再往上加，结果才不会变，可以用奥卡姆剃刀“剃掉”
		while(left<right)//[left,right)
		{
			int mid=(left+right)/2;
			//一个偏左的中间值使得 left≠mid+1，right≠mid，如果中间值偏右则可能会死循环
			if(isDrunk(mid))right=mid;
			//第一个True可能在[left,mid)，否则会最终依旧会回到此时的mid
			else left=mid+1;
			//如果[left,right)存在True的情况，只可能在[mid+1,right)
			//有可能返回
		}
		int x=left;//最终一定会得到left＝right
		if(x==1||x==n+1)printf("-1\n");// x=1一定会醉/x=n+1一定不会醉
		else printf("%d\n",x);
	}
	return 0;
}

PyPy3(仿列表+bisect):

from bisect import *
for _ in range(int(input())):
	n,m=map(int,input().split())
	a=[0]+list(map(int,input().split()))
	pre=[0]*(n+1)
	for i in range(1,n+1):pre[i]=pre[i-1]+a[i]# 前缀处理
	class bisect_list:
		def __len__(self):return n+1# 仿列表下标范围为 [0,n]，有n+1个数
		# 注意：如果x=n≠1时才会醉，那么不能输出-1
		# 因为这说明x=n-1到x=n也会有变化，不是一定不会醉
		# 只有x≥n再往上加，结果才不会变，可以用奥卡姆剃刀“剃掉”
		def __getitem__(self,x):# 通过[x]进行访问，实际上是调用这个函数进行 dp
			if x==0:return False# 不是正整数
			if x>=n+1:raise IndexError("索引超出范围")
			dp=[0]*(n+1)
			for i in range(1,n+1):
				dp[i]=dp[i-1]+a[i]
				if i>=x+1:
					dp[i]=min(dp[i],dp[i-x-1]+pre[i-1]-pre[i-x-1])
			return dp[n]>m# 超了就醉
	#你可以通过 print(bisect_list()) 输出一下这个仿列表
	x=bisect_left(bisect_list(),True)# 找到最小的正整数 x，范围内没有返回 len() 即 n+1
	if x==1 or x==n+1:print(-1)# x=1一定会醉/x=n+1一定不会醉
	else:print(x)

C 尝试逃逸

二维递推方法

注：一般来说，我们把涉及统筹优化的问题的无后效性递推方法称为动态规划方法，而本题是一些组合意义的东西，并非优化问题，故只称为递推方法。

注意到出栈序列能与合法的 $\mathtt{push}$ （加入栈顶）、 $\mathtt{pop}$ （弹出栈顶元素）操作构成的序列构成一一映射，所以只需要求出合法的操作序列的个数即可，所谓操作序列合法也就是不能在栈空的时候依然进行 $\mathtt{pop}$ （弹出栈顶元素）操作。

记录栈顶元素数为状态，再考虑上时间维度，可以设 $f[i][j]$ 表示到时间刻 $i$ 时，栈内有 $j$ 个元素的题目相关的合法的操作序列的种类数。

最初可以认为只有 $f[0][0]=1$ ，表示空序列只有一种。

单个操作 p 要求操作序列一定要加上一个 $\mathtt{push}$ 元素，转移方程为：

$\begin{aligned} \forall j\in\mathbb{N},f[i][j]\gets f[i-1][j-1], \end{aligned}$

显然，所有序列必须添加一个元素；

在一段等待期内（也就是整一段 w 操作段中），只有 $\mathtt{pop}$ 的数量可以影响结果，而它们分布所在的具体时间刻不会影响结果，我们只需要统计 w 操作段的长度即可，设连续 w 的个数为 $\mathrm{cnt}$ ，则转移方程为：

$\forall j\in\mathbb{N},f[i][j]\gets\sum\limits_{k=0}^{\mathrm{cnt}}f[i-1][j+k]$ 。

显然，栈内的元素个数不会超过 $n$ ，把握住这个上界即可。

C/C++:

#include<stdio.h>
const int MOD=998244353;
char S[3001];
int f[3001][1001];
int main()
{
	int n,m;scanf("%d%d%s",&n,&m,S);
	//S以'\0'结尾
	f[0][0]=1;
	//i0是S的下标，i是f的第一维的下标
	int i0=0,i=0;
	while(i0<m)
	{
		i++;
		if(S[i0]=='p')
		{
			for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];
			i0++;
		}
		else
		{
			int cnt=0;
			while(S[i0]=='w')cnt++,i0++;
			for(int j=0;j<=n;j++)
				for(int k=0;k<=cnt;k++)
					if(j+k<=n)f[i][j]=(f[i][j]+f[i-1][j+k])%MOD;
					else break;//该行是一个优化，这个优化可有可无
		}
	}
	int ans=0;
	for(int j=0;j<=n;j++)ans=(ans+f[i][j])%MOD;
	//此时的i就是最后一次更新的结果，显然最后不管栈内剩几个元素，都会被 pop 出去
	//j 不同，最后的 pop 的个数也不同，这就保证了 j 不同，对应的操作序列也不同
	printf("%d",ans);
	return 0;
}

记 $g(n,m)$ 是在给定 $n,m$ 后，给 $f$ 内复制

合理地枚举下标，消掉一维递推状态

注意到操作 p 状态转移只用到 $f$ 第二维更小的状态，可以倒序枚举消掉一维；而一段操作 w 只用到 $f$ 第二维更大的状态，可以正序枚举消掉一维。于是有以下转移方程：

$\begin{cases} \begin{aligned} \textbf{for}\;j\gets n\;\textbf{to}\;1:\;&f[j]\gets f[j-1],\\ &f[0]\gets 0, \end{aligned} &\text{操作 p},\\ \textbf{for}\;j\gets 0\;\textbf{to}\;n:\;f[j]\gets\sum\limits_{k=0}^{\mathrm{cnt}}f[j+k],&\mathrm{cnt}\,\text{个操作 w}. \end{cases}$

C/C++:

#include<stdio.h>
const int MOD=998244353;
char S[3001];
int f[1001];
int main()
{
	int n,m;scanf("%d%d%s",&n,&m,S);
	f[0]=1;
	for(int i=0;i<m;)
	{
		if(S[i]=='p')
		{
			for(int j=n;j>=1;j--)f[j]=f[j-1];
			f[0]=0;
			i++;
		}
		else
		{
			int cnt=0;
			while(S[i]=='w')cnt++,i++;
			for(int j=0;j<n;j++)
				for(int k=1;k<=cnt;k++)
					if(j+k<=n)f[j]=(f[j]+f[j+k])%MOD;
					else break;//该行是一个优化，这个优化可有可无
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++)ans=(ans+f[i])%MOD;
	printf("%d",ans);
	return 0;
}

在以下 C++ 和 Python 程序中，是只考虑到从 $1$ 到最后一个不为 $0$ 状态的实现方式。

C++17:

#include<string>
#include<vector>//#include<deque>
#include<numeric>
#include<iostream>
using namespace std;
const int MOD=998244353;
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n,m;string S; 
	cin>>n>>m>>S;
	vector<int> f={1};//deque<int>
	for(int i=0;i<m;)
	{
		if(S[i]=='p')f.insert(f.begin(),0),i++;//f.push_front(0)
		else
		{
			int cnt=0;
			while(i<m&&S[i]=='w')cnt++,i++;
			for(int j=0;j<f.size();j++)
				for(int k=1;k<=cnt;k++)
					if(j+k<f.size())f[j]=(f[j]+f[j+k])%MOD;
			else break;//该行是一个优化，这个优化可有可无
		}
	}
	cout<<accumulate(f.begin(),f.end(),0,[](int a,int b){return(a+b)%MOD;});
	//也可以是accumulate(f.begin(),f.end(),0ll)%MOD;
	//注意是 0ll 为初值，这样对应模板参数初始值是 long long型的了
	return 0;
}

Python3/PyPy3:

MOD=998244353
n,m=map(int,input().split())
S=input()
f=[1]
i=0
while i<m:
	if S[i]=='p':
		f=[0]+f
		i+=1
	else:
		cnt=0
		while i<m and S[i]=='w':
			cnt+=1
			i+=1
		for j in range(len(f)):
			for k in range(1,cnt+1):
				if(j+k<len(f)):
					f[j]=(f[j]+f[j+k])%MOD
				else:break# 该行是一个优化，这个优化可有可无
print(sum(f)%MOD)

D 舍入

alt

总之是奇偶讨论，方法很多，八仙过海吧。

C/C++:

#include<stdio.h>
int ans[1000];
int main()
{
	int n;scanf("%d",&n);
	int next_frame=12;//初始时默认下一帧是12(cs)
	for(int i=0;i<n;i++)
	{
		int num;scanf("%d",&num);
		if(num%2==0)//偶数帧，能够完整跳过若干个[12,13]周期
		{
			ans[i]=num/2*25;
		}
		else//奇数帧，需要考虑开头第一个帧的时间
		{
			//12,[13,12],[13,12],...,[13,12] 下面是 13
			//13,[12,13],[12,13],...,[12,13] 下面是 12
			ans[i]=next_frame+num/2*25;//除二向下取整个[12,13]周期
			//奇数帧，下一个帧要切换
			if(next_frame==12)next_frame=13;
			else next_frame=12;
		}
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]);
	return 0;
}

PyPy3:

input()
ans=[]
next_frame=12
for num in map(int,input().split()):
	if num%2==0:
		#偶数帧，能够完整跳过若干个[12,13]周期
		ans.append(num//2*25)
	else:
		#12,[13,12],[13,12],...,[13,12] 下面是 13
		#13,[12,13],[12,13],...,[12,13] 下面是 12
		#除二向下取整个[12,13]周期
		ans.append(next_frame+num//2*25)
		#奇数帧，下一个帧要切换
		if next_frame==12:next_frame=13
		else:next_frame=12
print(*ans)

E 等差数列（easy version）

当 $n<2k$ 时无论如何都不能让每个组有两个人，此时必定无解；

当 $n\geqslant 2k$ 时可以构造 $k$ 个集合分别为

$\begin{matrix} \{1,n\},\\ \{2,n-1\},\\ \{3,n-2\},\\ \vdots\\ \{k-1,n-(k-2)\},\\ \{k,k+1，\cdots,n-(k-2)-1\}, \end{matrix}$

alt

即每次将编号最小和最大的抽出来（取当前序列的极差为公差），他们的编号差是目前最大的，对应集合的公差不可能和之后的任何一个集合的公差重复。重复 $k$ 次这样的过程。最后将剩下的人全部“塞进”最后构造的那个集合里，最后这个集合的公差就是 $1$ 了。

用两个相向的指针可以模拟实现这一划分方式。

alt

两个指针相向走 $k-1$ 次，然后把中间的那段再处理一下。

C/C++:

#include<stdio.h>
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n,k;scanf("%d%d",&n,&k);
		if(n>=2*k)
		{
			int i=1,j=n;
			for(int _=1;_<k;_++)printf("2 %d %d\n",i++,j--);//执行 k-1 次
			printf("%d ",j-i+1);
			for(int l=i;l<=j;l++)printf("%d ",l);
			printf("\n");
		}
		else printf("-1\n");
	}
	return 0;
}

PyPy3:

for _ in range(int(input())):
	n,k=map(int,input().split())
	if n>=2*k:
		out=[]
		i,j=1,n
		for __ in range(k):
			out.append([i,j])
			i+=1;j-=1
		out[-1]+=list(range(i,j+1))
		for l in out:print(len(l),*l)
	else:
		print(-1)

F 等差数列（hard version）

对公差 $d$ 有贡献的结点 $u$ 需要满足 $d|u-1$ ，所以共有 $\left\lceil\dfrac{n}{d}\right\rceil$ 个结点对公差 $d$ 有贡献。整体看待所有结点对全体有效公差的贡献方式，设有 $f(n)$ 种不同的贡献，可以发现

$f(n)=\sum\limits_{d=1}^n\left\lceil\dfrac{n}{d}\right\rceil\leqslant\sum\limits_{d=1}^n\left(\dfrac{n}{d}+1\right)=nH(n)+n,f(n)=\mathcal{O}(n\log n),$

其中 $H(n)$ 是调和数列部分和函数， $H(n)=\sum\limits_{i=1}^n\dfrac{1}{i}\in[\ln n,\ln n+1]$ 。那么就可以对每组数据，一次性处理出来所有询问的答案，询问时直接输出答案。DFS 每次将当前访问到的结点对公差的贡献加上，然后回溯的时候再撤回这些贡献，这样就保证只有从根结点（ $1$ 号结点）到当前结点的链上的结点的贡献是有效的了，每次加上贡献的时候记录最大值，撤销则减去贡献。

$1$ 号结点出现在所有的链上，下面提供的程序直接将结点 $1$ 的贡献特别处理出来了。当然，不这么做也可以。

C/C++:

#include<stdio.h>
#include<string.h>
#define N 300001
typedef long long ll;
int head[N],next[2*N],to[2*N],gtop;
int diff[N][181],a[N];
ll dr[N],ans[N];//范围内277200约数个数最多，为180个
int max(int a,int b){return a>b?a:b;}
void DFS(int u,int fa)
{
	for(int i=1;i<=diff[u][0];i++)
	{
		int d=diff[u][i];
		dr[d]+=a[u];
		ans[d]=max(ans[d],dr[d]);
	}
	for(int i=head[u];i;i=next[i])
	{
		int v=to[i];
		if(v!=fa)DFS(v,u);
	}
	for(int i=1;i<=diff[u][0];i++)
	{
		dr[diff[u][i]]-=a[u];//回溯，撤销
	}
}
int main()
{
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j+=i)
			diff[j][++diff[j][0]]=i;
	int T;scanf("%d",&T);
	while(T--)
	{
		int n,q;scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		memset(head,0,sizeof(head[0])*(n+1));gtop=0;
		for(int i=1;i<n;i++)
		{
			int u,v;scanf("%d%d",&u,&v);
			gtop++,next[gtop]=head[u],to[gtop]=v,head[u]=gtop;
			gtop++,next[gtop]=head[v],to[gtop]=u,head[v]=gtop;
		}
		for(int i=1;i<=n;i++)dr[i]=ans[i]=a[1];
		DFS(1,0);
		while(q--)
		{
			int d;scanf("%d",&d);
			printf("%lld\n",ans[d]);
		}
	}
	return 0;
}

C++11:

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
class Solution
{
	vector<int> a;
	vector<vector<int>> e,diff;
	vector<ll> dr,ans;//dr:difference records
	void DFS(int u,int fa)
	{
		for(auto d:diff[u])
		{
			dr[d]+=a[u];
			ans[d]=max(ans[d],dr[d]);
		}
		for(auto v:e[u])if(v!=fa)DFS(v,u);
		for(auto d:diff[u])
		{
			dr[d]-=a[u];//回溯，撤销
		}
	}
public:
	void operator()()
	{
		int n,q;cin>>n>>q;
		a=vector<int>(n+1);
		for(int i=1;i<=n;i++)cin>>a[i];
		diff=e=vector<vector<int>>(n+1);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j+=i)
				diff[j].push_back(i);
		for(int i=1;i<n;i++)
		{
			int u,v;cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dr=ans=vector<ll>(n+1,a[1]);
		DFS(1,0);
		while(q--)
		{
			int d;cin>>d;
			cout<<ans[d]<<'\n';
		}
	}
};
Solution solution;
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--)solution();
	return 0;
}

Python（Python3 超时，PyPy3 段错误，PyPy3 的段错误似乎与 PyPy 的优化策略和牛客系统设定有关，不能完全算这段代码的问题）:

import sys
sys.setrecursionlimit(int(1e8))
N=300000
diff=[[]for i in range(N+1)]
# 整数类型无需在意深浅复制的事情，但是列表等容器需要注意这点
# diff 和 e 必须用 for 循环生成若干个不同的列表
for i in range(1,N+1):
	for j in range(i+1,N+1,i):
		diff[j].append(i)
for _ in range(int(input())):
	n,q=map(int,input().split())
	a=[0]+list(map(int,input().split()))
	e=[[]for i in range(n+1)]
	for i in range(n-1):
		u,v=map(int,input().split())
		e[u].append(v)
		e[v].append(u)
	dr=[a[1]]*(n+1)# 还是深浅复制的事情
	ans=[a[1]]*(n+1)# 两个不同的列表，必须分开写
	# dr: difference records
	def DFS(u,fa):
		for d in diff[u]:
			dr[d]+=a[u]
			ans[d]=max(ans[d],dr[d])
		for v in e[u]:
			if v!=fa:
				DFS(v,u)
		for d in diff[u]:
			dr[d]-=a[u]#回溯，撤销
	DFS(1,0)
	for __ in range(q):
		print(ans[int(input())])

G 树上交换

思路很简单，码量其实也可以不多的数据结构题。1.5kb以内的代码记录

所谓“好数对”的个数就是“逆序对”的个数加上“相等数对”的个数。交换某个结点的左右子结点只会将经由该结点的“逆序对”个数和“顺序对”个数进行调换。处理出来经由每个结点的“逆序对”个数和“顺序对”个数，处理出来 DFN，放到树状数组上跑子树和，单点修改即可。

处理每个结点上的数对时，可以使用二叉搜索树（得有某种平衡方式）、维护值域的线段树，只需要处理小并大操作与小于等于某数的操作即可。

以上方法中，树高在某种意义上是 $h(n)=\mathcal{O}\left(\log n\right)$ 的，再结合小并大，可以得出最劣情况下，树上递归的总次数 $f(n)=\mathcal{O}\left(n\log^2n\right)$ 。

没人会用 Python 写这种东西吧，那就不给 Python 代码了。

C++20(用 GNU 扩展库，牛客 Clang++ 亦支持该库):

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#include<ext/pb_ds/assoc_container.hpp>
class Solution
{
	using RBT=__gnu_pbds::tree<pii,__gnu_pbds::null_type,less<pii>,
		__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;//红黑树，更新树上序信息
	//使用pair<int,int>确保元素可以重复
	class BinaryIndexedTree
	{
		int n;vector<ll> a;
	public:
		void set_n(int n_){n=n_;a=vector<ll>(n+1);}
		void add(int x,ll c){while(x<=n)a[x]+=c,x+=x&-x;}
		ll sum(int x){ll s=0;while(x>0)s+=a[x],x-=x&-x;return s;}
		ll sum(int x,int y){return sum(y)-sum(x-1);}
		void print(){for(int i=1;i<=n;i++)cout<<(sum(i,i))<<' ';cout<<endl;}
	};
	BinaryIndexedTree BIT;
	vector<int> l,r,a;
	vector<ll> lt,gt;
	vector<int> DFN,nsize;int dtime;
	RBT*inorder(int u)
	{
		DFN[u]=++dtime;
		RBT*t1,*t2;
		if(l[u])t1=inorder(l[u]);else t1=new RBT;
		if(r[u])t2=inorder(r[u]);else t2=new RBT;
		nsize[u]=nsize[l[u]]+1+nsize[r[u]];
		gt[u]+=nsize[l[u]]-t1->order_of_key(pair(a[u]+1,0))
			  +t2->order_of_key(pair(a[u],0));
		lt[u]+=nsize[r[u]]-t2->order_of_key(pair(a[u]+1,0))
			  +t1->order_of_key(pair(a[u],0));
		if(t1->size()<t2->size())
		{
			for(auto[f,s]:*t1)
			{
				gt[u]+=t2->order_of_key(pair(f,0));
				lt[u]+=nsize[r[u]]-t2->order_of_key(pair(f+1,0));
			}
			swap(t1,t2);
		}
		else
		{
			for(auto[f,s]:*t2)
			{
				gt[u]+=nsize[l[u]]-t1->order_of_key(pair(f+1,0));
				lt[u]+=t1->order_of_key(pair(f,0));
			}
		}
		for(pii i:*t2)t1->insert(i);delete t2;
		t1->insert({a[u],u});
		ll nowans=(nsize[l[u]]+1ll)*(nsize[r[u]]+1)-1-lt[u];
		BIT.add(DFN[u],nowans);
		return t1;
	}
public:
	vector<ll> operator()(int s,vector<int> A,vector<pii> C,vector<pii> Q)
	{
		vector<ll> ans;
		int n=static_cast<int>(A.size());
		a={0};a.insert(a.end(),A.begin(),A.end());
		l=vector<int>(n+1);r=vector<int>(n+1);
		for(int i=1;i<=n;i++)tie(l[i],r[i])=C[i-1];
		DFN=vector<int>(n+1);nsize=vector<int>(n+1);dtime=0;
		lt=vector<ll>(n+1);gt=vector<ll>(n+1);
		BIT.set_n(n);delete inorder(s);
		for(auto[opt,u]:Q)
		{
			if(opt==1)ans.push_back(BIT.sum(DFN[u],DFN[u]+nsize[u]-1));
			else BIT.add(DFN[u],-gt[u]+lt[u]),swap(lt[u],gt[u]);
		}
		return ans;
	}
};
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n,s;cin>>n>>s;
	vector<int>A(n);for(int&i:A)cin>>i;
	vector<pii>C(n);for(auto&[l,r]:C)cin>>l>>r;
	int q;cin>>q;
	vector<pii>Q(q);for(auto&[opt,u]:Q)cin>>opt>>u;
	vector<ll>&&ans=Solution{}(s,A,C,Q);
	for(ll i:ans)cout<<i<<'\n';
}

C++17(AVL树，仅替换 class):

class Solution
{
	class BinaryIndexedTree
	{
		int n;vector<ll> a;
	public:
		void set_n(int n_){n=n_;a=vector<ll>(n+1);}
		void add(int x,ll c){while(x<=n)a[x]+=c,x+=x&-x;}
		ll sum(int x){ll s=0;while(x>0)s+=a[x],x-=x&-x;return s;}
		ll sum(int x,int y){return sum(y)-sum(x-1);}
		void print(){for(int i=1;i<=n;i++)cout<<(sum(i,i))<<' ';cout<<endl;}
	};
	BinaryIndexedTree BIT;
	static const int N=500001;
	class AVLTree
	{
		inline static int son[N][2],height[N],size[N],val[N];
		int root;
		void pushup(int p)
		{
			size[p]=size[son[p][0]]+size[son[p][1]]+1;
			height[p]=max(height[son[p][0]],height[son[p][1]])+1;
		}
		void rotate(int&p,const int f)//0左 1右 
		{
			int t=son[p][f^1];
			son[p][f^1]=son[t][f];
			son[t][f]=p;
			p=t;
			pushup(son[p][f]),pushup(p);
		}
		void charge(int&p)//rotate 需要引用
		{
			int nf=height[son[p][0]]-height[son[p][1]];//factor
			if(nf>1)//左偏 
			{
				int&ls=son[p][0];
				if(height[son[ls][0]]>height[son[ls][1]])rotate(p,1);//factor
				else rotate(ls,0),rotate(p,1);
			}
			else if(nf<-1)//右偏 
			{
				int&rs=son[p][1];
				if(height[son[rs][0]]<height[son[rs][1]])rotate(p,0);//factor
				else rotate(rs,1),rotate(p,0);
			}
			else if(p)pushup(p);
		}
		void insert(int&p,int x)
		{
			if(!p){p=x;return;}//newnode
			else if(val[x]<val[p])insert(son[p][0],x);//小在左
			else insert(son[p][1],x);//大等在右 
			charge(p);
		}
	public:
		AVLTree(int root=0):root(root){}
		friend Solution;
		static void staticInit(vector<int>&a)
		{
			for(int i=1;i<a.size();i++)
			{
				son[i][0]=son[i][1]=0;
				val[i]=a[i];
				height[i]=size[i]=1;
			}
		}
		int getSize()const{return size[root];}
		int numLessThan(int v)
		{
			int now=root,t=0;
			while(now)
			{
				if(val[now]>=v)now=son[now][0];
				else t+=1+size[son[now][0]],now=son[now][1];
			}
			return t;
		}
		void merge(AVLTree oth)
		{
			if(size[root]<size[oth.root])swap(root,oth.root);
			if(oth.root==0)return;
			auto traverse=[&](auto self,int u)->void
			{
				auto&[l,r]=son[u];
				if(l)self(self,l);
				if(r)self(self,r);
				height[u]=size[u]=1;
				l=r=0;
				insert(root,u);
			};
			traverse(traverse,oth.root);
			oth.root=0;
		}
	};
	vector<int> l,r,a;
	vector<ll> lt,gt;
	vector<int> DFN,nsize;int dtime;
	AVLTree inorder(int u)
	{
		DFN[u]=++dtime;
		AVLTree t1,t2;
		if(l[u])t1=inorder(l[u]);
		if(r[u])t2=inorder(r[u]);
		nsize[u]=nsize[l[u]]+1+nsize[r[u]];
		gt[u]+=nsize[l[u]]-t1.numLessThan(a[u]+1)
			  +t2.numLessThan(a[u]);
		lt[u]+=nsize[r[u]]-t2.numLessThan(a[u]+1)
			  +t1.numLessThan(a[u]);
		if(t1.getSize()<t2.getSize())
		{
			auto traverse=[&](auto self,int v)->void
			{
				auto[ls,rs]=AVLTree::son[v];
				if(ls)self(self,ls);
				if(rs)self(self,rs);
				gt[u]+=t2.numLessThan(a[v]);
				lt[u]+=nsize[r[u]]-t2.numLessThan(a[v]+1);
			};
			if(t1.root)traverse(traverse,t1.root);
		}
		else
		{
			auto traverse=[&](auto self,int v)->void
			{
				auto[ls,rs]=AVLTree::son[v];
				if(ls)self(self,ls);
				if(rs)self(self,rs);
				gt[u]+=nsize[l[u]]-t1.numLessThan(a[v]+1);
				lt[u]+=t1.numLessThan(a[v]);
			};
			if(t2.root)traverse(traverse,t2.root);
		}
		t1.merge(AVLTree(u));
		t1.merge(t2);
		ll nowans=(nsize[l[u]]+1ll)*(nsize[r[u]]+1ll)-1-lt[u];
		BIT.add(DFN[u],nowans);
		return t1;
	}
public:
	vector<ll> operator()(int s,vector<int> A,vector<pii> C,vector<pii> Q)
	{
		vector<ll> ans;
		int n=static_cast<int>(A.size());
		a={0};a.insert(a.end(),A.begin(),A.end());
		l=vector<int>(n+1);r=vector<int>(n+1);
		for(int i=1;i<=n;i++)l[i]=C[i-1].first,r[i]=C[i-1].second;
		DFN=vector<int>(n+1);nsize=vector<int>(n+1);dtime=0;
		lt=vector<ll>(n+1);gt=vector<ll>(n+1);
		BIT.set_n(n);
		AVLTree::staticInit(a);
		inorder(s);
		for(auto[opt,u]:Q)
		{
			if(opt==1)ans.push_back(BIT.sum(DFN[u],DFN[u]+nsize[u]-1));
			else BIT.add(DFN[u],-gt[u]+lt[u]),swap(lt[u],gt[u]);
		}
		return ans;
	}
};

H 解码

注：本题没有要求选手自己打表，题面末尾附有 std 用的解码表。

非扁平化处理

C/C++:

#include<stdio.h>
#include<string.h>
/*此处省略题面中给出的表的内容*/
const int heights[12]={3,3,3,3,3,3,3,3,2,2,2,2};
//前8个图像3格高,后4个图像2格高
char codes[100000][4];
int main()
{
	int n;scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%s",codes[i]);
	for(int i=0,j;i<n;)//i是当前起始行，匹配成功再跳行
	{
		//枚举12种图像
		for(j=0;j<12;j++)if(i+heights[j]<=n)
		{//[i,i+height)行得先得包含在[0,n)才能匹配上
			int failed=0;
			for(int k=0;k<heights[j];k++)//枚举每行
				if(strcmp(FIGURES[j][k],codes[i+k])!=0)//无法匹配
				{
					failed=1;
					break;//匹配失败，找下一个图像
				}
			if(failed==0)//匹配成功
			{
				printf("%s\n",KEYS[j]);
				i+=heights[j];//修改起始行，跳过当前匹配图像
				break;
			}
		}
		if(j==12)//特殊处理，自始至终没有匹配到任何图像
			return 1;//防止死循环，但主函数返回 1 会被判为RE
	}
	return 0;
}

PyPy3:

#此处省略题面中给出的表的内容
heights=[3,3,3,3,3,3,3,3,2,2,2,2]
n=int(input())
codes=[]
for i in range(n):codes.append(input())
i=0
while i<n:#i是当前起始行，匹配成功再跳行
	for j in range(12):
		if i+heights[j]<=n:
			#[i,i+height)行得先得包含在[0,n)才能匹配上
			for k in range(heights[j]):
				if FIGURES[j][k]!=codes[i+k]:
					break
			else:
				print(KEYS[j])
				i+=heights[j]
				break
	else:#特殊处理，自始至终没有匹配到任何图像
		exit(1)#防止死循环，但返回 1 会被判为RE

扁平化处理

C/C++:

#include<stdio.h>
#include<string.h>
const char FIGURES[12][10]=
{//扁平化处理，将每个图形处理成线性的编码
	"#.."
	"##."
	"#..",//中间没有逗号分隔相当于是同一个字符串
	".#."
	".##"
	".#.",
	".#."
	"##."
	"#..",
	"..#"
	".##"
	".#.",
	".#."
	"##."
	".#.",
	"..#"
	".##"
	"..#",
	"#.."
	"##."
	".#.",
	".#."
	".##"
	"..#",
	".#."
	"###",
	"##."
	"##.",
	".##"
	".##",
	"###"
	".#."
},KEYS[12][6]=
{
	"up","up","LT","LT","down","down","RT","RT",
	"left","A","A","right"//KEYS分别是对应的按键
};
const int lengthes[12]={9,9,9,9,9,9,9,9,6,6,6,6};
//前8个编码9个字符,后4个编码6个字符
char code[300001];
int main()
{
	int n;scanf("%d",&n);
	for(int i=0;i<3*n;i+=3)scanf("%s",&code[i]);
	for(int i=0,j;i<3*n;)//i是当前起始字符，匹配成功再跳转
	{
		//枚举12种图像
		for(j=0;j<12;j++)if(i+lengthes[j]<=3*n)
		{//字符串位置[i,i+length)先得包含在[0,3*n)中才能匹配上
			if(memcmp(FIGURES[j],&code[i],lengthes[j])==0)//匹配成功
			{
				printf("%s\n",KEYS[j]);
				i+=lengthes[j];
				break;
			}
		}
		if(j==12)//特殊处理，自始至终没有匹配到任何图像
			return 1;//防止死循环，但主函数返回 1 会被判为RE
	}
	return 0;
}

PyPy3:

FIGURES=\
[
	"#.."
	"##."
	"#..",#中间没有逗号分隔相当于是同一个字符串
	".#."
	".##"
	".#.",
	".#."
	"##."
	"#..",
	"..#"
	".##"
	".#.",
	".#."
	"##."
	".#.",
	"..#"
	".##"
	"..#",
	"#.."
	"##."
	".#.",
	".#."
	".##"
	"..#",
	".#."
	"###",
	"##."
	"##.",
	".##"
	".##",
	"###"
	".#."
]
KEYS=\
[
	"up","up","LT","LT","down","down","RT","RT",
	"left","A","A","right"#KEYS分别是对应的按键
]
lengthes=[9,9,9,9,9,9,9,9,6,6,6,6]
#前8个编码9个字符,后4个编码6个字符
n=int(input())
code=''.join([input()for i in range(n)])
#这相当于
# code=''
# for i in range(n):code+=input()
i=0
while i<3*n:#i是当前起始行，匹配成功再跳行
	for j in range(12):
		if i+lengthes[j]<=3*n:
			#字符串位置[i,i+length)先得包含在[0,3*n)中才能匹配上
			if FIGURES[j]==code[i:i+lengthes[j]]:
				print(KEYS[j])
				i+=lengthes[j]
				break
	else:#特殊处理，自始至终没有匹配到任何图像
		exit(1)#防止死循环，但返回 1 会被判为RE

I 多买点

容易发现可以筛掉限制不小但是折扣量不多的折扣类型，筛出的折扣集合必定可以构成一个限制和折扣量双双单调递增的序列。

筛选折扣类型后：方案①对于限制小于等于当前花费的折扣类型，选一个限制最大的即可，限制最大也就意味着折扣越大；方案②对于限制大于当前花费的折扣，选一个以最低限制折扣后价格最小的那个折扣类型。两者比小，选更小的那个。

将筛选后的折扣类型排序，求最低限制折扣后的价格序列的后缀最小值，二分找到限制小于等于当前花费的折扣类型，容易取到方案①和方案②的最小值。

C（写起来很啰嗦）:

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef struct{int l,d;}Discount;
Discount origen[200000],d[200000];
int suf[200000];
int Discount_cmp(const void*a,const void*b)
{
	Discount*da=(Discount*)a,*db=(Discount*)b;
	if(da->l!=db->l)return (da->l>db->l)-(da->l<db->l);
	else return(da->d<db->d)-(da->d>db->d);
}
int lower_bound(void*arr,size_t arrSize,size_t ElemSize,void*target,int(*cmpFn)(void*,void*))
{
	int left=0,right=arrSize;
	while(left<right)
	{
		int mid=left+(right-left)/2;
		if(cmpFn(arr+ElemSize*mid,target)<0)left=mid+1;
		else right=mid;
	}
	return left;
}
int min(int a,int b){return a<b?a:b;}
int main()
{
	int n;scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d%d",&origen[i].l,&origen[i].d);
	qsort(origen,n,sizeof(Discount),Discount_cmp);
	int d_top=-1;
	for(int i=0;i<n;i++)
		if(d_top==-1||origen[i].d>d[d_top].d)
			d[++d_top]=origen[i];
	suf[d_top]=d[d_top].l-d[d_top].d;
	for(int i=d_top-1;i>=0;i--)
		suf[i]=min(suf[i+1],d[i].l-d[i].d);
	int q;scanf("%d",&q);
	while(q--)
	{
		int k;scanf("%d",&k);
		Discount tar={k+1,INT32_MAX};
		int nowans=k,p=lower_bound(d,d_top+1,sizeof(Discount),&tar,Discount_cmp)-1;
		if(p+1<=d_top)nowans=min(nowans,suf[p+1]);
		if(p>=0)nowans=min(nowans,k-d[p].d);
		printf("%d\n",nowans);
	}
	return 0;
}

C++17:

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
using pii=pair<int,int>;
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n;cin>>n;
	vector<pii> origen(n),dc;//discounts
	dc.reserve(n);
	for(auto&[l,d]:origen)cin>>l>>d;
	sort(origen.begin(),origen.end());
	for(pii i:origen)
		if(dc.empty()||dc.back().second<i.second)
			dc.push_back(i);
	vector<int>suf(dc.size());
	suf.back()=dc.back().first-dc.back().second;
	for(int i=static_cast<int>(dc.size())-2;i>=0;i--)
		suf[i]=min(suf[i+1],dc[i].first-dc[i].second);
	int q;cin>>q;
	while(q--)
	{
		int k;cin>>k;
		int p=lower_bound(dc.begin(),dc.end(),pair(k+1,0))-dc.begin()-1;
		int ans=k;
		if(p!=-1)
			ans=min(ans,k-dc[p].second);
		if(p+1!=static_cast<int>(suf.size()))
			ans=min(ans,suf[p+1]);
		cout<<ans<<'\n';
	}
	return 0;
}

J 昨天看见个题

上小学学过带余除法的同学们都知道，除法做整除之后可能会有一个余数，例如 $13\div 3=4\;\cdots\,\!\cdots 1$ （除 $3$ 商 $4$ 余 $1$ ），这是因为 $13=3\times 4+1$ 。我们在数论中以此进一步规定了这一过程，其中一种规定即为 $a=q\times b+r$ ， $q=\left\lfloor\dfrac ab\right\rfloor,r=a\bmod b$ 且 $r\in[0,q)$ ，所以有

$\begin{aligned} a&= b\cdot\left\lfloor\dfrac ab\right\rfloor+a\bmod b\\ a&\equiv b\cdot\left\lfloor\dfrac ab\right\rfloor+a\bmod b\pmod P\\ a-a\bmod b&\equiv b\cdot\left\lfloor\dfrac ab\right\rfloor\pmod P\\ b\cdot\left\lfloor\dfrac ab\right\rfloor&\equiv a-a\bmod b\pmod P, \end{aligned}$

由 $b$ 与 $P$ 互质可知 $b$ 在模 $P$ 整数域里存在乘法逆元（因为 $P$ 是质数，所以其实就是说 $b$ 不是 $P$ 的倍数， $b\bmod P\neq 0$ ，域内零元是不存在乘法逆元的），记该逆元为 $b^{-1}$ ，有

$\left\lfloor\dfrac ab\right\rfloor\equiv\left(a-a\bmod b\right)b^{-1}\pmod P.$

如何求出 $b^{-1}\pmod P$ 呢？以下方法来源请见OI wiki 欧拉定理 & 费马小定理，即 $b^{-1}\equiv b^{P-2}\pmod P$ ，使用二进制取幂可在 $\left\lfloor\log_2(P-2+1)\right\rfloor+1$ 次迭代后求出。

同样我们还需要求出 $a\bmod P$ 和 $(a\bmod b)\bmod P$ 的值，由带模整数域性质可知域内元素的带模加和乘和一般的整数计算方法差别不大，满足加法交换结合律，乘法交换结合律，乘法对加法的分配律等，同样可以使用二进制取幂的方式计算，不过要注意计算过程中要及时取模，不可有溢出行为。

一般来说，常见 C/C++ 编译器（C/C++ 新标准中有明确规定）编译出的基础整数除法是向零取整，取模的结果 $r$ 和被除数 $a$ 同号（ $\operatorname{sign}(a)=\operatorname{sign}(r)$ ），请注意 $a$ 是负数的情况，这跟我们在初等数论中通常的规定不一样。

C/C++:

#include<stdio.h>
typedef long long ll;
ll bpow(ll a,int b,int mod)
{
	a%=mod;//本行代码可有可无
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ans=ans*a%mod;
	return ans;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n,b,P;scanf("%d%d%d",&n,&b,&P);
		ll a_P=1,a_b=1;//a mod P, a mod b
		for(int i=0;i<n;i++)
		{
			int p,k;scanf("%d%d",&p,&k);
			a_P=a_P*bpow(p,k,P)%P;
			a_b=a_b*bpow(p,k,b)%b;
		}
		printf("%lld\n",((a_P-a_b)%P+P)*bpow(b,P-2,P)%P);
		//a_P-a_b+P 不一定是个正数
	}
	return 0;
}

Python 中只要模数是正的，那么取模余数就是正的，无需在意被除数是负数的情况。不过比较隐蔽的是，如果模数是负的，那么取模结果就一定是负的。

PyPy3:

for _ in range(int(input())):
	n,b,P=map(int,input().split())
	a_b=a_P=1
	for i in range(n):
		p,k=map(int,input().split())
		a_P=a_P*pow(p,k,P)%P#a mod P
		a_b=a_b*pow(p,k,b)%b#a mod b
	print((a_P-a_b)*pow(b,P-2,P)%P)

K 昨天想了个题

设两个初始值分别依次为 $a,b\in\mathbb N^+$ ，由 $|a-b|\leqslant\max(a,b)$ ，根据数学归纳法（甚至不妨说数学归纳在此处是一个公理）可知对序列中每个元素 $c$ 都有 $c\leqslant\max(a,b)$ ，且 $c$ 一定是整数，那么序列元素一定有限。

设生成的序列中数的不同种类有 $f(a,b)$ 个。此处给出严格定义：

定义令函数 $f:\left(\mathbb N^+\right)^2\mapsto\mathbb N^+$ ，其具体表达式以如下方式定义：

$\begin{aligned} \forall a,b&\in\mathbb N^+,\\ a_1&=a,\\a_2&=b,\\ a_i&=|a_{i-1}-a_{i-2}|,i=3,4,5,\cdots.\\ S&=\{a_i\mid i\in\mathbb N^+\},\\ f(a,b)&=|S|. \end{aligned}$

注： $\mathbb N^+$ 是正整数集。

定理 $\forall a,b\in\mathbb N^+,f(a,b)=f(b,a)$ 。

证明:

当 $a=b$ 时， $f(a,b)=2=f(b,a)$ ；

当 $a>b$ 时， $f(a,b)$ 对应序列 $a,b,a-b,\cdots$ ； $f(b,a)$ 对应序列 $b,a,a-b,b,\cdots$ 。显然又有 $a>a-b$ ，序列之后的数字之后的数字不可能再出现 $a$ ，那就有 $f(a,b)=f(b,a-b)+1$ ， $f(b,a)=f(a-b,b)+1$ ，只需证明 $f(b,a-b)= f(a-b,b)$ ；

由等号（等价谓词）的自反性可知 $b>a$ 与 $a>b$ 对应的式子一致，无需重复说明。

可以找到 $(a,b)$ 二维点集 $\left(\mathbb N^+\right)^2$ 的一个良序集，应用超限数学归纳法可以证得。 $\square$

印象图

如你所见，图中沿每一个实线箭头走一步意味着新序列丢掉了一个“大数”，这个“大数”不会在之后任何地方出现。任何一个蓝色的点 $\color{#446cbe}{(a,b)}$ 和与之对称的点 $\color{#cc0000}{(b,a)}$ 到达绿色的点 $\color{#00a84c}{(2,1)}$ 走过的实线箭头数量是一样的，这也意味着 $f{\color{#446cbe}{(a,b)}}=f{\color{#cc0000}{(b,a)}}$ 。

设 $\overline{f}$ 是扩充的 $f$ 函数，其定义在 $\mathbb N^2$ 上，具体定义如下：

$\overline{f}(a,b)=\begin{cases} 1,&a=0\vee b=0,\\ f(a,b),&\text{其它情况}. \end{cases}$

也就是说，如果其一参数为 $0$ ，那么 $\overline{f}$ 的值为 $1$ ，否则其值等于 $f$ 。引入 $\overline f$ 的原因是 $\forall a\in\mathbb N^+,f(a,a)=f(a,0)=2$ ，这样就不能和 $f(a,b)=f(b,a-b)+1,f(b,a)=f(a-b,b)+1$ 统一起来了。经过这一处理后的 $\overline f$ 就有以下性质。

性质 1 $\forall a,b\in\mathbb N^+,\overline f(a,b)=\overline f\left(b,|a-b|\right)+1$ 。

性质 2 $\forall a,b\in\mathbb N^+,a\geqslant b,\overline f(a,b)=\overline f\left(b,a-b\right)+1$ 。

用 $\overline{f}$ 进行递归。类比更相减损术，每次都要求 $a\geqslant b$ ，执行一次更相减损术贡献加一，但是更相减损术执行效率堪忧，我们过渡到辗转相除法，每轮执行 $\left\lfloor\dfrac{a}{b}\right\rfloor$ 次迭代（少于这个次数都有 $a\geqslant b$ ），更新后有 $a\gets a-b\cdot\left\lfloor\dfrac{a}{b}\right\rfloor=a\bmod b$ ，显然必有 $a<b$ 。若 $a\neq 0$ ，那么交换 $a,b$ 继续迭代；若 $a=0$ ，得到 $\overline f(a,b)=1$ ，所以将总执行次数加上 $1$ 结束程序即可。

性质 3 $\forall a,b\in\mathbb N^+,a\geqslant b,\overline f(a,b)=\overline f\left(b,a\bmod b\right)+\left\lfloor\dfrac{a}{b}\right\rfloor$ 。

用欧几里得算法（辗转相除算法）可以在最多 $\log_{\varphi}\max(a,b)$ 左右次迭代完成计算，其中 $\varphi=\tfrac{\sqrt 5+1}{2}\approx 1.618$ ，证明略。 $\color{gray}{注：此处“最多”和“左右”不构成病句。}$

C/C++:

#include<stdio.h>
typedef long long ll;
int Euclid(ll a,ll b)//欧几里得，辗转相除
{
	ll res=1;
	while(b)
	{
		res+=a/b;
		ll t=b;
		b=a%b;
		a=t;
	}
	return res;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		ll a,b;scanf("%lld%lld",&a,&b);
		printf("%lld\n",Euclid(a,b));
	}
	return 0;
}

PyPy3:

def Euclid(a,b):#欧几里得，辗转相除
	res=1
	while b:
		res+=a//b
		a,b=b,a%b
	return res
for _ in range(int(input())):
	print(Euclid(*map(int,input().split())))

L 随机发生器

猜结论题，考验直觉。

条件：分数 $\dfrac{P}{Q}$ 的既约分数形式 $\dfrac{P'}{Q'}$ 的分母 $Q'$ 的质因子只有 $2,3,5,7$ 。

注：所谓“既约”，意思是已经约分过了。既约分数形式 $\dfrac{P'}{Q'}$ 满足

$\begin{cases} P=P'\cdot\gcd(P,Q),\\Q=Q'\cdot\gcd(P,Q). \end{cases}$

结论：在条件满足时可以用有限个投掷器达成目的。

AI 笑传之产产煤： $\dfrac{11}{200}$ 是抢夺 III 附魔加持下击杀 凋灵骷髅 掉落 凋灵骷髅头颅 的概率，这个概率可以在游戏中用该“赤石科技”形式化地模拟出来，这样就可以“赛博产煤”了。

其实样例给出了可以构造出来的例子和证明不可构造出的思路。

结论的证明

我们以下对结论进行完整的证明和讨论：

记单元概率集合 $S_\mathrm{u}=\left\{\dfrac{p}{q}\;\bigg|\;p,q\in\mathbb N,q\neq 0,0\leqslant p\leqslant q\leqslant 9\right\}$ ，

概率封闭集合 $S_\mathrm{c}=\left\{\dfrac{P}{Q}\;\bigg|\;P\in\mathbb N,Q\in\mathbb N^+,p\mid Q,\forall p=2,3,5,7\right\}$ 。

用 $\perp$ 表示不可能为真的命题公式，称为“底”。可以令 $\perp=r_0\wedge\neg r_0$ 。以下的不同的命题变元之间在概率模型中均相互独立，在谈及构造的时候忽略命题联结词，根据 $\{\neg,\vee\}$ 的完备性可知，这两个命题联结词可以构成任意二元真值联结词。

存在性构造

给定既约分数形式 $\dfrac{P'}{Q'}$ ， $Q'$ 的质因子都包含在 $\{2,3,5,7\}$ 当中，那么由唯一分解定理，可记 $Q'=2^{k_2}3^{k_3}5^{k_5}7^{k_7}$ ，通过构造逐步将分母上的这些质数因子消掉。

已知 $Q'=i^{k_i}(i=2,3,5,7)$ ，若 $\exists i_0\in\{2,3,5,7\},k_{i_0}\neq 0$ ，那么按照以下方式逐步递归转换：

若 $P'/Q'\leqslant\dfrac{1}{2}$ ，令 $r$ 为一命题变元，满足 $P(r)=\dfrac{i_0-1}{i_0}\in S_\mathrm{u}$ ，令 $\varphi=r\wedge\varphi_1$ ，其中 $\varphi_1$ 中不包含命题变元 $r$ 。只须构造出 $\varphi_1$ ，令其满足 $P\left(\varphi_1\right)=\dfrac{P'}{Q'}\dfrac{i_0}{i_0-1}\in[0,1]$ 即可。
若 $P'/Q'>\dfrac{1}{2}$ ，令 $\varphi=\neg\varphi_1$ 只须构造出 $\varphi_1$ ，令其满足 $P\left(\varphi_1\right)=\dfrac{Q'-P'}{P'}\in\left[0,\dfrac{1}{2}\right]$ 即可。

反复进行操作 2. 和 1.，需要构造出的概率的分母上的质数因子数会越来越少，直到为 $0$ 。

集合外不可构造的证明

定理 1 对任意由 $n(n\in\mathbb N)$ 个命题变元 $r_1,r_2,\cdots,r_n$ 构成的命题公式 $\varphi$ ，都有 $\varphi\equiv (r_n\wedge\varphi_1)\vee(\neg r_n\wedge\varphi_2)$ 或 $\varphi\equiv\varphi_1$ ，其中 $\varphi_1,\varphi_2$ 只由 $\perp,r_1,\cdots,r_{n-1}$ 构成。

证明：考虑构造优合取范式，若优合取范式中存在变元 $r_n$ ，那必定可以将 $r_n$ 与 $\neg r_n$ “提取”出来并写成 $(r_n\wedge\varphi_1)\vee(\neg r_n\wedge\varphi_2)$ 的形式；若不存在 $r_n$ ，那也毫无疑问可以将其写为 $\varphi_1$ 的形式。 $\square$

给定概率模型，该模型使得 $P(r_i)=\dfrac{p_i}{q_i}(n\in\mathbb N^+,i=1,2,\cdots,n)$ 以及只由 $r_1,\cdots,r_{n-1}$ 构成的公式 $\varphi_1,\varphi_2$ 满足 $P(\varphi_1)=\dfrac{P_1}{Q_1}\in S_\mathrm{c},P(\varphi_2)=\dfrac{P_2}{Q_2}\in S_\mathrm{c}$ ，那么

$\begin{aligned} &P\bigl((r_n\wedge\varphi_1)\vee(\neg r_n\wedge\varphi_2)\bigr)\\ =&\dfrac{p_i}{q_i}\dfrac{P_1}{Q_1}+\left(1-\dfrac{p_i}{q_i}\right)\dfrac{P_2}{Q_2}\\ =&\dfrac{{\tiny\text{一堆不重要但值为正的式子}}}{q_iQ_1Q_2}\in S_\mathrm{c}. \end{aligned}$

这样在已有命题公式上再加一个命题变量，那么新的命题公式的概率依然在 $S_\mathrm{c}$ 里。

定理 2 对于任意满足 $P(r_i)\in S_\mathrm{u}(n\in\mathbb N^+,i=1,2,\cdots,n)$ 的概率模型，由 $n(n\in\mathbb N)$ 个命题变元外加 $\perp$ 构成命题公式 $\varphi$ ，那么 $\varphi$ 为真的概率 $P(\varphi)\in S_\mathrm{c}$ ，即封闭在 $S_\mathrm{c}$ 中。

证明：结合 定理 1，找到良序集，由超限数学归纳法即可得到该定理。 $\square$

由 定理 2 可知，概率能被构造出来，那它一定在 $S_\mathrm{c}$ 里面。逆否命题为在 $S_\mathrm{c}$ 外面的概率都不能被构造出来。

实现

C/C++:

#include<stdio.h>
long long gcd(long long a,long long b)
{
	while(b!=0)
	{
		long long t=b;
		b=a%b;
		a=t;
	}
	return a;
}
//C++17 以上标准请用 numeric 库中的 std::gcd 函数
//也可以用 libstdc++ 在 algorithm 等库中支持的 std::__gcd
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		long long P,Q;scanf("%lld%lld",&P,&Q);
		Q/=gcd(P,Q);
		const int primes[]={2,3,5,7};
		for(int i=0;i<4;i++)
			while(Q%primes[i]==0)
				Q/=primes[i];
		puts(Q==1?"Yes":"No");
	}
	return 0;
}

PyPy3:

import math
for _ in range(int(input())):
	P,Q=map(int,input().split())
	Q//=math.gcd(P,Q)
	for p in[2,3,5,7]:
		while Q%p==0:Q//=p
	print("Yes"if Q==1 else"No")

M 不玩舞萌

找角法

初始角

设初始时射线的逆时针角为 $\color{#6042a6}{\beta=\dfrac{\pi}{2}+\dfrac{i}{5}\cdot 2\pi,i=0,1,2,3,4}$ 。

令 ${\color{#fa7e19}{\alpha}}$ 为初始角射线旋转后的角度，有 ${\color{#fa7e19}{\alpha}}={\color{#6042a6}{\beta}}+\omega t$ ， ${\color{#6042a6}{\varphi}}({\color{#6042a6}{\phi}})$ 为每个交点对应的逆时针角。

Desmos 链接

在上图中，我们通过初中学过的角加减与“三角形的外角等于与它不相邻的两个内角之和”可知，长为 ${\color{#348443}{r}}$ 的半径边对应角为 ${\color{#348443}{\pi-(\alpha-\theta)}}$ ，长为 ${\color{#c74440}{vt}}$ 的边对应角为 ${\color{#c74440}{\alpha-\varphi}}$ 。

套用正弦定理得到

$\begin{aligned} \dfrac{\sin({\color{#348443}{\pi-(\alpha-\theta)}})}{{\color{#348443}{r}}}&=\dfrac{\sin({\color{#c74440}{\alpha-\varphi}})}{{\color{#c74440}{vt}}}\\ \dfrac{\sin({\color{#348443}{\alpha-\theta}})}{{\color{#348443}{r}}}&=\dfrac{\sin({\color{#c74440}{\alpha-\varphi}})}{{\color{#c74440}{vt}}}, \end{aligned}$

变换一下形式得到

${\color{#6042a6}{\varphi}}={\color{#fa7e19}{\alpha}}-\arcsin\left(\dfrac{{\color{#c74440}{vt}}\sin({\color{#fa7e19}{\alpha}}-{\color{#2d70b3}{\theta}})}{{\color{#348443}{r}}}\right).$

${\color{#6042a6}{\varphi}}$ 就是交点的逆时针角了。显然，上过高中的同学都知道对应的点是 $({\color{#348443}{r}}\cos{\color{#6042a6}{\varphi}},{\color{#348443}{r}}\sin{\color{#6042a6}{\varphi}})$ 。

注意到正弦定理可以瞎用，所以我们得到以下的代码：

Python3(本场比赛允许使用 Numpy、Scipy 等模块):

import numpy as np
β=np.array([np.pi/2+2*i*np.pi/5 for i in range(5)])
for _ in range(int(input())):
	r,θ,ω,v,t=map(float,input().split())
	θ*=np.pi/180
	ω*=np.pi/180
	α=β+ω*t
	φ=α-np.arcsin(v*t/r*np.sin(α-θ))
	x,y=r*np.cos(φ),r*np.sin(φ)
	for i in range(5):print(x[i],y[i])

题解 | 2025年夏第九届河北工业大学程序设计校赛

A 酒鬼地图前传

B 酒鬼地图

C 尝试逃逸

二维递推方法

合理地枚举下标，消掉一维递推状态

D 舍入

E 等差数列（easy version）

F 等差数列（hard version）

G 树上交换

H 解码

非扁平化处理

扁平化处理

I 多买点

J 昨天看见个题

K 昨天想了个题

L 随机发生器

结论的证明

存在性构造

集合外不可构造的证明

实现

M 不玩舞萌

找角法