2020CCPC河南省赛题解

A. 班委竞选

签到题，模拟。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
//#define double long doubleusing namespace std;
typedef unsigned long long ULL ;
typedef pair<int,int> PII ;
typedef pair<double,double> PDD ;
const int N = 200010 , M = N * 2 , mod = 998244353 ;
int n , m ;
int a[20] , id[20] ;void solve()
{cin >> n >> m ;for(int i = 1 ; i <= n ; i ++) {int c , x ;cin >> c >> x ;if(x > a[c]) {a[c] = x ;id[c] = i ;}}for(int i = 1 ; i <= m ; i ++)cout << id[i] << " " ;cout << "\n" ;
}
signed main()
{std::ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;int t = 1 ;
//    cin >> t ;while (t --) solve() ;return 0;
}

C. 我得重新集结部队

模拟。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
//#define double long doubleusing namespace std;
typedef unsigned long long ULL ;
typedef pair<int,int> PII ;
typedef pair<double,double> PDD ;
const int N = 200010 , M = N * 2 , mod = 998244353 ;
int n ;
struct node{int id , x , y , h , c , r , f ;
}a[2010];void solve()
{cin >> n ;for(int i = 1 ; i <= n ; i ++) {cin >> a[i].id ;if(a[i].id == 1) {cin >> a[i].x >> a[i].y >> a[i].h ;a[i].f = 1 ;}else {cin >> a[i].x >> a[i].y >> a[i].c >> a[i].r ;a[i].f = 1 ;}}for(int i = 1 ; i <= n ; i ++) {if(a[i].id == 2) {int uid = -1 , dis = 1e18 ;for(int j = 1 ; j < i ; j ++)if(a[j].id == 1 && a[j].f == 1) {int s = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y) ;if(s < dis) {dis = s ;uid = j ;}}if(uid != -1) {int fx = a[uid].x , fy = a[uid].y , d = a[i].r * a[i].r , ct = a[i].c * 3 ;for(int j = 1 ; j < i ; j ++)if(a[j].id == 1 && a[j].f == 1) {int s = (fx - a[j].x) * (fx - a[j].x) + (fy - a[j].y) * (fy - a[j].y) ;if(s <= d) {if(a[j].h <= ct) {a[j].f = 0 ;}else {a[j].h -= ct ;a[i].f = 0 ;}}}}}}for(int i = 1 ; i <= n ; i ++)if(a[i].f) cout << "Yes\n" ;else cout << "No\n" ;
}
signed main()
{std::ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;int t = 1 ;
//    cin >> t ;while (t --) solve() ;return 0;
}

I. 太阳轰炸

这道题其实就是在问，投影的r+飞弹的r与轰炸范围的r的关系，如果前者大，所有飞弹都落在投影内，反之就需要去求落在投影内的概率，然后排列组合。用到了逆元，但不难。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 5000010, M = N * 2, mod = 1e9 + 7, md = 998244353;
int n, R1, R2, r, a, h;
int fa[N], infa[N], fu[N], fv[N];int qmi(int a, int k)
{int res = 1;while (k){if (k & 1)res = res * a % mod;a = a * a % mod;k >>= 1;}return res;
}
int C(int a, int b)
{if (b > a)return 0;return fa[a] * infa[b] % mod * infa[a - b] % mod;
}
void solve()
{cin >> n >> R1 >> R2 >> r >> a >> h;fa[0] = infa[0] = 1;for (int i = 1; i <= n; i++){fa[i] = i * fa[i - 1] % mod;infa[i] = infa[i - 1] * qmi(i, mod - 2) % mod;}int u = 1, v = 0;if (R2 > R1 + r){u = ((R1 + r) * (R1 + r) % mod) * qmi((R2 * R2) % mod, mod - 2) % mod;v = (R2 * R2 - (R1 + r) * (R1 + r)) % mod * qmi((R2 * R2) % mod, mod - 2) % mod;}else{if (n * a >= h)cout << "1\n";elsecout << "0\n";return;}int p = h / a;if (h % a)p++;fu[0] = fv[0] = 1;for (int i = 1; i <= n; i++)fu[i] = (fu[i - 1] * u) % mod;for (int i = 1; i <= n; i++)fv[i] = (fv[i - 1] * v) % mod;int res = 0;for (int i = p; i <= n; i++){int s = C(n, i) % mod;res = (res + s * fu[i] % mod * fv[n - i] % mod) % mod;}cout << res << "\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;//    cin >> t ;while (t--)solve();return 0;
}

