转载，原作者是他：邪神与厨二病(CSDN)

这场的出题组是郑州大学acm实验室，验题组是郑州大学和郑州轻工业大学的志愿者同学们。

唯一令我意想不到的是J过的很少

这里的代码只给一个参考作用，出题人写的代码在对应题目文件夹的std.cpp里。（除了E题是直接放的出题人代码，因为我不会写）

难度分布如下：alt

A 装备二选一（一）

alt

code：

#include <iostream>
#include <cstdio>
using namespace std;

int a,b,c,d;

int main(){
	cin>>a>>b>>c>>d;
	puts((a*(b-1)<c*(d-1))?"YES":"NO");
	return 0;
}

至于为什么这个地方只出了（一），出题人说要在后续比赛出（二），敬请期待吧。

B 百变吗喽

思路：

下面是出题人自己写的题解，我引用一下：

我们设在第一个字符串 的位置 上插入一个字符 之后，使得字符串 变为 并和目标字符串 完全相同。那么就等价于同时满足下列三个条件：

  • 由于 可以为任意字符，那么第三个条件一定成立。而前两个条件成立就等价于 和 在 处拆分的前缀和后缀字符串都相等。

于是我们找到s和t的最长公共前缀长度 ，以及最长公共后缀长度 。那么我们可以在 处插入一个字符 来实现 和 全等。 因此，总的方案数为 , 每个方案为

code：

这是字符串从 开始编号的写法，也就是第一个字符编号是 。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,i1,i2;
string s1,s2;

int main(){
	cin>>s1>>s2;
	n=s2.length();
	s1=" "+s1;
	s2=" "+s2;
	for(i1=1;i1<=n-1 && s1[i1]==s2[i1];i1++);
	for(i2=n;i2>=1 && s1[i2-1]==s2[i2];i2--);
	if(i2<=i1){
		cout<<i1-i2+1<<endl;
		for(int i=i2;i<=i1;i++)
			cout<<i-1<<" "<<s2[i]<<endl;
	}
	else cout<<0<<endl;
	return 0;
}

编号从 开始的。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,i1,i2;
string s1,s2;

int main(){
	cin>>s1>>s2;
	n=s2.length();
	for(i1=0;i1<n-1 && s1[i1]==s2[i1];i1++);
	for(i2=n-1;i2>=0 && s1[i2-1]==s2[i2];i2--);
	if(i2<=i1){
		cout<<i1-i2+1<<endl;
		for(int i=i2;i<=i1;i++)
			cout<<i<<" "<<s2[i]<<endl;
	}
	else cout<<0<<endl;
	return 0;
}

C 16进制世界

alt

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int inf=1e9;
const int maxn=1e5+5;
const int mod=16;

int n,m;
int dp[maxn][20];//饱食度 幸福度 

int main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<=m;i++)
		for(int j=0;j<mod;j++)
			dp[i][j]=-inf;
	dp[0][0]=0;
	
	for(int _=1,v,w;_<=n;_++){
		cin>>v>>w;
		w%=mod;
		for(int i=m-v;i>=0;i--)
			for(int j=0;j<16;j++)
				dp[i+v][(j+w)%mod]=max(dp[i+v][(j+w)%mod],dp[i][j]+1);
	}
	int ans=0;
	for(int i=0;i<=m;i++)ans=max(ans,dp[i][0]);
	cout<<ans<<endl;
	return 0;
}

D 四散而逃

思路：

发现如果中间 个位置只要存在一个偶数，就可以进行至少一次“奔逃”操作，这个位置的一侧可以让逃出来的一个人分配到这边的某个奇数位置上（如果没有就直接放在边上就可以了，就不要放到中间的位置上了，因为这样不仅让中间的某个位置人数变多，需要的“奔逃”次数变多，还让他变成了奇数人数，没有好处），然后就会产生一个偶数，重复这样的操作，就可以把中间所有数都变成偶数，进而都“奔逃”到两边。

反之如果一开始中间 个位置连一个偶素都没有，那么就无解了。

中间 个位置里，一个位置假设有 人，如果是奇数，就需要别的地方过来一个人补齐 ，需要的“奔逃”次数就是 ，如果是偶数，直接“奔逃”需要 次。

code：

#include <iostream>
#include <cstdio>
using namespace std;

int n;

int main(){
	cin>>n;
	bool flag=false;
	long long ans=0;
	for(int i=1,t;i<=n;i++){
		cin>>t;
		if(i!=1 && i!=n){
			if(t%2==0)flag=true;
			ans+=(t+1)/2;
		}
	}
	cout<<((flag)?ans:-1)<<endl;
	return 0;
}

E 铃兰小姐是我们的光

思路：

出题人和题解都是 Alear。本题需要的一些前置知识：替罪羊树，或其他类似作用的重量平衡树；最近公共祖先。

整体思路是替罪羊树维护动态的 dfs 序，然后把数颜色转换成序列区间和。在这题是转换成了子树和。插入一个点转化为把 和 （ 子树结束的标记，权值为 ，仅用于查询） 插入到 后。

