Preface

补题，感觉这场挺对口味的说，E直接秒出，虽然刚开始并不觉得能跑得过去，不过写了一发直接艹过去了可海星

F题挺有意思的一个题，不过刚开始没想到只要三次询问就行了所以想偏了，不然也是挺简单的

A. Trust Nobody

枚举说谎的人的个数\(x\)，统计出\(l_i>x\)的个数\(cur\)，只有当\(cur=x\)的时候\(x\)才合法

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,l[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&l[i]);
		bool flag=0; for (i=0;i<=n&&!flag;++i)
		{
			int cur=0; for (j=1;j<=n;++j) if (l[j]>i) ++cur;
			if (cur==i) flag=1,printf("%d\n",i);
		}
		if (!flag) puts("-1");
	}
	return 0;
}

B. Lunatic Never Content

考虑一对对应的位置\(a_i,a_{n-i+1}\)，令\(d_i=|a_i-a_{n-i+1}|\)，则合法的\(x\)必然满足\(x|d_i\)

因此给所有的\(d_i\)求一个\(\gcd\)即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N];
inline int gcd(CI n,CI m)
{
	return m?gcd(m,n%m):n;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		int ret=0; for (i=1;i<=n-i+1;++i) ret=gcd(ret,abs(a[i]-a[n-i+1]));
		printf("%d\n",ret);
	}
	return 0;
}

C. Dreaming of Freedom

考虑最终进入死循环时，一定是存在一个\(x|n(x>1)\)，使得\(n\)个人把票均分给这\(x\)个人

因此我们直接枚举\(n\)的所有非\(1\)因子\(x\)（注意可以包含\(n\)），若\(x\le m\)则有解

注意一些Corner Case即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,m;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d%d",&n,&m),n==1||m==1) { puts("YES"); continue; }
		RI i; bool flag=0; for (i=2;i*i<=n&&!flag;++i)
		if (n%i==0&&min(i,n/i)<=m) flag=1; flag|=n<=m;
		puts(flag?"NO":"YES");
	}
	return 0;
}

D. Running Miles

这题上来写了两个假算法，后面一拍脑袋发现是个傻逼题，还好没有现场打不然直接寄了

其实想到了就很简单，不妨枚举中间的某个数\(a_i\)，然后以此为基准向左向右扩展

当\(j<i\)时，把贡献的式子写出来发现其实就是要求\(a_i+i\)的最大值，而向右则要求\(a_i-i\)的最大值

直接预处理这些信息后答案就很好计算了

乍一想这么做并不能保证中间的那个数\(a_i\)是在计算贡献中的，但多手玩一下会发现这样总能找出最后的答案

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

E. Walk the Runway

什么CF神机，写个暴力然后真就敢写敢过

首先不难发现如果把每个人看作点，然后如果人\(i\)可以排在人\(j\)前面，则连一条\(i\to j\)的边

由于本题中严格的偏序关系，因此得到的就是一个DAG，在上面找答案就非常简单了

不过现在的问题就是整张图的建边如果直接暴力是\(O(n^2m)\)的，直接歇逼

但我们发现当只考虑其中一个维度时，我们排个序之后结合双指针可以\(O(n)\)求出每个点的前后可到达的点

因此我们可以给每个数的每个维度能走到的点用bitset存起来，然后若在\(m\)个维度中都存在\(i\to j\)的边，则最终就有\(i\to j\)这条边

细细算一下复杂度的话应该是\(O(nm\log n+\frac{n^2m}{\omega}+n^2)\)，最后1300ms卡过

#include<cstdio>
#include<iostream>
#include<bitset>
#include<utility>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=5005,M=505;
int n,m,a[M][N],p[N]; bitset <N> nxt[N]; pi w[N]; long long ans,f[N];
inline long long DP(CI now)
{
	if (~f[now]) return f[now]; f[now]=p[now];
	for (RI to=1;to<=n;++to) if (to!=now&&nxt[now].test(to))
	f[now]=max(f[now],p[now]+DP(to)); return f[now];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d%d",&m,&n),i=1;i<=n;++i) scanf("%d",&p[i]);
	for (i=1;i<=m;++i) for (j=1;j<=n;++j) scanf("%d",&a[i][j]);
	for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (i!=j) nxt[i].set(j);
	for (i=1;i<=m;++i)
	{
		for (j=1;j<=n;++j) w[j]=pi(a[i][j],j); bitset <N> tmp;
		for (sort(w+1,w+n+1),j=k=n;j>=1;--j)
		{
			while (k>j&&w[k].first>w[j].first) tmp.set(w[k--].second);
			nxt[w[j].second]&=tmp;
		}
	}
	//for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (i!=j&&nxt[i].test(j)) printf("%d %d\n",i,j);
	for (memset(f,-1,sizeof(f)),i=1;i<=n;++i) ans=max(ans,DP(i));
	return printf("%lld",ans),0;
}

F. Fading into Fog

TMD看了半天最后发现EPS设小了苦路西

首先很容易发现我们先问一发\(x=0,y=0\)这两条直线，就可以得出所有点的\(x,y\)坐标，现在的问题就是要在这\(n^2\)种可能的选法中找出正确的\(n\)对

然后由于题目没给出询问的上限而是很暧昧地说要最小化询问次数，因此没想到只要三次询问就行了

其实正解的思路很简单，我们考虑再问一条直线，使得之前得到的\(n^2\)个点可以不重复的投影在上面即可

观察到题目的性质，最终答案的每个点之间的横纵坐标差值都大于\(1\)，且横纵坐标的绝对值小于等于\(100\)

因此任意两点间的斜率其实就大于等于\(\frac{1}{200}\)，因此我们直接用直线\(y=\frac{1}{201}x\)来投影即可

不过要注意由于输出的时候要满足\(|a|,|b|\le 100\)，因此要变形成\(\frac{1}{3}x-\frac{201}{3}y=0\)输出

点到直线的投影可以拷板子，不过这题由于直线的方程已经固定了，因此点\((x,y)\)在\(y=\frac{1}{201}x\)上投影的横坐标即为\(\frac{201x+y}{201+\frac{1}{201}}\)

注意一下精度问题，总复杂度\(O(n^3)\)

#include<cstdio>
#include<iostream>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
const int N=30;
const double EPS=1e-3;
int t,n; double x[N],y[N],px[N],ansx[N],ansy[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k; scanf("%d",&n); double tmp; int cnt=0;
		for (printf("? 0 1 0\n"),fflush(stdout),i=1;i<=n;++i)
		scanf("%lf%lf",&x[i],&tmp);
		for (printf("? 1 0 0\n"),fflush(stdout),i=1;i<=n;++i)
		scanf("%lf%lf",&tmp,&y[i]);
		for (printf("? %lf %lf 0\n",1.0/3,-201.0/3),fflush(stdout),i=1;i<=n;++i)
		scanf("%lf%lf",&px[i],&tmp);
		for (i=1;i<=n;++i) for (j=1;j<=n;++j) for (k=1;k<=n;++k)
		if (fabs((x[i]*201+y[j])/(1.0/201+201)-px[k])<EPS) { ++cnt; ansx[cnt]=x[i]; ansy[cnt]=y[j]; break; }
		for (printf("! "),i=1;i<=cnt;++i)
		printf("%.8lf %.8lf%c",ansx[i],ansy[i]," \n"[i==cnt]); fflush(stdout);
	}
	return 0;
}