2021ICPC亞洲區域賽（昆明）複盤

Wogua_boy

I.Mr. Main and Windmills（計算幾何）

題意：

Mr.Main坐火車從s到t，經過了許多風車。

火車在一條直線上行駛。

随着火車的行駛，風車在Mr.Main的視野裡會發生位置相對變化。

現在給出風車們的坐标，請你找到當第h個風車與其他風車的相對位置變化k次時火車所在的坐标。

題解：

觀察後發現，隻需要取風車坐标兩兩之間直線和s到t線段的交點然後排序就好了。

比賽的時候因為天生對計算幾何的恐懼直接扔給隊友了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const double eps=1e-8;
int n,m;
double xs,ys,xt,yt; 
int sgn (double x) {
	if (fabs(x)<eps) return 0;
	else if (x<0) return -1;
	else return 1;
}
double x[maxn],y[maxn];
vector<pair<double,double> > p[maxn];
//每個點和剩下所有點連成的直線與母線的交點
pair<double,double> jd (double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4) {
	if (x1==x2&&y1==y2) return make_pair(1e18,1e18);
	//(x1,y1),(x2,y2)組成的直線和(x3,y3),(x4,y4)組成的直線的交點
	double k1=(x1==x2?1e18:(y1-y2)/(x1-x2));
	double k2=(y1==y2?1e18:(y3-y4)/(x3-x4));
	if (sgn(k1-k2)==0) return make_pair(1e18,1e18);
	//k1是1e18，k2不是，答案就是x1*k2+b2
	if (k1==1e18) {
		return make_pair(x1,x1*k2+y3-k2*x3);
	} 
	else if (k2==1e18) {
		return make_pair(x2,x2*k1+y1-k1*x1);
	}
	double b1=y1-k1*x1;
	double b2=y3-k2*x3;
	double x=(b2-b1)/(k1-k2);
	double y=k1*x+b1;
	return make_pair(x,y);
}
int cmp (pair<double,double> x,pair<double,double> y) {
	if (sgn(x.first-y.first)!=0) {
		return sgn(x.first-y.first)<0;
	}
	else {
		return sgn(x.second-y.second)<0;
	}
} 
int main () {
	scanf("%d%d",&n,&m);
 	scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);
 	for (int i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i);
 	for (int i=1;i<=n;i++) {
 		for (int j=1;j<=n;j++) {
 			if (i==j) continue;
 			pair<double,double> it=jd(x[i],y[i],x[j],y[j],xs,ys,xt,yt);	
 			if (it.first==1e18) continue;//沒有交點
			if (sgn(it.first-min(xs,xt))<0||sgn(it.first-max(xs,xt))>0||sgn(it.second-min(ys,yt))<0||sgn(it.second-max(ys,yt))>0) continue;//交點線上段以外
			p[i].push_back(it); 
		}
		if (xs<xt) sort(p[i].begin(),p[i].end(),cmp);
		else if (xs>xt) sort(p[i].rbegin(),p[i].rend(),cmp);
		else if (ys<yt) sort(p[i].begin(),p[i].end(),cmp);
		else sort(p[i].rbegin(),p[i].rend(),cmp);
	}
	while (m--) {
		int h,t;
		scanf("%d%d",&h,&t);
		//printf("%d\n",p[h].size());
		if (t>p[h].size()) {
			printf("-1\n");
			continue;
		}
		printf("%.10f %.10f\n",p[h][t-1].first,p[h][t-1].second);
	}
}

J.Parallel Sort（構造）

給出一個數組，單輪可以交換任意兩個元素的值，但是同一個下标在一輪中隻能調用一次。

詢問至少幾輪可以使數組有序？

比賽的時候在錯誤的貪心思路陷進去了。覺得\(10^5\)的資料範圍，\(nlogn\)複雜度很對。但實際上隻需要兩次即可。

考慮這樣一組樣例：

