Dashboard - 2023 CCPC Henan Provincial Collegiate Programming Contest - Codeforces

過題難度：A H F G B K E

銅獎： 2? 339

銀獎： 3? 318

金獎： 5? 523

A:

直接模擬

// Code Start Here	int t;cin >> t;while(t--){string s;cin >> s;set<char> seen;bool found = false;		for (int i = 1; i < sz(s); ++i) {bool ok = true;seen.clear();for (int j = 0; j < i; ++j) {if (seen.count(s[j])) {ok = false;break;}seen.insert(s[j]);}if (!ok) continue;int l = i, r = sz(s) - 1;while (l < r) {if (s[l] != s[r]) {ok = false;break;}++l;--r;}if (ok) {found = true;break;}}cout << (found ? "HE\n" : "NaN\n");}

H

思路：我們發現0.5會進位，而距離0.5無窮左邊就會被舍去，因此最小的方式是分出來的盡量距離0.5差一點點，最多的就是0.5

// Code Start Here	int t;cin >> t;while(t--){int n , k;cin >> n >> k;if(k > 2 * n)cout << 0 << " " << 2 * n <<endl;else{int minv = (2 * n - k + 2) / 2;int maxv = minv + k - 1;cout << minv << " " << maxv << endl;}}

F

題意：

給定一個數列A從中選出 k 個數，計算：這些數的最大值-最小值，記作 max。這些數相鄰差值中的最小值，記作 min。要求使max×min 最小

思路：我們發現排序后，任意 k 個數如果不連續，選中其中的最大和最小值之差一定不會比連續的更小。同時，相鄰差值的最小值如果跳著選，差值可能會變大，而連續的差值是最穩定的。

對于連續的 k 個數，max=A[i+k?1]?A[i]。假設有k?1 個相鄰差值，存在差分數組 diff，使得diff[j]=A[j+1]?A[j]。連續區間 [i, i+k-1] 中，相鄰差值的最小值就是min=min(diff[i],diff[i+1],...,diff[i+k?2])。

因此我們可以遍歷所有可能的連續 k 個數區間，求：每個區間內max×min，然后取最小值

考慮到5e5的數據規模，我們使用單調隊列維護區間內差值的最小值。在O(1) 時間內取當前窗口最小值，且在移動窗口時自動維護單調性，效率是O(n)。

// Code Start Here	int n , k;cin >> n >> k;vector<int> a(n);for(int i = 0;i<n;i++)cin >> a[i];sort(all(a));vector<int> diff(n-1);for(int i = 0;i<n-1;i++)diff[i] = a[i+1] - a[i];int ans =  1e18;deque<int> dq;for(int i = 0;i<n;i++){if(i > 0){while(!dq.empty() && diff[i-1] <= diff[dq.back()])dq.pop_back();dq.push_back(i - 1);}if(i >= k){if (!dq.empty() && dq.front() < i - k)dq.pop_front();}if(i >= k-1){int max_v = a[i] - a[i-k+1];int min_v = 1e9;if(k > 1 && !dq.empty() )min_v = diff[dq.front()];if(k == 1)min_v = 1e9;ans = min(ans , 1LL *max_v * min_v);}}cout << ans << endl;return 0;

G：

一道超級大模擬題，考慮到個體的特殊性，我們可以對底數和冪數分別開兩個數組來映射，使用的時候取出即可

