Preface

由于还有两周就要滚去打区域赛了，这周开始周末每天都训一场吧

这场总体来说打的还可以，虽然E题这个Easy从卡局卡到3h，但由于其它的题都是一遍过所以罚时还尚可跻进Au区

后面一个小时看徐神和祁神苦战K大分类讨论，虽然场下感觉摸了一个B的做法出来，但感觉实现还是太麻烦了就没写，最后K也是没写出来苦露西

由于明天早上9点要再打场VP，而且今晚在给学校趣味赛出题验题，所以就没补BK这两个题，过段时间有空补上吧

A. Lily

签到题，把两把不是L的位置都变成C即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n; char s[N];
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
	if (s[i]=='.'&&s[i-1]!='L'&&s[i+1]!='L') s[i]='C';
	return printf("%s",s+1),0;
}

B. Code With No Forces

每个人拆成三个来状压，细节好多以后再来写

C. Array Concatenation

首先发现当接上这个序列的转置后，后面两种操作就本质相同了，我们可以直接递推求出贡献

然后把贡献的式子写一写会发现最后其实只有两种情况，即要么一直不转置，要么第一步就转置，取其中较大的那个输出即可

#include<bits/stdc++.h>
#define int int64_t
using namespace std;
const int MOD = 1e9+7;

const int N = 1e5+5;
int n, m, sum[N];

int powe(int x, int p){
	int res=1;
	while (p>0){if (p%2) res=res*x%MOD; p/=2, x=x*x%MOD;}	
	return res;
}

signed main(){
	scanf("%lld%lld", &n, &m);
	for (int i=1; i<=n; ++i){
		int a; scanf("%lld", &a);
		sum[i]=(sum[i-1]+a)%MOD;	
	}
	
	int ans1 = sum[n]*powe(2, m-1)%MOD;
	ans1 = ans1*(n*powe(2, m)%MOD + 1)%MOD;
	
	int ans2=0;
	int len=n, S=sum[n], T=0;
	for (int i=1; i<=n; ++i) T=(T+sum[i])%MOD;
	for (int i=1; i<=m; ++i){
		T = (T*2%MOD + S*len%MOD)%MOD;	
		S = S*2%MOD, len=len*2%MOD;
		//printf("i=%lld T=%lld\n", i, T);
	}
	ans2 = T;
	
	//printf("ans1=%lld ans2=%lld\n", ans1, ans2);
	printf("%lld\n", max(ans1, ans2));
	return 0;	
}

D. Alice's Dolls

好神的多项式，做不了一点

E. Draw a triangle

徐神被这题要折磨疯了，不禁让我想起今年ICPC网络赛第二场的那个K，直接把我们队干爆炸了

把式子写出来会发现最小的可能取值就是\(\gcd(x,y)\)，然后求一组合法解就直接用exgcd跑一下即可

比赛的时候不知道怎么脑抽了一直卡着，但我一直在想别的题也没太管，最后能过就行

#include <bits/stdc++.h>

using llsi = long long signed int;
using ld = long double;
using std::abs;

llsi t, a, b, c, d;

