Preface

这场打的有点捞说实话，两个小时出头的时候写完6个题就开始坐牢了

K题由于我习惯性地不写数论就扔给徐神了，徐神也是很有思路写了个看着就很对的东西，但不知道为什么过不去

赛后发现K其实是个很傻逼的题，类似的思路我最近补CF的时候还遇到过，但就是没细想

虽然当时下机的时候和祁神把A题的正解讨论出来了，但因为这题实现还挺恶心的所以决策就是优先保证徐神写K题的时间，因此最后A题场上也就写了一半草草收场了

很奇怪感觉平时训练的时候我们队的后场都还可以的，有一次甚至最后一小时连过四题，但一到正式比赛后面就经常坐牢

唉区域赛在即要再多精进下了，感觉我们队的配合啥的都挺好的，可能还是练的不够多啊，一句话加训就完事

A Evaluation

这题在暑假集训的时候做到过一个类似的题，所以很快有了大致的思路，就是通过根号来构造开关

考虑对于每一对\(f(x_i)=a_i\)，我们希望能构造出一个式子\(W_i\)，使得这个式子在\(x=x_i\)时值为\(a_i\)，在\(x=x_j(i\ne j)\)时值为\(0\)，那么最后把所有的\(W_i\)加起来就是一个符合要求的式子了

考虑把\(W_i\)表示成\((A_i)\times (B_i)\)的形式，其中\(A_i\)是一个无论\(x\)取值为多少其返回值都为\(a_i\)的数，而\(B_i\)实现开关功能，当且仅当\(x=x_i\)时返回\(1\)，否则返回\(0\)

回忆拉格朗日插值的表达式，我们很容易想到把\(B_i\)构造成一个由若干个\((x-1-1-\cdots)\)乘起来的形式，其中每个括号内的\(-1\)个数就等于\(x_j(i\ne j)\)的值

而要得到值为\(1\)的数是很容易的，不管我们遇到的字符是什么，给它开两个根号后最后一定会变成\(1\)

另外插一嘴这题中\(1\)的作用很大，比如在没找到下一个\(x\)的时候就可以通过把式子一直乘上\(1\)来跳过某些无用的数

这样当\(x=x_j\)时其中有一个括号的值为\(0\)，因此整个式子的值为\(0\)，否则当\(x=x_i\)时它们乘起来会得到一个不为\(0\)的值

而我们最后要让\(B_i\)的值为\(1\)，考虑到这个乘积不会很大，因此在外面套若干个根号即可将这个非零值转化为\(1\)

接下来就是考虑怎么构造\(A_i\)了，像这种构造题中一个最常见的思路就是二进制分解

由于这里可以用乘法和加法，因此考虑按二进制下每一位来构造，但这样有个问题就是如果只是找到所有的\(2\)然后乘起来，这样是不够在\(15000\)的随机长度下构造出来的，因此我们考虑提高利用率

不难发现对于\(4\sim 8\)，它们开一次根号后就能得到\(2\)，因此在这一步时把它们也拿过来用即可

然后最后对于剩下的没用完的部分，刚开始我是把它们全部暴力变成\(1\)然后乘起来，但发现这样可能会让总长度超过限制的\(10^5\)

后面徐神指出其实对于多余的这些数，把它们全部加起来后再开若干次根号即可得到\(1\)，就可以减少根号的使用量了

最后代码长度虽然不长，但细节还是有一些的，赛后调了快两个多小时才过，比赛的时候估计也写不出来的说

