头像

负壹




离线:1天前


活动打卡代码 AcWing 1277. 维护序列

负壹
2天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, p, m;
int w[N];
struct Node
{
    int l, r;
    int sum, add, mul;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void eval(Node &t, int add, int mul)
{
    t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
    t.mul = (LL)t.mul * mul % p;
    t.add = ((LL)t.add * mul + add) % p;
}

void pushdown(int u)
{
    eval(tr[u << 1], tr[u].add, tr[u].mul);
    eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0, 1};
    else
    {
        tr[u] = {l, r, 0, 0, 1};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add, int mul)
{
    if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, add, mul);
        if (r > mid) modify(u << 1 | 1, l, r, add, mul);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
    return sum;
}

int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    scanf("%d", &m);
    while (m -- )
    {
        int t, l, r, d;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1)
        {
            scanf("%d", &d);
            modify(1, l, r, 0, d);
        }
        else if (t == 2)
        {
            scanf("%d", &d);
            modify(1, l, r, d, 1);
        }
        else printf("%d\n", query(1, l, r));
    }

    return 0;
}



活动打卡代码 AcWing 247. 亚特兰蒂斯

负壹
3天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
struct Segment
{
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}seg[N * 2];
struct Node
{
    int l, r;
    int cnt;
    double len;
}tr[N * 8];

vector<double> ys;

int find(double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u)
{
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r)
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else tr[u].len = 0;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++ )
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[j ++ ] = {x1, y1, y2, 1};
            seg[j ++ ] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        build(1, 0, ys.size() - 2);

        sort(seg, seg + n * 2);

        double res = 0;
        for (int i = 0; i < n * 2; i ++ )
        {
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        }

        printf("Test case #%d\n", T ++ );
        printf("Total explored area: %.2lf\n\n", res);
    }

    return 0;
}





负壹
18天前

给一个线段的集合S,其中有n条线段,给定任意一条直线L,判断直线L是否将集合S中的线段分隔?

“分隔”是指S中每个线段都处于直线L的一边,并且直线L不与任何一个线段相交,如下图蓝色直线分隔红色线段集

分隔.png

现在要求对集合S做预处理,然后对于任意一条直线,查询是否“分隔”时间复杂度为logn.

请问如何做出预处理啊?给个思路也可以~
祝大家新年快乐!



活动打卡代码 AcWing 1172. 祖孙询问

负壹
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

int main()
{
    scanf("%d", &n);
    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);

    scanf("%d", &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }

    return 0;
}





负壹
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 510, M = 10010;

int n, m;
struct Edge
{
    int a, b, w;
    bool f;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}edge[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
    d1[u] = maxd1, d2[u] = maxd2;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa)
        {
            int td1 = maxd1, td2 = maxd2;
            if (w[i] > td1) td2 = td1, td1 = w[i];
            else if (w[i] < td1 && w[i] > td2) td2 = w[i];
            dfs(j, u, td1, td2, d1, d2);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }

    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    LL sum = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            p[pa] = pb;
            sum += w;
            add(a, b, w), add(b, a, w);
            edge[i].f = true;
        }
    }

    for (int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);

    LL res = 1e18;
    for (int i = 0; i < m; i ++ )
        if (!edge[i].f)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            LL t;
            if (w > dist1[a][b])
                t = sum + w - dist1[a][b];
            else if (w > dist2[a][b])
                t = sum + w - dist2[a][b];
            res = min(res, t);
        }

    printf("%lld\n", res);

    return 0;
}




活动打卡代码 AcWing 346. 走廊泼水节

负壹
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 6010;
int n;
struct Edge{
    int a,b,w;
    bool operator<(const Edge &t)const{
        return w<t.w;
    }
}e[N];

int p[N],sizes[N];
int find(int x){
    if(p[x]!=x)p[x] = find(p[x]);
    return p[x];
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i = 0;i<n-1;i++){
            int a,b,c;
            cin>>a>>b>>c;
            e[i] = {a,b,c};
        }
        sort(e,e+n-1);
        for(int i = 1;i<=n;i++)p[i] = i,sizes[i] = 1;
        int res = 0;
        for(int i = 0;i<n-1;i++){
            int a = find(e[i].a);
            int b = find(e[i].b);
            int w = e[i].w;
            if(a!=b){
                res += (sizes[a]*sizes[b]-1)*(w+1);
                sizes[a] += sizes[b];
                p[b] = a;
            }
        }
        cout<<res<<endl;
    }


}




