5月26日

Love is the best medicine.

前傳

“同學們，這種試卷我們明天訂正完‘反交’一下。”——5.25 Mr 袁

這就是生物的魅力嗎？

“赫魯曉夫提出了兩個條件：一個是要到美國的肯尼迪（？？？）玩？”——Miss 殷

“嗯？？？” 全班

“哦不對，迪士尼” 笑

第二次“沒有答應他去肯尼迪”？？？？

這就是歷史的魅力嗎

CF1527E Partition Game

線段樹優化dp

對于暴力 \(dp[i][j]\) 表示前i個分為j段的值

轉移 \(dp[i][k] = min \{dp[j][k-1]+cost(j+1,i)\}\)

對于cost，從后往前枚舉 \(j\) 計算時只要加入 \(j+1\) 位置和后面第一個的差就可以 \(O(n^2k)\) 完成了。

如果從前忘后算，加入 \(i\) 的時候，也就是將 \([1,lst]\) 的代價都加 \(i-lst\) 就可以用線段樹區間加求最小值啦！枚舉一下k，就可以 \(O(kn log n)\) 啦！

#include <bits/stdc++.h>
typedef long long ll;
const int N=35005;
const ll INF=1e15;
ll dp[N];
int a[N],pre[N],n,k,lst[N];
struct SGT{
	ll t[N<<2],tg[N<<2];
	void build(int k,int L,int R){
		tg[k]=0;
		if (L==R){
			t[k]=dp[L-1];
			return;
		}
		int mid=(L+R)>>1;
		build(k<<1,L,mid),build(k<<1|1,mid+1,R);
		t[k]=std::min(t[k<<1],t[k<<1|1]);
	}
	void puttag(int k,int x){
		tg[k]+=x;
		t[k]+=x;
	}
	void pushdown(int k){
		if (tg[k]){
			puttag(k<<1,tg[k]);
			puttag(k<<1|1,tg[k]);
			tg[k]=0;
		}
	}
	void modify(int k,int L,int R,int l,int r,int x){
		if (r<l) return;
		if (L==l && R==r){
			puttag(k,x);
			return;
		}
		pushdown(k);
		int mid=(L+R)>>1;
		if (r<=mid) modify(k<<1,L,mid,l,r,x);
		else if (l>mid) modify(k<<1|1,mid+1,R,l,r,x);
		else{
			modify(k<<1,L,mid,l,mid,x);
			modify(k<<1|1,mid+1,R,mid+1,r,x);
		}
		t[k]=std::min(t[k<<1],t[k<<1|1]);
	}
	ll query(int k,int L,int R,int l,int r){
		if (l==L && R==r) return t[k];
		pushdown(k);
		int mid=(L+R)>>1;
		if (r<=mid) return query(k<<1,L,mid,l,r);
		if (l>mid) return query(k<<1|1,mid+1,R,l,r);
		return std::min(query(k<<1,L,mid,l,mid),query(k<<1|1,mid+1,R,mid+1,r));
	}
}T;
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]); 
	for (int i=1;i<=n;i++){
		pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for (int i=1;i<=k;i++){
		T.build(1,1,n);
		dp[i-1]=INF;
		for (int j=i;j<=n;j++){
			T.modify(1,1,n,1,pre[j],j-pre[j]);
			dp[j]=T.query(1,1,n,1,j);
		}
	}
	printf("%lld\n",dp[n]);
}

CF1515F Phoenix and Earthquake

題目名指路歌曲名：涅槃 (Phoenix) 敲代碼超配

構造

瞄了一眼發現什么boruvka，然后想到最后得出的猜測是。

我也不會boruvka怎么做（后來發現人家說他假了，我眼瞎），感覺要是和 \(<(n-1) \times k\) 一定無解。否則每次把可行的并掉一定就可以了吧。

至于怎么并可行的，找任意一棵生成樹都是可行的，因為如果總和滿足條件，一定有一條邊是 \(>2k\) 的，否則達不到 \((n-1) \times k\) 。

然后的構造：

每次找到一個葉節點 \(u\)

如果 \(a_u<k\) 那么把 \(u\) 在最后和父親合起來，繼續考慮剩下部分（剩下部分的和一定滿足），壓入棧
否則就可以當前就把 \(u\) 和 \(fa\) 連起來，變成 \(a_u+a_{fa}-k\)，繼續構造，直接輸出