为了维护 dfs 序，能够支持插入和比较前后关系，我们为每个节点维护一个标记 ，需要比较两个节点在 dfs 序上的前后关系，只需要比较 的大小即可。

如何维护这个标记呢？我们让每个点对应一个实数区间 ，其中根节点对应实数区间 。对于每个节点 ，该节点的 ，左儿子对应的区间为 ，右儿子对应的区间为 。由于插入节点的时候都是插入到节点 后面，我们只需根据 找到替罪羊树上的该节点，然后插入到 右儿子的位置即可。替罪羊树用重构保证了树高 的，分母的复杂度为 ，因此无需担心浮点数精度问题。该做法的来源是陈立杰的 IOI 2013 集训队论文《重量平衡树和后缀平衡树在信息学奥赛中的应用》。

对于维护颜色，我们将相同颜色的节点按 dfs 序排序，对每个节点维护另一个权值 。只需在每个节点处 ，相邻节点处的 （最近公共祖先）处 ，这样计算一个节点的子树内颜色数就变成了求子树权值和。实现上可以每加入一个节点 在本身处 ； 和同色前驱的 处 ； 和同色后继的 处 ；前驱和后继的 处 ，因为前驱和后继不再相邻。需要操作的节点不存在（例如没有前驱）则跳过该步。这个思想类似树上链并，看成对同颜色的节点到根节点的链求一个并，也是本题的灵感来源之一。

为了实现同颜色节点排序、查找前驱后继的操作，我们可以每个颜色开一个 set 保存所有该颜色的节点，这个 set 的比较函数用替罪羊树的标号比较进行重载，这样就能找到当前插入节点相同颜色前驱和后继。替罪羊树发生重构时虽然会修改 的值，但是大小关系一直没变，保证了重载比较的正确性。最近公共祖先可以使用倍增实现。

这样处理之后，问题变成了单点修改，子树求和。前面我们使用替罪羊树维护了 dfs 序，单点修改，区间求和也可以在替罪羊树上完成。因为替罪羊树树高是 的，我们类似线段树地维护所有节点的子树和即可。查询的时候也类似线段树地求 和 之间所有节点的权值和即可。

总复杂度 。

code：

#include<bits/stdc++.h>
#define next nxt
using namespace std;
int read(){
	int c=0,nx,sign=1;
	while(!isdigit(nx = getchar()))
		if(nx=='-')
			sign=-1;
	while(isdigit(nx))
		c=c*10+nx-'0',nx=getchar();
	return sign*c;
}

const int N=2e6 + 20,M=N*2;
int head[N],next[M],ver[M];
inline void addEdge(int u,int v){
	static int now = 0;
	next[++now]=head[u],head[u]=now,ver[now]=v;
	next[++now]=head[v],head[v]=now,ver[now]=u;
}

const int K = N * 2;
double alpha = 0.7;
int n, m, root;
int sum[K], dat[K];
int ls[K], rs[K], sz[K];
double val[K];
int k;
// bool cmp(int x, int y){
// 	return val[x] < val[y];
// }
 
class cmp {
	public:
		bool operator() (const int& lc, const int& rc)const {
				return val[lc] < val[rc];
		}
};
set<int, cmp> col[N];

int *to_build;
double tol, tor;

inline int New(int x){
	static int now = 0;
	dat[++now] = x;
	return now;
}
inline void pushup(int s){
	sz[s] = sz[ls[s]] + sz[rs[s]] + 1;
	sum[s] = sum[ls[s]] + sum[rs[s]] + dat[s];
}
inline bool is(int s){
	// cerr<<"&"<<sz[s] * alpha<<' '<<max(sz[ls[s]], sz[rs[s]])<<endl;
	return sz[s] * alpha < max(sz[ls[s]], sz[rs[s]]); 
}


void add(double p, int u, int x, int &s = root, double l=0, double r=1){
	// cerr<<"add "<<p<<' '<<u<<' '<<x<<' '<<s<<' '<<l<<' '<<r<<endl;
	if(!s){
		s = u;
		val[s] = (l + r) / 2;
		// cerr<<"feijo\n";
		dat[s] = x;
		sz[s] = 1;
		return ;
	}
	if(p < val[s])
		add(p, u, x, ls[s], l, val[s]);
	else
		add(p, u, x, rs[s], val[s], r);
	pushup(s);
	if(is(s))
		to_build = &s, tol = l, tor = r;
}

void modify(double p, int x, int s = root){
	if(p < val[s])
		modify(p, x, ls[s]);
	else if(p > val[s])
		modify(p, x, rs[s]);
	else
		dat[s] += x;
	pushup(s);
}

int query(double ql, double qr, int s = root, double l=0, double r=1){
	// cerr<<"query "<<ql<<' '<<qr<<' '<<s<<' '<<l<<' '<<r<<endl;
	if(!s)
		return 0;
	if(ql <= l and r <= qr){
		return sum[s];
	}
	int ans = 0;
	if(ql < val[s])
		ans = query(ql, qr, ls[s], l, val[s]);
	if(qr > val[s])
		ans += query(ql, qr, rs[s], val[s], r);
	if(ql <= val[s] and qr >= val[s])
		ans += dat[s];
	return ans;
}