活动打卡代码 AcWing 1145. 北极通讯网络

负壹
3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510, M = N * N / 2;

int n, k, m;
struct Edge
{
    int a, b;
    double w;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}e[M];

PII q[M];
int p[N];

double get_dist(PII a,PII b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx*dx+dy*dy);
}

int find(int x){
    if(p[x]!=x)p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin>>n>>k;
    for(int i = 0;i<n;i++)cin>>q[i].x>>q[i].y;
    for(int i = 0;i<n;i++)
        for(int j = 0;j<i;j++)
            e[m++] = {i,j,get_dist(q[i],q[j])};

    sort(e,e+m);
    for(int i = 0;i<n;i++)p[i] = i;

    int cnt = n;
    double res = 0;
    for(int i = 0;i<m;i++){
        if(cnt<=k)break;
        int a = find(e[i].a);
        int b = find(e[i].b);
        double w = e[i].w;
        if(a!=b){
            cnt--;
            res = w;
            p[a] = b;
        }
    }
    printf("%.2lf\n", res);
    return 0;
}





活动打卡代码 AcWing 1146. 新的开始

负壹
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int n;
int w[N][N];
int dist[N];
bool st[N];

int prim(){
    memset(dist,0x3f,sizeof dist);
    dist[0] = 0;
    int res = 0;

    for(int i = 0;i<n+1;i++){
        int t = -1;
        for(int j = 0;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t = j;
        st[t] = true;
        res += dist[t];
        for(int j = 0;j<=n;j++)dist[j] = min(dist[j],w[t][j]);
    }
    return res;
}


int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>w[0][i];
        w[i][0] = w[0][i];
    }

    for(int i = 1;i<=n;i++)
    for(int j = 1;j<=n;j++)
    cin>>w[i][j];

    cout<<prim()<<endl;

    return 0;

}


活动打卡代码 AcWing 345. 牛站

负壹
3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int N = 210;

int k, n, m, S, E;
int g[N][N];
int res[N][N];

void mul(int c[][N], int a[][N], int b[][N])
{
    static int temp[N][N];
    memset(temp, 0x3f, sizeof temp);
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
    memcpy(c, temp, sizeof temp);
}

void qmi()
{
    memset(res, 0x3f, sizeof res);
    for (int i = 1; i <= n; i ++ ) res[i][i] = 0;

    while (k)
    {
        if (k & 1) mul(res, res, g);    // res = res * g
        mul(g, g, g);   // g = g * g
        k >>= 1;
    }
}

int main()
{
    cin >> k >> m >> S >> E;

    memset(g, 0x3f, sizeof g);
    map<int, int> ids;
    if (!ids.count(S)) ids[S] = ++ n;
    if (!ids.count(E)) ids[E] = ++ n;
    S = ids[S], E = ids[E];

    while (m -- )
    {
        int a, b, c;
        cin >> c >> a >> b;
        if (!ids.count(a)) ids[a] = ++ n;
        if (!ids.count(b)) ids[b] = ++ n;
        a = ids[a], b = ids[b];

        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    qmi();

    cout << res[S][E] << endl;

    return 0;
}


活动打卡代码 AcWing 344. 观光之旅

负壹
3个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int n,m;
int d[N][N],g[N][N];
int pos[N][N];
int path[N],cnt;


void get_path(int i,int j){
    if(pos[i][j]==0)return;
    int k = pos[i][j];
    get_path(i,k);
    path[cnt++] = k;
    get_path(k,j);
}



int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i = 1;i<=n;i++)g[i][i] = 0;

    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }

    int res = INF;
    memcpy(d,g,sizeof d);
    for(int k = 1;k<=n;k++){
        for(int i = 1;i<k;i++)
            for(int j = i+1;j<k;j++)
                if((long long)d[i][j]+g[j][k]+g[k][i]<res){
                    res = d[i][j] + g[j][k] + g[k][i];
                    cnt = 0;
                    path[cnt++] = k;
                    path[cnt++] = i;
                    get_path(i,j);
                    path[cnt++] = j;
                }
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                    pos[i][j] = k;
                }
    }

    if(res==INF)cout<<"No solution."<<endl;
    else{
        for(int i = 0;i<cnt;i++)cout<<path[i]<<' ';
        cout<<endl;
    }
    return 0;
}