专业网站开发制作公司,句容网站建设,禁止搜索引擎收录的方法,个人网站设计过程The 2023 ICPC Asia Regionals Online Contest (1)(A D I J K L)
PTA | 程序设计类实验辅助教学平台
A Qualifiers Ranking Rules(模拟)
考虑先对第一场和第二场分别去重(取最好) #xff0c; 归并排序后再次去重即可。
#includebits/stdc.h
using namespace std;…The 2023 ICPC Asia Regionals Online Contest (1)(A D I J K L)
PTA | 程序设计类实验辅助教学平台
A Qualifiers Ranking Rules(模拟)
考虑先对第一场和第二场分别去重(取最好) 归并排序后再次去重即可。
#includebits/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 pairint,intPII;string x[N] , y[N] , all[N] , s;
mapstring,boolvis;
int n , m , cnt1 , cnt2 , cnt;
vectorstringans;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(并查集)
考虑对于每一个连通块是否是一个完全图 如果都是 那么贡献就是合并两个最小的连通块需要加的边数 否则贡献是把所有连通块补成完全图所需要的边数。
#includebits/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 pairint,intPII;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;vectorintve;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)
根据题目中给出的约束设计状态 d p [ n ] [ 63 ] [ 0 / 1 ] [ 0 / 1 ] [ 0 / 1 ] 为前 i 位第 i 位为 j 是否有小写大写数字的方案数 dp[n][63][0/1][0/1][0/1] ~为前 ~i~ 位第~i~位为j是否有小写大写数字的方案数 dp[n][63][0/1][0/1][0/1] 为前 i 位第 i 位为j是否有小写大写数字的方案数
时间复杂度 O ( n ∗ 6 2 2 ∗ 8 ) O(n*62^2*8) O(n∗622∗8)
空间复杂度 O ( n ∗ 62 ∗ 8 ) O(n*62*8) O(n∗62∗8)
考虑优化
对于空间 不难发现每一位的状态只与前一位有关 考虑滚动数组优化。 优化后空间复杂度 O ( 2 ∗ 62 ∗ 8 ) 优化后空间复杂度O(2*62*8) 优化后空间复杂度O(2∗62∗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 ∗ 62 ∗ 8 ) 优化后时间复杂度O(n*62*8) 优化后时间复杂度O(n∗62∗8)
易错点滚动数组要注意清空 前缀和数组要注意清空。
#includebits/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 pairint,intPII;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[n1][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°方向的点上的 枚举一下即可。 #includebits/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 pairint,intPII;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(计算几何)
以圆心为原点建立极坐标系 进行极坐标积分 可以算出答案就是 1 2 r 2 d 2 \frac{1}{2}r^2d^2 21r2d2
d 是凸包上的点到圆心的距离
判断圆心是否在多边形内即可 在内 d 0 否则计算圆心到每一条边的距离 取最小。
#includebits/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 pairint,intPII;/*
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!(签到) 答案就是 m a x ( 2 , ( t − 1 ) / T 1 ) 答案就是~~max(2,(t - 1)/T1) 答案就是 max(2,(t−1)/T1)
#includebits/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 pairint,intPII;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);