int stk[K], top;
void dfs(int s){
	// cerr<<"dfs "<<s<<' '<<l<<endl;
	if(!s)
		return ;
	dfs(ls[s]);
	stk[++top] = s;
	dfs(rs[s]);
}
void build(int &s, int l=1, int r=top, double vl=tol, double vr=tor){
	// cerr<<"build "<<s<<' '<<l<<' '<<r<<' '<<vl<<' '<<vr<<endl;
	if(l > r){
		s = 0;
		return ;
	}
	int mid = (l + r) >> 1;
	s = stk[mid];
	val[s] = (vl + vr) / 2;
	build(ls[s], l, mid - 1, vl, val[s]);
	build(rs[s], mid + 1, r, val[s], vr);
	pushup(s);
}

inline void insert(double p, int u, int x){
	add(p, u, x);
	if(to_build){
		// cerr<<"????\n";
		top = 0;
		dfs(*to_build);
		// cerr<<"**top="<<top<<endl;
		// for(int i=1;i<=top;i++)
		// 	cerr<<stk[i]<<' ';
		// cerr<<endl;
		build(*to_build);
		to_build = 0;
	}
}

namespace lca_bz{
	int lg[N];
	int fa[21][N],d[N];
	
	int lca(int u,int v){
		if(d[u] < d[v])
			swap(u,v);
		while(d[u] > d[v])
			u = fa[lg[d[u] - d[v]]][u];
		if(u==v)
			return u;
		for(int i=lg[d[u]];i>=0;i--)
			if(fa[i][u] != fa[i][v])
				u = fa[i][u], v = fa[i][v];
		return fa[0][u];
	}
}
using namespace lca_bz;

// void print(int s=root){
// 	if(!s)
// 		return ;
// 	print(ls[s]);
// 	cerr<<'*'<<s<<' '<<ls[s]<<' '<<rs[s]<<' '<<val[s]<<' '<<dat[s]<<' '<<sum[s]<<' '<<sz[s]<<endl;
// 	print(rs[s]);
// }

int main(){
	// 强制在线版标程
	// fclose(stderr);
	n = read(), m = read();
	// printf("%d %d\n", n, m);
	
	d[0] = -1;
	int cntt = 0;
	
	for(int i=1;i<=n;i++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	for(int i=0;i<=n;i++)
		--lg[i];
	
	int pre = 0;
	while(m--){
		int op = read(), u = read() ^ pre, f, c;
		if(op == 0){
			cntt++;
			f = read() ^ pre, c = read() ^ pre;
			// printf("%d %d %d %d", op, u ^ pre, f ^ pre, c ^ pre);
			d[u] = d[f] + 1;
			fa[0][u] = f;
			for(int i=1, tt = lg[d[u]];i<=tt;i++)
				fa[i][u] = fa[i - 1][fa[i - 1][u]];
			insert(val[f], u, 1);
			insert(val[u], u + n, 0);
			// cerr<<"EFJIO\n";
			
			
			auto &cc = col[c];
			auto lp = cc.lower_bound(u), rp = cc.upper_bound(u);
			auto lt = lp != cc.begin(), rt = rp != cc.end();
			if(lt){
				lp--;
				f = lca(u, *lp);
				modify(val[f], -1);
			}
			if(rt){
				f = lca(u, *rp);
				modify(val[f], -1);
			}
			if(lt and rt){
				f = lca(*lp, *rp);
				modify(val[f], 1);
			}
			cc.insert(u);
		}else{
			// printf("%d %d %d %d", op, u ^ pre);
			printf("%d\n", pre = query(val[u], val[u + n]));
			pre = query(val[u], val[u + n]);
			// cout<<'*'<<cntt-u+1<<endl;
		}
		// cerr<<query(val[u], val[u + n])<<endl;
		// print();
		// cerr<<'*'<<(val[1] <= val[1])<<endl;
	}
	// cerr<<"color "<<clock()<<endl;
}

F 追寻光的方向

思路1（前缀和）：

注意一开始是停在第一个路灯下面的，所以第一个路灯的值是无所谓的，直接跳过。

准确来说应该是后缀和，我们用 表示 中最大的数的位置（如果有多个就记最靠前的那个）。然后从第一个路灯开始模拟一下跳的过程就行了。

因为跑到最后一个路灯的时候直接就到终点了，不需要休息，所以答案要减一。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;

int n,a[maxn],suf[maxn];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	suf[n]=n;
	for(int i=n-1;i>=1;i--)
		suf[i]=(a[i]>=a[suf[i+1]])?i:suf[i+1];
	
	int ans=0;
	for(int p=2;p<=n;p=suf[p]+1,ans++);
	cout<<ans-1<<endl;
	return 0;
}

思路2（排序+模拟）：

因为亮度最大的灯只要在我们前方，我们就优先考虑跑到它下面，如果在身后就不用考虑了。所以可以对所有路灯的亮度从大到小排个序，然后模拟上面的过程。先跑到最亮的灯下，再跑到次大的灯下……如果看到某个灯编号比我们自己所在的编号要小就丢弃。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
#define pii pair<int,int>

int n;
pii a[maxn];