E. 发通知

异或前缀和，想到了这一点这道题就很明了了，还需要一个离散化就ok了。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 500010, M = N * 2, mod = 1e9 + 7, md = 998244353;
int n, k, cnt;
int a[N], b[N], w[N], sw[N * 3], s[N * 3];void solve()
{cin >> n >> k;vector<int> q;map<int, int> mp;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> w[i];q.push_back(a[i]), q.push_back(b[i]), q.push_back(b[i] + 1);}sort(q.begin(), q.end());for (int i = 0; i < q.size(); i++)if (!mp.count(q[i]))mp[q[i]] = ++cnt;for (int i = 1; i <= n; i++){int l = mp[a[i]], r = mp[b[i]] + 1;s[l]++, s[r]--;sw[l] ^= w[i], sw[r] ^= w[i];}for (int i = 2; i <= cnt; i++)s[i] += s[i - 1], sw[i] ^= sw[i - 1];int res = -1;for (int i = 1; i <= cnt; i++)if (s[i] >= k)res = max(res, sw[i]);cout << res << "\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;//    cin >> t ;while (t--)solve();return 0;
}

B. 广告投放

首先要知道$x/a/b=x/(a\times b)$。
这样我们就可以预处理出m所以取值，只有$\sqrt{m}$种可能。
这样就可以用dp来解决了，$f[i][j]$表示在第$i$集$j$个人观看的最大收益。
转移方程：$f[i+1][j/d[i]]=max(f[i+1][j/d[i]],f[i][j]+c\ast p[i])$
$n\le 10^5$，我们可以优化掉第一维度,因为$j/d[i]\le j$，所以第二维度需要从大到小枚举，其实只要我们预处理m的时候，从大到小处理就可以了。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 100010, M = N * 2, mod = 1e9 + 7, md = 998244353;
int n, m, cnt;
int p[N], d[N], f[N], a[N];void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> p[i];for (int i = 1; i <= n; i++)cin >> d[i];a[++cnt] = 0;set<int> st;for (int i = m; i >= 1; i--){if (!st[m / i]){st.insert(m / i);a[++cnt] = m / i;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= cnt; j++)f[a[j] / d[i]] = max(f[a[j]] + a[j] * p[i], f[a[j] / d[i]]);}int res = 0;for (int i = 0; i <= m; i++)res = max(res, f[i]);cout << res << "\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;//    cin >> t ;while (t--)solve();return 0;
}

J. 二进制与、平方和

在线段树上维护区间或和区间平方和即可。
如果某一段的区间或&x没有变化，则说明这一段区间不需要修改。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 300010, M = N * 2, mod = 998244353;
int n, q;
int a[N];struct Node
{int s, s2;
} tr[N * 4];void pushup(int u)
{tr[u].s2 = (tr[u << 1].s2 + tr[u << 1 | 1].s2) % mod;tr[u].s = tr[u << 1].s | tr[u << 1 | 1].s;
}
void build(int u, int l, int r)
{if (l == r){tr[u].s = a[l];tr[u].s2 = a[l] * a[l] % mod;return;}int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}
int query(int u, int l, int r, int L, int R)
{if (l >= L && r <= R)return tr[u].s2;int mid = l + r >> 1;int v = 0;if (L <= mid)v = (v + query(u << 1, l, mid, L, R)) % mod;if (R > mid)v = (v + query(u << 1 | 1, mid + 1, r, L, R)) % mod;return v;
}
void modify(int u, int l, int r, int L, int R, int x)
{if ((tr[u].s & x) == tr[u].s)return;if (l == r){tr[u].s = tr[u].s & x;tr[u].s2 = tr[u].s * tr[u].s % mod;return;}int mid = l + r >> 1;if (L <= mid)modify(u << 1, l, mid, L, R, x);if (R > mid)modify(u << 1 | 1, mid + 1, r, L, R, x);pushup(u);
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];build(1, 1, n);cin >> q;while (q--){int op;cin >> op;if (op == 1){int l, r, x;cin >> l >> r >> x;modify(1, 1, n, l, r, x);}else{int l, r;cin >> l >> r;cout << query(1, 1, n, l, r) << "\n";}}
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;//    cin >> t ;while (t--)solve();return 0;
}

