2023“钉耙编程”中国大学生算法设计超级联赛（5）
1001 Typhoon
题意：
给你台风的轨迹坐标以及避难所的坐标，台风的半径不可预测，求让每个避难所不安全的最小台风半径是多少。
分析:
枚举每个点到所有“线段”的距离取个min。
代码:
附上队友的代码（懒）:
#include <bits/stdc++.h>
#include <math.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
const double eps=1e-8;
int precision_cmp(double x){
if(x<eps&&x>-eps) return 0;
if(x>0) return 1;
return -1;
}
#ifndef POINT_H
#define POINT_H
struct point { /*以向量的形式表示*/
double x,y;
point() {}
point(double a,double b): x(a),y(b) {}
void input() {
scanf("%lf %lf",&x,&y);
}
friend point operator + (const point &a,const point &b) {
return point(a.x+b.x,a.y+b.y);
}
friend bool operator == (const point &a,const point &b) {
return precision_cmp(a.x-b.x)==0&&precision_cmp(a.y-b.y)==0;
}
friend point operator -(const point &a,const point &b) {
return point(a.x-b.x,a.y-b.y);
}
friend point operator *(const point &a,const double b) {
return point(a.x*b,a.y*b);
}
friend point operator *(const double a,const point b) {
return point(a*b.x,a*b.y);
}
friend point operator /(const point &a,const double b) {
return point(a.x/b,a.y/b);
}
double norm(){//这里为欧氏范数
return sqrt(x*x+y*y);
}
double modulus(){//模长 据知乎上的一篇文章说,modulus一词源于拉丁语"unit of measure",指测量的单位.
return sqrt(x*x+y*y);
}
};
double det(const point &a,const point &b){//叉积 A到B逆时针为正,顺时针为负
return a.x*b.y-b.x*a.y;
}
double dot(const point &a,const point &b){//点积
return a.x*b.x+a.y*b.y;
}
double dist(const point &a,const point &b){
return (a-b).norm();
}
double cross(point a,point b,point c){//ab与ac的叉积
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
point rotate_point(const point &a,const double A){//向量旋转
double tx=a.x,ty=a.y;
return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}
#endif
using namespace std;
double dis(point a,point b,point c){
point r=point(b.x-a.x,b.y-a.y);
point q=point(c.x-a.x,c.y-a.y);
point p=point(c.x-b.x,c.y-b.y);
if(dot(p,r)*dot(p,q)<0){
return abs(det(p,q)/p.modulus());
}
else return min(r.modulus(),q.modulus());
}
int main(){
int m,n;
scanf("%d %d",&m,&n);
double x,y;
point p[m+1],s[n+1];
rep(i,1,m){
scanf("%lf %lf",&x,&y);
p[i]=point(x,y);
}
rep(i,1,n){
cin>>x>>y;
s[i]=point(x,y);
}
double ans[n+1];
for(int i=n;i>=1;i--){
ans[i]=999999999;
rep(j,1,m-1){
ans[i]=min(dis(s[i],p[j],p[j+1]),ans[i]);
}
}
rep(i,1,n){
printf("%.4lf\n",ans[i]);
}
}
1003 String Magic (Easy Version)
题意:
给定一个长度为n的字符串，编号1-n，求满足条件的区间（i, j）的数量：
①1 ≤ i ＜ j ≤ n
②j − i + 1 = 2k, k > 0（即区间长度为大于0的偶数）
③S[i, i + k − 1] = S[i + k, j] （左半段字符串和右半段相同）
④S[i, i + k − 1]是回文串
分析:
根据题目要求，我们实际要求的是满足如下条件的子串s数量：
①s是长度为偶数的回文串
②s的左半段也是回文串
根据manacher算法可知中心点为"#"的回文串满足条件1。
现在考虑条件2：
设s的对称中心为i，最长回文半径为r。对称中心j分布在[(i + (i - r + 1)) / 2, i - 1]内（设他的最长回文半径r2），且j + r2 - 1 ≥ i的子串满足条件2。
综上，我们可以枚举回文中心点"#"的位置i，通过计算区间[(i + (i - r + 1)) / 2, i - 1]内满足j + r2 - 1 ≥ i的对称中心点的数量即可求出以i为对称中心的对称回文子串s的数量。
现在问题在于如何求出区间[(i + (i - r + 1)) / 2, i - 1]内满足j + r2 - 1 ≥ i的对称中心点的数量。很容易想到前缀和，用[1, i - 1]内满足条件的数量减去[1, (i + (i - r + 1)) / 2]满足条件的数量，因此我们要保存[1, (i + (i - r + 1)) / 2]的记录，因此有了主席树，可以用主席树来维护值i + r - 1出现的次数。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
struct Tr {
int l, r; // l,r 存的是指针
LL cnt; // 区间内值出现的次数
}tr[4 * N + N * 18]; // 一次insert产生一个新版本，对应增加logN个节点
int root[N],idx; // root存历史版本根节点
char s[N], s2[N];
int r[N], n, m;
void manacher() {
n = strlen(s);
s2[m ++] = '$', s2[m ++] = '#';
for (int i = 0; i < n; i ++)
s2[m ++] = s[i], s2[m ++] = '#';
s2[m ++] = '^';
int mr = 0, mid = 0;
for (int i = 1; i <= m - 2; i ++) {
r[i] = i < mr ? min(r[2 * mid - i], mr - i) : 1;
while (s2[i + r[i]] == s2[i - r[i]])
r[i] ++;
if (i + r[i] > mr) {
mr = i + r[i];
mid = i;
}
}
}
void init() {
idx = m = 0;
for (int i = 0; i <= 4 * N + N * 18; i ++)
tr[i] = {0, 0, 0};
}
int build(int l, int r) {
int p = idx ++;
if (l == r)
return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}
int insert(int p, int l, int r, int x) {
int q = ++ idx;
tr[q] = tr[p];
if(l == r) {
tr[q].cnt ++;
return q;
}
int mid = l + r >> 1;
if(x <= mid)
tr[q].l = insert(tr[p].l, l, mid, x);
else
tr[q].r = insert(tr[p].r, mid + 1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
LL query(int p, int q, int l, int r, int l2, int r2) {
if (l2 <= l && r <= r2)
return tr[q].cnt - tr[p].cnt;
int mid = (l + r) >> 1;
LL ans = 0;
if(l2 <= mid)
ans = query(tr[p].l, tr[q].l, l, mid, l2, r2);
if(r2 > mid)
ans += query(tr[p].r, tr[q].r, mid + 1, r, l2, r2);
return ans;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
cin >> s;
init();
manacher();
root[0] = build(1, m - 2);
LL ans = 0;
for (int i = 1; i <= m - 2; i ++) {
root[i] = insert(root[i - 1], 1, m - 2, i + r[i] - 1);
}
for (int i = 1; i <= m - 2; i ++) {
if (s2[i] == '#') {
int j = (2 * i - r[i] + 1) / 2;
ans += query(root[j - 1], root[i - 1], 1, m - 2, i, m - 2);
}
}
cout << ans << "\n";
}
return 0;
}
1006 Touhou Red Red Blue
题意:
现在有三种颜色的球：R、G、B，两个袋子，依次给你n个球，对于某个球，你可以选择选或不选，若选择，你要按照下面规则将其放入袋子中：
1.每个袋子只允许放一个球。优先放袋子1，若袋子1满放袋子2
2.若两个袋子都满：
①若袋中球和你手中的球颜色两两相同，获得一点分数，然后扔掉三个球，生成一个新球放入袋子1，新球颜色自定。
②若袋中球和你手中的球颜色两两不同，则扔掉三球，生成两个球分别放入袋1袋2，新球颜色自定。
③若不是上述两种情况，则扔掉袋1的球，将袋2的球放入袋1，并将手中的球放入袋2。
问，最后获得的最大分数是多少。
分析:
贪心。只有颜色相同的时候才能获得分数，球的数量有限，因此最优解要尽可能的往这一状态靠。设st = 0,1,2 表示从上轮的结果转移过来，这轮要先生成st个球。
1.st = 0:
累计三种颜色的球的数量，考虑转移到st = 1和 st = 2的条件。
2.st = 1:
判断当前手中的球和下一个球颜色是否相同，如果相同则让其满足两两相同的局面，获得分数,转移到st = 1;否则优先让其满足两两不同的局面, 转移到st = 2。倘若不转移到st = 2则只能转移到st = 0。由于st = 2必得分显然比先到st=0再到st = 1或2得分消耗的球更少更有利于得更多分，所以转移至st = 2更优。
3.st = 2:
优先令两个球的颜色与手中球颜色相同，获得分数，转移到st = 1。
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
string s;
cin >> s;
int n = s.size(), r = 0, g = 0, b = 0, res = 0, st = 0;
for (int i = 0; i < n; ) {
if (st == 1) {
if (i == n - 1)
break; // 只剩两个球，不能得分了
if (s[i] == s[i + 1])
st = 1, res ++;
else
st = 2;
i += 2; // 跳过本次和下一次
} else if (st == 2) {
st = 1, res ++, i ++; // 跳过本次
} else {
if (s[i] == 'R')
r ++;
else if (s[i] == 'G')
g ++;
else
b ++;
if (r && g && b)
st = 2;
else if (r == 3 || g == 3 || b == 3)
st = 1, res ++;
i ++; // 继续
}
}
cout << res << "\n";
}
return 0;
}
1007 Expectation (Easy Version)
题意：
玩一个游戏n次，每次有\(\frac{a}{b}\)的概率赢，如果某次赢了，将获得\(k^m\)的分数，k是到目前为止赢得总次数。问最终得分的期望。
分析：
推公式，期望为：\(\sum_{k = 1}^n(1^m+2^m+...+k^m)C_n^k(\frac{a}{b})^k(1 - \frac{a}{b})^{n - k}\) = \(\sum_{k = 1}^n(1^m+2^m+...+k^m)C_n^k\frac{a^k(b - a)^{n - k}}{b^n}\)
通过预处理逆元的方式求组合数，其他部分也可以通过预处理求出来。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5, mod = 998244353;
typedef long long LL;
LL f[N], f2[N], p[N], s[N], B[N];
LL qmi(LL m, LL k) {
LL res = 1, t = m;
while (k) {
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
void init() {
f[0] = f2[0] = 1;
for (int i = 1; i < N; i ++) {
f[i] = f[i - 1] * i % mod;
f2[i] = f2[i - 1] * qmi(i, mod - 2) % mod;
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
init();
while (t --) {
LL n, m, a, b;
cin >> n >> m >> a >> b;
LL A = 1, tmp = 1;
for (int i = n; i >= 1; i --) {
B[i] = tmp;
tmp = tmp * (b - a) % mod;
}
for (int i = 1; i <= n; i ++) {
A = A * a % mod;
s[i] = qmi(i, m);
s[i] = (s[i] + s[i - 1]) % mod;
p[i] = A * B[i] % mod;
}
LL p2 = qmi(qmi(b, n), mod - 2);
LL res = 0;
for (int i = 1; i <= n; i ++) {
res = (res + ((f[n] * f2[i]) % mod * f2[n - i]) % mod * p[i] % mod * p2 % mod * s[i] % mod) % mod;
}
cout << res << "\n";
}
return 0;
}
1009 Tree
题意：
给你有一个有根树，在这棵树的每条重链上构造一个二叉树，重链上的每个点都是该链构造的二叉树的叶子节点且他们的深度都相同，重链上的点依旧连接着他们的轻儿子。问构造出的二叉树的深度是多少。
二叉树（双杠表示重边）：
重链有：
构造出的二叉树：
分析:
设重链长度为len，根据题意，该链所能构成的二叉树的深度为\(\lceil log_22len \rceil\)。我们可以dfs遍历每条重链，在重链末尾更新该链能构成的二叉树的深度并下传至与其相连的轻儿子，回溯的过程中给该链上的重儿子赋相同的值，最后对每个点记录的depth取个max即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int h[N], e[N], ne[N], idx;
int depth[N], weight[N], len[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int d) {
if (weight[u]) { // 优先遍历重链
int j = weight[u];
len[j] = len[u] + 1;
dfs(j, d);
len[u] = len[j];
depth[u] = depth[j]; // 回溯赋值
} else {
depth[u] += (int)ceil(log(2 * len[u]) / log(2)); // 当前重链所能构造的搜索树深度
depth[u] += d; // 深度下传
}
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (weight[u] == j)
continue;
dfs(j, depth[u]); // 遍历轻儿子
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// 按题目提示扩大栈空间
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
int t;
cin >> t;
while (t --) {
int n;
cin >> n;
idx = 0;
for (int i = 1; i <= n; i ++) {
depth[i] = 0;
len[i] = 1; // 单个点也是一条重链
h[i] = -1;
}
for (int i = 1; i <= n; i ++) {
int fa;
cin >> fa;
if (fa) {
add(fa, i);
}
}
for (int i = 1; i <= n; i ++) {
int a;
cin >> a;
weight[i] = a;
}
dfs(1, 0);
int res = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++) {
res = max(res, depth[i]);
}
cout << res << "\n";
}
exit(0);
return 0;
}
1012 Counting Stars
题意:
我们定义k-星图：一个有k+1个点和k个边的图称为k-星图。给定一个无向图，设k-星图的数量为\(cnt_k\)，求\(cnt_k\)（2 ≤ k ≤ n - 1）的异或和。
分析：
设点u的度为d，则u对k-星图数量的贡献为：\(C_d^k\)，因此统计每个点对不同k-星图的贡献即可
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
typedef long long LL;
LL cnt[N], f[N], f2[N], d[N];
LL qmi(LL m, LL k) {
LL res = 1, t = m;
while (k) {
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
void init() {
f[0] = f2[0] = 1;
for (int i = 1; i < N; i ++ ) {
f[i] = f[i - 1] * i % mod;
f2[i] = f2[i - 1] * qmi(i, mod - 2) % mod;
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
init();
while (t --) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
d[i] = cnt[i] = 0;
}
while (m --) {
int a, b;
cin >> a >> b;
d[a] ++, d[b] ++;
}
for (int i = 1; i <= n; i ++) {
for (int j = 2; j <= d[i]; j ++) { // 所有度累加起来不超过2m, 所以两层循环整体是O(n + m)的时间复杂度。
cnt[j] = (cnt[j] + ((f[d[i]] * f2[j]) % mod * f2[d[i] - j]) % mod) % mod;
}
}
LL res = 0;
for (int i = 2; i <= n - 1; i ++) {
res = res ^ cnt[i] % mod;
}
cout << res << "\n";
}
return 0;
}