The 2023 ICPC Asia Regionals Online Contest (1)(A D I J K L)

The 2023 ICPC Asia Regionals Online Contest (1)(A D I J K L)

PTA | 程序设计类实验辅助教学平台

A Qualifiers Ranking Rules(模拟)

考虑先对第一场和第二场分别去重(取最好) ， 归并排序后再次去重即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e4 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;string x[N] , y[N] , all[N] , s;
map<string,bool>vis;
int n , m , cnt1 , cnt2 , cnt;
vector<string>ans;signed main(){cin >> n >> m;for(int i = 1 ; i <= n ; i ++) {cin >> s;if(vis[s]) continue;vis[s] = 1;x[++cnt1] = s;}vis.clear();for(int i = 1 ; i <= m ; i ++) {cin >> s;if(vis[s]) continue;vis[s] = 1;y[++cnt2] = s;		}int i = 1 , j = 1 ;while(i <= cnt1 && j <= cnt2) {all[++cnt] = x[i];all[++cnt] = y[j];i += 1;j += 1;}while(i <= cnt1) {all[++cnt] = x[i];i += 1;}while(j <= cnt2) {all[++cnt] = y[j];j += 1;}vis.clear();for(int i = 1 ; i <= cnt1 + cnt2 ; i ++) {if(vis[all[i]]) continue;vis[all[i]] = 1;ans.push_back(all[i]);}for(auto x : ans) {cout << x << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

D Transitivity(并查集)

考虑对于每一个连通块是否是一个完全图 ， 如果都是 ， 那么贡献就是合并两个最小的连通块需要加的边数 ，否则贡献是把所有连通块补成完全图所需要的边数。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int fa[N] , siz1[N] , siz2[N];
int n , m;
int find(int x){if(x == fa[x]) return x;else return fa[x] = find(fa[x]);
}signed main(){IOScin >> n >> m;for(int i = 1 ; i <= n ; i ++) {fa[i] = i;siz1[i] = 1;siz2[i] = 0;}for(int i = 1 ; i <= m ; i ++) {int u , v;cin >> u >> v;u = find(u);v = find(v);if(u == v) {siz2[u] += 1;} else {fa[u] = v;siz1[v] += siz1[u];siz2[v] += siz2[u] + 1;}}bool tag = 0;int res = 0;vector<int>ve;for(int i = 1 ; i <= n ; i ++) {int v = find(i);if(v != i) continue;int x = siz1[i];x = (x - 1) * x / 2;int y = siz2[i];if(x == y) {ve.push_back(siz1[i]);} else {res += x - y;tag = 1;}}sort(ve.begin() , ve.end());if(!tag) res = ve[0] * ve[1];cout << res << "\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

I Pa?sWorD(dp)

根据题目中给出的约束设计状态

$$dp[n][63][0/1][0/1][0/1]为前i位第i位为j是否有小写，大写，数字的方案数$$

时间复杂度

$$O(n\ast 62^2\ast 8)$$

空间复杂度

$$O(n\ast 62\ast 8)$$

考虑优化

对于空间 ，不难发现每一位的状态只与前一位有关 ， 考虑滚动数组优化。

$$优化后空间复杂度O(2\ast 62\ast 8)$$

对于时间 ， 观察转移

for(int i = 0 ; i <= 62 ; i ++) {//枚举前一位for(int j = 0 ; j <= 62 ; j ++) {//枚举当前位if(i == j) continue;for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {if(id >= 1 && id <= 26)  dp[now][i][1][l][m] = (dp[now][i][1][l][m] + dp[pre][j][k][l][m]) % mod;if(id >= 27 && id <= 52) dp[now][i][k][1][m] = (dp[now][i][k][1][m] + dp[pre][j][k][l][m]) % mod;if(id >= 53 && id <= 62) dp[now][i][k][l][1] = (dp[now][i][k][l][1] + dp[pre][j][k][l][m]) % mod;}}}}	}

不难发现只有当(i == j) 的时候不加 ， 其余时候都要加 ， 可以把加法转化为减法 ， 用前缀和维护。

$$优化后时间复杂度O(n\ast 62\ast 8)$$

易错点：滚动数组要注意清空 ， 前缀和数组要注意清空。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 998244353;
typedef pair<int,int>PII;string s;
int get(char c){if(c >= 'a' && c <= 'z') return c - 'a' + 1;if(c >= 'A' && c <= 'Z') return c - 'A' + 27;if(c >= '0' && c <= '9') return c - '0' + 53;return 63;
}
int dp[2][63][2][2][2] , n , res;
int sum[2][2][2] , noww[2][2][2];signed main(){IOScin >> n >> s;s = 'x' + s;dp[0][0][0][0][0] = 1;for(int i = 1 ; i <= n ; i ++) {int now = i & 1;int pre = 1 - now;int id = get(s[i]);int id1 = get(toupper(s[i]));for(int j = 0 ; j <= 62 ; j ++) {for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {dp[now][j][k][l][m] = 0;}	}}}for(int j = 0 ; j <= 62 ; j ++) {for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {if(id >= 1 && id <= 26 && j != id)  dp[now][id][1][l][m] = (dp[now][id][1][l][m] + dp[pre][j][k][l][m]) % mod;if(id >= 27 && id <= 52 && j != id) dp[now][id][k][1][m] = (dp[now][id][k][1][m] + dp[pre][j][k][l][m]) % mod;if(id >= 53 && id <= 62 && j != id) dp[now][id][k][l][1] = (dp[now][id][k][l][1] + dp[pre][j][k][l][m]) % mod;if(id == id1) continue;if(j != id1) dp[now][id1][k][1][m] = (dp[now][id1][k][1][m] + dp[pre][j][k][l][m]) % mod;}}}}if(id == 63) {for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {sum[k][l][m] = noww[k][l][m] = 0;}}}for(int j = 0 ; j <= 62 ; j ++) {for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {sum[k][l][m] = (sum[k][l][m] + dp[pre][j][k][l][m]) % mod;}}}}for(int j = 1 ; j <= 62 ; j ++) {for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {noww[k][l][m] = ((sum[k][l][m] - dp[pre][j][k][l][m]) % mod + mod) % mod;}}}for(int k = 0 ; k <= 1 ; k ++) {for(int l = 0 ; l <= 1 ; l ++) {for(int m = 0 ; m <= 1 ; m ++) {if(j >= 1 && j <= 26)  dp[now][j][1][l][m] = (dp[now][j][1][l][m] + noww[k][l][m]) % mod;if(j >= 27 && j <= 52) dp[now][j][k][1][m] = (dp[now][j][k][1][m] + noww[k][l][m]) % mod;if(j >= 53 && j <= 62) dp[now][j][k][l][1] = (dp[now][j][k][l][1] + noww[k][l][m]) % mod; }}}}}	}int res = 0;for(int i = 1 ; i <= 62 ; i ++) {res = (res + dp[n&1][i][1][1][1]) % mod;}cout << res << "\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);/*
3
a?0
52
*/