void exgcd(llsi a, llsi b, llsi &x, llsi &y) {
	if(!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}

int main() {
	// freopen("1.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	std::cin >> t;
	while(t--) {
		std::cin >> a >> b >> c >> d;
		if(a == c) { std::cout << a + 1 << ' ' << b << char(10); continue; }
		if(b == d) { std::cout << a << ' ' << b + 1 << char(10); continue; }
		
		const llsi A = b - d, B = c - a, C = a * d - b * c;
		
		llsi x, y;
		exgcd(A, B, x, y);
		// const llsi gab = x * A + y * B;
		// std::cerr << "X = " << x << " Y = " << y << char(10);
		
		std::cout << a + x << ' ' << b + y << char(10);
	}
	return 0;
}

F. Union of Circular Sectors

扇形面积并，巨恶心的计算几何神题，直接给我们队两个几何之神干懵了

G. Group Homework

典中典之换根DP，闪总的最爱

这题首先要手玩发现两条路径要么完全不相交，要么只有一个公共点，否则我们可以交换配对情况来得到一组更大的解

考虑只有一个公共点的情况是很简单的，直接把到每个点的路径中前\(4\)大的找出来即可，当然这里复杂度不卡可以直接大力排序

而另一种情况我们可以枚举在哪条边断开，然后在两边的树中分别找直径即可

但我们换根DP求出来的只有强制经过某个点的最长路，但我们现在要求的是一个子树中的最大值，乍一看很不好处理

但仔细一想，我们可以直接定义状态\(F(x,y)\)表示在\(x\)的子树内（不走\(y\)这个点方向的边），能得到的最长路

不难发现有效的状态其实是\(O(n)\)的，那么直接记搜一下就好了

这里为了方便用了sort和map，实际可以做到完全线性

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,x,y,a[N],ans; vector <int> v[N]; vector <pi> l[N]; map <int,int> f[N];
inline void DFS1(CI now=1,CI fa=0)
{
	for (auto to:v[now]) if (to!=fa)
	DFS1(to,now),l[now].push_back(pi((l[to].empty()?0:l[to][0].fi)+a[to],to));
	sort(l[now].begin(),l[now].end(),greater <pi>());
}
inline void DFS2(CI now=1,CI fa=0,CI out=0)
{
	if (fa) l[now].push_back(pi(out+a[fa],fa)),sort(l[now].begin(),l[now].end(),greater <pi>());
	while (l[now].size()<4) l[now].push_back(pi(0,0));
	for (auto to:v[now]) if (to!=fa) DFS2(to,now,to!=l[now][0].se?l[now][0].fi:l[now][1].fi);
}
inline int F(CI now,CI fa)
{
	if (f[now].count(fa)) return f[now][fa];
	int p1=0; while (l[now][p1].se==fa) ++p1;
	int p2=p1+1; while (l[now][p2].se==fa) ++p2;
	int ret=l[now][p1].fi+l[now][p2].fi+a[now];
	for (auto to:v[now]) if (to!=fa) ret=max(ret,F(to,now));
	return f[now][fa]=ret;
}
int main()
{
	//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (DFS1(),DFS2(),i=1;i<=n;++i) ans=max(ans,l[i][0].fi+l[i][1].fi+l[i][2].fi+l[i][3].fi);
	for (i=1;i<=n;++i) for (auto j:v[i]) ans=max(ans,F(i,j)+F(j,i));
	return printf("%d",ans),0;
}

H. Hysteretic Racing

啥玩意根本没人过

I. Invincible Hotwheels

徐神最爱的字符串，但难度有点大写不了一点

J. Permutation Puzzle

很有意思的一个题，感觉随便rush了一个写法就过了

首先我们可以给所有值不确定的位置\(i\)搞出一个取值区间\([l_i,r_i]\)

\(l_i\)的求解就是正向拓扑排序一遍，每次更新\(u\to v\)的时候就令\(l_v=\max(l_v,l_u+1)\)，\(r_i\)的情况同理，在反图上拓扑排序一遍即可

然后我们考虑现在的问题，给出\(n\)个区间和\(n\)个，要求在每个区间内选一个数，使得所有\([1,n]\)中的每个数都被选了恰好一次

这个问题有个经典的贪心做法，我们从小到大枚举每个数，在所有左端点小于它的区间中，我们找右端点最小的那个区间和它配对，不难发现这样一定是最优的

这道题和上面的问题看似有区别，因为它还附带了一些拓扑关系，在符合上述配对的条件下还要满足大小关系

但仔细一想会发现对于图中\(u\to v\)连接的两点，一定有\(l_u<l_v,r_u< r_v\)，而上面的贪心跑出的结果天然满足拓扑序的性质，因此可以直接上

实现的话用个堆模拟一下即可，总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,n,m,p[N],x,y,deg_G[N],deg_R[N],l[N],r[N],ans[N]; vector <int> G[N],R[N]; vector <pi> o[N];
int main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		scanf("%d",&p[i]),G[i].clear(),R[i].clear(),deg_G[i]=deg_R[i]=0;
		for (i=1;i<=m;++i)
		{
			scanf("%d%d",&x,&y);
			G[x].push_back(y); ++deg_G[y];
			R[y].push_back(x); ++deg_R[x];
		}
		queue <int> q; for (i=1;i<=n;++i) if (p[i]) l[i]=r[i]=p[i]; else l[i]=1,r[i]=n;
		for (i=1;i<=n;++i) if (!deg_G[i]) q.push(i);
		int cnt=0; while (!q.empty())
		{
			int now=q.front(); q.pop(); ++cnt;
			for (auto to:G[now]) if (l[to]=max(l[to],l[now]+1),!--deg_G[to]) q.push(to);
		}
		if (cnt!=n) { puts("-1"); continue; }
		for (i=1;i<=n;++i) if (!deg_R[i]) q.push(i);
		while (!q.empty())
		{
			int now=q.front(); q.pop();
			for (auto to:R[now]) if (r[to]=min(r[to],r[now]-1),!--deg_R[to]) q.push(to);
		}
		bool flag=1; for (i=1;i<=n;++i) if (l[i]>r[i]) flag=0;
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=n;++i) o[i].clear();
		for (i=1;i<=n;++i) o[l[i]].push_back(pi(r[i],i));
		priority_queue <pi,vector <pi>,greater <pi>> hp;
		for (i=1;i<=n;++i)
		{
			for (auto [pos,id]:o[i]) hp.push(pi(pos,id));
			if (hp.empty()||hp.top().fi<i) { flag=0; break; }
			ans[hp.top().se]=i; hp.pop();
		}
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

