头像

山海皆可平

!ZAFU--




离线:4小时前


最近来访(431)
用户头像
Youn
用户头像
Rain丶bow
用户头像
歸海的一刀
用户头像
CF不上紫名不改名
用户头像
不再摆烂
用户头像
to_you
用户头像
LittleGiant
用户头像
Linclon
用户头像
墨雪染星辰ぬ
用户头像
Nirvana_58
用户头像
理塘丁真_
用户头像
CNor
用户头像
yxh52cc
用户头像
xyzfrozen
用户头像
fengyanweijing
用户头像
baitianshuijiao
用户头像
RageAgainsttheMachine
用户头像
Loki
用户头像
蜉蝣
用户头像
wolf


感觉最小生成树好像很神奇,日后有空好好研究。
1706E
1708E
最小生成树和并查集?
输入边的边权和输入顺序有关?
并查集?




板子测试
边界情况:
点在多边形上,特判
交点为多边形顶点,将该点视作在射线的上侧。
复杂度 $O(n)$
这种方法不会有精度问题。
如果是凸多边形,可以用$n$次 $to—left$ 测试 有$O(n log n)$ 方法

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'
#define rep(i, l, r) for (auto(i) = (l); (i) <= (r); ++(i))
const int N = 5e3+10;
struct Point{
    ll x, y;
}a[N];
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y};
}
ll operator * (Point a, Point b){
    return a.x*b.x + a.y*b.y;
}
ll operator ^ (Point a, Point b){
    return a.x*b.y - a.y*b.x;
}
// to-left测试 判断点在直线的哪一边
int toleft(Point a, Point b, Point c){
    ll temp = (b-a) ^ (c-a);
    if(temp > 0) return 1; // 在左边
    else if(temp == 0) return 0; //在线上
    else return -1; //在右边
}
// 判断点c是不是在 线段ab 上
bool cont(Point a, Point b, Point c){
    ll temp = (b-a) ^ (c-a);
    //这种判断方式并不好 因为如果x相同要考虑y坐标
    //所以一般用点积小于等于0来判断
    //if(!temp&&max(a.x,b.x)>=c.x&&min(a.x,b.x)<=c.x) return true;
    return !temp && ((c-a) * (c-b) <= 0);
    //return false;
}
void Solve(){
    int n;
    cin >> n;
    rep(i, 0, n-1) cin >> a[i].x >> a[i].y;
    int m;
    cin >> m;
    rep(i, 1, m){
        Point c;
        cin >> c.x >> c.y;
        Point d = c;
        d.x ++;
        int res = 0;
        // 回转数 判断点是否在多边形内
        rep(j, 0, n-1){
            if(cont(a[j],a[(j+1)%n],c)){
                cout << "EDGE" << endl;
                break;
            }
            int t1 = toleft(c, d, a[j]);
            int t2 = toleft(c, d, a[(j+1)%n]);
            int t3 = toleft(a[j], a[(j+1)%n], c);
            if(t1 >= 0 && t2 < 0 && t3 < 0) res --;
            else if(t1 < 0 && t2 >= 0 && t3 > 0) res ++;
            if(j == n-1) cout << res << endl;
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
} 

两直线相交

struct Point{
    double x, y;
}a[N];
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y};
}
Point operator + (Point a, Point b){
    return {a.x + b.x, a.y + b.y};
}
double operator * (Point a, Point b){
    return a.x*b.x + a.y*b.y;
}
double operator ^ (Point a, Point b){
    return a.x*b.y - a.y*b.x;
}
Point operator * (double b,Point a){
    return {a.x * b, a.y * b};
}
int toleft (Point a, Point b, Point c){
    ll temp = (b-a) ^ (c-a);
    if(temp == 0) return 0;
    else if(temp > 0) return 1;
    else return -1;
}
//如果是线段和直线的交点,先用这个判断有没有交点,避免精度误差。
bool inleft (Point a, Point b, Point c, Point d){
    ll t1 = toleft(a, b, c);
    ll t2 = toleft(a, b, d);
    if(t1 <= 0 && t2 >= 0) return true;
    if(t1 >= 0 && t2 <= 0) return true;
    return false;
}
Point corsspoint(Point a, Point b, Point c, Point d){
    Point v1 = b - a;
    Point v2 = d - c;
    double t1 = v2 ^ (a - c);
    double t2 = v1 ^ v2;
    return a + ((t1/t2) * v1);
}

极角序