#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
const int N=15005;
int n,m,x[15],f[15]; char s[N]; string ans;
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	auto get_char=[&](void)
	{
		char ch; while (ch=getchar(),ch==' '||ch=='\n'); return ch;
	};
	RI i,j,k,l; for (scanf("%d",&n),i=1;i<=n;++i) s[i]=get_char();
	for (scanf("%d",&m),i=1;i<=m;++i) scanf("%d%d",&x[i],&f[i]);
	for (ans="(",i=j=1;j<=m;++j)
	{
		ans+="(";
		if (f[j])
		{
			for (k=29;k>=1;--k) if ((f[j]>>k)&1)
			{
				int left=k; while (left>0)
				{
					if (s[i]=='2') ans+="2",--left; else
					if (s[i]>='4'&&s[i]<='8') ans+="s("+string(1,s[i])+")",--left; else
					ans+="s(s("+string(1,s[i])+"))"; ++i;
					if (left) ans+="*"; else ans+="+";
				}
			}
			if (f[j]&1) ans+="s(s("+string(1,s[i])+"))+",++i;
			ans.pop_back();
		} else
		{
			ans+="s(s("+string(1,s[i++])+"))";
			ans+="-";
			ans+="s(s("+string(1,s[i++])+"))";
		}
		ans+=")";
		if (m>1)
		{
			ans+="*s(s(s(s(s(s(";
			int k=1; if (k==j) ++k;
			while (k<=m)
			{
				if (s[i]!='x')
				{
					ans+="s(s("+string(1,s[i++])+"))*"; continue;
				}
				ans+="(x"; ++i;
				for (l=1;l<=x[k];++l) ans+="-s(s("+string(1,s[i++])+"))";
				ans+=")*";
				if (++k==j) ++k;
			}
			ans.pop_back();
			ans+="))))))+";
		}
	}
	if (m>1) ans.pop_back(); ans+=")";
	ans+="*s(s(s(s(s(";
	while (i<=n) ans+=string(1,s[i++])+"+";
	ans.pop_back(); ans+=")))))";
	//cout<<ans.size()<<endl;
	return cout<<ans,0;
}

B Wormholes

做不来的题连题目都没看捏

C Covering

这题核心思想在这道题里出现过，因此比赛的时候看了题目就知道怎么写了

每个位置选或不选，还有各种限制，一眼2-SAT模型，考虑抽象题目中的约数来建图

首先任意两个相邻的位置中要至少选一个，同时所有同类型的pair中只能至多取一个

后者的处理方式很套路，一个集合中，要求其中不能选两个及以上的元素同时为\(1\)，朴素地建边是\(O(n^2)\)的

然后用经典的前后缀优化建图即可，具体建图方式可以看上面的链接

当然这题数据范围不大因此用线段树优化建图也可以通过的说