最后把第一類邊倒序輸出即可

#include <bits/stdc++.h>
typedef long long ll;
const int N=300005;
std::queue<int> q;
int n,m,k,f[N],to[N<<1],edge,Next[N<<1],last[N],id[N<<1],fw[N],st[N],tp,x,y;
int d[N];
ll a[N],sum;
int find(int x){
	if (f[x]==x) return x;
	return f[x]=find(f[x]);
}
void add(int x,int y,int z){
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
	id[edge]=z;
}
void dfs(int x,int y,int z){
	f[x]=y,fw[x]=z;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (u==y) continue;
		dfs(u,x,id[i]);
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++) f[i]=i;
	for (int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum+=a[i];
	} 
	if (sum<(ll)(n-1)*k) return puts("NO"),0; 
	puts("YES");
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		int fx=find(x),fy=find(y);
		if (fx==fy) continue;
		add(x,y,i),add(y,x,i);
		d[x]++,d[y]++;
		f[fx]=fy;
	}
	dfs(1,0,0);
	for (int i=2;i<=n;i++)
		if (d[i]==1) q.push(i);
	while (q.size()){
		int x=q.front(),fa=f[x];
		q.pop();
		if (!fa) continue;
		d[fa]--;
		if (d[fa]==1) q.push(fa);
		if (a[x]<k) st[++tp]=fw[x];
		else printf("%d\n",fw[x]),a[fa]=a[fa]+a[x]-k;
	}
	while (tp) printf("%d\n",st[tp--]);
}

CF1477D Nezzar and Hidden Permutations

拓撲序，構造

這題我以前一定看過，然而我想了半天還是不會做。

開始一下午一道題的摸魚時光。

首先如果一個點度數是 \(n-1\) ，定向后這個點的拓撲序一定唯一確定了，可以把這個點去掉。

去完以后，最大點的度數 \(<n-1\)，猜測此時已經有方案使兩排列完全不相同。

考慮如果一張不止一個點的圖中有一個孤立點，那么這個孤立點拓撲序可以任意，只要放在第一個+其他、其他+最后一個就可以了，稱次為孤立圖。

那么我們努力把剩下的圖分成若干個有孤立點的集合，這樣把這些圖的拓撲序拼起來（一段一段拼就行）后也不會相同（只要按集合編號大小連定外面的邊就行了）。這些孤立圖在反圖中的表現即為菊花圖。建出反圖的一棵生成樹，從下往上處理。如果子節點還未被加入某一個集合，那么和父親并在一起，父親為孤立點。到最后如果根成為了單獨的點，任選一個它的兒子加入進去即可。

反圖的邊數數量很多，如何建一棵生成樹？隨便了。看到了一種簡單的寫法，雖然他是 \(O(n log n)\) 的，就這樣吧。

#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int T,n,m,x,y,d[N],match[N],a[N],b[N],siz[N],ap[N],bp[N];
vector<int> e[N],s[N];
queue<int> q;
void clear(){
	for (int i=1;i<=n;i++)
		d[i]=0,e[i].clear(),match[i]=0,s[i].clear();
}
int main(){
	scanf("%d",&T);
	while (T--){
		clear();
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			d[x]++,d[y]++;
			e[x].push_back(y),e[y].push_back(x); 
		} 
		for (int i=1;i<=n;i++) sort(e[i].begin(),e[i].end());
		int tp=0;
		for (int i=1;i<=n;i++){
			if (d[i]==n-1){
				a[++tp]=i;
				b[tp]=i;
				continue;
			}
			if (match[i]) continue;
			int p=0,u;
			for (u=1;u<=n;u++){
				if (u==i) continue;
				if (p>=e[i].size() || u!=e[i][p]){
					if (d[i]!=n-1) break;
				}else p++;
			}
			int rt=match[u];
			if (!rt){//新建 
				rt=u;
				match[i]=match[u]=u;
				siz[u]=2;
			}else{
				if (rt==u){//直接加入 
					siz[rt]++;
					match[i]=rt;
				}else{
					if (siz[rt]>2){//分裂 
						siz[rt]--;
						rt=u;
						match[u]=match[i]=u;
						siz[u]=2;
					}else{//換根 
						siz[u]=3;
						match[rt]=match[u]=match[i]=u;
					}
				}
			}
		}
		for (int i=1;i<=n;i++)
			if (match[i] && match[i]!=i) s[match[i]].push_back(i);
		for (int i=1;i<=n;i++){
			if (match[i]==i){
				a[tp+1]=i;
				b[tp+siz[i]]=i;
				for (int j=0;j<siz[i]-1;j++){
					a[tp+1+j+1]=s[i][j];
					b[tp+1+j]=s[i][j];
				}
				tp+=siz[i];
			}
		}
		for (int i=1;i<=tp;i++) ap[a[i]]=i,bp[b[i]]=i;
		for (int i=1;i<=n;i++) printf("%d ",ap[i]);puts("");
		for (int i=1;i<=n;i++) printf("%d ",bp[i]);puts(""); 
	}
}

