题意:构造一个 $n$ 位数 $s$ 使其满足:$s$ 为正数,每一位不等于零,$s$ 不被每一位整除。
思路:就构造就行了,也没啥可说的。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define fast ios::sync_with_stdio(false) #define mset(a, n) memset(a, n, sizeof(a)) #define forn(i, n) for (int i = 0; i < (n); ++i) #define forab(i, a, b) for (int i = (a); i <= (b); ++i) #define forba(i, b, a) for (int i = (b); i >= (a); --i) #define db double #define ll long long #define endl ' ' #define fi first #define se second using namespace std; typedef pair<int, int> P; inline int lowbit(int x) { return x & (-x); } int main(){ fast; int t; cin >> t; while (t--) { int n; cin >> n; if (n == 1){ cout << "-1 "; } else { cout << "8"; forn(i, n - 1){ cout << "9"; } cout << " "; } } return 0; }
题意:现有一个长度为 $n$ 的数列 $a$ ,定义数列 $x_{i} = max(0, a_{1}...a_{i-1})$,当 $i = 1$时,$x_{1} = 0$,另定义数列 $b_{i} = a_{i} - x_{i}$。目前给定数列 $b$,求数列 $a$。
思路:维护当前最大值向后遍历就行了。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define fast ios::sync_with_stdio(false) #define mset(a, n) memset(a, n, sizeof(a)) #define forn(i, n) for (int i = 0; i < (n); ++i) #define forab(i, a, b) for (int i = (a); i <= (b); ++i) #define forba(i, b, a) for (int i = (b); i >= (a); --i) #define db double #define ll long long #define endl ' ' #define fi first #define se second using namespace std; typedef pair<int, int> P; inline int lowbit(int x) { return x & (-x); } const int N = 2e5 + 5; ll b[N], ans[N], n; int main(){ fast; cin >> n; forab(i, 1, n){ cin >> b[i]; } ll maxx = -0x3f3f3f3f; ans[1] = b[1]; maxx = max(ans[1], maxx); forab(i, 2, n){ ans[i] = b[i] + maxx; maxx = max(maxx, ans[i]); } forab(i, 1, n){ cout << ans[i]; if (i != n) cout << " "; } cout << " "; return 0; }
题意:感觉题目稍微有点绕,给定一个 $1-n$ 上的全排列,将这个全排列分成不相交的 $k$ 段,定义该划分的 $value$ 为各段最大值的和,求该全排列所有可能划分中 $value$ 的最大值和达到最大值的划分情况个数。
思路:读懂题目之后思路其实就出来了,$1-n$ 的全排列分成 $k$ 段,显然最大的 $value$ 为前 $k$ 大的数之和,至于满足情况的个数,从小到大记录前 $k$ 个数出现的位置,每次将答案乘以相邻两数位置之差就是答案,这题两发才过,第一发我模数写错了真是***了。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define fast ios::sync_with_stdio(false) #define mset(a, n) memset(a, n, sizeof(a)) #define forn(i, n) for (int i = 0; i < (n); ++i) #define forab(i, a, b) for (int i = (a); i <= (b); ++i) #define forba(i, b, a) for (int i = (b); i >= (a); --i) #define db double #define ll long long #define endl ' ' #define fi first #define se second using namespace std; typedef pair<int, int> P; inline int lowbit(int x) { return x & (-x); } const ll MOD = 1e9 + 7; const ll mod = 998244353; vector<ll> v; int main(){ fast; ll n, k; cin >> n >> k; ll ans = 0, cnt = 1; forab(i, 1, n){ int x; cin >> x; if (x > (n - k)){ v.push_back(i); ans += x; } } for (int i = 0; i < v.size() - 1; ++i) { cnt = cnt * (v[i + 1] - v[i]) % mod; } cout << ans << " " << cnt << " "; return 0; }
D1. Prefix-Suffix Palindrome (Easy version)
题意:给定字符串 $s$,要求构造字符串 $t$ 满足:$t$ 的长度不大于 $s$且为回文串,并且由 $s$ 的一个前缀和一个后缀(可以为空串)加和构成。
思路:首先求出 $s$ 中前后缀相等部分,之后对于剩余子串求最长回文子串即可(Manacher即可,顺便更新了一下模板)。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define fast ios::sync_with_stdio(false) #define mset(a, n) memset(a, n, sizeof(a)) #define forn(i, n) for (int i = 0; i < (n); ++i) #define forab(i, a, b) for (int i = (a); i <= (b); ++i) #define forba(i, b, a) for (int i = (b); i >= (a); --i) #define db double #define ll long long #define endl ' ' #define fi first #define se second using namespace std; typedef pair<int, int> P; inline int lowbit(int x) { return x & (-x); } const ll MOD = 1e9 + 7; const ll mod = 998244353; string Manacher(string &s) { string t = "$#"; for (int i = 0; i < s.length(); ++i) { t += s[i]; t += '#'; } int ml = 0, p = 0, R = 0, M = 0; int len = t.length(); vector<int> P(len, 0); for (int i = 0; i < len; ++i) { P[i] = R > i ? min(P[2 * M - i], R - i) : 1; while (t[i + P[i]] == t[i - P[i]]) ++P[i]; if (i + P[i] > R) { R = i + P[i]; M = i; } if (ml < P[i] && (i - P[i]) / 2 == 0) { ml = P[i]; p = i; } } return s.substr((p - ml) / 2, ml - 1); } int main(){ fast; int t; cin >> t; while (t--) { string s; cin >> s; int l = 0, r = s.size() - 1; while (s[l] == s[r] && l < r) ++l, --r; string pre = s.substr(0, l), suf = s.substr(r + 1); //cout << pre << " " << suf << " "; string ss = s.substr(l, r - l + 1); string ex = Manacher(ss); reverse(ss.begin(), ss.end()); string exx = Manacher(ss); //cout << ss << " " << ex << " " << exx << " "; if (ex.length() > exx.length()) cout << pre + ex + suf << " "; else cout << pre + exx + suf << " "; } return 0; }
D2. Prefix-Suffix Palindrome (Hard version)
思路同上,一样的代码即可。