Dashboard - 2024 CCPC Liaoning Provincial Contest - Codeforces

過題難度

B A J C L E?G

銅獎? 4 953

銀獎? 6 991

金獎? 8 1664

B：

模擬題

// Code Start Here	string s;cin >> s;reverse(all(s));cout << s << endl;

A：很明顯的哈希一下，然后去重即可，這里set和map都可以

// Code Start Here	string s;getline(cin , s);for(int i = 0;i<sz(s);i++){if((s[i] >= 'A' && s[i] <= 'Z')){s[i] += 32;}}set<string> st;for(int i = 0;i<sz(s);i++){if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')){int j = i;string t = "";while((s[j] >= 'a' && s[j] <= 'z') || (s[j] >= 'A' && s[j] <= 'Z')) t += s[j++];i = j;st.insert(t);}}int q;cin >> q;while(q--){string t;cin >> t;if(st.find(t) != st.end())st.erase(t);}
//	for(auto i : st)cout << i <<" ";cout << sz(st) << endl;

J

模擬前后兩次的人數

// Code Start Here	int n;cin >> n;int a , b , c;cin >> a >> b >> c;vector<int> x(n + 1) , y (n + 1);for(int i = 1;i<=n;i++)cin >> x[i] >> y[i];int d;cin >> d;int before = 0 , after = 0;for(int i = 1;i<=n;i++){if(x[i] + y[i] >= c){before++;}}for(int i = 1;i<=n;i++) x[i] = min(a , x[i] + d);for(int i = 1;i<=n;i++){if(x[i] + y[i] >= c){after++;}}cout <<after - before << endl;

C

DFS跑一遍每個插座和插排的功率，然后貪心跑一遍判斷即可

// Code Start Here	int n;cin >> n;vector<int> w(n + 1);vector<vector<int>> g(n + 1);vector<int> f(n + 1);for(int i = 1;i<=n;i++){int u;cin >> u >> w[i];g[u].push_back(i);}w[0] = 2200;auto dfs = [&](auto &&self , int u)->void{if(g[u].empty())f[u] += w[u];for(auto v : g[u]){self(self,v);f[u] += f[v];}};dfs(dfs , 0);vector<int> e , ee;for(int i = 0;i<=n;i++){if(!g[i].empty()){e.push_back(f[i]);ee.push_back(w[i]);}}sort(all(e)) , sort(all(ee));bool flag = true;for(int i = 0;i<sz(e);i++){if(e[i] > ee[i] || e[i] > w[0])flag = false;}cout << ( flag ? "YES" : "NO") <<endl;

L

題意：

2024年起，每平年 +1 層數。但有特殊規則，年份必須是 4 的倍數，且不能是 100 的倍數但不是 10000 的倍數，否則是平年。到第 k 層的時候，是哪一年

思路：

可以不斷貪心，更簡單的方法是二分年份，然后找第k個合法年份。

計算到年份 x 之間，有多少個平年。遍歷 i = 4, 400, 40000, ... 逐個計算：x / i 表示小于等于 x 有多少個 i 的倍數（4, 400, 40000, ...）x / (25 * i) 表示去掉那些是100倍數但不是10000倍數的年數。x - sum 表示有效的龍之研習年份數量，看看是不是到達了第 n + 1533 個。這里的 1533 是因為：2024是第0層，到2024年底總共經歷了 2024 - 1533 = 491 個有效年份（實際上這1533是題目設定的初始偏移值，具體是為了校正年份起點和層數的關系）

// Code Start Here	int t;cin >> t;while(t--){int n;cin >> n;int l = 2025 , r = 2e18;auto check = [&](int x)->bool{int sum = 0;for(int i = 4;i<=x;i*= 100){sum += x / i - x / (25 * i);}return (x - sum) >= (n + 1533);};while(l <= r){int mid = l + r >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}cout << l << endl;}

E

一道大模擬