CF1515G Phoenix and Odometers

昨天回家想了想。你保存了嗎？保存了嗎？？？

今天打開哦果然是一片空白，真是太棒了，清理一下心情。

我不想寫了看這個就行了好東西和好東西

至于為什么弄了這么久，Longlong不要直接用abs，死的不明不白。

還學會了gcd的新寫法，這樣就不用管0了。

果斷ctrl+s

哦它恢復回來了

想了一會兒.

對不起沒有然后了我以為它是個無向圖，還想著每條邊都可以繞來繞去繞成余數為零。

重新開始！有向圖，回路，那一定是一個強連通分量里的，不妨只考慮某一個。且兩兩間都有回路，那么易知，整個強連通分量對 \((s,t)\) 的答案是一樣的，因為你可以從 \(v\) 繞一個回路繞t次就余數為0了，中途再從 \(u\) 繞出去一下，這樣 \(u\) 能達到的 \(v\) 也行了。

同理也可以知道，所有的環都可以任意取到，如果把圖中所有環長取出來，問的就是 \(k_1 len_1+k_2 len_2 + \dots k_t len_t +S\equiv 0 (\text{mod } T)\)

根據裴蜀定理可知，前面那一堆東西能表示出任意\(kg(g=gcd(len))\) 那么成立條件即為 \(gcd(g,T)|S\)

問題轉化為怎么求所有環長

因為是有向圖，所以任意一個環都可以表示成樹上返祖邊環的組合。

好東西

#include <bits/stdc++.h>
typedef long long ll;
const int N=200005;
int dfn[N],low[N],idn,col[N],to[N],last[N],Next[N],w[N],edge;
int x,y,n,Q,vis[N],st[N],tp,cnt,z,m,s,t;
ll d[N],a[N];
ll g;
ll gcd(ll x,ll y){
	return y?gcd(y,x%y):x;
}
void add(int x,int y,int z){
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
	w[edge]=z;
}
void tarjan(int x){
	dfn[x]=low[x]=++idn;
	vis[x]=1;
	st[++tp]=x;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (!dfn[u]){
			tarjan(u);
			low[x]=std::min(low[x],low[u]);
		}else if (vis[u]) low[x]=std::min(low[x],dfn[u]);
	}
	if (dfn[x]==low[x]){
		cnt++;
		int u;
		do{
			u=st[tp--];
			vis[u]=0;
			col[u]=cnt;
		}while (u!=x);
	}
}
ll Abs(ll x){
	return x>0?x:-x;
}
void dfs(int x,int c){
	vis[x]=1;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (col[u]!=c) continue;
		if (!vis[u]){
			d[u]=d[x]+w[i];
			dfs(u,c);
		}else {
			ll t=Abs(d[x]-d[u]+w[i]);
			g=gcd(g,t);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i);
	for (int i=1;i<=n;i++){
		if (vis[i]) continue;
		g=0;
		dfs(i,col[i]);
		a[col[i]]=g;
	}
	scanf("%d",&Q);
	while (Q--){
		scanf("%d%d%d",&x,&s,&t);
		x=col[x];
		if ((!s) || s%gcd(a[x],t)==0) puts("YES");
		else puts("NO"); 
	}
}

posted @ 2021-05-27 10:23 flyfeather 閱讀(92) 評論(0) 收藏舉報

刷新頁面返回頂部

flyfeather

夢里飛羽化夢。偶爾夢見你而已

5月26日

5月26日

前傳

CF1527E Partition Game

CF1515F Phoenix and Earthquake

CF1477D Nezzar and Hidden Permutations

CF1515G Phoenix and Odometers

公告