526互联

2023 United Kingdom and Ireland Programming Contest (UKIEPC 2023)

发布时间 2024-01-12 20:49:38作者: 空気力学の詩

Preface

最坐牢的一集，前3h狂出10题然后最后2h坐牢，祁神写J怒调2h最后喜提MLE

赛后我Rush了个H的做法常数太大又喜提TLE，评价是不如去写E题的模拟退火

A. Assessment Disruption

挺精巧的构造题，刚开始以为是构造数据不卡掉想歪了好久，后面仔细一想还是挺简单的

我们将原序列分成两块，前\(\frac{n}{2}\)个元素放的全是两两之间不能比较的，而后\(\frac{n}{2}\)个元素只要从小到大放上可比较的即可（要求后半部分的所有元素均大于前半部分）

不难发现这样每次只会在后半部分删除一个元素，因此保底有\(\frac{n}{2}\)轮

然后每一轮前\(\frac{n}{2}\)个数可以卡满比较次数，大致为\(\frac{n}{2}\times \frac{n}{2}\times \frac{1}{2}\)，因此总体来看可以做到\(\frac{n^3}{16}\)次比较，可以通过此题

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,m,W,w[N];
int main()
{
	RI i; for (scanf("%d%d",&n,&W),m=n>>1,i=1;i<=n;++i)
	if (W-i>=0) w[i]=W-i; else if (W+i<=10000) w[i]=W+i;
	for (i=1;i<=n-m;++i) printf("%d %d\n",w[m+i],i);
	for (i=1;i<=m;++i) printf("%d %d\n",w[m-i+1],n-m+i);
	return 0;
}

B. Boat Commuter

签到题，对于每张卡模拟一下即可（妈的这题刚开始看错题了WA了一发后红温了好久）

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,k,x,y,lst[N],ans[N];
int main()
{
	RI i,j; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=k;++i)
	{
		scanf("%d%d",&x,&y);
		if (lst[y]==0) lst[y]=x,ans[y]+=100; else
		{
			ans[y]+=abs(x-lst[y]);
			if (x!=lst[y]) ans[y]-=100; lst[y]=0;
		}
	}
	for (i=1;i<=m;++i) printf("%d ",ans[i]);
	return 0;
}

C. Clearing Space

ORZ祁神秒了此题

注意到我们可以先枚举钦定一个点强制选，然后从这个点向后可以设计一个DP状态

\(f_{i,j}\)表示向后考虑了\(i\)个点，其中一共选了\(j\)个点时得到的最大面积，转移的话枚举下上次选的是哪个点即可

总复杂度\(O(n^4)\)，因为常数极小因此可以跑过

#include<bits/stdc++.h>
#define LD long double
using namespace std;
const LD eps = 1e-8;
int sgn(LD x){return (fabs(x)<=eps ? 0 : (x>eps ? 1 : -1));}

const int N = 105;
struct Pt{
	LD x, y;
//	Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
//	Pt operator+(Pt b)const{return Pt{x-b.x, y-b.y};}
	LD crs(Pt b)const{return x*b.y-y*b.x;}
}pt[N];

const LD R = 1000;
const LD PI = acos(-1.0L);
int n, p;
LD A[N];
LD dp[N][N];
signed main(){
	cout << setiosflags(ios::fixed) << setprecision(10);
	cin >> n;
	cin >> p;
	for (int i=0; i<n; ++i){
		cin >> A[i];
		pt[i].x = R*cos(1.0L*A[i]/180*PI);
		pt[i].y = R*sin(1.0L*A[i]/180*PI);
	}
	
	LD ans = 0.0L;
	for (int x=0; x<n; ++x){
		dp[0][0] = 0;
		for (int i=1; i<=n; ++i){
			for (int k=1; k<=min(i, p); ++k){
				dp[i][k] = 0.0L;
				for (int j=k-1; j<i; ++j){
					dp[i][k] = 	max(dp[i][k], dp[j][k-1] + pt[(x+j)%n].crs(pt[(x+i)%n]));
				}
			}
		}
		ans = max(ans, dp[n][p]);
	}
	cout << ans*0.5L << endl;
	return 0;
}

D. Delivery Forces

签到，不难发现最优策略就是拿一个最小值和两个最大值配对

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,a[N]; long long ans;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	RI i,j; for (cin>>n,i=1;i<=n;++i) cin>>a[i];
	for (sort(a+1,a+n+1),i=1,j=n-1;i<=n/3;++i,j-=2) ans+=a[j];
	return printf("%lld",ans),0;
}