int main(){
	cin>>n;n--;
	int t;
	cin>>t;
	for(int i=1;i<=n;i++){
		cin>>t;
		a[i]={t,i};
	}
	
	sort(a+1,a+n+1,[](pii a,pii b)->bool{
		return (a.first==b.first)?a.second<b.second:a.first>b.first;
	});
	
	int ans=0,p=0;
	for(int i=1;i<=n;i++){
		auto [l,id]=a[i];
		if(id>p)p=id,ans++;
	}
	cout<<ans-1<<endl;
	return 0;
}

思路3（单调栈）：

第一次我们是跑到 中最大的值下的，假如是第 个元素，然后我们再跑到 中的最大值……

换个思路，第 个位置上的数其实相当于把前面的 位置上的数都挤掉了，因为有第 位置上的最大值，所以前面的数都不需要考虑，这种“比你小还比你强，所以你就没用了”的思想就很单调队列（不过不需要从队首出队，所以直接用单调栈就行了）。

code：

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

int n;
stack<int> sta;

int main(){
	cin>>n;
	for(int i=1,t;i<=n;i++){
		cin>>t;
		if(i==1)continue;
		while(!sta.empty() && t>sta.top())sta.pop();
		sta.push(t);
	}
	cout<<sta.size()-1;
	return 0;
}

G 等公交车

思路：

我们在距离为 的车站等候，那么第 辆公交车到站的时刻就是 ，那我们在某个时刻 ，要等的第一辆车就是第一个大于等于 的时刻到的车（这一步可以二分查找）。但是我们不可能给每个公交车的发车时刻都加上一个 ，这样是 的。

不妨这样来想，我们在距离为 的车站在 时刻开始等候，其实就相当于我们在距离为 的车站在 时刻开始等候。因为一辆车在某个时间到距离为 的车站，那么在 分钟前一定到距离为 的车站，所以两者的到站顺序是完全一致的。这样就不需要给每个公交车的发车时刻都加上一个 ，而只需要在二分查找的时候找 的时刻后第一辆发的车就可以了。时间复杂度

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;

int n,m,q;
int a[maxn],b[maxn];

int main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	cin>>q;
	for(int i=1,tm,id,idx;i<=q;i++){
		cin>>tm>>id;
		tm-=a[id];
		auto it=lower_bound(b+1,b+m+1,tm);
		if(it-b>m)cout<<"TNT\n";
		else cout<<*it-tm<<"\n";
	}
	
	return 0;
}

H 24点

思路：

就，暴搜，就可以了。

这题一开始没想到有原题的，结果发现开赛两分钟就被某牛客rk几十的大佬秒了然后榜就开始歪了，大伙都来写这爆搜粪题才发现问题所在。不过好在没原的那么彻底，还是有点不一样的地方的。这题一开始数据量给的 ，但是验题的时候发现根本没人做，临时改数据量换成了 。

先把输入的扑克牌点数转化为对应的数字，用 就行。

一组数据总共就四个数，不同顺序相同的四个数可以看作是一种情况。我们把 种取值看成 个盒子，四个数看成是 个相同的小球，这样就相当于相同球放入不同盒可以空盒的球盒问题，用隔板法可以计算，这样总共就是 种情况。所以 可以开的很大，但大部分都是重复的，所以最多不会超过 种情况，如果 非常大的话打表然后查表即可。不过这里直接爆搜就行了。

问题在于如何判定一种情况有解，爆搜即可。数的顺序是可变的，确定好数的顺序后，运算的顺序也是可变的，比如我们可以先算第二个数和第三个数，然后它们的结果再和第一个数进行运算（也就是加括号调整运算顺序）。如果只枚举所有排列，不枚举运算顺序的话（也就是只从左向右运算）是有可能出bug的，比如 这个我们是不能通过枚举排列然后从左到右依次结合算出 的。所以需要枚举数的顺序和运算的顺序，弄好这两个东西后，再枚举一下运算符就可以了。整个的运算次数大概是 ，之后查表也花不了太多时间， 时限很稳。

  1. 枚举数的顺序好说，直接用 STL 的 bool next_permutation(iterator start,iterator end) 函数就可以了。

  2. 运算的顺序的枚举可以枚举运算符的序号，一开始是 个数 个运算符，用 代表第 个运算符，两边分别是第 个数和第 个数，枚举到 就将它们结合，同理 。运算一次后剩余 个数 个运算符，同理用 来代表这两个运算符以及两边的操作数。最后剩下 个数 个运算符，直接计算。这样一共是 种情况。

  3. 枚举运算符好说，可以写三重 循环，为了方便也可以用 位 进制数来代表三个运算符。

实际在写的时候你会发现有时候会出现除出分数的情况，而且这无法通过枚举数的顺序和运算顺序规避掉。比如 A 3 4 6 这种情况，运算方法只有 6/(1-(3/4))=24 一种。解决方法也简单，就是直接用浮点数来算，因为就四个数运算，精度损失几乎可以忽略不计。可以设置一个精度值 ，最后和 比较一下，如果精度（与 的差值的绝对值）在 以内，就认为结果就是 ，不过浮点运算太慢，一些比较烂的机器可能容易超时。或者可以用取模运算，这样除法就被转化为乘法了，除以一个数相当于乘上这个数的逆元，直接用整数来做即可。