最后注意\(1,n-1\)这两个位置是必选的，需要当作条件把边连上再跑，不然会出现问题

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
typedef long long LL;
const int N=200005;
int n,m,a[N],tot,nxt[N],pre[N]; LL b[N],c[N]; vector <int> pos[N];
inline int ID(CI x,CI tp)
{
	return x+tp*(n-1);
};
namespace Two_Sat
{
	const int NN=N<<2;
	int dfn[NN],low[NN],stk[NN],col[NN],idx,top,scc; bool vis[NN]; vector <int> v[NN];
	inline void addedge(CI x,CI y)
	{
		v[x].push_back(y);
	}
	inline void Tarjan(CI now)
	{
		dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
		for (auto to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
		else if (vis[to]) low[now]=min(low[now],dfn[to]);
		if (low[now]==dfn[now])
		{
			col[now]=++scc; vis[now]=0;
			while (stk[top]!=now) col[stk[top]]=scc,vis[stk[top--]]=0; --top;
		}
	}
	inline void solve(void)
	{
		RI i; for (i=1;i<=tot;++i) if (!dfn[i]) Tarjan(i);
		for (i=1;i<n;++i) if (col[ID(i,0)]==col[ID(i,1)]) return (void)(puts("NO"));
		vector <int> ans; for (i=1;i<n;++i)
		if (col[ID(i,1)]<col[ID(i,0)]) ans.push_back(i);
		printf("%d\n",ans.size());
		for (auto x:ans) printf("%d ",x);
	}
};
using namespace Two_Sat;
int main()
{
	//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	if (n==1) return puts("NO"),0;
	if (n==2) return puts("1\n1"),0;
	for (i=1;i<n;++i) b[i]=c[i]=1000001LL*a[i]+a[i+1];
	sort(c+1,c+n); m=unique(c+1,c+n)-c-1;
	for (i=1;i<n;++i) pos[lower_bound(c+1,c+m+1,b[i])-c].push_back(i);
	addedge(ID(1,0),ID(1,1)); addedge(ID(n-1,0),ID(n-1,1));
	for (i=1;i<n-1;++i) addedge(ID(i,0),ID(i+1,1)),addedge(ID(i+1,0),ID(i,1));
	for (tot=2*(n-1),i=1;i<=m;++i) if (pos[i].size()>1)
	{
		for (j=0;j<pos[i].size();++j) nxt[j]=++tot,pre[j]=++tot;
		for (j=1;j<pos[i].size();++j) addedge(nxt[j-1],nxt[j]),addedge(pre[j],pre[j-1]);
		for (j=0;j<pos[i].size();++j) addedge(ID(pos[i][j],1),nxt[j]),addedge(ID(pos[i][j],1),pre[j]);
		for (j=1;j<pos[i].size();++j) addedge(nxt[j-1],ID(pos[i][j],0)),addedge(pre[j],ID(pos[i][j-1],0));
		//for (j=0;j<pos[i].size();++j) for (RI k=j+1;k<pos[i].size();++k)
		//addedge(ID(pos[i][j],1),ID(pos[i][k],0)),addedge(ID(pos[i][k],1),ID(pos[i][j],0));
	}
	return solve(),0;
}

D Project Manhattan

首先考虑把所有代价\(\le 0\)的位置都站了，并删去所有已经被覆盖了的行和列，考虑对剩下的仅包含正数的矩形的操作

不难发现最优方案一定是在每行中找一个最小的站人，或者是在每列中找一个最小的站人

因为如果存在某一行没有站人，则一定有某个位置没有被覆盖，对于列的情况也是同理，因此二者取较小的输出即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
int t,n,a[N][N];
int main()
{
	//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		for (j=1;j<=n;++j) scanf("%d",&a[i][j]);
		long long ans=0,ret1=0,ret2=0;
		for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (a[i][j]<=0) ans+=a[i][j];
		for (i=1;i<=n;++i)
		{
			int cur=1e6; for (j=1;j<=n;++j)
			if (a[i][j]<=0) { cur=0; break; } else cur=min(cur,a[i][j]);
			ret1+=cur;
		}
		for (j=1;j<=n;++j)
		{
			int cur=1e6; for (i=1;i<=n;++i)
			if (a[i][j]<=0) { cur=0; break; } else cur=min(cur,a[i][j]);
			ret2+=cur;
		}
		printf("%lld\n",ans+min(ret1,ret2));
	}
	return 0;
}

E Another Bus Route Problem

ORZ祁神，本来我都打算去写各种东西优化建图了，祁神提出只要暴力BFS就行了

但因为我实现的时候一个地方没想清楚导致WA了好多发，实在是罪过罪过

考虑从根节点开始，每次加入所有以当前点为路线端点的点至队列中

不难发现在任意时刻当一个点被访问时，它所有的祖先都一定可以被访问