E. Enchanted Fortress

比赛的时候徐神提出了很多乱搞做法，但由于机时没有去写

后面看题解发现是个meet in middle或者退火，但都没想清楚怎么写，先坑着

F. Fast Forward

被徐神一眼秒了的题

首先可以用双指针求出每首歌后面第一次插入广告的位置

不难发现这个东西可以套个倍增在外面，表示插入\(2^j\)个广告后的位置，然后就做完了

#include <bits/stdc++.h>

using llsi = long long signed int;

constexpr int $n = 2000000 + 10;

int n, c;
int d[$n];
int nxt[$n][21];

int main(void) {
    std::ios::sync_with_stdio(false);
	std::cin >> n >> c;
	for(int i = 1; i <= n; ++i) std::cin >> d[i], d[i + n] = d[i];
	
	{
		int sum = 0;
		for(int i = 1; i <= n; ++i) sum += d[i];
		if(sum <= c) {
			for(int i = 1; i <= n; ++i) std::cout << '0' << char(i == n ? 10 : 32);
			return 0;
		}
	}
	
	int l = 1, r = 1, sum = 0, dn = n << 1;
	while(l <= dn) {
		while(r <= dn && sum < c) sum += d[r++];
		nxt[l][0] = r;
		sum -= d[l++];
	}
	
	for(int j = 0; j <= 20; ++j) nxt[dn + 1][j] = dn + 1;
	
	for(int i = dn; i; --i) for(int j = 1; j <= 20; ++j)
		nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
	
	for(int i = 1; i <= n; ++i) {
		int cur = i, ans = 0;
		for(int j = 20; j >= 0; --j) {
			if(nxt[cur][j] - i < n) {
				ans |= 1 << j;
				cur = nxt[cur][j];
			}
		}
		std::cout << ans << char(i == n ? 10 : 32);
	} 
	return 0;
}

G. Glacier Travel

又又又又又又被徐神秒了的题

首先当两点在同一线段上移动时显然不是最小值，因此我们总可以拆出两点在不同线段上移动的情况

注意到此时两者之间的距离关于时间是单峰函数，因此可以三分求最小值（证明的话考虑用速度的合成，问题等价于一条直线到某个点的距离，这个显然是单峰的）

但实际写起来感觉细节很多，但徐神好像没一会就写完一遍过了

#include <bits/stdc++.h>

using real = long double;

struct vivi {
	real x, y;
	
	inline vivi(real x = 0.0L, real y = 0.0L): x(x), y(y) {}
	inline vivi operator +(const vivi &b) const { return vivi {x + b.x, y + b.y}; }
	inline vivi operator -(const vivi &b) const { return vivi {x - b.x, y - b.y}; }
	inline vivi operator *(const real &b) const { return vivi {x * b, y * b}; }
	
	inline real len2() const { return x * x + y * y; }
	inline real len() const { return std::sqrt(x * x + y * y); }
	inline real dist(const vivi &b) const { return (*this - b).len(); }
	
	inline friend std::istream& operator >> (std::istream& in, vivi &v) {
		return in >> v.x >> v.y;
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(10);
	int n; real s;
	std::cin >> s >> n;
	std::vector<vivi> p(n);
	for(auto &[x, y]: p) std::cin >> x >> y;
	
	auto res = [&] (size_t st, real offset) {
		return (p[st + 1] - p[st]).len() - offset;		
	};
	
	auto fwd = [&] (size_t st, real offset) {
		auto ll = (p[st + 1] - p[st]).len();
		return p[st] + (p[st + 1] - p[st]) * (offset / ll);
	};
	
	size_t as = 0, bs = 0;
	real   af = 0.0L, bf = 0.0L;
	
	while(as < n - 1) {
		real r = res(as, af);
		if(s > r) {
			s -= r;
			as += 1;
			af = 0;
		} else {
			af = s;
			break;
		}
	}
	
	if(as == n - 1) {
		std::cout << (p.back() - p.front()).len() << char(10);
		return 0;
	}
	
	real ans = 1e30L;

	while(as < n - 1) {
		// std::cerr << as << ' ' << af << ' ' << bs << ' ' << bf << char(10);
		real ar = res(as, af), br = res(bs, bf);
		real l = 0, r = std::min(ar, br);
		while(r - l > 1e-8) {
			real m1 = (l + l + r) / 3, m2 = (l + r + r) / 3;
			vivi ap1 = fwd(as, af + m1);
			vivi ap2 = fwd(as, af + m2);
			vivi bp1 = fwd(bs, bf + m1);
			vivi bp2 = fwd(bs, bf + m2);
			if((ap1 - bp1).len() < (ap2 - bp2).len()) r = m2;
			else                                     l = m1;
		}
		vivi ap = fwd(as, af + l);
		vivi bp = fwd(bs, bf + l);
		ans = std::min(+ans, real((ap - bp).len()));
		if(ar < br) {
			bf += ar;
			as += 1;
			af = 0;
		} else {
			af += br;
			bs += 1;
			bf = 0;
		}
	}
	
	std::cout << ans << char(10);
	return 0;	
}

H. History in Numbers

很裸的一个线段树维护奇奇怪怪的东西的题，但我的写法好像常数太大了就是跑不过

不妨用线段树来维护一个区间内所有有用的信息，朴素的想法是要维护以下三者：