代码：

浮点数运算

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <ctime>
using namespace std;
const double eps=1e-9;

int T;
bool ck[15][15][15][15];

bool merge(vector<double> &a,int idx,int opt){//是否可以成功合并，可以则合并 
	if(a.end()-a.begin()<idx+1)return false;
	if(opt==3 && a[idx+1]==0)return false;//除0了
	
	if(opt==0)a[idx]+=a[idx+1];
	else if(opt==1)a[idx]-=a[idx+1];
	else if(opt==2)a[idx]*=a[idx+1];
	else if(opt==3)a[idx]/=a[idx+1];
	
	a.erase(a.begin()+idx+1);
	return true;
}
double compute(vector<int> t,int order,int optr){//od顺序，opt运算符 
	vector<double> a;
	for(int i=0;i<4;i++)
		a.push_back(t[i]);
	int idx,opt;
	idx=order%3;order/=3;
	opt=optr%4;optr/=4;
	if(!merge(a,idx,opt))return -1;
	idx=order;
	opt=optr%4;optr/=4;
	if(!merge(a,idx,opt))return -1;
	idx=0;
	opt=optr%4;optr/=4;
	if(!merge(a,idx,opt))return -1;
	return a[0];
}
void check(vector<int> a){
	auto &flag=ck[a[0]][a[1]][a[2]][a[3]];
	do{
		for(int od=0;od<6;od++)//这里枚举运算顺序，用两位3进制数代替，不过最高位只能取得到0,1
			for(int opt=0;opt<64;opt++)
				if(abs((compute(a,od,opt)-24))<=eps){
					flag=true;
					return;
				}
	}while(next_permutation(a.begin(),a.end()));
	flag=false;
	return;
}

map<string,int> mp;

int main(){
	cin.tie(0)->sync_with_stdio(false);
	
	mp["A"]=1;
	mp["2"]=2;
	mp["3"]=3;
	mp["4"]=4;
	mp["5"]=5;
	mp["6"]=6;
	mp["7"]=7;
	mp["8"]=8;
	mp["9"]=9;
	mp["10"]=10;
	mp["J"]=11;
	mp["Q"]=12;
	mp["K"]=13;
	
	for(int a=1;a<=13;a++)
		for(int b=a;b<=13;b++)
			for(int c=b;c<=13;c++)
				for(int d=c;d<=13;d++)
					check(vector<int>{a,b,c,d});
	
	cin>>T;
	
	int t[4];
	string tmp;
	while(T--){
		for(int i=0;i<4;i++){
			cin>>tmp;
			t[i]=mp[tmp];
		}
		sort(t,t+4);
		cout<<((ck[t[0]][t[1]][t[2]][t[3]])?"YES":"NO")<<"\n";
	}
	
	return 0; 
}

取模运算。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <ctime>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

int T;
bool ck[15][15][15][15];

ll qpow(ll a,ll b){
	b%=mod;
	ll ans=1,base=a%mod;
	while(b){
		if(b&1){
			ans=ans*base%mod;
		}
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}
inline ll inv(ll x){
	return qpow(x,mod-2);
}

bool merge(vector<ll> &a,int idx,int opt){//是否可以成功合并，可以则合并 
	if(a.end()-a.begin()<idx+1)return false;
	if(opt==3 && a[idx+1]==0)return false;
	
	if(opt==0)a[idx]+=a[idx+1];
	else if(opt==1)a[idx]+=mod-a[idx+1];
	else if(opt==2)a[idx]*=a[idx+1];
	else if(opt==3)a[idx]*=inv(a[idx+1]);
	
	a.erase(a.begin()+idx+1);
	a[idx]%=mod;
	return true;
}
ll compute(vector<ll> a,int order,int optr){//od顺序，opt运算符 
	int idx,opt;
	idx=order%3;order/=3;
	opt=optr%4;optr/=4;
	if(!merge(a,idx,opt))return -1;
	idx=order;
	opt=optr%4;optr/=4;
	if(!merge(a,idx,opt))return -1;
	idx=0;
	opt=optr%4;optr/=4;
	if(!merge(a,idx,opt))return -1;
	return a[0];
}
void check(vector<ll> a){
	auto &flag=ck[a[0]][a[1]][a[2]][a[3]];
	do{
		for(int od=0;od<6;od++)
			for(int opt=0;opt<64;opt++){
				if(compute(a,od,opt)==24){
					flag=true;
					return;
				}
			}
	}while(next_permutation(a.begin(),a.end()));
	flag=false;
	return;
}

map<string,int> mp;

int main(){
	cin.tie(0)->sync_with_stdio(false);
	
	mp["A"]=1;
	mp["2"]=2;
	mp["3"]=3;
	mp["4"]=4;
	mp["5"]=5;
	mp["6"]=6;
	mp["7"]=7;
	mp["8"]=8;
	mp["9"]=9;
	mp["10"]=10;
	mp["J"]=11;
	mp["Q"]=12;
	mp["K"]=13;
	
	for(int a=1;a<=13;a++)
		for(int b=a;b<=13;b++)
			for(int c=b;c<=13;c++)
				for(int d=c;d<=13;d++)
					check(vector<ll>{a,b,c,d});
	
	cin>>T;
	
	int t[4];
	string tmp;
	while(T--){
		for(int i=0;i<4;i++){
			cin>>tmp;
			t[i]=mp[tmp];
		}
		sort(t,t+4);
		cout<<((ck[t[0]][t[1]][t[2]][t[3]])?"YES":"NO")<<"\n";
	}
	
	return 0; 
}

I 正义从不打背身

思路：

这题我觉的挺神秘的，是打表找规律。因为题目给出的操作是比较固定的，所以我们猜测估计会出现什么规律，为了找到规律所以要先暴力打个表，思路其实挺明确的。

我们暴力模拟里面的反转过程，看看进行 次后每个位置上的人原本的编号是多少，以及翻转情况

打表程序：

cin>>n>>m;
vector<int> a(n+1);
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++){
	for(int j=1;j<=i/2;j++)
	swap(a[j],a[i-j+1]);
	for(int j=1;j<=i;j++)vis[a[j]]^=1;
	
	printf("%2d:",i);
	for(int j=1;j<=i;j++)
		cout<<a[j]<<" ";
	cout<<endl;
	printf("  :");
	for(int j=1;j<=i;j++)
		cout<<(vis[a[j]]?"*":"-")<<" ";
	cout<<endl;
}