K. 子串翻转回文串

哈希，先找到最开始不同的位置l和最后不同的位置r，翻转一定是(l,i)或者(i,r)。
对正串和反串做哈希，枚举翻转位置，用哈希判断是否对称。（需要双哈希…

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 500010, M = N * 2, mod = 1e9 + 7, P = 131;
int n;
string s, u;
ULL h1[N], p[N], h2[N];ULL get1(int l, int r)
{return (h1[r] - h1[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
ULL get2(int l, int r)
{return (h2[r] - h2[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
void solve()
{cin >> s;n = s.size();u = s;reverse(u.begin(), u.end());s = " " + s, u = " " + u;int l = 1, r = n;while (l <= n && s[l] == u[l])l++;while (r >= 1 && s[r] == u[r])r--;if (l >= r){cout << "Yes\n";return;}p[0] = 1;for (int i = 1; i <= n; i++){p[i] = p[i - 1] * P % mod;h1[i] = (h1[i - 1] * P % mod + s[i]) % mod;h2[i] = (h2[i - 1] * P % mod + u[i]) % mod;}ULL f1 = h1[n], f2 = h2[n];for (int i = l; i <= r; i++){ULL suma = ((h1[n] - get1(l, i) * p[n - i] % mod + mod) % mod + get2(n - i + 1, n - l + 1) * p[n - i] % mod) % mod, suma1 = ((h2[n] - get2(n - i + 1, n - l + 1) * p[l - 1] % mod + mod) % mod + get1(l, i) * p[l - 1] % mod) % mod;ULL sumb = ((h1[n] - get1(i, r) * p[n - r] % mod + mod) % mod + get2(n - r + 1, n - i + 1) * p[n - r] % mod) % mod, sumb1 = ((h2[n] - get2(n - r + 1, n - i + 1) * p[i - 1] % mod + mod) % mod + get1(i, r) * p[i - 1] % mod) % mod;if (suma == suma1 || sumb == sumb1){cout << "Yes\n";return;}}cout << "No\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--)solve();return 0;
}

F. 旅游胜地

二分距离+2-set。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 1000010, M = N * 2, mod = 1e9 + 7, P = 131;
int n, m;
int a[N], b[N], u[N], v[N];
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tmp, stk[N], top, in_stk[N], id[N], s_cnt;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{low[u] = dfn[u] = ++tmp;stk[++top] = u;in_stk[u] = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if (in_stk[j])low[u] = min(low[u], dfn[j]);}if (dfn[u] == low[u]){++s_cnt;int y;do{y = stk[top--];in_stk[y] = 0;id[y] = s_cnt;} while (y != u);}
}
bool check(int mid)
{for (int i = 0; i <= n * 2; i++)h[i] = -1, dfn[i] = low[i] = stk[i] = in_stk[i] = id[i] = 0;idx = top = s_cnt = tmp = 0;for (int i = 0; i < m; i++){int fu = u[i], fv = v[i];if (abs(a[fu] - a[fv]) > mid){add(fu, fv + n), add(fv, fu + n);}if (abs(a[fu] - b[fv]) > mid){add(fu, fv), add(fv + n, fu + n);}if (abs(b[fu] - a[fv]) > mid){add(fu + n, fv + n), add(fv, fu);}if (abs(b[fu] - b[fv]) > mid){add(fu + n, fv), add(fv + n, fu);}}for (int i = 1; i <= n * 2; i++){if (!dfn[i])tarjan(i);}for (int i = 1; i <= n; i++)if (id[i] == id[i + n])return false;return true;
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 0; i < m; i++){cin >> u[i] >> v[i];}int l = 0, r = 1e10;while (l < r){int mid = (l + r) / 2;if (check(mid))r = mid;elsel = mid + 1;}cout << l << "\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}