Preface

好久没有和队友一起打比赛了，然后今天纯战犯，G一个初值设错WA了三发还卡了1h，最后冲D也因为细节原因没调出来

但这场现场的榜只能用惨淡来形容，6题就稳Au了，而且感觉如果最后能出7个题的话甚至能有出线机会？看来还是前面题目区分度太小了

A. Best Player

签到题，按题意模拟即可

#include<cstdio>
#include<iostream>
#include<set>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=105;
int n,p[N][3],ans=-1,cs;
inline int solve(CI axis)
{
	set <pi> rst; for (RI i=1;i<=n;++i)
	{
		pi it; if (axis==0) it=pi(p[i][1],p[i][2]);
		else if (axis==1) it=pi(p[i][0],p[i][2]);
		else it=pi(p[i][0],p[i][1]); rst.insert(it);
	}
	return rst.size();
}
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
	for (j=0;j<3;++j) scanf("%d",&p[i][j]);
	for (i=0;i<3;++i)
	{
		int tmp=solve(i); if (tmp>ans) ans=tmp,cs=i;
	}
	return putchar('X'+cs),0;
}

B. The Great Wall

这题我们全队给了114514种假算法，后面终于发现正确的方向才过掉

注意到这题在每一段中取\(\max-\min\)的值，其实可以看作任意取一个数乘上系数\(1\)，再加上令一个数（可以和前面的相同）乘上系数\(-1\)，然后再求其最大值

这样转化后由于外层套的还是个求最大值，因此我们可以直接把内层的最大值去掉来做，这样就可以比较容易地DP转移了

设\(f_{i,j,0/1/2/3}\)表示已经处理了前\(i\)个数，且已经分了\(j\)段，此时第\(j\)段的状态为：

\(0\)：既没有选乘\(1\)的，也没有选乘\(-1\)的
\(1\)：没有选乘\(1\)的，但选了乘\(-1\)的
\(2\)：选了乘\(1\)的，但没有选乘\(-1\)的
\(3\)：选了乘\(1\)的，也选了乘\(-1\)的

这样就得到一个状态数为\(O(n^2)\)，转移为\(O(1)\)的DP了，可以卡过此题

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e4+5;
const int INF = 1e18+7;
int n, A[N];
int dp[2][N][4];

signed main(){
	// freopen("1.in", "r", stdin);
	scanf("%lld", &n);
	for (int i=1; i<=n; ++i) scanf("%lld", &A[i]);
	for (int k=0; k<4; ++k){
		for (int j=0; j<=n; ++j) dp[1][j][k]=dp[0][j][k]=-INF; 
	}dp[0][0][0]=dp[0][0][3]=0;
	for (int i=1; i<=n; ++i){
		for (int j=i; j>0; --j){
			int mx=0;
			int cur=(i&1), lst=(cur^1);
			mx = dp[lst][j-1][3];
			for (int k=0; k<4; ++k) dp[cur][j][k]=-INF;
			dp[cur][j][0]=max({mx, dp[lst][j][0]});
			dp[cur][j][1]=max({mx-A[i], dp[lst][j][0]-A[i], dp[lst][j][1]});
			dp[cur][j][2]=max({mx+A[i], dp[lst][j][0]+A[i], dp[lst][j][2]});
		//	printf("i=%d j=%d %d %d %d %d %d\n", i, j, mx, dp[lst][j][0], dp[lst][j][1]+A[i], dp[lst][j][2]-A[i], dp[lst][j][3]);
			dp[cur][j][3]=max({mx, dp[lst][j][0], dp[lst][j][1]+A[i], dp[lst][j][2]-A[i], dp[lst][j][3]});
			//for (int k=0; k<4; ++k) printf("dp[%d][%d][%d]=%d\n", i, j, k, dp[cur][j][k]);
		}
	}
	for (int i=1; i<=n; ++i) printf("%lld\n", dp[n&1][i][3]);
	return 0;	
}

C. Lucky Sequence

计数题，撤退

D. Farm

思路并不难想的一个图论题，但细节还是挺多的

考虑把带有限制关系的边称为special的，我们用类似于克鲁斯卡尔求MST的过程，用并查集维护点之间的连通关系

我们可以先对于所有的special的边，将其对应两点合并

然后再对剩下的集合关系，用非special的边跑一边克鲁斯卡尔，不难发现此时选中的边一定在最后的答案中

接下来只把上面选中的边选上得到一个新图，注意到新图中连通块的数量是\(O(q)\)级别的

