2.25-3.2
1. 计算几何
1.1 二维几何基础
struct Point{
double x,y;
Point(double x = 0, double y = 0):x(x),y(y){}
}
typedef Point Vector;
Vector operator + (Vector A ,Vector B){ return Vector(A.x+B.x,A.y+B.y); }
Vector operator - (Vector A ,Vector B){ return Vector(A.x-B.x,A.y-B.y); }
Vector operator / (Vector A ,Vector B){ return Vector(A.x/B.x,A.y/B.y); }
Vector operator * (Vector A ,Vector B){ return Vector(A.x*B.x,A.y*B.y); }
bool operator < (const Point &a,const Point &b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps = 1e-10;
int dcmp(double x){
if(fabs(x)<eps) return 0;
else return x<0?-1:1;
}
bool operator == (const Point &a,const Point &b){
return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}
//atan2计算极角
1.1.1 基本运算
double Dot(Vector A,Vector B){ return A.x*B.x+A.y*B.y; }
double Length(Vector A){return sqrt(Dot(A,A)); }
double Angle(Vector A,Vector B){ return acos(Dot(A,B)/Length(A)/Length(B)); }
double Cross(Vector A,Vector B){ return A.x*B.y - A.y*B.x;}
double Area2(Point A,Point B,Point C){ return Cross(B-A,C-A); }
Vector Rotate(Vector A,double rad){
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A){
double L = Length(A);
return Vector(-A.y/L,A.x/L);
}
1.1.2 点与直线
//直线用P = P0+tv表示
//调用前确保两条直线P+tv,Q+tw有唯一交点，当且仅当Cross(v,w)非0
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
Vector u = P-Q;
double t = Cross(w,u)/Cross(v,w);
return p+v*t;
}
double DistanceToLine(Point P,Point A,Point B){
Vector v1 = B-A,v2 = P-A;
return fabs(Cross(v1,v2))/Length(v1);//不取绝对值得到有向距离
}
double DistanceToSegment(Point P,Point A,Point B){
if(A==B)return Length(P-A);
Vector v1 = B-A,v2 = P-A,v3 = P-B;
if(dcmp(Dot(v1,v2)) < 0)return Length(v2);
else if(dcmp(Dot(v1,v3)) > 0)return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
//点在直线上的投影
Point GetLineProjection(Point p,Point A,Point B){
Vector v = B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}
//线段相交 严格相交
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){
double c1 = Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1);
double c3 = Cross(b2-b1,a1-b1),c4 = Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}
//不严格相交，还没有补充
bool Onsegment(Point p,Point a1,Point a2){
return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p)) < 0;
}
1.1.3 多边形
//多边形
double ConvexPolygonArea(Point *p,int n){
double area = 0;
for(int i=1;i<n-1;i++)
area += Cross(p[i]-p[0],p[i+1]-p[0]);
return area/2;
}
double PolygonArea(Point *p,int n){
return ConvexPolygonArea(P,n);
}
1.2 与圆有关的计算问题
2. CF-1130
D题和E题
- 火车只能顺时针走
- 一次只能从一个地方拿走一个，所以对于当前 j ，如果有cnt[j]个糖果，那么必须经过它cnt[j]次，而且把需要传递距离最近的那个留到最后。这样该点需要走的最远距离就是
(cnt[j]-1)*n + last，last为最后一个要走的距离。 - (O(n^2)) 遍历所有。输出答案
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 5010;
int n,m,cnt[N],last[N];
int main(){
cin>>n>>m;
memset(last,0x3f,sizeof last);
for(int i=0,a,b;i<m;i++){
scanf("%d%d",&a,&b);
b = (b+n-a)%n;
cnt[a]++;
last[a] = min(last[a],b);
}
for(int i=1;i<=n;i++){
int res = 0;
for(int j=1;j<=n;j++)if(cnt[j])
res = max(res,(cnt[j]-1)*n + last[j] + (j-i+n)%n);
printf("%d ",res);
}
puts("");
return 0;
}
3. CF-1038
C - Gambling
- 这题很简单，贪心就可以了，奈何我脑痴把数组下标写的小了，浪费了二十分钟
D - Slime
- 每个数给答案的贡献无非只有两种，一种正的，一种负的，让我们想想极端的情况。假如这个序列整个都是正的，那我们需要一个数来充当被减数，然后之后整个序列就可以进行运算了。当我们运算出当前结果时，可以想到的是，该结果可以进行内部取反，来迎合下一次操作。（妙啊）
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
typedef long long ll;
ll a[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
if(n==1)cout<<a[1]<<endl;
else{
ll mi = 1e9,cnt_pos=0,cnt_neg=0,res=0;
for(int i=1;i<=n;i++){
mi = min(mi,abs(a[i]));
res+=abs(a[i]);
if(a[i]>0)cnt_pos++;
else if(a[i]<0)cnt_neg++;
}
if(cnt_pos&&cnt_neg)
cout<<res<<endl;
else cout<<res-2*mi<<endl;
}
return 0;
}
4. CF-1025
B - Weakened Common Divisor
- 这个题差点就想出来了，然而我太着急。
- 每组两个数字，从中取出一个，然后整个序列很n个组，使得取出来的这n个数字的gcd不为1
- 因为每组两个数字都可以取，所以可以提供的质因子就变成了两份，为了产生对答案的贡献，我们不妨把该组可以产生的贡献都计算进去。然后筛选出来的答案再进行压缩，使得他符合所有组中的选择。
- 每组的数乘起来，然后求整个序列的gcd，可以想到这个gcd包含了所有组中共有的质因数（质因数的指数是多少不用管）。然后每次筛的时候，选一个质因数不为一的数字选就可以了。
#include <bits/stdc++.h>
using namespace std;
#define g std::__gcd
long long A[555555],B[555555],n,a=0;
int main(){
scanf("%lld", &n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&A[i],&B[i]);
a=g(a,A[i]*B[i]);
}
if(a==1){
return puts("-1"),0;
}
for(int i=1;i<=n;i++){
if(g(a,A[i])>1)
a=g(a,A[i]);
else
a=g(a,B[i]);
}
return printf("%lld
", a), 0;
}
C - Plasticine zebra
- 取一个切点然后反转，两次反转我们可以发现完全就是将前缀串接到了后缀串的后面，而一次反转效果也是同样的，把切割点分开，两端连上，中间的情况我们不需要考虑。
- 所以这个题就转换为了把这个串结成一个圈，然后在圈上取一段长度最长不超过n的连续不同序列。注意极端情况(如果不是cf给的数据，恐怕要卡很久)
#include <bits/stdc++.h>
using namespace std;
char s[200100];
int main(){
cin>>s;
int res = 0, cnt = 1;
int len = strlen(s);
for(int i=len;i<len+len;i++)
s[i] = s[i-len];
for(int i=0;i<2*len-1;i++)
if(s[i]==s[i+1]){
res = max(res,cnt);
cnt = 1;
}
else cnt++;
res = max(res,cnt);
if(res>len)
cout<<len<<endl;
else
cout<<res<<endl;
return 0;
}
D - Recovering BST
- 区间dp，思路挺顺，但是有一点马虎了之后就会造成很大的麻烦
dp[l][r][0]表示以 l-1 为根的区间可否组成二叉搜索树。然后搜就可以了- 代码可以优化一下
#include <bits/stdc++.h>
using namespace std;
const int N = 770;
int n;
int d[N][N][2],g[N][N],a[N];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int dp(int l,int r,int m){
int p = m==0?l-1:r+1;
int &res = d[l][r][m];
if(res)return res;
if(l==r){
if(g[l][p]>1)res = 1;
else res = -1;
}
else{
int flag = 0;
for(int i=l;i<=r;i++){
if(g[i][p]>1){
if(i==l){
if(dp(i+1,r,0)==1){
flag = 1;break;
}
}
if(i==r){
if(dp(l,i-1,1)==1){
flag = 1;break;
}
}
else{
if(dp(l,i-1,1)==1&&dp(i+1,r,0)==1){
flag = 1;break;
}
}
}
}
if(flag)res = 1;
else res = -1;
}
return res == 1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
g[i][i] = a[i];
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
g[i][j] = g[j][i] = gcd(a[i],a[j]);
}
if(n == 2){
if(g[1][2]>1)
puts("Yes");
else puts("No");
return 0;
}
int flag = 0;
for(int i=1;i<=n;i++){
if(i==1){
if(dp(2,n,0)==1){
flag = 1;
break;
}
}
else if(i==n){
if(dp(1,n-1,1)==1){
flag = 1;break;
}
}
else if(dp(1,i-1,1)==1&&dp(i+1,n,0)==1){
flag = 1;break;
}
}
/*
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)
printf("%d %d %d %d
",i,j,d[i][j][0],d[i][j][1]);
}
*/
if(flag)puts("Yes");
else
puts("No");
return 0;
}
压缩后：
#include <bits/stdc++.h>
using namespace std;
const int N = 770;
int n;
int d[N][N][2],g[N][N],a[N];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int dp(int l,int r,int m){
int p = m==0?l:r;
int &res = d[l][r][m];
if(res)return res;
if(l==r) res = 1;
else{
l = m==0?l+1:l;
r = m==1?r-1:r;
int flag = 0;
for(int i=l;i<=r;i++){
if(g[i][p]>1){
if(dp(l,i,1)==1&&dp(i,r,0)==1){
flag = 1;break;
}
}
}
if(flag)res = 1;
else res = -1;
}
return res == 1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
g[i][i] = a[i];
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
g[i][j] = g[j][i] = gcd(a[i],a[j]);
}
int flag = 0;
for(int i=1;i<=n;i++){
if(dp(1,i,1)==1&&dp(i,n,0)==1){
flag = 1;
break;
}
}
if(flag)puts("Yes");
else puts("No");
return 0;
}
5. CF-1027
B - Numbers on the Chessboard
- 思路还是比较清晰的，不过在处理各种情况时，不要一味想着统一所有情况，其实分一下奇偶也是可以的，更容易写对
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,x,y;
int main(){
cin>>n>>q;
ll res;
for(int i=1;i<=q;i++){
cin>>x>>y;
if((x+y)%2==0){
if(x&1) res = ((x-1)/2)*n+(y/2+1);
else res = ((x-2)/2)*n + ((n+1)/2)+y/2;
}
else {
if(x&1) res = ((x-1)/2)*n + y/2 + (n*n+1)/2;
else res = ((x-2)/2)*n + n/2 + y/2+1 + (n*n+1)/2;
}
cout<<res<<endl;
}
return 0;
}
C - Minimum Value Rectangle
- 虽然是个难度1600的贪心，但是贪心策略很好想，难点在于处理上，如果用hash存储的话，即使是1e4的数组，每组test memset一下时间也会爆炸，貌似有人卡过的，不过这不是正解。
- 正解是先排个序，然后两个相同的变成一个，单着的就抛弃了就可以了。然后扫一次
- T了半小时之后看正解，因为数组下标，还有循环，又坑了半小时。感觉状态不太好的时候就不要硬干了，肯定是小问题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000*1000+13;
int T,n,m,a[N],b[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
int m = 0;
for(int i=0;i<n-1;i++){
if(a[i]==a[i+1]){
b[m++] = a[i];
i++;
}
}
int A = b[0],B = b[1];
ll P = (A+B)*ll(A+B);
ll S = A*ll(B);
for(int i=0;i<m-1;i++){
ll TP = (b[i]+b[i+1])*ll(b[i]+b[i+1]);
ll TS = b[i]*ll(b[i+1]);
if(TS*P > S*TP){
A = b[i];B = b[i+1];
P = TP;
S = TS;
}
}
printf("%d %d %d %d
",A,A,B,B);
}
return 0;
}
D - Mouse Hunt
- 这题一眼就是并查集，NONONO，忽略了两点的有向关系。也是巧了，刚做了这题第二天就在牛客碰到了。
- 具体处理就是先拓扑扫一遍，剩下的就是环，在环内找个最小值放哨兵就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
int n;
int c[N],p[N],deg[N],v[N];
int dfs(int x){
v[x] = 1;
if(v[p[x]])return c[x];
else return min(c[x],dfs(p[x]));
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
deg[p[i]]++;
}
queue<int> q;
for(int i=1;i<=n;i++)if(deg[i]==0)q.push(i);
while(!q.empty()){
int x = q.front();q.pop();
deg[p[x]]--;
if(deg[p[x]]==0)q.push(p[x]);
}
int res = 0;
for(int i=1;i<=n;i++){
if(deg[i]&&!v[i]){
//printf("%d
",i);
res+=dfs(i);
}
}
cout<<res<<endl;
return 0;
}
6.CF-1023
A - Single Wildcard Pattern Matching
- 被A题卡特判了。难过
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
char s[N],t[N];
int n,m;
bool check(int x){
if(x==n&&n!=m)return false;
for(int i=0;i<x;i++)
if(s[i] != t[i])return false;
for(int i=n-1;i>x;i--){
int j = m-1-(n-1-i);
if(j<x)return false;
if(s[i] != t[j])return false;
}
return true;
}
int main(){
cin>>n>>m;
cin>>s>>t;
if(n>m+1){
puts("NO");return 0;
}
int index = n;
for(int i=0;i<n;i++)if(s[i]=='*'){
index = i;break;
}
if(check(index))puts("YES");
else puts("NO");
return 0;
}
大佬的代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s1,s2;int n,m,i=0;cin>>n>>m>>s1>>s2;
while(s1[i]==s2[i]&&i<min(m,n))i++;
while(s1[n-1]==s2[m-1]&&i<min(m,n)){n--;m--;}
return cout<<(s1[i]=='*'&&n-i==1||s1==s2?"YES":"NO"),0;
}
C - Bracket Subsequence
- 直接放代码了，这题没什么好说的，还卡了那么久。
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n,k;
char s[N],t[N];
int main(){
while(cin>>n>>k){
cin>>s;
int l = 0,r = 0,p = 0;
for(int i=0;i<n;i++){
if(s[i] == '('){
l++;
}
else{
r++;
}
putchar(s[i]);
if(l == k/2)break;
}
for(r = r+1;r<=l;r++)putchar(')');
puts("");
}
return 0;
}