心得
這場只答對三題pA, pB, pC
所以掉分了(´Д` )
1793 -> 1781
Problem A - Copy-paste
給予一個 $n$ 項的陣列以及一個 $k$ 值
你能挑選 $1\leq i,j \leq n$
並讓 $a_j = a_j + a_i$
問最多能做幾次
這題我一看到是直接砸priority_queue
不過其實這題很簡單的做法是
選取 $min(a_0,a_1,…,a_n)$ 的值
並用該值去增加其他項的數值
程式碼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
using namespace std;
void solve(){
int n,k;
cin >> n >> k;
int cnt = 0;
priority_queue<int,vector<int>,greater<int>> pq;
for(int i = 0,tmp;i < n;i++){
cin >> tmp;
pq.push(tmp);
}
while(pq.top()<=k){
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
if(a+b <= k){
cnt++;
}else{
break;
}
pq.push(a+b);
pq.push(a);
}
cout << cnt << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem B - Two Arrays
題意是說
給予一個 $n$ 項的陣列與一個 $T$ 值
你可以將整個陣列塗兩種顏色
使得同一個顏色當中 任兩個元素總和為 $T$ 的數量最小化
這題我一開始想錯 砸了兩次WA 不過這題非常簡單
首先 我們先掃過每一個元素 $a_i$
決定是否將 $a_i$ 塗色
若我們尚未塗過 $T-a_i$ 我們就將 $a_i$ 塗色
這個題目有一個小陷阱
那就是當元素可重複且元素為 $\frac{t}{2}$
我們就必須把同個元素塗上不同的顏色
否則同元素放在同一顏色當中反而更好
程式碼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
using namespace std;
void solve(){
unordered_map<int,int> c,cnt;
int n,t;
cin >> n >> t;
int arr[n];
for(auto &x : arr) cin >> x;
for(int i = 0;i < n;i++){
cnt[arr[i]]++;
if(!c[t-arr[i]])
c[arr[i]] = 1;
}
for(int i = 0;i < n;i++){
if(arr[i]==t-arr[i]&&cnt[arr[i]]%2==0) cout << (c[arr[i]]^1) << " ";
else cout << c[arr[i]] << " ";
cnt[arr[i]]--;
}
cout << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem C - k-Amazing Numbers
這題是說給予一個 $n$ 項的陣列
問在每一個長度為 $k$ 的子陣列當中 都有出現的最小元素
並依序從 $k=1 \sim k=n$ 分別輸出最小元素
這題我的做法是紀錄 $1 \sim n$ 相隔最久都沒有出現重複的長度
之後就能用這個去得到答案了
由於出現在每個長度為 $k$ 的子陣列的元素 一定出現在長度為 $k+1$的子陣列 我們也需要用 $k$的元素來更新 $k+1$的元素
程式碼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
using namespace std;
void solve(){
int n;
cin >> n;
int g = 0, mi = INT_MAX;
int arr[n+1] = {};
int ans[n+1] = {};
for(int i = 0, tmp;i < n;i++){
cin >> tmp;
mi = min(mi,tmp);
ans[tmp] = max(ans[tmp],(arr[tmp]+g + (ans[tmp]==0 ? 1 : 0)));
arr[tmp] = -i;
g++;
}
vector<int> pr(n+2,1e9+7);
for(int i = 1;i <= n;i++){
ans[i] = max(ans[i],arr[i]+g);
pr[ans[i]] = min(i,pr[ans[i]]);
}
pr[n] = mi;
for(int i = 1;i <= n;i++){
pr[i+1] = min(pr[i+1],pr[i]);
}
for(int i = 1;i <= n;i++){
if(pr[i]==1e9+7) cout << -1 << " ";
else cout << pr[i] << " ";
}
cout << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem D - Make Them Equal
這題真的要說的話 難度並不高
不過我一直砸 伴隨而來的是無止盡的WA
度的 就是如此的可撥(／‵Д′)／~ ╧╧
這題的題目是說給予一個n項的陣列
你可以進行操作
$\Rightarrow$ 選擇三個整數 $i,j,x$
$\Rightarrow$ 將$a_j = a_j + i\times x$，$a_i = a_i - i \times x$
問是否能在 $3n$ 次操作內 使得陣列中的所有元素相等
這題其實 $3n$ 是非常寬的一個數字
而這題的作法其實非常簡單
我們可以把題目的操作理解成 $\Rightarrow$ 選擇 $a_i$ 並將 $i$ 的倍數轉移至 $a_j$
我們可以很輕易想到 如果要使得每個元素相等 代表所有元素應變為他們的算術平均數
因此 當總和不是 $n$ 的倍數時 我們就可以排除這個解
接下來的作法就非常簡單了
由於我們不容易想應該如何將 $i$ 的倍數轉移
如果我們可以先將所有的數字先集中到 $a_1$ 之後
再由 $a_1$ 去分配給其他元素 這就會是一個非常好的解法了
然而，說來簡單 如何將其他元素都集中到 $a_1$ 呢？
題目有一個條件 $1 \leq a_i \leq 10^5$
既然 $a_i$ 一定大於0 我們可以從 $a_2$ 開始分別將數字轉移至 $a_1$
當我們要轉移 $a_i$ 的值到 $a_1$ 時
我們會先將 $a_i$ 的值變為 $i$ 的倍數
這樣我們就可以直接轉移到 $a_1$ 身上了
附上程式碼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
using namespace std;
void solve(){
int n, sum = 0;
cin >> n;
int arr[n];
for(int i = 0;i < n;i++){
cin >> arr[i];
sum += arr[i];
}
if(sum%n){
cout << -1 << "\n";
return;
}
sum/=n;
vector<array<int,3>> v;
for(int i = 1;i < n;i++){
if(arr[i]%(i+1)){
v.push_back({1,i+1,i+1-arr[i]%(i+1)});
arr[0] -= i+1-arr[i]%(i+1);
arr[i] += i+1-arr[i]%(i+1);
}
v.push_back({i+1,1,arr[i]/(i+1)});
arr[0] += (arr[i]/(i+1))*(i+1);
arr[i] = 0;
}
for(int i = 1;i < n;i++){
v.push_back({1,i+1,sum});
}
cout << v.size() << "\n";
for(auto x : v){
for(auto y : x){
cout << y << " ";
}
cout << "\n";
}
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem E - XOR Inverse
待補