给个 的数据：

 1:1
  :*
 2:2 1
  :* -
 3:3 1 2
  :* * -
 4:4 2 1 3
  :* * - -
 5:5 3 1 2 4
  :* * * - -
 6:6 4 2 1 3 5
  :* * * - - -
 7:7 5 3 1 2 4 6
  :* * * * - - -
 8:8 6 4 2 1 3 5 7
  :* * * * - - - -
 9:9 7 5 3 1 2 4 6 8
  :* * * * * - - - -
10:10 8 6 4 2 1 3 5 7 9
  :* * * * * - - - - -
11:11 9 7 5 3 1 2 4 6 8 10
  :* * * * * * - - - - -
12:12 10 8 6 4 2 1 3 5 7 9 11
  :* * * * * * - - - - - -
13:13 11 9 7 5 3 1 2 4 6 8 10 12
  :* * * * * * * - - - - - -
14:14 12 10 8 6 4 2 1 3 5 7 9 11 13
  :* * * * * * * - - - - - - -
15:15 13 11 9 7 5 3 1 2 4 6 8 10 12 14
  :* * * * * * * * - - - - - - -

其实还是比较好看出规律的。后 没有参与操作，就维持原本的状态。前 个数的前半部分是以 开头， 为公差递减到 或者 的等差数列，后半部分以 中剩余的那个开头，以 为公差递增到 。状态的反转情况是：前半部分翻转。

前半部分的长度是 ，后半部分的长度是 ，整除运算。知道这个之后就几个 循环就搞定了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=2e6+5;

int n,m;
bool vis[maxn];
string s;

int main(){
	cin>>n>>m;
	cin>>s;
	s=" "+s;

	for(int i=1,j=m;j>=1;i++,j-=2)vis[i]=(s[j]=='P');
	for(int i=(m+1)/2+1,j=(m&1)?2:1;j<=m;i++,j+=2)vis[i]=(s[j]=='P');
	for(int i=m+1;i<=n;i++)vis[i]=(s[i]=='P');
	for(int i=1;i<=(m+1)/2;i++)vis[i]^=1;
	for(int i=1;i<=n;i++)cout<<vis[i]<<" ";
	
	return 0;
}

J 临场发挥

思路：

不那么明显的区间 。

首先要看出来一个贪心的小结论。就是就是能力值大的，应该放在两边，反之放中间。因为如果大数 与内侧的某个数 交换位置，假如说向这两个数距离为 格，那么大数减少了 的贡献，而小数只增加了 的贡献，得不偿失了。

所以我们可以将所有数从小到大排序，然后设 为用前 个数填满区间 的最大贡献。根据上面的贪心小结论，我们每次拿到的数与前面用到的数相比是最大的，所以一定是放在区间两边的。假设拿到的数的大小为 ，原本的位置为 ，所以递推方程就是 。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pll pair<ll,ll>
const int maxn=2005;
const ll linf=1e18;

int n;
ll dp[maxn][maxn];
pll a[maxn];

int main(){
	cin>>n;
	for(int i=1,t;i<=n;i++){
		cin>>t;
		a[i]=pll(t,i);
	}
	sort(a+1,a+n+1);
	
	for(int len=1;len<=n;len++){
		auto [ai,id]=a[len];
		for(int l=1,r=l+len-1;r<=n;l++,r++){
			dp[l][r]=max(dp[l+1][r]+abs(l-id)*ai,dp[l][r-1]+abs(r-id)*ai);
		}
	}
	
	cout<<dp[1][n]<<endl;
	return 0;
}

其实我一开始没看懂上面说的啥，然后我用另外一种写法硬是写过了……