6
2 3 4 5 6 1

我們将元素應該在的位置和它目前位置連邊，可以得到這樣的圖：

一個顯然的貪心思路是2和3連邊，4和5連邊，6和1連邊，然後第二輪繼續這個貪心方法，即遇到能換的就換，擴充之後可以發現大概需要\(logn\)次可以完成排序的任務。

但是有一個更加優秀的構造方法。觀察之後可以發現，任意排列通過圖表示，都是一個一個獨立的環。

對于這個環，第一輪分别交換[1,2]，[3,6]，[4,5]，這樣可以得到一個這樣的數組：

6
2 3 4 5 6 1
1 6 5 4 3 2

這樣可以把這個環拆成若幹個小環，比如這樣：

進一步觀察後可以發現，每個環都可以用這種方法拆成若幹個長度為2的小環。

第二輪對每個環交換一次即可。

是以穩定小于等于2次。

做法就是先處理出每個環的資訊，然後将每個環的第一個元素和倒數第一個元素、第二個元素和倒數第二個元素...交換，可以把環拆成若幹個大小小于等于2的小環。

第二輪就一步到位了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int n,p[maxn];
int vis[maxn];
vector<pair<int,int> > ans[2];
int b[maxn];
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",p+i),b[p[i]]=i;
	for (int i=1;i<=n;i++) {
		if (p[i]==i) continue;
		if (vis[p[i]]) continue;
		int u=p[i];
		vector<int> tt;
		while (p[u]!=p[i]) {
			tt.push_back(b[u]);
			u=p[u];
		}
		for (int j=0;j<tt.size()/2;j++) {
			swap(p[tt[j]],p[tt[tt.size()-j-1]]);
			b[p[tt[j]]]=tt[j];
			b[p[tt[tt.size()-j-1]]]=tt[tt.size()-j-1];
			ans[0].push_back(make_pair(tt[j],tt[tt.size()-j-1]));
		}
	}
	int f=1;
	for (int i=1;i<=n;i++) if (p[i]!=i) f=0;
	if (f) {
		if (ans[0].size()==0) return printf("0"),0;
		printf("1\n");
		printf("%d",ans[0].size());
		for (pair<int,int> i:ans[0]) printf(" %d %d",i.first,i.second);
		printf("\n");
		return 0;
	}
	for (int i=1;i<=n;i++) {
		if (p[i]==i) continue;
		ans[1].push_back(make_pair(i,b[i]));
		swap(p[i],p[b[i]]);
		b[p[i]]=i;
		b[p[b[i]]]=b[i];
	}
	int cnt=((ans[0].size()>0?1:0)+(ans[1].size()>0?1:0)); 
	printf("%d\n",cnt);
	for (int i=0;i<2;i++) {
		if (!ans[i].size()) continue; 
		printf("%d",ans[i].size());
		for (pair<int,int> j:ans[i]) printf(" %d %d",j.first,j.second);
		printf("\n");
	}
}

M.Stone Games（結論推導+可持久化線段樹維護）

給出一個數組，每次詢問一個區間，請你找到最小的x，使得這個區間裡的數通過加法湊不出x。

強制線上。

這道題應該是2019ICPC徐州的弱化版本。

首先，沒有1的話答案就是1。

然後2的話，求小于2的所有數的和，設這個和為sum，如果sum<2，那麼答案就是2，否則[1~sum]都可以被表示出來。

再去找比sum+1小的數的和，如果這個和小于sum+1，說明答案就是sum+1，否則找到sum+1繼續相同的操作。

那麼做法就是：先對所有的數離散化，建可持久化線段樹。

然後，用可持久化線段樹維護區間比某個數小的數的和即可。這個和是每次近似兩倍的速度增長的，時間複雜度大概是\(O(32nlogn)\)。

ICPC昆明M題結論的證明：

假設目前維護的集合\(S\)可以構造出1到x的所有數，同時和為x。一開始\(S\)為空。