  • 该区间是否合法
  • 该区间在去重后得到的序列
  • 该区间在去重后所有minimum元素构成的序列

但稍作思考我们会发现后两者完全不需要知道整个序列的值，只需要知道至多左边两个、右边两个元素的值即可

因此这题的难点就在于合并区间，耐心讨论下即可，最后修改套个Lazy Tag即可

估计可能是我操作的时候全部大力用vector来搞了因此常数巨大，但后面换了deque后又喜提MLE直接给我整不会了

这里扔一份能过对拍正确性没问题的代码供参考

#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=300005,INF=1e18;
int n,a[N],m;
class Segment_Tree
{
	private:
		struct segment
		{
			bool ok; int tag; vector <int> num,mi;
			inline void init(void)
			{
				ok=1; tag=0; num.clear(); mi.clear();
			}
			friend inline segment operator + (segment A,segment B)
			{
				segment C; C.init(); C.ok=A.ok&&B.ok;
				if (!C.ok) return C;
				int LL=A.num.size()>1?A.num[A.num.size()-2]:INF;
				int RR=B.num.size()>1?B.num[1]:INF;
				int L=A.num.back(),R=B.num[0];
				if (L==R)
				{
					if (LL==INF&&RR==INF)
					{
						C.num.push_back(L); return C;
					}
					B.num.erase(B.num.begin());
					if (B.mi.size()&&B.mi[0]==R) B.mi.erase(B.mi.begin());
					if (L<LL&&L<RR)
					{
						if (A.mi.empty()||A.mi.back()!=L) A.mi.push_back(L);
					}
				} else
				{
					if (A.mi.empty()||A.mi.back()!=L)
					{
						if (L<LL&&L<R)
						{
							A.mi.push_back(L);
							if (A.mi.size()>=2&&A.mi[A.mi.size()-2]>=A.mi.back()) C.ok=0;
						}
					} else
					{
						if (!(L<LL&&L<R)) A.mi.pop_back();
					}
					if (B.mi.empty()||B.mi[0]!=R)
					{
						if (R<L&&R<RR)
						{
							B.mi.insert(B.mi.begin(),R);
							if (B.mi.size()>=2&&B.mi[0]>=B.mi[1]) C.ok=0;
						}
					} else
					{
						if (!(R<L&&R<RR)) B.mi.erase(B.mi.begin());
					}
				}
				if (A.mi.size()&&B.mi.size()&&A.mi.back()>=B.mi[0]) C.ok=0;
				if (!C.ok) return C;
				auto merge=[&](vector <int> A,vector <int> B)
				{
					vector <int> vec;
					for (auto x:A) vec.push_back(x);
					for (auto x:B) vec.push_back(x);
					if (vec.size()<=4) return vec;
					vector <int> nvec;
					nvec.push_back(vec[0]); nvec.push_back(vec[1]);
					nvec.push_back(vec[vec.size()-2]); nvec.push_back(vec.back());
					return nvec; 
				};
				C.num=merge(A.num,B.num); C.mi=merge(A.mi,B.mi);
				return C;
			}
		}O[N<<2];
		inline void pushup(CI now)
		{
			O[now]=O[now<<1]+O[now<<1|1];
		}
		inline void apply(CI now,CI mv)
		{
			O[now].tag+=mv;
			for (auto& x:O[now].num) x+=mv;
			for (auto& x:O[now].mi) x+=mv;
		}
		inline void pushdown(CI now)
		{
			if (O[now].tag) apply(now<<1,O[now].tag),apply(now<<1|1,O[now].tag),O[now].tag=0;
		}
	public:
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			if (l==r)
			{
				O[now].init(); O[now].num.push_back(a[l]); return;
			}
			int mid=l+r>>1; build(LS); build(RS); pushup(now);
		}
		inline void modify(CI beg,CI end,CI mv,TN)
		{
			if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
			if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS); pushup(now);
		}
		inline segment query(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end)	return O[now]; int mid=l+r>>1; pushdown(now);
			if (end<=mid) return query(beg,end,LS);
			if (beg>mid) return query(beg,end,RS);
			return query(beg,mid,LS)+query(mid+1,end,RS);
		}
		inline bool Query(CI l,CI r)
		{
			return query(l,r).ok;
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
signed main()
{
	//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	RI i; for (cin>>n,i=1;i<=n;++i) cin>>a[i];
	for (SEG.build(),cin>>m,i=1;i<=m;++i)
	{
		string opt; int l,r,x; cin>>opt>>l>>r;
		if (opt=="check") cout<<(SEG.Query(l,r)?"YES":"NO")<<endl;
		else cin>>x,SEG.modify(l,r,x);
	}
	return 0;
}

I. International Travel

疑似又是个几何题，但过的人极少鉴定为做不了一点

J. Journey of Recovery

祁神被这题狠狠地腐乳了，比赛时没想清楚去写了个复杂的单调队列做法，后面发现直接建图DFS就行了

这题大致思路就是按照地点画出一些轴，然后每个航班可以看作轴上的一些点，同时将同一个轴上的点按时间顺序排列，并将同一个轴上的相邻的点之间也连上边，在上面跑DFS即可

具体代码留着祁神填坑

K. Kernel Scheduler

思博题，徐神刚开始提了很多繁琐的做法

后面我被B搞红温后仔细想了下发现是个经典trick，我们不妨把图中的边分为两类

  • \(u\to v\and u<v\)，称为A类边
  • \(u\to v\and u>v\)，称为B类边

不难发现若仅保留A,B类边的一种则得到的图一定无环，因此保留数量较多的一类边即可

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	int n, m; std::cin >> n >> m;
	std::vector<int> e1, e2;
	for(int i = 0, f, t; i < m; ++i) {
		std::cin >> f >> t;
		(f > t ? &e1 : &e2)->push_back(i);
	}
	std::vector<int> *e = (e1.size() > e2.size() ? &e1 : &e2);
	std::cout << "YES\n" << e->size() << char(10);
	for(size_t i = 0; i < e->size(); ++i)
		std::cout << (*e)[i] + 1 << char(i == e->size() ? 10 : 32);
	return 0;
}