J Minimum Manhattan Distance(计算几何)

给出两个圆 C1 , C2 , 在 C2 中找一点 ， 最小化这个点到 C1 中任意点曼哈顿距离的期望。

首先考虑转化期望 ， 有一个很重要的条件就是两个圆 xy坐标是没有重合部分的 ， 对于C1 中的任意一点 x1 ， C2中的一个点 y ， 我们都能在 C1 中找到 x1 关于圆心的对称点 x2 , 使得 y 到 x1 x2 的曼哈顿距离等于二倍 y 到 C1 圆心的曼哈顿距离 。 可证明如果C1C2 x y坐标不重合这样是成立的 。 这样就把期望转化成了到 C1 圆心的距离。如何在C2中找一个点使得其到C1曼哈顿距离最小呢 ， 手模一下不难发现这个点一定在C1的四个45°方向的点上的 ， 枚举一下即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;const double eps = 1e-5;
const double pi = acos(-1);
inline double sqr(double x) {return x * x;} //平方
int sign(double x){if(fabs(x) < eps) return 0;if(x > 0) return 1;return -1;
}//符号
struct point{double x , y;point(){}point(double a , double b) : x(a) , y(b){}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 point &b){return point(a.x - b.x , a.y - b.y);}friend bool operator == (const point &a , const point &b){return !sign(a.x - b.x) && !sign(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);}void output(){ cout << x << " " << y << "\n"; }//向量模长 double norm(){ return sqrt(sqr(x) + sqr(y));}
}; double dist(const point &a , const point &b){return (a - b).norm();
}double dist_m(const point &a , const point &b){return abs(a.x - b.x) + abs(a.y - b.y);
}int t;
point p[4] , o1 , o2;
double r;signed main(){cout << fixed << setprecision(10);cin >> t;while(t --){for(int i = 0 ; i < 4 ; i ++) {double x , y;cin >> x >> y;p[i] = point{x , y};}o1 = point{(p[0].x + p[1].x) / 2.0 , (p[0].y + p[1].y) / 2.0};o2 = point{(p[2].x + p[3].x) / 2.0 , (p[2].y + p[3].y) / 2.0};r = dist(p[2] , p[3]) / 2.0;r = r * sqrt(2) / 2.0;double minn = 9e18;minn = min(minn , dist_m(point{o2.x + r , o2.y - r} , o1));minn = min(minn , dist_m(point{o2.x - r , o2.y + r} , o1));minn = min(minn , dist_m(point{o2.x + r , o2.y + r} , o1));minn = min(minn , dist_m(point{o2.x - r , o2.y - r} , o1));cout << minn << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

K Minimum Euclidean Distance(计算几何)

以圆心为原点建立极坐标系 ， 进行极坐标积分 ， 可以算出答案就是

$$\frac{1}{2}{r}^2+d^2$$

d 是凸包上的点到圆心的距离

判断圆心是否在多边形内即可 ， 在内 d =0 ， 否则计算圆心到每一条边的距离 ， 取最小。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;/*
1/2r^2 + d^2
d 点到圆心的距离
*/const double eps = 1e-5;
const double pi = acos(-1);
inline double sqr(double x) {return x * x;} //平方
int sign(double x){if(fabs(x) < eps) return 0;if(x > 0) return 1;return -1;
}//符号
struct point{double x , y;point(){}point(double a , double b) : x(a) , y(b){}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 point &b){return point(a.x - b.x , a.y - b.y);}friend bool operator == (const point &a , const point &b){return !sign(a.x - b.x) && !sign(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);}void output(){ cout << x << " " << y << "\n"; }//向量模长 double norm(){ return sqrt(sqr(x) + sqr(y));}
}; double det(const point &a , const point &b){return a.x * b.y - a.y * b.x;
}//叉积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();
}//两点距离//判断点 p 是否在线段 st 上(包括端点)
bool point_on_segment(point p , point s , point t){return sign(det(p - s , t - s)) == 0 && sign(dot(p - s , p - t)) <= 0;
}// p 到 线段 st 的距离
double dis_point_segment(const point p , const point s , const point t){if(sign(dot(p - s , t - s)) < 0) return (p - s).norm();if(sign(dot(p - t , s - t)) < 0) return (p - t).norm();return fabs(det(s - p , t - p) / dist(s , t));
}struct polygon{int n;point p[N];int nex(int x){ return (x + 1) % n; }int pre(int x){ return (x - 1 + n) % n; }//多边形周长double perimeter(){double sum = 0;for(int i = 0 ; i < n ; i ++) sum += (p[nex(i)] - p[i]).norm();return sum;}//三角剖分求多边形面积double area(){double sum = 0;for(int i = 0 ; i < n ; i ++) sum += det(p[i] , p[nex(i)]);return sum / 2.0;}//判断点是否在多边形上bool point_on_poly(const point &now){for(int i = 0 ; i < n ; i ++) if(point_on_segment(now , p[i] , p[nex(i)])) return 1;return 0;}// 用光线投射法求回转数 回转数为 0 在外部 ， 不为 0 在内部 ， 借用回转数判断点的位置// 2 点在多边形上 1 点在多边形内 0 点在多边形外int point_int_poly(const point &now){int num = 0;for(int i = 0 ; i < n ; i ++){if(point_on_segment(now , p[i] , p[nex(i)])) return 2;int k = sign(det(p[nex(i)] - p[i] , now - p[i]));int d1 = sign(p[i].y - now.y);int d2 = sign(p[nex(i)].y - now.y);if(k > 0 && d1 <= 0 && d2 > 0) num += 1;if(k < 0 && d2 <= 0 && d1 > 0) num -= 1;}return num != 0;}
};polygon c;
point p[2] , o;
int q;
double r;signed main(){IOScout << fixed << setprecision(10);cin >> c.n >> q;for(int i = 0 ; i < c.n ; i ++) {double x , y;cin >> x >> y;c.p[i] = {x , y};}while(q --) {for(int i = 0 ; i < 2 ; i ++) {double x , y;cin >> x >> y;p[i] = {x , y};}o = point{(p[1].x + p[0].x) / 2.0 , (p[1].y + p[0].y) / 2.0};r = dist(o , p[0]);int now = c.point_int_poly(o);double ans = 0;if(now >= 1) {ans = r * r / 2.0;} else {double d = 9e18;for(int i = 0 ; i < c.n ; i ++) {d = min(d , dis_point_segment(o , c.p[i] , c.p[c.nex(i)]));}ans = r * r / 2.0 + d * d;}cout << ans << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

L KaChang!(签到)

$$答案就是max(2,(t-1)/T+1)$$

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , k , now;int res = 2;signed main(){IOScin >> n >> k;for(int i = 1 ; i <= n ; i ++) {cin >> now;res = max(res , (now - 1) / k + 1);}cout << res << "\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);