活动打卡代码 AcWing 1077. 皇宫看守

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
const int N=1510;
vector<int> son[N];
int w[N];
int f[N][3];
void dfs(int now,int fa){
    f[now][2]=w[now];
    int sum=0;
    for(auto x:son[now]){
        if(x==fa) continue;
        dfs(x,now);
        f[now][0]+=min(f[x][1],f[x][2]);
        //当前节点被父节点看见且自己不选守卫,只能由儿子看到自已或者儿子被儿子的儿子看见
        sum+=min(f[x][1],f[x][2]);
        f[now][2]+=min({f[x][0],f[x][1],f[x][2]});
        //在当前节点放守卫,只用都取最小就行
    }
    f[now][1]=2e9;
    //枚举看见自己的点
    for(auto x:son[now]){
        if(x==fa) continue;
        f[now][1]=min(f[now][1],sum+f[x][2]-min(f[x][1],f[x][2]));
    }
}
void Solve(){
    int n;
    cin>>n;
    rep(i,1,n){
        int a,k,m;
        cin>>a>>k>>m;
        w[a]=k;
        rep(j,1,m){
            int b;
            cin>>b;
            son[a].push_back(b);
            son[b].push_back(a);
        }
    }
    dfs(1,0);
    cout<<min(f[1][1],f[1][2]);
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
}


活动打卡代码 AcWing 323. 战略游戏

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
const int N=1510;
int f[N][2];
vector<int> son[N];
// f[i]表示以i为根节点的子树至少需要选多少个点
void dfs(int now,int fa){
    f[now][1]=1;
    f[now][0]=0;
    for(auto x:son[now]){
        if(x==fa) continue;
        dfs(x,now);
        f[now][1]+=min(f[x][1],f[x][0]);
        // 因为已经选了根节点所以与他相连的可以是选也可以不选
        f[now][0]+=f[x][1];
        //根节点不选所以只能选儿子选了的节点
    }
}
void Solve(int n){
    rep(i,0,n-1) son[i].clear();
    rep(i,1,n){
        int a,m;
        scanf("%d:(%d)",&a,&m);
        rep(j,1,m){
            int b;
            scanf("%d",&b);
            son[a].emplace_back(b);
            son[b].emplace_back(a);
        }
    }
    dfs(0,-1);
    printf("%d\n",min(f[0][1],f[0][0]));
    return;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF)
    Solve(n);
    return 0;
}


活动打卡代码 AcWing 1074. 二叉苹果树

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
const int N=110;
int n,k;
ll f[N][N];
//f[i][j]表以i为根节点的子树,选择了j根树枝
struct node{
    int i,w;
};
vector<node> son[N];
void dfs(int now,int fa){
    for(auto x:son[now]){
        if(x.i==fa) continue;
        dfs(x.i,now);
        per(i,k,0){
            //从大到小枚举,不会被重复更新,都是用上一层的去更新
            rep(j,0,i-1){
                f[now][i]=max(f[now][i],f[x.i][j]+f[now][i-j-1]+x.w);
                // 以now为根节点 保留了i根树枝的最大值
                // 以now的儿子为根保留了j根树枝的最大值+以now为根保留了i-j-1根树枝的=的最大值
                // 再加上新加进来的根的权重
            }
        }
    }
}
void Solve(){
    cin>>n>>k;
    rep(i,1,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        son[a].push_back({b,c});
        son[b].push_back({a,c});
    }
    dfs(1,0);
    cout<<f[1][k];
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
}


活动打卡代码 AcWing 1075. 数字转换

拿着约数找倍数 $nlogn$ 建图
或者是暴力跑约数 $n\sqrt n$ 建图

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
const int N=5e5+10;
vector<int> son[N];
int sum[N],res;
bool st[N];
int dfs(int now,int fa){
   int d1=0,d2=0;
   st[now]=true;
    for(auto x:son[now]){
        if(x==fa) continue;
        int dist=dfs(x,now)+1;
        if(dist>=d1){
            d2=d1;
            d1=dist;
        }else if(dist>d2){
            d2=dist;
        }
    }
    res=max(d1+d2,res);
    return d1;
}
void Solve(){
    int n;
    cin>>n;
    rep(i,1,n){
        for(int j=1;i*j<=n;j++){
            sum[i*j]+=i;
        }
    }
    rep(i,1,n){
        sum[i]-=i;
        if(sum[i]<i){
            son[i].push_back(sum[i]);
            son[sum[i]].push_back(i);
        }
    }
    rep(i,1,n){
        if(st[i]) continue;
        dfs(i,0);
    }
    cout<<res;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
}


活动打卡代码 AcWing 4501. 收集卡牌