L. Last One Standing

祁神写的一个Easy题，我连题目都没看

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

signed main(){
	int h1, d1, t1; cin >> h1 >> d1 >> t1;
	int h2, d2, t2; cin >> h2 >> d2 >> t2;
	int T1 = (h1 + d2-1)/d2*t2 -t2, T2 = (h2 + d1-1)/d1*t1 -t1;
	if (T1 > T2) cout << "player one\n";
	else if (T1 < T2) cout << "player two\n";
	else cout << "draw\n";
	return 0;	
}

M. Mini-Tetris 3023

签到讨论题，不难发现拿两个Corner可以和所有的S-tile拼成矩形，然后多余的Corner两两配对即可

#include <bits/stdc++.h>

int main(void) {
	int a, b, c;
	std::cin >> a >> b >> c;
	std::swap(b, c);
	int ans = a << 1;
	if(b >= 2) {
		ans += (c << 1) + 3;
		ans += (b - 2 >> 1) * 3;
	}
	std::cout << ans << char(10);
	return 0;
}

N. Naming Wine Bottles

签到题，先给每种瓶子分配一个整形编号，然后把这个编号转化成\(26\)进制的数即可保证命名的唯一性

#include<bits/stdc++.h>
#define LD long double
using namespace std;
const int N = 1e4+5;

int n;
LD A[N];
int idx=0;

string calc(int x){
	string str;
	while (x>0){
		str += 'a'+x%26;
		x/=26;
	}
	return str;
}

signed main(){
	map<LD, int> mp;
	string str("a");
	scanf("%d", &n);
	for (int i=1; i<=n; ++i){
		scanf("%LfL", &A[i]);
		if (!mp.count(A[i])) mp[A[i]] = ++idx;
	}
	for (int i=1; i<=n; ++i) cout << calc(mp[A[i]]) << '\n';
	return 0;	
}

Postscript

感觉今天没啥存在感啊，被徐神和祁神带飞了