CPTC 心得

題目在這裡,就跳過題序了QAQ

考前

三個完全還沒進入狀況的人：我,吳文元,余原齊被一開始登不進去的DOMjudge嚇到，於是發現team的編號從3位數多加了2000（？並延後15分鐘開始。

正式開始 (18:15)

原齊看pA,我看pB,文元去了廁所（？
後來調成我看pA
我先有了map+計數+discretization的想法，然後原齊和文元覺得pB是水題，於是原齊就快速讓它AC掉（？
後來我發現我在實做上idx的discretization卡住了，而且還用了map<int,pair<int,int>>分別紀錄aij,cnt,prefix，文元來用板書幫我把思緒整理過一遍，順便提醒我map的複雜度很爛$O(nlog(len))$。
(今天的我狀況極差QAQ)
然後好好的做出了我上面那三個想法，但一直爛掉，我把原齊和文元找來，確認都有好好做事，後來才發現在最後二分搜時要用upper_bound-1而非lower_bound，並AC了這題。
後來文元在刻pD，原齊告訴我pC,pE的題序，我馬上說pE是數位DP，但我沒有學過(very sad)，然後pC沒想法。
此時原齊想說要不要用數學的方式解pE，但始終想不出規律，於是一起幫文元想pD。
pD: 一棟樓1001層，有三顆只有超過其承受高度才會破掉且一樣的蛋，並從第n層往下丟，尋找蛋的確切硬度。尋找次數$\leq30$。
他們當時的想法是LCA倍增，但LCA是倒著做的，所以卡住。
我當時還不知道這是互動題，我就跟原齊說兩頭都倍增，壓縮L,R的範圍，如果已知會破就不做，不會破就可以將左邊界快速向右移。但當時文元一聽到就很生氣的說絕對行不通，我想嘗試說明給他聽，卻被文元直接插斷說：「不是你算法的問題，是你腦袋的問題！」我心態瞬間崩掉，直接去廁所消氣，回來繼續想其他方法。(說白的就是我欠嘴，不然我不會變強OwO)
(常打FPS都知道互嘴是正常的(畢竟台灣人不嘴不會變強OwO)，但心態崩時會繼續爭吵不休，甚至會賭氣，進而影響整支隊伍)
回來想一段時間後，我說：不然先二分搜直到第一顆蛋破掉，我們至少可以在第一顆蛋砍掉一半長，接下來留兩顆做你們的倍增。
後來又把第三顆蛋的狀態改掉，最後三人一起調整後統整如下：
第一顆：二分搜直到破掉
第二顆：倍增到$\frac{L+R}{2}$就回到從+1重新倍增
第三顆：+1直到結束
但直到Contest Over依舊WA
直到看了題解才知道有$(log10^3)\times10$的分10份想法。

結束 (21:15)

pA (AC)

#include <bits/stdc++.h>
using namespace std;
map<long long,int> mp;
long long str[100005],ct[100005];
int main(){
    int n,m,q;
    long long a;
    cin >> n >> m >> q;
    for(int i=0;i<n*m;i++){
        cin >> a;
        mp[a]++;
    }
    int fl=0,qu;
    for(map<long long ,int>::iterator it=mp.begin();it!=mp.end();it++){
        ct[fl] = it->first;
        str[fl]+=it->second;
        if(fl>0) str[fl]+=str[fl-1];
        fl++;
    }
    for(int i=0;i<q;i++){
        cin >> qu;
        long long *pos=upper_bound(ct, ct+fl, qu);
        cout << str[pos-ct-1] <<"\n";
    }
    return 0;
}

pB (AC)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int g[n], t[n];
    memset(g, 0, sizeof(g));
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        ++g[a - 1];
        ++g[b - 1];
    }
    for(int i = 0; i < n; ++i) cin >> t[i];
    sort(g, g + n); 
    sort(t, t + n);
    long long int ans = 0;
    for(int i = 0; i < n; ++i) ans += g[i] * t[n - i - 1];
    cout << ans;
    return 0;
}

pD (WA)

#include <bits/stdc++.h>
#ifdef TEST
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
#define EB emplace_back
#define MP make_pair
#define X first
#define Y second
using namespace std;
using ll = long long;
using llu = long long unsigned;
using pii = pair<int,int>;
/************************/
int main() {
	const int R = 1001;
    int l = 0, r = R, mul = 1, m = l+((r-l)/2); // [l, r)
    int cnt = 0;
    // tumor egg throw
    while(++cnt){
    	if(30-cnt > r-l+1){
    		goto TUMOR;
    	}
    	if(m == R-1){
    		cout << "! " << m << endl;
    		return 0;
    	}
    	// SAFE
    	debug("%d\n", cnt);
    	cout << "? " << m << endl;
    	string s;
        cin >> s;
        if(s == "SAFE"){
        	l = m;
        	m = l+((r-l)/2);	
        }
        else{
        	break;
        }
    }
    // normal
    while(++cnt) { 
    	if(30-cnt >= r-l+1){
    		goto TUMOR;
    	}
    	debug("%d\n", cnt);
    	cout << "? " << l+mul << endl;
        string s;
        cin >> s;
        if(s == "SAFE") {
        	if(l+mul > m){	
        		l = l+mul;
        		mul = 1;
        		m = (l+r)/2;
        	}
        	else{
				mul = mul << 1;
        	}
      	}
        else{
        	r = l+mul;
        	l = l + (mul>>1);
        	m = (l+r)/2;
        	mul = 1;
        	break;
        }
    }
    TUMOR:
    while(++cnt){
    	debug("%d\n", cnt);
    	cout << "? " << l+1 << endl;
    	string s;
        cin >> s;
        if(s == "SAFE"){
        	++l;
        }
        else{
        	cout << "! " << l << endl;
        	break;
        }
    }
    return 0;
}

結論

  • 名次: 43/94
  • AC: 2/5
  • WA: 1
  • Penalty:111
  • 文元使用goto，然後整個人變得很母湯www
  • Sad~檢討文就不發了，反正都知道我自己的問題出在那OwO