K. Barrel Theory

大力分类讨论，感觉我们队比赛时候写的做法挺对的但就是过不去，看了题解又只能怀疑人生，留着过两天补吧

L. Largest Unique Wins

我只能说出题人这个数据范围真是神来一笔，差点把我骗去想什么单纯形法这类的东西了

这题其实想通的话非常简单，直接先拉两个人出来以\(100\%\)的概率选\(m\)，然后再拉两个人出来以\(100\%\)的概率选\(m-1\)，一直往前放下去即可

此时手玩不难发现对于任意一个人都达到了纳什均衡态

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=20;
int n,m,l,c[N],a[N][N];
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),l=m,i=1;i<=n;++i)
	{
		if (l>1&&c[l]==2) --l; ++c[l]; a[i][l]=1; 
	}
	for (i=1;i<=n;++i) for (j=1;j<=m;++j) printf("%.10lf%c",(double)a[i][j]," \n"[j==m]);
	return 0;
}

M. Youth Finale

傻逼题，但是我脑抽了写复杂了

首先求出初始逆序对数，考虑每次shift操作带来的影响，不难发现其实就是看后面的数和\(p_1\)的大小关系

而reverse操作就直接拿\(C_n^2\)减去当前答案即可，然后把原来在前面的shift操作改到后面即可

因此直接拿个deque模拟一下，比赛的时候脑抽了拿树状数组去维护了下后面的数，我的评价是脑子被门夹了

#include<cstdio>
#include<iostream>
#include<deque>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=600005;
int n,m,p[N],ret,all,rev; deque <int> dq; char s[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline int get(RI x,int ret=0)
		{
			for (;x<=n;x+=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x;x-=lowbit(x)) bit[x]+=y;
		}
		#undef lowbit
}A,B;
signed main()
{
	//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
	RI i; for (scanf("%lld%lld",&n,&m),all=n*(n-1)/2LL,i=1;i<=n;++i)
	scanf("%lld",&p[i]),ret+=A.get(p[i]),A.add(p[i],1),dq.push_back(p[i]);
	for (A.add(p[1],-1),i=1;i<n;++i) B.add(p[i],1);
	for (scanf("%s",s+1),printf("%lld\n",ret),i=1;i<=m;++i)
	{
		if (n==1) { putchar('0'); continue; }
		if (s[i]=='R') rev^=1; else
		{
			if (rev)
			{
				int grt=B.get(dq.back()); ret-=grt; ret+=n-1-grt;
				int ed=dq.back(); dq.pop_back(); int sed=dq.back();
				A.add(ed,-1); B.add(sed,-1); A.add(dq.front(),1); B.add(ed,1); dq.push_front(ed);
			} else
			{
				int grt=A.get(dq.front()); ret-=n-1-grt; ret+=grt;
				int fr=dq.front(); dq.pop_front(); int sfr=dq.front();
				A.add(sfr,-1); B.add(fr,-1); A.add(fr,1); B.add(dq.back(),1); dq.push_back(fr);
			}
		}
		putchar((rev?all-ret:ret)%10+'0');
	}
	return 0;
}