// Code Start Here	int t;cin >> t;auto solve = [&]()->void{int x, y; cin >> x >> y;if(x*y %4 !=0){cout << "NO\n";return ;}vector a(x+1, vector<int>(y+1, 0));auto yes = [&](){cout << "YES\n";for(int i=1; i<=x; ++i){for(int j=1; j<=y; ++j) cout << a[i][j] << " ";cout << endl;}};if(x % 4 == 0){int cnt = 1;for(int j=1; j<=y; j++){for(int i=1; i<=x; i+=4){a[i][j] = a[i+1][j] = a[i+2][j] = a[i+3][j] = cnt++;}}yes();return;}if(y % 4 ==0){int cnt=1;for(int i=1; i<=x; i++){for(int j=1; j<=y; j+=4){a[i][j] = a[i][j+1] = a[i][j+2] = a[i][j+3] = cnt++;}}yes();return;}if(x%2 ==0 && y%2 ==0){if(y >=6 && (y-6)%4 ==0){for(int i=1; i<=x; i+=2){int temp = (i/2)*((y-6)/4*2 +3) +1;a[i][1] = a[i][2] = a[i][3] = a[i+1][1] = temp;a[i][4] = a[i][5] = a[i][6] = a[i+1][6] = temp+1;a[i+1][2] = a[i+1][3] = a[i+1][4] = a[i+1][5] = temp+2;int cnt = temp+3;for(int j=7; j<=y; j+=4){a[i][j] = a[i][j+1] = a[i][j+2] = a[i][j+3] = cnt++;a[i+1][j] = a[i+1][j+1] = a[i+1][j+2] = a[i+1][j+3] = cnt++;}}yes();return;}else if(x >=6 && (x-6)%4 ==0){for(int j=1; j<=y; j+=2){int temp = (j/2)*((x-6)/4*2 +3) +1;a[1][j] = a[2][j] = a[3][j] = a[1][j+1] = temp;a[4][j] = a[5][j] = a[6][j] = a[6][j+1] = temp+1;a[2][j+1] = a[3][j+1] = a[4][j+1] = a[5][j+1] = temp+2;int cnt = temp+3;for(int i=7; i<=x; i+=4){a[i][j] = a[i+1][j] = a[i+2][j] = a[i+3][j] = cnt++;a[i][j+1] = a[i+1][j+1] = a[i+2][j+1] = a[i+3][j+1] = cnt++;}}yes();return;}}cout << "NO\n";};while(t--){solve();}

G

題意：給定一個長度為n的數組，求存在多少個子數組滿足最大 值出現至少k 次。

思路：對于每一個位置i，我們可以考慮其作為第一個最大值時對答案的貢獻，即能保證不重不漏的計數。不妨設：Li 為以 i 為起點，從右往左第一個比ai 大的元素的位置；Ri 為以 i 為起點，從左往右第一個比ai 大的元素的位置；lsti 為相對于當前位置 i，ai 上一次出現的位置；nxti 為相對于當前位置 i，ai 第 k 次出現的位置。

其中，Li 和Ri 可以通過單調棧計算，lsti 和nxti 則可以通過對值域開桶，根據每個位置在對應的桶中的相對位置進行計算。對于當前位置i 作為第一個最大值的數組：其左端點的合法范圍是(max(lsti,Li),i]，其右端點的合法范圍是[i,min(nxti,Ri))。最后，統計每個位置作為第一個最大值時的貢獻，即能求出結果

// Code Start Here	int t;cin >> t;while(t--){int n , k;cin >> n >> k;vector<int> a(n + 1) , l (n + 1) , r(n + 1);vector<vector<int>> num(n + 1);for(int i = 1;i<=n;i++){cin >> a[i];num[a[i]].push_back(i);}int ans = 0;vector<int> left , right;for(int i = 1;i<=n;i++){while(!left.empty() && a[left.back()] <=a[i])left.pop_back();if(left.empty())l[i] = 1;else l[i] = left.back() + 1;left.push_back(i);}for(int i = n;i>=1;i--){while(!right.empty() && a[right.back()] <= a[i])right.pop_back();if(right.empty())r[i] = n;else r[i] = right.back() - 1;right.push_back(i);}for(int i = n;i>=1;i--){if(sz(num[i]) >= k){for(int j = 0;j + k - 1 < sz(num[i]);j++){int p = num[i][j] , q = num[i][j + k - 1];int l_ = l[p] , r_ = r[p];if(j >= 1) l_ = max(l_ , num[i][j - 1] + 1);if(r_ >= q)ans += (p - l_ + 1) *(r_ - q + 1);}}	}cout << ans << endl;}