char a[][100] = {"",".................................................................................",".................................................................................",".0000000.......1.2222222.3333333.4.....4.5555555.6666666.7777777.8888888.9999999.",".0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",".0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",".0.....0.......1.2222222.3333333.4444444.5555555.6666666.......7.8888888.9999999.",".0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",".0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",".0000000.......1.2222222.3333333.......4.5555555.6666666.......7.8888888.9999999.",".................................................................................",
};char b[][100] = {"",".............................................................",".00000.....1.22222.33333.4...4.55555.66666.77777.88888.99999.",".0...0.....1.....2.....3.4...4.5.....6.........7.8...8.9...9.",".0...0.....1.22222.33333.44444.55555.66666.....7.88888.99999.",".0...0.....1.2.........3.....4.....5.6...6.....7.8...8.....9.",".00000.....1.22222.33333.....4.55555.66666.....7.88888.99999.",".............................................................",".............................................................",".............................................................",".............................................................",
};char c[][100] = {"",".................................",".................................",".........IIIIIII.N.....N.FFFFFFF.","............I....NN....N.F.......",".=======....I....N.N...N.F.......","............I....N..N..N.FFFFFFF.",".=======....I....N...N.N.F.......","............I....N....NN.F.......",".........IIIIIII.N.....N.F.......",".................................",
};char ans[20][1000];
int tot;void add(ll x, int d){stack<int> q;if (x == 0) q.push(0);while (x) {q.push(x % 10);x /= 10;}while (!q.empty()) {int top = q.top();for (int i = 1; i <= 10; i++) {if (d == 1)for (int j = tot, k = top * 8; j < tot + 8; j++, k++)ans[i][j] = a[i][k];elsefor (int j = tot, k = top * 6; j < tot + 6; j++, k++)ans[i][j] = b[i][k];}if (d == 1) tot += 8;else tot += 6;q.pop();}
}void INV(int l, int r){for (int i = 1; i <= 10; i++)for (int j = tot, tl = l; tl <= r; j++, tl++)ans[i][j] = c[i][tl];tot = tot + (r - l + 1);
}bool check(ll x, ll y){if (x == 1) return false;ll a = 1e18;for (ll i = 1; i <= y; i++) {if (a < x) return true;a /= x;}return false;
}ll qp(ll x, ll y){if (x == 1) return 1;ll t = 1;for (; y; y--) {if (t > 1e18 / x) return 1e18 + 1;t = t * x;}return t;
}
int main(){int T;cin >> T;cin.ignore();for (int t = 0; t < T; t++) {string s;getline(cin, s);ll x = 0, y = 0;size_t pos = s.find("^{");string xs = s.substr(0, pos);string ys = s.substr(pos + 2, s.size() - pos - 3);x = stoll(xs);y = stoll(ys);tot = 0;add(x, 1);add(y, 2);INV(0, 7);if (check(x, y))INV(8, 31);elseadd(qp(x, y), 1);for (int i = 1; i <= 10; i++) {ans[i][tot] = 0;printf("%s.\n", ans[i]);}printf("\n");}
}

B

發現對于ai>aj，i<j，那么i和j必須在同一個塊里。否則任意即可

所以可以直接劃分成最小的不可再分的幾個區間。從l到i，i是右端點當且僅當區間最大值小于等于后面的最小值。把這些右端點標記一下，滿足答案的必須滿足是倍數

預處理一下后綴，再暴力掃一遍倍數即可

// Code Start Here	int n;cin >> n;vector<int> a(n+10) , m(n+10) , f(n+10);for(int i = 1;i<=n;i++)cin >> a[i];m[n+1] = a[n];for(int i = n;i>=1;i--)m[i] = min(m[i+1],a[i]);int max_val = 0;for(int i = 1;i<=n;i++){max_val = max(max_val , a[i]);if(max_val <= m[i + 1] || i == n){f[i] = 1;max_val = 0;}}int ans = 0;for(int i = 1;i<=n;i++){ans ++;for(int j = i;j<=n;j+=i){if(f[j] == 0){ans--;break;}}}cout << ans <<endl;

K

題意：構造一個序列使得相鄰兩個數差的絕對值為質數

對于n < 10可以暴力枚舉，對于n > 10

若n為奇數，可以1 3 5 ... n-2 .. n .. n-3 .. n-5 .. 6 4 2

若n為偶數，可以1 3 5 .. n-3? n n-2 ...6 4 2

// Code Start Here	
int n;cin >> n;
switch (n) {
case 1: case 2: case 3: case 4:cout << "-1";break;
case 5:cout << "5 3 1 4 2";break;
case 6:cout << "5 3 1 6 4 2";break;
case 7:cout << "6 3 5 2 7 4 1";break;
case 8:cout << "6 3 8 5 2 7 4 1";break;
case 9:cout << "1 3 8 5 7 2 9 6 4";break;
default:if (n % 2) {for (int i = 4; i <= n; i += 2) {cout << i << ' ';if (n - 7 == i) cout << n - 2 << ' ';if (n - 5 == i) cout << n << ' ';}for (int i = n - 4; i >= 1; i -= 2) {cout << i << ' ';if (i == 7) cout << "2 ";}} else {for (int i = 4; i <= n; i += 2) {cout << i << ' ';if (n - 6 == i) cout << n - 1 << ' ';}for (int i = n - 3; i >= 1; i -= 2) {cout << i << ' ';if (i == 7) cout << "2 ";}}
}

E

考慮到可以使用KMP算法來計算最大前后綴，我們跑一遍KMP然后對ne數組去一個最大值即可，當最大值大于 50就可以考慮是錯的

// Code Start Here	string s;cin >> s;vector<int> ne(sz(s)+10 , 0);for(int i = 1;i<sz(s);i++){int j = ne[i - 1];while(j && s[i] != s[j]){j = ne[j - 1];}if(s[j] == s[i])j++;ne[i] = j;if(ne[i] >= 50){cout <<"No" << endl;return 0;}}cout <<"Yes" <<endl;