2022-SZUACM招新 训练赛2
https://vjudge.net/contest/544906#overview
下午打了一下，稍微记录一波，有一些蛮有意思的小题。
A - Array
https://codeforces.com/problemset/problem/57/C
这是组合数学的一个小模型。
由于对组合数学的理解不够，讲不出来（感觉非常的抽象啊），这里贴一个洛谷的题姐
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5, p = 1000000007;
ll n, ans;
ll fact[N], infact[N];
ll qmi(ll a, ll k) {
ll ans = 1;
while (k) {
if (k & 1) ans = ans * a % p;
k >>= 1;
a = a * a % p;
}
return ans;
}
int main () {
cin >> n;
ll fz = 1, fm = 1;
for (int i = 1; i < n; i++) (fm *= i) %= p;
for (int i = n + 1; i < 2 * n; i++) (fz *= i) %= p;
cout << (2 * fz * qmi (fm, p - 2) - n + p) % p;
//cout << (2 * C (2 * n - 1, n) - n) % p;
}
//推式子
//去重
B - Divisible Substring
https://atcoder.jp/contests/abc158/tasks/abc158_e?lang=en
这个也没想到，是一个很巧妙的转化。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10005;
ll ans, cnt[N];
void solve () {
int n, p;
string s;
cin >> n >> p >> s;
if (p == 2 || p == 5) {
for (int i = 0; i < s.size (); i++) {
if ((s[i] - '0') % p == 0) ans += (i + 1);
}
}
else {
ll dx = 1, sum = 0;
cnt[0] = 1; //init模数0因子
for (int i = s.size () - 1; i >= 0; i--) {
sum += dx * (s[i] - '0');
sum %= p;
ans += cnt[sum];
cnt[sum] ++;
dx = (dx * 10) % p;
//cout << sum << ' ';
}
}
cout << ans << endl;
}
int main () {
solve ();
}
//串s,t末尾数字余数相等，且一个是另一个的末尾，则他们相减后得到的串符合要求
//(a+x)-(b+x)=10^x+c
//2,5是例外(是10的因子)
C - Can you answer these queries III
https://www.spoj.com/problems/GSS3/en/
线段树维护区间最大和。
比较典的一道题，按照这篇题解图中描述的去分情况维护即可。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
int n, m, k, x, y;
int a[N];
struct tree{
int l, r, sum;
int lmax, rmax, tmax;//最大前后缀和, 最大子段和
}st[4 * N];
void pushup (tree &u, tree &l, tree &r){
u.sum = l.sum + r.sum;
u.lmax = max (l.lmax, l.sum + r.lmax);//左半段中的最大 or 左半段和+右半段中的最大
u.rmax = max (r.rmax, r.sum + l.rmax);//右半段中的最大 or 右半段和+左半段中的最大
u.tmax = max (max (l.tmax, r.tmax), l.rmax + r.lmax);//左半段中的最大 or 右半段中的最大 or 左半段后缀和+右半段前缀和
}
void pushup (int u){
pushup (st[u], st[u << 1], st[u << 1 | 1]);
}
void build (int u, int l, int r){
if (l == r){
st[u] = {l, r, a[r], a[r], a[r], a[r]};
return;
}
st[u] ={l, r};
int mid = l + r >> 1;
build (u << 1, l, mid), build (u << 1 | 1, mid + 1, r);
pushup (u);
}
void modify (int u, int x, int v){
if (st[u].l == x && st[u].r == x)
st[u] = {x, x, v, v, v, v};
else{
int mid = st[u].l + st[u].r >> 1;
if (x <= mid)
modify (u << 1, x, v);
else
modify (u << 1 | 1, x, v);
pushup (u);
}
}
tree query (int u, int l, int r){
if (st[u].l >= l && st[u].r <= r)
return st[u];
int mid = st[u].l + st[u].r >> 1;
if (r <= mid)
return query (u << 1, l, r);
else if (l > mid)
return query (u << 1 | 1, l, r);
else{
auto le = query (u << 1, l, r);
auto ri = query (u << 1 | 1, l, r);
tree ans;
pushup (ans, le, ri);
return ans;
}
}
int main(){
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
build (1, 1, n);
cin >> m;
while (m --){
cin >> k >> x >> y;
if (k == 0) modify (1, x, y);
else{
if (x > y) swap (x, y);
cout << query (1, x, y).tmax << endl;
}
}
}
//维护和
//对于横跨两区间的最大子段和 = 左子区间最大后缀 + 右子区间最大前缀
D - Nun Heh Heh Aaaaaaaaaaa
https://acm.hdu.edu.cn/showproblem.php?pid=7131
以为是什么数据结构结果是比较典型的线性dp（啊果然dp水平还是太烂了www）
注：为了方便书写，以下字符串默认下标从1开始。
定义状态 \(f_{i,j}\)，表示当前串的前 \(i\) 位中匹配上 \(t\) 的第 \(j\) 为的数量。同时利用 \(a_i\) 记录当前串的 \(i\) 位以后有 \(a_i\) 个字符 '\(a\)'。
转移：\(f_{i,j}=f_{i-1,j}\)（无条件），若匹配上 \(t\) 的第 \(j\) 位则有 \(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\)（多匹配了一位）
最终答案就是 \(\sum_{i=1}^n f_{i,8}*(2^{a_i}-1)\)，当且仅当 \(s_i=\)'\(h\)'
进行一些细节的解释：因为当前位是 \(h\)，则保证了末位（第9位匹配）匹配上，因此是乘上 \(f_{i,8}\)；至于后面字符 \(a\) 的贡献，手推一下也可以得出结论：
然后注意随时取模，防止爆了。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 998244353;
ll f[N][15], a[N], pw[N];
string t = "$nunhehheh";
void solve () {
string s;
cin >> s;
int n = s.size ();
s = ' ' + s;
for (int i = 0; i <= n + 1; i++) { //init
a[i] = 0, f[i][0] = 1; //一个也没匹配上的个数是1
for (int j = 1; j <= 9; j++) f[i][j] = 0;
}
for (int i = n; i; i--) {
a[i] = a[i + 1];
if (s[i] == 'a') (a[i] += 1) %= mod;
}
//for (int i = 1; i <= n; i++) cout << a[i] << ' ';cout << endl;
//match
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 9; j++) {
f[i][j] = f[i-1][j] % mod;
if (s[i] == t[j]) (f[i][j] += f[i-1][j-1]) %= mod;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == 'h') (ans += f[i][8] * (pw[a[i]] - 1) % mod) %= mod;
}
cout << ans << endl;
}
int main () {
pw[0] = 1;
for (int i = 1; i <= 1e5; i++) pw[i] = pw[i-1] * 2 % mod;
int t;
cin >> t;
while (t --) solve ();
}
//求子序列p的个数
//dp[i][j]:s的第i位和p匹配到j
//a[i]:i后面有a[i]个'a'
//ans += dp[i][8] * (2^a[i]-1)
E - GCD
https://acm.hdu.edu.cn/showproblem.php?pid=2588
数论小题，关键在于转化。
题目是要找到 \(1-n\) 中满足的 \(gcd(n,x)\geq m\) 的数 \(x\) 的个数。
分析
首先这个 \(x\) 一定与 \(n\) 有共同的因子，则设 \(gcd(n,x)=d\)，有 \(n=pd, x=qd\) 且 \(p,q\) 互质。
因此问题转化为，对于 \(n\) 的 \(\geq m\) 的因子 \(d\)，求 \(\leq p=\frac nd\) 的数的个数。不难发现，这符合欧拉函数的定义（即求 \(\phi(\frac nd)\)）：
（摘自oi-wiki）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll phi (ll n) {
ll ans = n;
for (ll i = 2; i*i <= n; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1); //*(1-1/i)
while (n % i == 0) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1); //还剩下就再乘
return ans;
}
void solve () {
ll n, m;
cin >> n >> m;
// for (ll i = 1; i <= n; i++) cout << __gcd (i, n) << ' ';
// cout << endl;
ll ans = 0;
for (ll i = 1; i * i <= n; i++) {
if (n % i) continue;
if (i * i == n && i >= m) ans += phi (i);
else if (i * i < n) {
if (i >= m) ans += phi (n / i);
if (n / i >= m) ans += phi (i);
}
}
cout << ans << endl;
}
int main () {
int t;
cin >> t;
while (t --) solve ();
}
F - 123-sequence
https://codeforces.com/problemset/problem/52/A
签到
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N], n;
int main () {
map<int, int> mp;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
mp[x] ++;
}
cout << n - max ({mp[1], mp[2], mp[3]});
}