現在想看看是否能構造出x+1這個數。

首先，比x+1大的數是不可能對構造産生貢獻的。是以先找所有值為x+1的數。假設一共有y個值為x+1的數，目前\(sum=y(x+1)+x=(y+1)(x+1)-1\)。

現在嘗試構造一個數k，\(x+1 \leq k \leq sum\)。根據上面的柿子，\(k/(x+1)\)一定小于等于\(y\)，那麼就可以這樣構造：

設\(t_1=k/(x+1),t_2=k\%(x+1)\)。

\(t_1 \leq y\)，是以一定存在足夠的值為\(x+1\)的數來構造\(t_1\)。

\(t_2 \leq x\)，之前的集合\(S\)并沒有被使用過，直接用集合\(S\)來構造\(t_2\)即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
const int M=maxn*40;
int a[maxn],t[maxn];
int T[maxn];
int lson[M];
int rson[M];
ll c[M];
int tot;
int n,m,q;
int build (int l,int r) {
	int root=tot++;
	c[root]=0;
	if (l!=r) {
		int mid=(l+r)>>1;
		lson[root]=build(l,mid);
		rson[root]=build(mid+1,r);
	}
	return root;
}
int up (int root,int p,int v) {
	int newRoot=tot++;
	int tmp=newRoot;
	int l=1,r=m;
	c[newRoot]=c[root]+t[p];
	while (l<r) {
		int mid=(l+r)>>1;
		if (p<=mid) {
			lson[newRoot]=tot++;
			rson[newRoot]=rson[root];
			newRoot=lson[newRoot];
			root=lson[root];
			r=mid;
		}
		else {
			rson[newRoot]=tot++;
			lson[newRoot]=lson[root];
			newRoot=rson[newRoot];
			root=rson[root];
			l=mid+1;
		}
		c[newRoot]=c[root]+t[p];
	}
	return tmp;
}
ll query (int left_root,int right_root,int l,int r,int L,int R) {
	if (L>R) return 0;
	if (l>=L&&r<=R) return c[left_root]-c[right_root];
	int mid=(l+r)>>1;
	ll ans=0;
	if (L<=mid) ans+=query(lson[left_root],lson[right_root],l,mid,L,R);
	if (R>mid) ans+=query(rson[left_root],rson[right_root],mid+1,r,L,R);
	return ans;
}
int main () {
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) scanf("%d",a+i),t[i]=a[i];
	sort(t+1,t+n+1);
	m=unique(t+1,t+n+1)-t-1;
	for (int i=1;i<=n;i++) a[i]=upper_bound(t+1,t+m+1,a[i])-t-1;
	ll ans=0;
	T[n+1]=build(1,m);
	for (int i=n;i>=1;i--) T[i]=up(T[i+1],a[i],1);
	while (q--) {
		ll l,r;
		scanf("%lld%lld",&l,&r);
		ll ql=min((l+ans)%n+1,(r+ans)%n+1);
		ll qr=max((l+ans)%n+1,(r+ans)%n+1);
		//printf("%lld %lld\n",ql,qr);
		ll tt=1;
		while (1) {
			ll t1=-1;
			int L=1,R=m;
			while (L<=R) {
				int mid=(L+R)>>1;
				if (t[mid]<=tt) {
					t1=mid;
					L=mid+1;
				}
				else{
					R=mid-1;
				}
			}
			ll t2=query(T[ql],T[qr+1],1,m,1,t1);
			if (t2<tt) {
				ans=tt;
				break;
			}
			tt=t2+1;
		}
		printf("%lld\n",ans);
	}
}

2021ICPC亞洲區域賽（昆明）複盤

Wogua_boy

I.Mr. Main and Windmills（計算幾何）

J.Parallel Sort（構造）

M.Stone Games（結論推導+可持久化線段樹維護）

繼續閱讀

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

數組和類數組

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述