大体思路和上面是一样的，不过我们排序是从大到小排序，然后先给大的排到两边。设 表示用前 个最大值，左边放 个，右边放 个的最大贡献。

状态转移方程应该也挺好想的，不过就没有区间dp的感觉了。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pll pair<ll,ll>
const int maxn=2005;
const ll linf=1e18;

int n;
ll dp[maxn][maxn];//左边有l个，右边有r个 
pll a[maxn];

int main(){
	cin>>n;
	for(int i=1,t;i<=n;i++){
		cin>>t;
		a[i]=pll(t,i);
	}
	sort(a+1,a+n+1,greater<pll>());
	
	for(int i=1;i<=n;i++){
		auto [ai,id]=a[i];
		ll l,r;
		for(l=0;l<=i;l++){
			r=i-l;
			if(l>0)dp[l][r]=max(dp[l][r],dp[l-1][r]+abs(l-id)*ai);
			if(r>0)dp[l][r]=max(dp[l][r],dp[l][r-1]+abs(n-r+1-id)*ai);
		}
	}
	
	ll ans=0;
	for(int l=0;l<=n;l++)
		ans=max(ans,dp[l][n-l]);
	cout<<ans<<endl;
	return 0;
}

K BanG Dream! It's MyGO!!!!!

思路：

表达了作者的思乡之情

这题算是狠狠地扫盲了。

  1. 三角形的计数是三元环计数问题。
  2. 三芒星简单，统计一下每个点的度数 ，然后用组合数就能算了。总个数是 。
  3. 闪电折线不能直接算出来。我们可以枚举中间那条边，然后两个端点的度数-1乘起来就是闪电折线和三角形*3的总个数。因为三角形个数可以算出来，那这个也就可以算了 。

所以这题重点在于三元环计数求三角形个数。详情请看 OI wiki，讲的还挺不错。

code：

本来出题人还想出个模数，答案对模数取模，避免溢出，结果发现数据并不会超，就删掉了。这里计数的时候一开始也没写long long就过了，保险起见还是加上了 。

#include <iostream> 
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;

int n,m;
int deg[maxn];
int u[maxn<<1],v[maxn<<1];

int head[maxn],ent;
struct edge{
	int v,nxt;
}e[maxn<<2];
void add(int u,int v){
	e[++ent]={v,head[u]};
	head[u]=ent;
}

ll cnt1,cnt2,cnt3;
bool vis[maxn];
void triangle(){
	for(int u=1;u<=n;u++){
		for(int i=head[u];i;i=e[i].nxt)
			vis[e[i].v]=true;
		for(int i=head[u],v;i;i=e[i].nxt){
			v=e[i].v;
			for(int j=head[v],w;j;j=e[j].nxt){
				w=e[j].v;
				if(vis[w])cnt1++;
			}
		}
		for(int i=head[u];i;i=e[i].nxt)
			vis[e[i].v]=false;
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i];
		deg[u[i]]++;
		deg[v[i]]++;
	}
	for(int i=1;i<=m;i++){
		cnt3+=1ll*(deg[u[i]]-1)*(deg[v[i]]-1);//闪电折线和三角形*3 
		if(deg[u[i]]>deg[v[i]] || (deg[u[i]]==deg[v[i]] && u[i]>v[i]))
			swap(u[i],v[i]);
		add(u[i],v[i]);
	}
	for(int i=1;i<=n;i++)
		cnt2+=1ll*deg[i]*(deg[i]-1)*(deg[i]-2)/6;
	
	triangle();
	cnt3-=3*cnt1;
	
	cout<<cnt1+cnt2+cnt3;
	return 0;
}

L koala的程序

思路：

这题本来出的是裸约瑟夫问题，不过后来感觉直接能搜到原题不好，所以换成了看程序。不过应该还是比较容易看出是约瑟夫问题吧。

约瑟夫问题可是老朋友了，不熟悉的可以去 OI wiki 长长见识（线性方法的一个证明）。这个题还要输出每一个出局的人，所以暴力模拟删人的过程，用线段树或者树状数组来优化找到下一个要删的人的过程即可。时间复杂度是 或者 。

code：

不动脑子的暴力线段树二分写法。这题一开始数据比较弱，而且只有 ，导致 暴力删数可以直接写过（ 是 ，但是常数很小），后来加强了，但是加强之后这个线段树过不去了（线段树是常数比较大的 ），后来大家伙一致认为还是放行线段树比较好，所以最后还是调整时限给过了。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=3e5+5;

int n,k;

struct segement_tree{
	#define ls (p<<1)
	#define rs (p<<1|1)
	
	int tr[maxn<<3],n;
	
