2022 CCPC 桂林训练

十月最后一场训练赛，成功花了两个小时做出来我校去参赛队伍五个小时的罚时。

参赛人数 $2$ 参赛时间 $3$ 小时（其实过了 $4$ 题之后就在摆了），大概参赛的话能混个 Cu ,有希望 Ag 吧

$\text{\color{red} O\color{black}ctober}$ 大神狂切题大显神威，$\text{\color{grey}scmmm}$ 大菜鸡尽显菜鸡本色。

本菜鸡就做了两道题，神仙怒d：”我有你这个时间可以做两百道题“

E Draw a triangle

上帝视角来看， A 得第四多的题，可以算铜牌题？

题目是给你三角形得两个点 $(a_1,b_1),(a_2,b_2)$，求你找出来第三个点，使得三角形面积最小，并且这个点一定得是整数点。

我们先考虑平行或者垂直于 $x$ 轴的情况，显然这个时候最小面积是当前两点长度乘以二分之一 ，答案点是$(a_1+1,b_1)$ 或者 $(a_1,b_1+1)$

否则，我们记两个点组成的线段斜率为$k$ ，如果 $k$ 是个整数，答案依然是$(a_1+1,b_1)$ 或者 $(a_1,b_1+1)$ ，考虑这个三角形以这个线段为底，高最小就是 $\frac{1}{k}$

不然的话，假设当前斜率为 $k=\frac{c}{d}$ ，如果面积最小的话，我们肯定需要 $t*k=\frac{1}{d}+\phi$ ，$\phi$ 是一个整数

欸，这个写法好熟悉

$t *c \equiv 1 \pmod d$

用一个 $\text{exgcd}$ 即可

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int T;
	cin >> T;
	while(T -- ) {
		LL x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 > x2) {
			swap(x1, x2);
			swap(y1, y2);
		}
		if(x1 == x2) {
			cout << x1 + 1 << " " << y1 << "\n";
			continue; 
		} 
		if(y1 == y2) {
			cout << x1 << " " << y1 + 1 << "\n";
			continue;
		}
		function<LL(LL, LL)> gcd = [&](LL a, LL b) -> LL {
			return b ? gcd(b, a % b) : a;
		};
		function<LL(LL, LL, LL&, LL&)> Exgcd = [&](LL a, LL b, LL &x, LL &y) -> LL {
		  	if (!b) {
			    x = 1;
			    y = 0;
		    	return a;
		  	}	
		  	LL d = Exgcd(b, a % b, x, y);
		  	LL t = x;
		  	x = y;
		  	y = t - (a / b) * y;
			return d;
		};
		LL dx = abs(x1 - x2);
		LL dy = abs(y1 - y2);
        LL g = gcd(dx, dy);
		dx /= g;
		dy /= g;
		if(dx == 1) {
			cout << x1 << " " << y1 + 1 << "\n";
			continue;
		}
		int rev = 0;
		if(y2 < y1) {
			x1 = x2 + x2 - x1;
			rev = 1;
		}
		LL ddy=dy%dx;
		LL xx,yy;
		Exgcd(ddy,dx,xx,yy); 
        xx=((xx%dx)+dx)%dx; 
		LL anx = (xx) + min(x1, x2);
		if(rev) anx -= 2 * (anx - x2);
		LL any = (xx) * dy / dx + min(y1, y2) ;
		cout << anx << " " << any << "\n"; 
	}
	return 0;
}

J Permutation Puzzle

神曰：“圣哉$p_{u_i}<p_{v_i}$”

神再曰:“ $0$ 者，菜鸡写乎 ”

换句话说，对于我这个菜鸡，我需要在一个残缺的排列中（指有些数字是$0$ ,需要你填上数，满足上面的关系）

我们对于未知的两个数 $x,y$ ， 如果他们满足第一个条件 $p_x<p_y$ ，那我们记两个数最小的可能值为 $L_x,L_y$ ，最大值为 $R_x,R_y$

可以得到这两个东西：

$L_y>=L_x+1,R_x<=R_y-1$

我们可以利用一个拓扑排序，来得到所有数字的 $L_i,R_i$ 特别的，当 $p_i$ 已知，$L_i=R_i=a[i]$ 如果$L_i>R_i$ 那就说明无解。

问题就转化成了给你 $n$ 个区间，每个数字满足 $a_x \in [L_i,R_i]$ 询问是否有合法解。

那么我们先按照 $L_i$ 排序，考虑将 $pos$ 赋值给 $i$ ，那么 $i$ 需要满足 $L_i \leq pos $

那么贪心地给当前 $R$ 最小的 $pos$ 是否最优呢？

我想很显然，所以我咕了

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=2e5+20;

vector <int> G1[maxn],G2[maxn];
int ind[maxn],dni[maxn];
int L[maxn],R[maxn],a[maxn];
int n,m,T,usd[maxn];

struct que{
	int l,r,x;
	bool operator <(const que &b) const
	{
		if(l==b.l) return r<b.r;
		return l<b.l;
 	}
}qm[maxn];

int toposort()
{
	queue <int> q;
	int tot=0;
	for(int i=1;i<=n;i++) if(!ind[i]) q.push(i);
	while(!q.empty())
	{
		tot++;
		int t=q.front(); q.pop();
		if(a[t]&&L[t]!=a[t] ){cout<<-1<<endl; return 0;} 
		int sz=G1[t].size();
		for(int i=0;i<sz;i++)
		{
			int j=G1[t][i];
			ind[j]--;
			L[j]=max(L[t]+1,L[j]);
			if(!ind[j]) q.push(j); 
		}
	}
	if(tot!=n) {cout<<-1<<endl; return 0;} tot=0;
	for(int i=1;i<=n;i++) if(!dni[i]) q.push(i);
	while(!q.empty())
	{
		tot++;
		int t=q.front(); q.pop();
		int sz=G2[t].size();
		if(a[t]&&R[t]!=a[t])  {cout<<-1<<endl; return 0;}
		for(int i=0;i<sz;i++)
		{
			int j=G2[t][i];
			dni[j]--;
			R[j]=min(R[t]-1,R[j]);
			if(!dni[j]) q.push(j); 
		}
	}
	if(tot!=n) {cout<<-1<<endl; return 0;}
	priority_queue <que> qq;
	int cnt=0;
	for(int i=1;i<=n;i++) if(!a[i]) qm[++cnt]=que{L[i],R[i],i};
	for(int i=1;i<=n;i++) if(a[i]) usd[a[i]]=1;
	sort(qm+1,qm+cnt+1); 
	int pos=1;
	for(int i=1;i<=n;i++)
	if(!usd[i]){
		while(qm[pos].l<=i&&pos<=cnt) qq.push(que{-qm[pos].r,-qm[pos].l,qm[pos].x}),pos++;  
		if(qq.empty()) {cout<<"-1\n"; return 0;}
		int t=qq.top().x;
		if(R[t]<i||(L[t]>R[t])) {cout<<-1<<endl;return 0;}
		a[t]=i;
		qq.pop();
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		int t1,t2;
		for(int i=1;i<=n;i++)
		{
			usd[i]=0;
			L[i]=1,R[i]=n;
			ind[i]=dni[i]=0;
			G1[i].clear();
			G2[i].clear();
		}
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			if(a[i]) L[i]=R[i]=a[i];
		}
		for(int i=1;i<=m;i++) 
		{
			cin>>t1>>t2;
			G1[t1].push_back(t2);
			G2[t2].push_back(t1);
			ind[t2]++,dni[t1]++;
		}
		toposort();
	}
}