Codeforces 869 Div. 2 題解

A. Politics

題目概述

有 NN 個人需要參與 MM 場投票，每場投票的方式如下：

每個人可以投同意或反對票，當同意票 >> 反對票時，投反對票的人會被淘汰；當反對票 << 同意票時，投同意票的被淘汰；當同意和反對票數相同時，則全部人都淘汰。

而現在你是第一為參與者，你知道了這 MM 場投票的結果，也就是每個人的選擇，現在你可以在開始投票前淘汰一些人，使得最後留下來的人最多，並且你自己 (第一位參賽者) 必須要留下來，請問最後留下來的人數一共是多少。

題解

第一位參賽者一定要留下來，那如果投票跟第一位參賽者不同的只有可能造成某一些人被淘汰，所以留下來的參賽者意見一定要跟第一位參賽者一致，所以就數有幾個人投票跟第一位參賽者相同就行。
這裡是用 std::map 紀錄

AC Code

1
2
3
4
5
6
7
8
9
10
11
void solve(){
	int n,k;
	cin>>n>>k;
	vector<string>v(n);
	map<string, int>mp;
	for(int i = 0;i < n;++i){
		cin>>v[i];
		mp[v[i]]++;
	}
	cout<<mp[v[0]]<<'\n';
}

B. Indivisible

題目概述

給你一個 NN ，請你輸出一個長度為 NN 的排列使得 ∀[l,r]∈N(l<r,∑lrai∤r−l+1)\forall [l,r] \in N (l < r, \sum^r_l a_i \nmid r - l + 1)

題解

我是暴力產生所有大小為 NN 的排列，並輸出符合的，然後找出規律
大概就是 NN 是奇數時無解，偶數時是 2,1,4,3,6,5,8,7,...2, 1, 4, 3, 6, 5, 8, 7, ...
N=1N = 1 時特判一下就好

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
	int n;
	cin>>n;
	if(n==1){
		cout<<1<<endl;
		return;
	}
	if(n&1){
		cout<<-1<<endl;
		return;
	}
	for(int i = 2;i<=n;i+=2){
		cout<<i<<' '<<i-1<<' ';
	}
	cout<<endl;
}

C. Almost Increasing Subsequence

題目概述

給你一個長度為 NN 的序列，然後有 QQ 筆詢問，每次詢問某個區間內的最長子序列滿足不會有連續三個元素 ai,ai+1,ai+2a_i, a_{i+1}, a_{i+2} 使得 ai≥ai+1≥ai+2a_i \ge a_{i+1} \ge a_{i+2} 的序列長度是多少。

題解

對於原序列來說，可以先把原序列當中滿足該條件的地方打上標記，最後對於每筆詢問就只要計算區間內一共有幾個標記就行，因為是在三個元素的其中一個元素的位置打上標記，所以要記得處理邊界情況。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> v(n+1),s(n+1),tmp(n+1);
	for(int i = 1;i<=n;++i)cin>>v[i];
    for(int i = 1;i<=n-2;++i){
		if(v[i]>=v[i+1] and v[i+1]>=v[i+2]){
			tmp[i+1] = 1;
		}
	}
	for(int i = 1;i<=n;++i){
		s[i] = s[i-1]+tmp[i];
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		if(r-l+1<=2){
			cout<<r-l+1<<endl;
			continue;
		}
		int tmp = r-l+1;
		r--;
		l++;
		cout<<tmp-(s[r]-s[l-1])<<endl;
	}
}

D. Fish Graph

題目概述

給一張連通圖，找出一個環，並且環上的一個節點可以延伸出兩條長度為 11 邊，且那兩條邊不在環上，這個就叫做 Fish 。
請找出圖上的 Fish 並輸出。

題解

這題是賽後才補掉的，因為自己對圖論不熟，用 stack 判環也只寫過一兩次，想說自己對於用 DSU 判環比較熟，所以就砸 DSU 了，然後又想說要從 DSU 上拆邊，拆掉後再判，就想到了用時間線段樹，反正就是一連串的耍毒耍到最後。
賽後聽朋友說只要對於每個節點都暴力去找環就好了，因為 N,MN, M 很小所以可以這樣做。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
bitset<2005>vis,in_stk;
void solve(){
	int n,m;
	cin>>n>>m;
	vector<int>g[n+1];
	for(int i = 0;i<m;++i){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1;i<=n;++i){
		if(g[i].size()<4)continue;
		vis.reset(),in_stk.reset();
		stack<int>st;
		bool flag = 0;
		function<void(int,int)>dfs = [&](int u,int p){
			vis[u] = in_stk[u] = 1;
			st.push(u);
			if(flag)return;
			for(auto v:g[u]){
				if(flag)return;
				if(v==p)continue;
				if(v==i){
					vector<int> tmp;
					for(auto j:g[i]){
						if(!in_stk[j])tmp.pb(j);
					}
					if(tmp.size()<2)continue;
					cout<<"Yes\n";
					vector<pair<int,int>>ans;
					ans.pb({v,tmp[0]});
					ans.pb({v,tmp[1]});
					int now = v;
					while(!st.empty()){
						ans.pb({now,st.top()});
						now = st.top();
						in_stk[now] = 0;
						st.pop();
					}
					cout<<ans.size()<<endl;
					for(auto [a,b]:ans){
						cout<<a<<' '<<b<<endl;
					}
					flag = 1;
					return;
				}
				if(vis[v])continue;
				dfs(v,u);
			}
			in_stk[u] = 0;
			st.pop();
		};
		dfs(i,-1);
		if(flag)return;
	}
	cout<<"No\n";
}

心得

這場最後加了 136 分，如果把 D 寫出來可能這場就可以上藍了吧，但可惜沒有，下次再繼續加油。

最近打 cf 有多少打出了一點心得，讓自己意識到自己學的黑科技跟思考能力落差太多，導致在 cf 這種比較考察想法的比賽中會表現略於遜色，像是高中三年級時有試著打了一兩個月的 cf ，結果上青之後就一直卡在青，大一下 (也就是這學期) 想說鐵下心來認真打 cf ，結果就是一直滑鐵盧，掉到快要變綠色的時候上分上完之後繼續掉，原本這場沒打好可能就綠色了，但還好這場手速夠快，差點噴上藍色。

希望能繼續進步，越來越強。