那么所有没选中的边其实归根到底只有\(O(q^2)\)种有意义的取值，我们把这些边保留存入集合\(E'\)中

最后来个\(O(2^q)\)枚举每个限制的情形，第\(i\)位上为\(0\)则表示钦定第\(u_i\)条边加入图中，为\(1\)则表示钦定第\(v_i\)条边加入图中

当然这样处理完强制加入的边后图可能还不连通，因此就需要对\(E'\)中的边再跑一次克鲁斯卡尔算法来使得图连通

总复杂度\(O(m\log m+2^q\times q^2)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
typedef pair <int,int> pi;
struct edge
{
	int x,y,z;
	friend inline bool operator < (const edge& A,const edge& B)
	{
		return A.z<B.z;
	}
}; int n,m,q,ans,x[N],y[N],z[N],u[N],v[N],sp[N],fa[N],bel[N],rst[N],vis[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void merge(CI x,CI y)
{
	fa[getfa(x)]=getfa(y);
}
int main()
{
	//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%d",&x[i],&y[i],&z[i]);
	for (i=1;i<=n;++i) fa[i]=i;
	for (i=1;i<=m;++i) merge(x[i],y[i]);
	for (i=2;i<=n;++i) if (getfa(i)!=getfa(1)) return puts("-1"),0;
	for (scanf("%d",&q),i=0;i<q;++i)
	scanf("%d%d",&u[i],&v[i]),sp[u[i]]=sp[v[i]]=1;
	for (i=1;i<=n;++i) fa[i]=i; vector <edge> E;
	for (i=1;i<=m;++i) if (sp[i]) merge(x[i],y[i]);
	else E.push_back((edge){x[i],y[i],z[i]});
	sort(E.begin(),E.end()); vector <edge> cs;
	for (auto [x,y,z]:E)
	{
		if (getfa(x)==getfa(y)) continue;
		cs.push_back((edge){x,y,z}); merge(x,y); ans+=z;
	}
	for (i=1;i<=n;++i) fa[i]=i;
	for (auto [x,y,z]:cs) merge(x,y);
	int idx=0; for (i=1;i<=n;++i)
	{
		int tmp=getfa(i); if (!rst[tmp]) rst[tmp]=++idx; bel[i]=rst[tmp];
	}
	map <pi,int> mp; vector <edge> left;
	for (i=1;i<=m;++i) if (bel[x[i]]!=bel[y[i]])
	{
		int a=bel[x[i]],b=bel[y[i]];
		if (!mp[pi(a,b)]) mp[pi(a,b)]=z[i];
		else mp[pi(a,b)]=min(mp[pi(a,b)],z[i]);
	}
	for (auto [it,val]:mp)
	left.push_back((edge){it.first,it.second,val});
	sort(left.begin(),left.end());
	int ret=1e9; for (i=0;i<(1<<q);++i)
	{
		for (j=1;j<=idx;++j) fa[j]=j; int cur=0;
		for (j=0;j<q;++j) vis[u[j]]=vis[v[j]]=0;
		for (j=0;j<q;++j) if ((i>>j)&1)
		{
			if (!vis[v[j]]) cur+=z[v[j]],vis[v[j]]=1; merge(bel[x[v[j]]],bel[y[v[j]]]);
		} else
		{
			if (!vis[u[j]]) cur+=z[u[j]],vis[u[j]]=1; merge(bel[x[u[j]]],bel[y[u[j]]]);
		}
		for (auto [x,y,z]:left)
		{
			if (getfa(x)==getfa(y)) continue; merge(x,y); cur+=z;
		}
		ret=min(ret,cur);
	}
	return printf("%d",ans+ret),0;
}

E. Isomerism

什么化学阅读理解题，反正我高中选考没选化学，全靠徐神秒了

#include <bits/stdc++.h>

int T;

std::map<std::string, int> pri;

int main() {
	std::ios::sync_with_stdio(false);
	pri["-F"] = 1;
	pri["-Cl"] = 2;
	pri["-Br"] = 3;
	pri["-I"] = 4;
	pri["-CH3"] = 5;
	pri["-CH2CH3"] = 6;
	pri["-CH2CH2CH3"] = 7;
	pri["-H"] = 8;
	int T; std::cin >> T; while(T--) {
		std::string R1, R2, R3, R4;
		std::cin >> R1 >> R2 >> R3 >> R4;
		if(R1 == R3 || R2 == R4) std::cout << "None\n";
		else if(R1 == R2 || R3 == R4)
			std::cout << "Cis\n";
		else if(R1 == R4 || R2 == R3)
			std::cout << "Trans\n";
		else if(pri[R1] < pri[R3] && pri[R2] < pri[R4] || pri[R1] > pri[R3] && pri[R2] > pri[R4])
			std::cout << "Zasamman\n";
		else std::cout << "Entgegen\n";
	}
	return 0;
}

F. Maximize the Ratio

好神的几何题，祁神对着jiangly的题解研究了很久，反正我是一点做不来

G. Photograph

本来我是不会这个题的，但徐神告诉我链表后我马上就想到了关键，然后就会了

这题其实修改操作啥的都可以模拟，而维护贡献的过程显然可以用set维护前驱后继来做，但这样\(10^7\)再带个\(\log\)显然是跑不过\(1s\)的时限的

考虑去掉\(\log\)，这题的一个最好的性质就是我们是知道当\(n\)次操作后的最终状态的，因此不妨考虑从后往前倒着做

每次删除一个数并求前驱后继很显然可以用双向链表来维护，这样就把\(\log\)去掉了

总复杂度\(O(nq)\)

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=100005;
int n,q,h[N],p[N],tmp[N],L[N],R[N],k,all;
inline LL solve(LL ret=0)
{
	RI i; for (i=1;i<=n;++i) L[i]=i-1,R[i]=i+1; R[0]=1; L[n+1]=n;
	LL cur=all; for (ret=cur,i=n;i>1;--i)
	{
		int now=p[i],pre=L[now],nxt=R[now];
		if (pre!=0) cur-=1LL*(h[now]-h[pre])*(h[now]-h[pre]);
		if (nxt!=n+1) cur-=1LL*(h[now]-h[nxt])*(h[now]-h[nxt]);
		if (pre!=0&&nxt!=n+1) cur+=1LL*(h[pre]-h[nxt])*(h[pre]-h[nxt]);
		R[pre]=nxt; L[nxt]=pre; ret+=cur;
	}
	return ret;
}
signed main()
{
	// freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	RI i; for (scanf("%lld%lld",&n,&q),i=1;i<=n;++i) scanf("%lld",&h[i]);
	for (i=1;i<=n;++i) scanf("%lld",&p[i]);
	for (i=1;i<n;++i) all+=1LL*(h[i]-h[i+1])*(h[i]-h[i+1]);
	LL ans=solve(); printf("%lld\n",ans);
	while (q--)
	{
		scanf("%lld",&k); k=(ans+k)%n;
		for (i=1;i<=n;++i) tmp[i]=p[(i+k-1)%n+1];
		for (i=1;i<=n;++i) p[i]=tmp[i];
		//for (i=1;i<=n;++i) printf("%d%c",p[i]," \n"[i==n]);
		ans=solve(); printf("%lld\n",ans);
	}
	return 0;
}

H. Absolute Space

神仙题，题目都没看

I. The Answer!

看jiangly的博客就知道这题肯定是这场的防AK题了

J. Let's Play Jigsaw Puzzles!

签到题，直接爆搜一下就好了

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int n,d[N*N][4],a[N][N];
inline void DFS(CI num,CI x,CI y)
{
	if (a[x][y]) return; a[x][y]=num;
	for (RI i=0;i<4;++i) if (d[num][i]!=-1)
	DFS(d[num][i],x+dx[i],y+dy[i]);
}
int main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	RI i,j; int st; for (scanf("%d",&n),i=1;i<=n*n;++i)
	{
		for (j=0;j<4;++j) scanf("%d",&d[i][j]);
		if (d[i][0]==-1&&d[i][2]==-1) st=i;
	}
	for (DFS(st,1,1),i=1;i<=n;++i)
	for (j=1;j<=n;++j) printf("%d%c",a[i][j]," \n"[j==n]);
	return 0;
}

K. Browser Games

徐神写的字符串，我题目都没看来着

#include <bits/stdc++.h>

constexpr int $n = 2.5e6 + 5;

int go[$n][28], siz[$n], O = 1, pa[$n];

int insert(std::string &s) {
	int now = 1;
	for(char c: s) {
		int u;
		if(c == '.') u = 26; else if(c == '/') u = 27;
		else u = c - 'a';
		if(!go[now][u]) go[now][u] = ++O, pa[go[now][u]] = now;
		now = go[now][u];
		siz[now] += 1;
	}
	return now;
}

int ue[$n], cur[$n], fa[$n];

int father(int i) {
	if(i == fa[i]) return i;
	return fa[i] = father(fa[i]);
}

int main() {
	// freopen("K.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	int n; std::cin >> n;	
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= n; ++i) {
		std::string s; std::cin >> s;
		ue[i] = insert(s);
		cur[ ue[i] ] = i;
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		ans += 1;
		int s = ue[i];
		auto unionn = [&ans] (int a, int b) {
			if(!a) return b; if(!b) return a;
			a = father(a), b = father(b);
			if(a != b) fa[b] = a, ans -= 1;
			return a;
		};
		while(s > 1) {
			siz[s] -= 1;
			if(siz[s] == 0) for(int ch: go[s]) if(ch && siz[ch] == 0)
				cur[s] = unionn(cur[s], cur[ch]);
			s = pa[s];
		}
		std::cout << ans << char(10);
	}
	for(int i = 1; i <= O; ++i) if(siz[i]) perror("Wcao\n");
	return 0;
}

L. Sheep Village

好，又是不会的一题

M. Tower of the Sorcerer

好劲的题啊，看了好久的jiangly博客才会做，然后还被卡了精度把double改成叉积才跑过

首先要想到最优方案的形式，一定是先不断提示自己的攻击力直到最高，然后再去杀其它的怪

因此不妨假设所有怪都是最后被杀掉的，然后考虑最小化从初始状态到最后所掉的血量

令\(f_i\)表示当前攻击力为\(i\)时，最少需要额外收到多少伤害才能把攻击力变成最大值

转移的话考虑倒推，对于攻击力为\(j(j>i)\)的怪物，设其血量为\(hp_j\)，则转移为：

\[f_i=\min_{j>i} (f_j+(\lceil\frac{hp_j}{i}\rceil-\lceil\frac{hp_j}{maxatk}\rceil)\times j) \]

乍一看这个转移很难优化，但有个很妙的trick就是我们直接枚举\(k=\lceil\frac{hp_j}{i}\rceil\)，然后化一下后面的部分就发现我们要最小化\(k\times j+f_j-\lceil\frac{hp_j}{maxatk}\rceil\times j\)的值

不妨把\(hp_j\)看作版本号，\(j,\lceil\frac{hp_j}{maxatk}\rceil\times j\)看作一条直线的斜率和截距，那么我们查询时就是要求\(hp_j\le i\times k\)的版本中，当横坐标为\(k-1\)时，该版本中直线的纵坐标的最小值

这个就是个经典的Convex Trick，直接维护一个上凸壳然后二分查询即可，至于版本号由于这里只有前缀查询，可以给以版本号为下标用树状数组维护凸壳

总复杂度\(O(n\log^3 n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const LL N=100005,INF=1e18;
int n,mxhp,mxatk,satk,atk[N],hp[N],f[N]; vector <int> v[N];
struct Line
{
	int k,b;
	inline Line(CI K=0,CI B=0)
	{
		k=K; b=B;
	}
	inline LL get(CI x)
	{
		return 1LL*k*x+b;
	}
	friend inline Line operator - (const Line& A,const Line& B)
	{
		return Line(A.k-B.k,A.b-B.b);
	}
};
inline int Cross(const Line& A,const Line& B)
{
	return A.k*B.b-A.b*B.k;
}
struct Convex
{
	vector <Line> stk;
	inline void insert(const Line& L)
	{
		while (stk.size()>1&&Cross(stk.back()-stk[stk.size()-2],L-stk.back())>=0) stk.pop_back(); stk.push_back(L);
	}
	inline LL query(CI x)
	{
		if (stk.empty()) return INF;
		int l=0,r=stk.size()-1,mid; while (l<r)
		{
			mid=l+r>>1; if (stk[mid].get(x)<stk[mid+1].get(x)) r=mid; else l=mid+1;
		}
		return stk[l].get(x);
	}
};
class Tree_Array
{
	private:
		Convex t[N];
	public:
		#define lowbit(x) (x&-x)
		inline void add(RI x,const Line& L)
		{
			for (;x<=mxhp;x+=lowbit(x)) t[x].insert(L);
		}
		inline int get(RI x,CI y,int ret=INF)
		{
			for (;x;x-=lowbit(x)) ret=min(ret,t[x].query(y)); return ret;
		}
		#undef lowbit
}BIT;
signed main()
{
	//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
	RI i,j; for (scanf("%lld%lld",&n,&satk),i=1;i<=n;++i)
	scanf("%lld%lld",&atk[i],&hp[i]),v[atk[i]].push_back(hp[i]);
	mxatk=max(satk,*max_element(atk+1,atk+n+1));
	mxhp=*max_element(hp+1,hp+n+1); int ans=0;
	for (i=1;i<=n;++i) ans+=(hp[i]-1)/mxatk*atk[i];
	for (i=1;i<mxatk;++i) f[i]=INF;
	for (i=mxatk;i>=1;--i)
	{
		for (j=1;;++j)
		{
			f[i]=min(f[i],BIT.get(min(i*j,mxhp),j-1));
			if (i*j>mxhp) break;
		}
		for (auto x:v[i]) BIT.add(x,Line(i,f[i]-(x-1)/mxatk*i));
	}
	return printf("%lld",ans+f[satk]),0;
}