果然是映射写错了,裂开。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define str string
#define PII pair<ll, ll>
#define fir first
#define sec second
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N=1e5+10;
int h[N],ph[N],hp[N],cnt,mm;
int q[N],mp[N]; 
void jh(int x,int y){
    swap(mp[h[x]],mp[h[y]]);
    swap(h[x],h[y]);
}
void down(int t){
    int u=t;
    if(t*2<=cnt&&q[h[t*2]]<q[h[u]])   u=2*t;
    if(t*2+1<=cnt&&q[h[t*2+1]]<q[h[u]]) u=2*t+1;
    if(u!=t){
        jh(u,t);
        down(u);
    }
}
void up(int t){
    while(t/2&&q[h[t/2]]>q[h[t]]){
        jh(t,t/2);
        t/=2;
    }
}
void inerst(int x){
    ++cnt;
    h[cnt]=x;
    if(!mp[x])
    mp[x]=cnt;
    up(cnt);
}
void midofy(int x){
    int qq=mp[x];
    up(qq);
    down(qq);
}
void Solve(){
    int n,m;
    scanf("%d%d",&n,&m);
    int now=0;
    rep(i,1,n) inerst(i);
    rep(i,1,m){
        int x;
        scanf("%d",&x);
        q[x]++;
        midofy(x);
        if(q[h[1]]>now){
            printf("1");
            now++;
        }
        else printf("0");
    }
    return;
}
int main(){
    Solve();
    return 0;
}


活动打卡代码 AcWing 1073. 树的中心

应该算是经典的对一个点考虑上下关系

想清楚就行

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
const int N=1e5+10;
struct node{
    int i,w;
};
vector<node> son[N];
int dist1[N],dist2[N],p1[N],p2[N];
int res;
int up[N];  
int dfs1(int now,int fa){
    int d1=0,d2=0;
    d1=d2=-2e9;
    for(auto u:son[now]){
        if(u.i==fa) continue;
        int deep=dfs1(u.i,now)+u.w;
        if(deep>=d1){
            d2=d1,d1=deep;
            p1[now]=u.i;
        }
        else if(deep>d2){
            d2=deep; 
        }
    }
    if(d1==-2e9){
        d1=d2=0;
    }
    dist1[now]=d1;
    dist2[now]=d2;
    return d1;
}
void dfs2(int now,int fa){
    for(auto x:son[now]){
        if(x.i==fa) continue;
        if(p1[now]!=x.i) up[x.i]=max(up[now],dist1[now])+x.w;
        else up[x.i]=max(up[now],dist2[now])+x.w;
        dfs2(x.i,now);  
    }
}
void Solve(){
    int n;
    cin>>n;
    rep(i,2,n){
        int a,b,c;
        cin>>a>>b>>c;
        son[a].push_back({b,c});
        son[b].push_back({a,c});
    }
    dfs1(1,-1);
    dfs2(1,-1);
    int res=2e9;
    rep(i,1,n)
    res=min(res,max(up[i],dist1[i]));
    cout<<res;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
}


活动打卡代码 AcWing 1072. 树的最长路径

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
const int N=1e5+10;
struct node{
    int i,w;
};
vector<node> son[N];
int res;
int dfs(int now,int fa){
    int dist=0;
    int d1=0,d2=0;
    for(auto u:son[now]){
        if(u.i==fa) continue;
        int deep=dfs(u.i,now)+u.w;
        dist=max(dist,deep);
        if(deep>d1) d2=d1,d1=deep;
        else if(deep>d2) d2=deep; 
    }
    res=max(res,d1+d2);
    return dist;
}
void Solve(){
    int n;
    cin>>n;
    rep(i,2,n){
        int a,b,c;
        cin>>a>>b>>c;
        son[a].push_back({b,c});
        son[b].push_back({a,c});
    }
    dfs(1,0);
    cout<<res;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
}


活动打卡代码 AcWing 321. 棋盘分割

#include <bits/stdc++.h>
using namespace std;
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
const int N=16;
const double INF=1e9;
double f[N][N][N][N][N];
int pre[N][N];
double X;
int n;
double query(int x,int y,int sx,int sy){
    double now=pre[sx][sy]-pre[x-1][sy]-pre[sx][y-1]+pre[x-1][y-1]-X;
    return now*now*1.0/n;
}
double dp(int x,int y,int sx,int sy,int k){
    double &now=f[x][y][sx][sy][k];
    if(now>=0) return now;
    if(k==1) return query(x,y,sx,sy);
    now=INF;
    rep(i,x,sx-1){
        now=min(now,dp(x,y,i,sy,k-1)+query(i+1,y,sx,sy));
        now=min(now,dp(i+1,y,sx,sy,k-1)+query(x,y,i,sy));
    }
    rep(i,y,sy-1){
        now=min(now,dp(x,y,sx,i,k-1)+query(x,i+1,sx,sy));
        now=min(now,dp(x,i+1,sx,sy,k-1)+query(x,y,sx,i));
    }
    return now;     
}
void Solve(){
    cin>>n;
    rep(i,1,8)
        rep(j,1,8){
            cin>>pre[i][j];
            pre[i][j]+=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
        }
    X=(double)pre[8][8]/n;
    memset(f,-1,sizeof f);
    cout<<SPO(3)<<sqrt(dp(1,1,8,8,n));
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
}