如果我们暴力向上跳来更新，每次遇到有值的点就直接停下，复杂度是\(O(n)\)的

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,fa[N],x,y,ans[N],vis[N]; vector <int> v[N];
int main()
{
	//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=2;i<=n;++i) scanf("%d",&fa[i]);
	for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	queue <int> q; q.push(1); memset(ans,-1,sizeof(ans)); ans[1]=0; vis[1]=1;
	while (!q.empty())
	{
		auto reset=[&](CI now)
		{
			for (auto to:v[now])
			if (!~ans[to]||ans[to]>ans[now]+1)
			{
				ans[to]=ans[now]+1;
				if (!vis[to]) vis[to]=1,q.push(to);
			}
		};
		int now=q.front(); q.pop(); vector <int> tmp; tmp.push_back(now);
		for (x=fa[now];!~ans[x]||ans[x]>ans[now];x=fa[x]) ans[x]=ans[now],tmp.push_back(x);
		reverse(tmp.begin(),tmp.end()); for (auto x:tmp) reset(x);
	}
	for (i=2;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

F Greedy LCS

开场的时候看错题了，看到E有人过了然后点开了F，还把题意喂给了徐神

后面发现原来是经典不可做题，弃了弃了

G Basic Polynomials

题目都没看的说

H Ballet

中间这些题都是给WF水平的队准备的吗，做不了一点

I Impatient Patient

乍一看和之前做过的一道成环期望DP很像，但后面发现这里的最优策略就是选择在某天进行挑战，而之前的每一天都选择跳过

枚举在哪天进行挑战，稍微推一下式子就可以直接算答案了

#include <bits/stdc++.h>

int t, n;

std::vector<int> a, p;

int main() {
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	std::cin >> t;
	while(t--) {
		std::cin >> n;
		a.resize(n), p.resize(n);
		for(auto &a: a) std::cin >> a;
		for(auto &p: p) std::cin >> p;
		long double ans = n;
		for(int i = 0; i < n; ++i) if(p[i]){
			long double upd = (i + 1) + (long double)(1 - p[i]) * (i - a[i] + 1) / p[i];
			if(upd < ans) ans = upd;
		}
		std::cout << ans << '\n';
	}
	return 0;
}

J Street Quality

题目好长，做不了一点

K Super-knight

被这个全场艹穿的题战俘了，感觉最近很容易把简单题想复杂的说

这题其实很容易发现因为第一步走到的点就是\((a,b)\)，而如果往后跳不经过循环使得某一维减小的话答案一定不会更优

因此每次直接找到第一个能让某一维发生变化的位置，然后模拟着跳就完事

考虑这种做法的复杂度，首先在\(n\)次操作后一定会回到\((0,0)\)这个点，此时我们直接结束这个过程

而每次\(x\)这一维发生变化所需的步数大概是\(\frac{n}{a}\)级别，同理\(y\)发生变化所需的步数也是\(\frac{n}{b}\)级别，因此总操作次数大约为\(\frac{n}{n/a}+\frac{n}{n/b}=a+b\)，可以通过此题，不需要任何数论知识

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,n,a,b;
signed main()
{
	//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld%lld",&a,&b,&n);
		int x=a%n,y=b%n,ans=x*x+y*y;
		while (x||y)
		{
			if (x<=a+b&&y<=a+b) ans=min(ans,x*x+y*y);
			int d=min((n-x+a-1)/a,(n-y+b-1)/b);
			x=(x+d*a)%n; y=(y+d*b)%n;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

L Super-palindrome

ORZ徐神看一眼秒了此题

首先发现super-palindrome长度一定为偶数，因此枚举回文中心然后向两边扩展

考虑记录当前未匹配的位置，每次向两边扩展一位的时候如果可以匹配就直接贪心匹配并使得答案加\(1\)

这样的正确性徐神在场上进行了证明，后面发现原来是个结论还有原题来着，我直接呃呃

（不过据说这题数据造假了把\(O(n^3)\)放过去了也是够抽象的）

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
const int N=5005;
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}h[N],pw[N]; int t,n; char s[N];
const Hasher seed=Hasher(31,131);
inline Hasher get(CI l,CI r)
{
	return h[r]-h[l-1]*pw[r-l+1];
}
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%s",s+1); n=strlen(s+1);
		for (pw[0]=Hasher(1,1),i=1;i<=n;++i)
		pw[i]=pw[i-1]*seed,h[i]=h[i-1]*seed+Hasher(s[i],s[i]);
		int ans=0; for (i=1;i<n;++i)
		for (int l1=i,r1=i,l2=i+1,r2=i+1;l1>=1&&r2<=n;--l1,++r2)
		if (get(l1,r1)==get(l2,r2)) ++ans,r1=l1-1,l2=r2+1;
		printf("%d\n",ans);
	}
	return 0;
}

M Dirty Work

签到题，根据经典结论把所有题按照期望解决时间从小到大排序再算答案即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long double LDB;
const int N=5005;
int t,n,a,b; LDB p,tim[N];
int main()
{
	//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d%d%Lf",&a,&b,&p),tim[i]=1.0L*a*(1.0L-p)+1.0L*(a+b)*p;
		LDB ans=0; for (sort(tim+1,tim+n+1),i=1;i<=n;++i)
		tim[i]+=tim[i-1],ans+=tim[i]; printf("%.12Lf\n",ans);
	}
	return 0;
}