心得
再度掉分｡ﾟヽ(ﾟ´Д`)ﾉﾟ｡
從1781 -> 1760 我怎麼那麼爛R
這場因為pB一開始題目出問題 卡了一陣子（也不算一陣子 大概是快一小時吧(／‵Д′)／~ ╧╧)
最後只解出 pA, pB, pC
連結: https://codeforces.com/contest/1408
Problem A - Circle Coloring
這題一開始因為 這敘述想了一下子
不過理解後 題目下一段就直接告訴你那行的意思了（直接給不就好了╰(〒皿〒)╯）
反正就是給你三個陣列 從這三個陣列中挑一個數字組成新的陣列
然後新的陣列相鄰兩元素不相等（包括最後一個和第一個）
程式碼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
using namespace std;
void solve(){
int n;
cin >> n;
int arr[3][n];
for(int i = 0;i < 3;i++) for(int j = 0;j < n;j++) cin >> arr[i][j];
int ans[n];
for(int i = 0;i < n;i++){
for(int j = 0;j < 3;j++){
if(i==0){
ans[i] = arr[j][i];
break;
}
if(i!=n-1&&arr[j][i]!=ans[i-1]){
ans[i] = arr[j][i];
break;
}
if(i==n-1&&arr[j][i]!=ans[0]&&arr[j][i]!=ans[i-1]){
ans[i] = arr[j][i];
break;
}
}
}
for(auto x : ans) cout << x << ' ';
cout << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem B - Arrays Sum
這題其實一開始讀到題目的時候就想到正解了
覺得答案應該是 $\lceil \frac{不同數字的數量-1}{k-1} \rceil$
然後特判 $k=1$ 的情況
不過測資出了問題
一開始看到測資時 想了一下子
明明用我的想法第四和第五個測資答案就是2 2
結果不是 把$\lceil \frac{不同數字的數量-1}{k-1} \rceil$ 的結論丟掉之後就卡住了
直到
然後我又想了好久 那第五個測資呢٩(ŏ﹏ŏ、)۶
後來終於
測資終於正確之後 開始寫 結果丟上去
想了好久 我到底錯在哪裡 結果是 $\lceil \rceil$ 的時候寫錯了…
總之 多災多難的一次pB 然後還rated ヽ(`Д´)ノ
程式碼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
using namespace std;
void solve(){
int n,k;
cin >> n >> k;
set<int> s;
for(int i = 0, tmp;i < n;i++){
cin >> tmp;
s.insert(tmp);
}
if(k==1){
if(s.size()==1){
cout << 1 << "\n";
}else{
cout << -1 << "\n";
}
return;
}
cout << max(1,((int)s.size()-1+k-2)/(k-1)) << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem C - Discrete Acceleration
這題剛點開時想了一下
示意圖（有點醜）
反正就是有點國小那種追趕問題 不過是相向而行
這題基本上就分前後討論就好了
C++的話可以用deque
程式碼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
using namespace std;
void solve(){
int n,l;
cin >> n >> l;
deque<double> v;
for(int i = 0, tmp;i < n;i++){
cin >> tmp;
v.push_back(tmp);
}
double ans = 0;
double sa = 1, sb = 1, apos = 0, bpos = l;
while(!v.empty()){
if((v.front()-apos)/sa < (bpos-v.back())/sb){
bpos -= (v.front()-apos)/sa*sb;
ans += (v.front()-apos)/sa;
apos = v.front();
sa++;
v.pop_front();
}else if((v.front()-apos)/sa > (bpos-v.back())/sb){
apos += (bpos-v.back())/sb*sa;
ans += (bpos-v.back())/sb;
bpos = v.back();
sb++;
v.pop_back();
}else{
ans += (v.front()-apos)/sa;
apos = v.front();
bpos = v.back();
sa++;
sb++;
v.pop_front();
if(!v.empty())v.pop_back();
}
}
ans += (bpos-apos)/(sa+sb);
cout << ans << "\n";
}
signed main(){
fastio
cout << fixed << setprecision(10);
int t = 1;
cin >> t;
while(t--) solve();
}
Problem D - Searchlights
這題是要移動每個小偷 使得沒有一個小偷的 $x$ 或 $y$ 小於任何一個燈的 $x$ 或 $y$
這題我解完pB之後 一直想不到解答
我原本的想法是使用三分搜來找的最小值
不過不是WA就是TLE
慘狀
然後賽後看了其他人的解以及Editorial才會解這題
這題的 $m,n$ 並不大，都小於 2000
因此如果我們能有一個 $O(mn)$ 甚至是 $O(mnlogn)$也都能通過
原本的想法是去枚舉增加的 $x$ ，不過 $10^6$ 有點大 不容易去做這件事
所以仔細想想後會發現增加的 $x$ 對應答案會成單調性
增加的 $x$ 越小 所需增加的y就越大
所以我們可以做一件事 就是做 $nm$ 次 並更新小於 $\Delta x$ 時 小偷的 $y$ 座標應增加的數字
接著我們就可以用後綴最大值來達到這點
複雜度：$O(nm+10^6)$
程式碼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
using namespace std;
const int N = 1e6+5;
int arr[N];
signed main(){
fastio
int n,m;
cin >> n >> m;
vector<pair<int,int>> rb,sl;
for(int i = 0;i < n;i++){
int x,y;
cin >> x >> y;
rb.push_back({x,y});
}
for(int i = 0;i < m;i++){
int x,y;
cin >> x >> y;
sl.push_back({x,y});
}
for(auto x : rb){
for(auto y : sl){
if(x.first > y.first) continue;
arr[y.first-x.first] = max(arr[y.first-x.first],y.second-x.second+1);
}
}
int ans = INT_MAX;
for(int i = N-1;~i;i--){
arr[i] = max(arr[i],arr[i+1]);
ans = min(arr[i]+i,ans);
}
cout << ans << "\n";
}