牛客寒假训练营1
A-九小时九个人九扇门_2022牛客寒假算法基础集训营1 (nowcoder.com)
结论：一个数的数字根等于这个数对9取模的结果，特别地，取模得0则数字根为9
证明：
假设一个数为abcd, 那么：abcd % 9 = (a * 1000 + b * 100 + c * 10 + d * 1) % 9由取模的性质我们可以知道:= ((a % 9) * (1000 % 9) + (b % 9) * (100 % 9) + (c % 9) * (10 % 9) + (d % 9) * (1 % 9)) % 9= (a + b + c + d) % 9
第一眼没看出来是DP，以为是个组合数，没想到居然是一个01背包变种问题，太菜了太菜了
#include#define x first#define y secondusing namespace std;typedef long long LL;typedef pair PII;const int N = 100010, mod = 998244353;int t, n, m;int dp[N][10]; // 状态表示f[i, j]: 考虑前i个人，数字根是j的方案数int main(void){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> m; m %= 9; dp[i][m]++; for (int j = 0; j < 9; j++) { // 这一层数字根(j + m) % 9的方案数加上上一层数字根为j的方案数 dp[i][(j + m) % 9] = (dp[i][(j + m) % 9] + dp[i - 1][j]) % mod; // 这一层的j加上上一层j的方案数 dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod; } } for (int i = 1; i < 9; i++) cout << dp[n][i] << " "; cout << dp[n][0] << endl ; // 9的情况单独输出 return 0;}
B-炸鸡块君与FIFA22_2022牛客寒假算法基础集训营1 (nowcoder.com)
倍增预处理or线段树维护区间信息
先预处理出来初始分%3的各个情况下，从某局开始进行多少局的得分情况，然后利用二进制来修改答案即可
#include#define x first#define y secondusing namespace std;typedef long long LL;typedef pair PII;const int N = 200010, M = 21; // 开21是因为2^21保证足够大int t, n, m;string c;int f[3][N][M]; // f[k][i][j]，初始分%3是k的情况下，从第i局开始，进行2^j局的得分int main(void){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> c; // 预处理 for (int i = 0; i < n; i++) { if (c[i] == 'W') // 如果是赢，不管初始分多少，在第i局都是加分 f[0][i][0] = f[1][i][0] = f[2][i][0] = 1; else if (c[i] == 'L') // 如果是输，初始分%3得0得情况是不扣分的，和平局情况一样都是0 f[1][i][0] = f[2][i][0] = -1; } for (int j = 1; (1 << j) <= n; j++) // 枚举从第i局开始进行2^j局 for (int i = 0; i + (1 << j) - 1 < n; i++) // 枚举i，注意不要越界 for (int k = 0; k < 3; k++) // 枚举初始分 // 状态转移可以这样理解，往后进行2^j可以看作先进行2^(j-1)局，再进行2^(j-1)局 // f[k][i][j - 1]表示前一半的得分 // f[(k + f[k][i][j - 1]) % 3][i + (1 << (j - 1))][j - 1]表示后一半的得分 f[k][i][j] = f[k][i][j - 1] + f[(k + f[k][i][j - 1]) % 3][i + (1 << (j - 1))][j - 1]; while (m--) { int l, r, s; cin >> l >> r >> s; l--, r--; // 因为我们下标是从0开始的，所以需要-- int len = r - l + 1, y = 0; // len表示区间长度，y是用来枚举二进制 while (l <= r) { if ((len >> y) & 1) // 寻找每一位上的1 { s = s + f[s % 3][l][y]; // 修改分数 l = l + (1 << y); // 每次都进行2^y局 } y++; } cout << s << endl ; } return 0;}
C-Baby’s first attempt on CPU_2022牛客寒假算法基础集训营1 (nowcoder.com)
简单模拟
理解题意，模拟一下就可以了
#includeusing namespace std; int main(){ int n, x; cin >> n; vector f(n); // f[i] 表示第i个语句的最终位置 f[0] = 1; for (int i = 0; i < n; i++) { if (i) f[i] = f[i - 1] + 1; for (int j = 1; j <= 3; j++) { cin >> x; if (x) f[i] = max(f[i], f[i - j] + 4); } } cout << f.back() - n << endl ; // 最后一条语句的位置减去初始的位置就是多插入的空语句数量 return 0;}
D-牛牛做数论_2022牛客寒假算法基础集训营1 (nowcoder.com)
简单数论
结论：第一个问题的答案是最大连续质因子乘积，第二个问题的答案是最大质数
证明：
首先明确一个概念：任何数字都可以分解成质数的乘积，也就是质因子所以第一个问题我们只需要找到一个数，它包含的质因子最多即可，也就是最大连续质因子乘积第二个就比较容易了，因为质数的因子只有1和本身，所以它和其他数都肯定是互质的，所以答案是最大质数
#includeusing namespace std;int t, n;int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; // 这些质数乘积已经超过数据范围了bool is_primes(int x){ if (x < 2) return false; for (int i = 2; i <= x / i; i++) if (x % i == 0) return false; return true;}int main(void){ cin >> t; while (t--) { cin >> n; if (n == 1) { cout << -1 << endl ; continue; } long long x = 1; for (int i = 0; x * primes[i] <= n; i++) // 找到最大连续质因子乘积 x *= primes[i]; cout << x << " "; while (!is_primes(n)) n--; // 找到最大质数 cout << n << endl ; } return 0;}
E-炸鸡块君的高中回忆_2022牛客寒假算法基础集训营1 (nowcoder.com)
推公式
结论： ( n + m − 3 ) / ( m − 1 ) ∗ 2 − 1 (n + m - 3) / (m - 1) * 2 - 1 (n+m−3)/(m−1)∗2−1
证明：
首先找规律：进一次校门：m进两次校门：m + m - 1进三次校门：m + 2 * (m - 1)···进k次校门：m + (k - 1) * (m - 1) 依题意可得不等式：m + (k - 1) * (m - 1) >= n两边同时减1：m - 1 + (k - 1) * (m - 1) >= n - 1化简可得：k * (m - 1) >= n - 1所以 k >= (n - 1) / (m - 1) 注意是上取整，保证全部都走完最终公式就是: (n - 1 + (m - 1) - 1) / (m - 1) * 2 + 1
#includeusing namespace std;int main(void){ int t; cin >> t; while (t--) { int n, m; cin >> n >> m; if (n == m) cout << 1 << endl ; else if (m == 1) cout << -1 << endl ; else cout << (n + m - 3) / (m - 1) * 2 - 1 << endl ; } return 0;}
F-中位数切分_2022牛客寒假算法基础集训营1 (nowcoder.com)
思维题
结论：统计大于等于m的个数 c n t 1 cnt1 cnt1和小于m的个数 c n t 2 cnt2 cnt2，如果 c n t 1 − c n t 2 cnt1-cnt2 cnt1−cnt2小于等于0，则无解，反之则为答案
证明：
其实也很容易能理解：最理想的情况肯定是一个区间的所有数字都大于等于m，这样中位数一定大于等于m，但是这个情况我们肯定是把每个数字都单独分为一个区间，因为这样子可以分成最多个满足条件的区间而最极限的情况呢，就是前半区间是小于m的，后半区间是大于等于m的，那么就可以看作是除了中位数外左右两边的数字相互抵消了，因此也就是为什么答案是cnt1 - cnt2了
#includeusing namespace std;int main(void){ int t; cin >> t; while (t--) { int n, m, cnt1 = 0, cnt2; cin >> n >> m; for (int i = 0; i < n; i++) { int x; cin >> x; if (x >= m) cnt1++; } cnt2 = n - cnt1; if (cnt1 - cnt2 <= 0) cout << -1 << endl ; else cout << cnt1 - cnt2 << endl ; } return 0;}
G-ACM is all you need_2022牛客寒假算法基础集训营1 (nowcoder.com)
差分前缀和
做法：我们对于从 2 ≤ i ≤ n − 1 2 ≤i≤n-1 2≤i≤n−1的数求出满足条件的 b b b的范围 [ l , r ] [l, r] [l,r]，然后将问题转换成给出 n − 2 n-2 n−2个区间，找出覆盖区域最多的最小点，很容易联想到差分
#includeusing namespace std;const int N = 100010;int t, n, x;int a[N];int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> t; while (t--) { cin >> n; map mp; for(int i = 1; i <= n; i++) cin >> a[i]; int ans = 0; for(int i = 2; i < n; i++) { if (a[i] == a[i - 1] || a[i] == a[i + 1]) continue; if (a[i] < a[i - 1] && a[i] < a[i + 1]) { ans++; mp[(a[i] + min(a[i - 1], a[i + 1]) + 1) / 2] ++; } else if (a[i] > a[i - 1] && a[i] > a[i + 1]) { mp[(a[i] + max(a[i - 1], a[i + 1])) / 2 + 1]--; } else { mp[(a[i] + max(a[i - 1], a[i + 1]) + 1) / 2]++; mp[(a[i] + min(a[i - 1], a[i + 1]))/ 2 + 1]--; } } int res = 0, tot = 0; for (auto i : mp) { tot += i.second; res = max(res, tot); } cout << ans - res << endl ; } return 0;}
H-牛牛看云_2022牛客寒假算法基础集训营1 (nowcoder.com)
思维题
看着 1 e 6 1e6 1e6数据范围很大，但是每个数都才 1 e 3 1e3 1e3而已，记录每个数字的个数，推出等价公式跑个双循环即可
#includeusing namespace std;typedef long long LL;const int N = 1010;LL cnt[N];int n, x;int main(){ cin >> n; for (int i = 0; i < n; i++) { cin >> x; cnt[x]++; } LL res = 0; for (int i = 0; i <= 1000; i++) { for (int j = i; j <= 1000; j++) { if (i == j) res += (cnt[i] + cnt[i] * (cnt[i] - 1) / 2) * abs(i + i - 1000); else res += cnt[i] * cnt[j] * abs(i + j - 1000); } } cout << res << endl ; return 0;}
I-B站与各唱各的_2022牛客寒假算法基础集训营1 (nowcoder.com)
期望+逆元
结论： m ∗ ( 2 n − 2 ) / 2 n m * (2^n - 2) / 2^n m∗(2n−2)/2n
因为句子和句子之间是没有办法影响的，所以只需要求出一个话的期望乘上数量即可
除法取模需要用到逆元，注意 1 e 9 + 7 1e9+7 1e9+7是一个质数，所以直接用快速幂求即可，不需要用拓展欧几里得
#includeusing namespace std;typedef long long LL;const int mod = 1e9 + 7;LL t, n, m;LL qmi(LL a, LL b, LL p){ LL res = 1 % p; while (b) { if (b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res;}int main(void){ cin >> t; while (t--) { cin >> n >> m; LL k = qmi(2, n, mod); cout << (m * (k - 2 + mod) % mod * qmi(k, mod - 2, mod)) % mod << endl ; } return 0;}
J-小朋友做游戏_2022牛客寒假算法基础集训营1 (nowcoder.com)
简单模拟
#include#define x first#define y secondusing namespace std;int main(void){ int t; cin >> t; while (t--) { int a, b, n, x; vector> vec; cin >> a >> b >> n; for (int i = 0; i < a + b; i++) { cin >> x; if (i < a) vec.push_back({x, 0}); else vec.push_back({x, 1}); } if (a < (n + 1) / 2) cout << -1 << endl ; else { sort(vec.begin(), vec.end()); reverse(vec.begin(), vec.end()); int cnt = 0, res = 0, temp = n; for (int i = 0; i < n; i++) { if (!vec[i].y) res += vec[i].x; else if (cnt < temp / 2) { res += vec[i].x; cnt++; } else n++; } cout << res << endl ; } } return 0;}
K-冒险公社_2022牛客寒假算法基础集训营1 (nowcoder.com)
DP问题
f [ i , j , k , l ] f[i, j,k,l] f[i,j,k,l] 表示考虑前 i i i个字符，分别放了 j , k , l ( j , k , l ∈ 0 , 1 , 2 ) j,k,l(j,k,l∈{0,1,2}) j,k,l(j,k,l∈0,1,2)时的最大绿岛数
优化成二维 f [ i , j ] f[i, j] f[i,j]就是用 j j j的三进制来表示 j , k , l j,k,l j,k,l
#include using namespace std;const int N = 100010, M = 27, INF = 1e6;int dp[N][M], n;char str[N];int cnt(int x) { int g = (x % 3 == 0) + ((x / 3) % 3 == 0) + ((x / 9) % 3 == 0); int r = (x % 3 == 2) + ((x / 3) % 3 == 2) + ((x / 9) % 3 == 2); return g - r;}int main(){ cin >> n >> str + 1; for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) dp[i][j] = -INF; for(int i = 0; i < M; i++) { if(str[3] == 'G' && cnt(i) <= 0) continue; if(str[3] == 'B' && cnt(i) != 0) continue; if(str[3] == 'R' && cnt(i) >= 0) continue; dp[3][i] = (i % 3 == 0) + ((i / 3) % 3 == 0) + ((i / 9) % 3 == 0); } for(int i = 4; i <= n; i++) for(int j = 0; j < M; j++) { if(str[i] == 'G' && cnt(j) <= 0) continue; if(str[i] == 'B' && cnt(j) != 0) continue; if(str[i] == 'R' && cnt(j) >= 0) continue; for(int k = 0; k < M; k++) if(k % 3 == (j / 3) % 3 && (k / 3) % 3 == (j / 9) % 3) dp[i][j] = max(dp[i][j], dp[i - 1][k] + (j % 3 == 0)); } int ans = -INF; for(int i = 0; i < M; i++) ans = max(ans, dp[n][i]); if (ans < 0) cout << -1 << endl ; else cout << ans << endl ; return 0;}
L-牛牛学走路_2022牛客寒假算法基础集训营1 (nowcoder.com)
简单模拟
#includeusing namespace std;int t, n, x, y;double res;string s;int main(void){ cin >> t; while (t--) { cin >> n >> s; res = 0; x = 0, y = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == 'U') y++; else if (s[i] == 'D') y--; else if (s[i] == 'R') x++; else x--; res = max(res, sqrt(x * x + y * y)); } printf("%.12fn", res); } return 0;}