Codeforces Round #679 (Div.2)

這場解出了 pABCD 不過速度有點慢

如果速度在快一點 應該能上更多分

不過這場把我前一天摔青的分數全都加回來了

已經算是不錯了

Problem A - Finding Sasuke

這題的關鍵在 $n$ is even 的這句話

很明顯我們就可以讓 $b1=-a2,b2=a1$ 來讓總和為$0$

程式碼

#include <bits/stdc++.h>
 
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
void solve(){
	int n;
	cin >> n;
	int arr[n];
	for(auto &x : arr) cin >> x;
	for(int i = 0;i < n;i+=2){
		cout << -arr[i+1] << " " << arr[i] << " ";
	}
	cout << "\n";
}
 
signed main(){
	fastio
	int t = 1;
	cin >> t;
	while(t--) solve();
}

Problem B - A New Technique

給任意順序的直行以及橫列

問你是否能找出原來的版面

我原本以為數字會重複 用了很麻煩的解

但是他提到 “It is also guaranteed that each number from $1$ to $nm$ occurs exactly once”

就判斷一行就好

程式碼

#include <bits/stdc++.h>
 
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
void solve(){
	int n,m;
	cin >> n >> m;
	map<int,int> idx;
	int arr[n][m];
	for(int i = 0;i < n;i++) for(int j = 0;j < m;j++){
		cin >> arr[i][j];
		if(j==0) idx[arr[i][j]] = i+1;
	}
	vector<int> a(n);
	for(int i = 0;i < m;i++){
		vector<int> order(n);
		bool ok = 1;
		for(int j = 0, tmp;j < n;j++){
			cin >> tmp; 
			order[j] = idx[tmp];
			if(idx[tmp]==0) ok = 0;
		}
		if(ok) a = order;
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++) cout << arr[a[i]-1][j] << " ";
		cout << "\n";
	}
}
 
signed main(){
	fastio
	int t = 1;
	cin >> t;
	while(t--) solve();
}

Problem C - Perform Easily

這題基本上可以把題目化成 Smallest Range in K List

然後用他的概念就可以解出來了

（賽中想不到解法就直接抄code下來了）

程式碼

#include <bits/stdc++.h> 
  
using namespace std; 
  
void smallestRange(vector<vector<int>>& nums) {
    int rangeLeft = 0, rangeRight = INT_MAX;
    int size = nums.size();
    vector<int> next(size);
    
    auto cmp = [&](const int& u, const int& v) {
        return nums[u][next[u]] > nums[v][next[v]];
    };
    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    int minValue = 0, maxValue = INT_MIN;
    for (int i = 0; i < size; ++i) {
        pq.emplace(i);
        maxValue = max(maxValue, nums[i][0]);
    }
 
    while (true) {
        int row = pq.top();
        pq.pop();
        minValue = nums[row][next[row]];
        if (maxValue - minValue < rangeRight - rangeLeft) {
            rangeLeft = minValue;
            rangeRight = maxValue;
        }
        if (next[row] == nums[row].size() - 1) {
            break;
        }
        ++next[row];
        maxValue = max(maxValue, nums[row][next[row]]);
        pq.emplace(row);
    }
 
    cout << rangeRight-rangeLeft << "\n";
}
 

int main() 
{ 
	int a[6];
	for(auto &x : a) cin >> x;
	sort(a,a+6,greater<int>());
	int n;
	cin >> n;
    vector<vector<int>> arr(n,vector<int>(6)); 
  	for(int i = 0, tmp;i < n;i++){
  		cin >> tmp;
  		for(int j = 0;j < 6;j++){
  			arr[i][j] = tmp-a[j];
  		}
  	}
  
    smallestRange(arr); 
  
    return 0; 
} 

Problem D - Shurikens

看到這題的時候讓我想到 dsu 的拔邊與加邊的題目

可以將詢問與操作反轉過來進行

這個題目就變得很簡單了

用一個 set 維護所有的元素

當出現比最小元素還大的元素 或 要拿掉 set 的元素但 set 是空的

都可以直接回答 NO

最後的程式碼就很簡單了

#include <bits/stdc++.h>
 
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
signed main(){
	fastio
	int n;
	cin >> n;
	n*=2;
	set<int> s;
	vector<int> ans;
	vector<pair<char,int>> v;
	while(n--){
		char c;
		int val = 0;
		cin >> c;
		if(c=='-'){
			cin >> val;
		}
		v.push_back({c,val});
	}
	while(!v.empty()){
		auto [c,val] = v.back();
		v.pop_back();
		if(c=='+'){
			if(s.empty()){
				cout << "NO\n";
				return 0;
			}
			ans.push_back(*s.begin());
			s.erase(*s.begin());
		}else{
			if(!s.empty()&&val > *s.begin()){
				cout << "NO\n";
				return 0;
			}else{
				s.insert(val);
			}
		}
	}
	cout << "YES\n";
	reverse(ans.begin(),ans.end());
	for(auto x : ans) cout << x << " ";
}