	void push_up(int p){
		tr[p]=tr[ls]+tr[rs];
	}
	void build(int p,int l,int r){
		if(l==r){
			tr[p]=1;
			return;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(p);
	}
	void build(int _n){
		n=_n;
		build(1,1,_n);
	}
	void print(int p,int l,int r){
		printf("%d[%d,%d]:%d\n",p,l,r,tr[p]);
		if(l==r){
			
			return;
		}
		int mid=(l+r)>>1;
		print(ls,l,mid);
		print(rs,mid+1,r);
	}
	void print(){
		print(1,1,n);
		cout<<endl;
	}
	
	void mdy(int p,int l,int r,int id){
		if(l==r){
			tr[p]=0;
			return;
		}
		int mid=(l+r)>>1;
		if(id<=mid)mdy(ls,l,mid,id);
		else mdy(rs,mid+1,r,id);
		push_up(p);
	}
	int count(int p,int l,int r,int L,int R){//区间[L,R]的剩余人数 
		if(L<=l && r<=R){
			return tr[p];
		}
		int mid=(l+r)>>1,ans=0;
		if(mid>=L)ans+=count(ls,l,mid,L,R);
		if(mid<R)ans+=count(rs,mid+1,r,L,R);
		return ans;
	}
	int search(int l,int r,int x){//范围[l,r]二分找第x个人的编号 
		int L=l,mid;
		while(l<r){
			mid=(l+r)>>1;
			if(count(1,1,n,L,mid)>=x)r=mid;
			else l=mid+1;
		}
		return l;
	}
	int q(int id,int x){//从id开始向下报x次数
		int idx;
		x=(x-1)%count(1,1,n,1,n)+1;//先转整轮，剩下的次数是不够一轮报数的
		if(count(1,1,n,id,n)>=x)idx=search(id,n,x);//区间[id,n]的剩余人数可以报完
		else {//不能报完，回到[1,id]区间继续报数
			x-=count(1,1,n,id,n);
			idx=search(1,id,x);
		}
		mdy(1,1,n,idx);//删人
		return idx;
	}
	
	#undef ls
	#undef rs	
}tr;

int main(){
    cin.tie(0)->sync_with_stdio(false);
	cin>>n>>k;
	tr.build(n);
	for(int i=1,idx=1;i<n;i++){
//		tr.print();
		idx=tr.q(idx,k);
		cout<<idx<<" ";
	}
	return 0;
}

神中神的树状数组倍增写法，直接把大佬的神迹std搬过来，下面再给一个我自己抄的。

有两个亮点：

  1. 树状数组利用了辖域这个概念，直接倍增找到了最后一个等于 的数，把时间复杂度优化到了 。辖域指的是树状数组上某个节点管理的区域（如果节点结合的运算是加法，那么这个节点管理的就是区域的和），对于树状数组某个位置 上的节点 ，它的辖域是 到 这长为 lowbit(idx) 的区间。
  2. 在删人的时候没有取模再分类讨论，而是先找到上次出局的人前面已经报过数的人数，然后再向后报 个人，假设此时剩下 个人，模 就是最后报到了第几个人。
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
template <typename T>
struct Fenwick {
  int n;
  std::vector<T> a;

  Fenwick(int n_ = 0) { init(n_ + 1); }

  void init(int n_) {
    n = n_;
    a.assign(n, T{});
  }

  void add(int x, const T& v) {
    if (x < 1)
      return;
    for (int i = x; i <= n; i += i & -i) {
      a[i] = a[i] + v;
    }
  }

  T sum(int x) {
    T ans{};
    for (int i = x; i > 0; i -= i & -i) {
      ans = ans + a[i];
    }
    return ans;
  }

  T rangeSum(int l, int r) { return sum(r) - sum(l - 1); }

  int select(const T& k) {
    int x = 0;
    T cur{};
    for (int i = 1 << std::__lg(n); i; i /= 2) {
      if (x + i < n && cur + a[x + i] < k) {
        x += i;
        cur = cur + a[x];
      }
    }
    return x + 1;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie();
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  Fenwick<int> fen(n + 1);
  for (int i = 1; i <= n; ++i)
    fen.add(i, 1);
  int cur = 0, killed = 0;
  for (int i = n; i > 1; --i) {
    cur = (fen.sum(killed) + k) % i;
    if (cur == 0)
      cur = i;

    killed = fen.select(cur);
    // cout << cur << ' ' << killed << '\n';
    fen.add(killed, -1);
    cout << killed << ' ';
  }
  return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=3e5+5;

int n,k;

struct tree_array{
	int tr[maxn],n;
	
	int lowbit(int x){return x&-x;}
	void add(int id,int x){
		for(int i=id;i<=n;i+=lowbit(i))
			tr[i]+=x;
	}
	void build(int _n){
		n=_n;
		for(int i=1;i<=n;i++)add(i,1);
	}
	int query(int id){
		int ans=0;
		for(int i=id;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
	int query(int l,int r){
		return query(r)-query(l-1);
	}
	int kth(int k){//倍增找第k大 
		int id=0,tot=0;
		for(int i=1<<20;i;i>>=1){
			if(id+i<n && tot+tr[id+i]<k){
				tot+=tr[id+i];
				id+=i;
			}
		}
		return id+1;
	}
}tr;

int main(){
	cin>>n>>k;
	tr.build(n);
	for(int i=n,cur=1,dead=0;i>1;i--){
		cur=(tr.query(dead)+k-1)%i+1;//取模后的范围不在[0,i)，而在[1,i+1)，所以内部-1，外部+1
		dead=tr.kth(cur);
		tr.add(dead,-1);
		cout<<dead<<" ";
	}
	return 0;	
}