首页 > 其他分享 >2022NOIPA层联测34

2022NOIPA层联测34

时间：2022-11-24 19:34:36浏览次数：57  
标签：ch 2022NOIPA int long 34 while maxn 联测 getchar

A. bs 串

只知道去找环然后挨个判断……正解是把不同色的边连上，枚举哪两个同色的边两端已经联通。二分+并查集。

code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 3;
const int M = 4e5 + 3;

int n, m, q, f[maxn], fa[maxn], tot;
char s[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node
{
    int u, v;
}e[maxn], a[maxn], b[maxn];

int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
int find2(int x) {return fa[x] == x ? x : fa[x] = find2(fa[x]);}

bool check()
{
    for(int i=1; i<=tot; i++)
    {
        if(find(e[i].u) == find(e[i].v)) return 1;
    }
    return 0;
}

bool check2(int mid)
{
    memcpy(fa, f, sizeof(f));
    for(int i=1; i<=mid; i++)
    {
        if(!b[i].u) continue;
        fa[find2(b[i].u)] = find2(b[i].v);
    }
    for(int i=1; i<=tot; i++)
    {
        if(find2(e[i].u) == find2(e[i].v)) return 1;
    }
    for(int i=1; i<=mid; i++)
    {
        if(!a[i].u) continue;
        if(find2(a[i].u) == find2(a[i].v)) return 1;
    }
    return 0;
}

int main()
{
    freopen("bssb.in", "r", stdin);
    freopen("bssb.out", "w", stdout);
    
    n = read(), m = read(), q = read();
    scanf("%s", s+1);
    for(int i=1; i<=n; i++) f[i] = i;
    for(int i=1; i<=m; i++)
    {
        int u = read(), v = read();
        if(s[u] == s[v]) e[++tot] = (node){u, v};
        else f[find(u)] = find(v);
    }
    if(check())
    {
        for(int i=1; i<=q; i++)
        {
            printf("Yes\n");
        }
        exit(0);
    }
    for(int i=1; i<=q; i++)
    {
        int u = read(), v = read();
        if(s[u] == s[v]) a[i] = (node){u, v};
        else b[i] = (node){u, v};
    }
    int l = 1, r = q + 1;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check2(mid)) r = mid;
        else l = mid + 1;
    }
    for(int i=1; i<l; i++) printf("No\n");
    for(int i=l; i<=q; i++) printf("Yes\n");

    return 0;
}

 

D. 愤怒的小鸟

一看就是反悔贪心然而不知道反悔贪心怎么用……于是%%%Chen_jr

具体原理还不是很理解感觉应该去研究一下费用流……

合法的反悔方案似乎很有规律，顺序毫无关系因为所有的方案都可以被反悔：

  • 3 2 1

3：直接拿3

2：拿2 、3换2

1：拿1、拿2+2换1、拿3+3换1、拿2+2换3+3换1、拿3+3换2+2换1

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 3;

int n, p, q, r, a[maxn], b[maxn], c[maxn], vis[maxn];
typedef pair<ll, int> pli;
priority_queue<pli> qcb, qca, qbc, qba;
priority_queue<pli, vector<pli>, greater<pli> > qa, qb, qc;
ll ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void make_3star(int x)
{
    vis[x] = 3;
    qcb.push(pli(c[x]-b[x], x));
    qca.push(pli(c[x]-a[x], x));
}
void make_2star(int x)
{
    vis[x] = 2;
    qbc.push(pli(b[x]-c[x], x));
    qba.push(pli(b[x]-a[x], x));
}
void make_1star(int x)
{
    vis[x] = 1;
}
ll get_1star()
{
    while(!qa.empty() && vis[qa.top().second]) qa.pop();
    return qa.empty() ? 1e18 : qa.top().first;
}
ll get_2star()
{
    while(!qb.empty() && vis[qb.top().second]) qb.pop();
    return qb.empty() ? 1e18 : qb.top().first;
}
ll get_3star()
{
    while(!qc.empty() && vis[qc.top().second]) qc.pop();
    return qc.empty() ? 1e18 : qc.top().first;
}
ll make3to2()
{
    while(!qcb.empty() && vis[qcb.top().second] != 3) qcb.pop();
    return qcb.empty() ? -1e18 : qcb.top().first;
}
ll make3to1()
{
    while(!qca.empty() && vis[qca.top().second] != 3) qca.pop();
    return qca.empty() ? -1e18 : qca.top().first;
}
ll make2to3()
{
    while(!qbc.empty() && vis[qbc.top().second] != 2) qbc.pop();
    return qbc.empty() ? -1e18 : qbc.top().first;
}
ll make2to1()
{
    while(!qba.empty() && vis[qba.top().second] != 2) qba.pop();
    return qba.empty() ? -1e18 : qba.top().first;
}

int main()
{
    freopen("angrybird.in", "r", stdin);
    freopen("angrybird.out", "w", stdout);
    
    n = read(), p = read(), q = read(), r = read();
    for(int i=1; i<=n; i++) a[i] = read();
    for(int i=1; i<=n; i++) b[i] = read();
    for(int i=1; i<=n; i++) c[i] = read();
    for(int i=1; i<=n; i++) b[i] = min(b[i], c[i]);
    for(int i=1; i<=n; i++) a[i] = min(a[i], b[i]);
    for(int i=1; i<=n; i++)
    {
        qa.push(pli(a[i], i)); qb.push(pli(b[i], i)); qc.push(pli(c[i], i));
    }
    p = p - max(q, r); q = q - r;
    for(int i=1; i<=r; i++)
    {
        make_3star(qc.top().second); ans += qc.top().first; qc.pop();
    }
    for(int i=1; i<=q; i++)
    {
        ll v1 = get_2star(), v2 = get_3star() - make3to2();
        if(v1 < v2)
        {
            ans += v1;
            int x = qb.top().second; make_2star(x); qb.pop();
        }
        else
        {
            ans += v2;
            int x = qc.top().second, y = qcb.top().second;
            make_3star(x); make_2star(y);
        }
    }
    for(int i=1; i<=p; i++)
    {
        ll v1 = get_1star(), v2 = get_2star()-make2to1(), v3 = get_3star()-make3to1();
        ll v4 = get_2star()-make2to3()-make3to1(), v5 = get_3star()-make3to2()-make2to1();
        if(v1 < v2 && v1 < v3 && v1 < v4 && v1 < v5)
        {
            ans += v1;
            int x = qa.top().second; qa.pop();
            make_1star(x);
        }
        else if(v2 < v3 && v2 < v4 && v2 < v5)
        {
            ans += v2;
            int x = qb.top().second, y = qba.top().second;
            qb.pop(), qba.pop();
            make_2star(x), make_1star(y);
        }
        else if(v3 < v4 && v3 < v5)
        {
            ans += v3;
            int x = qc.top().second, y = qca.top().second;
            qc.pop(), qca.pop();
            make_3star(x), make_1star(y);
        }
        else if(v4 < v5)
        {
            ans += v4;
            int x = qb.top().second, y = qbc.top().second, z = qca.top().second;
            qb.pop(); qbc.pop(); qca.pop();
            make_2star(x), make_3star(y), make_1star(z);
        }
        else 
        {
            ans += v5;
            int x = qc.top().second, y = qcb.top().second, z = qba.top().second;
            qc.pop(); qcb.pop(); qba.pop();
            make_3star(x), make_2star(y), make_1star(z);
        }
    }
    printf("%lld\n", ans);

    return 0;
}
  • 1 2 3

1：直接拿1

2：拿2、1换2

3：拿3、拿2+2换3、拿1+1换3、拿2+2换1+1换3、拿1+1换2+2换3

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 3;

int n, p, q, r, a[maxn], b[maxn], c[maxn], vis[maxn];
typedef pair<ll, int> pli;
priority_queue<pli> qab, qac, qba, qbc;
priority_queue<pli, vector<pli>, greater<pli> > qa, qb, qc;
ll ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void make_1star(int x)
{
    vis[x] = 1;
    qab.push(pli(a[x]-b[x], x));
    qac.push(pli(a[x]-c[x], x));
}
void make_2star(int x)
{
    vis[x] = 2;
    qba.push(pli(b[x]-a[x], x));
    qbc.push(pli(b[x]-c[x], x));
}
void make_3star(int x)
{
    vis[x] = 3;
}
ll get_1star()
{
    while(!qa.empty() && vis[qa.top().second]) qa.pop();
    return qa.empty() ? 1e18 : qa.top().first;
}
ll get_2star()
{
    while(!qb.empty() && vis[qb.top().second]) qb.pop();
    return qb.empty() ? 1e18 : qb.top().first;
}
ll get_3star()
{
    while(!qc.empty() && vis[qc.top().second]) qc.pop();
    return qc.empty() ? 1e18 : qc.top().first;
}
ll make1to2()
{
    while(!qab.empty() && vis[qab.top().second] != 1) qab.pop();
    return qab.empty() ? -1e18 : qab.top().first;
}
ll make1to3()
{
    while(!qac.empty() && vis[qac.top().second] != 1) qac.pop();
    return qac.empty() ? -1e18 : qac.top().first;
}
ll make2to1()
{
    while(!qba.empty() && vis[qba.top().second] != 2) qba.pop();
    return qba.empty() ? -1e18 : qba.top().first;
}
ll make2to3()
{
    while(!qbc.empty() && vis[qbc.top().second] != 2) qbc.pop();
    return qbc.empty() ? -1e18 : qbc.top().first;
}

int main()
{
    freopen("angrybird.in", "r", stdin);
    freopen("angrybird.out", "w", stdout);
    
    n = read(), p = read(), q = read(), r = read();
    for(int i=1; i<=n; i++) a[i] = read();
    for(int i=1; i<=n; i++) b[i] = read();
    for(int i=1; i<=n; i++) c[i] = read();
    for(int i=1; i<=n; i++) b[i] = min(b[i], c[i]);
    for(int i=1; i<=n; i++) a[i] = min(a[i], b[i]);
    p = p - max(q, r); q = q - r;
    for(int i=1; i<=n; i++)
    {
        qa.push(pli(a[i], i)); qb.push(pli(b[i], i)); qc.push(pli(c[i], i));
    }
    for(int i=1; i<=p; i++)
    {
        make_1star(qa.top().second); ans += qa.top().first; qa.pop();
    }
    for(int i=1; i<=q; i++)
    {
        ll v1 = get_2star(), v2 = get_1star() - make1to2();
        if(v1 < v2)
        {
            ans += v1;
            int x = qb.top().second; make_2star(x); qb.pop();
        }
        else 
        {
            ans += v2;
            int x = qa.top().second, y = qab.top().second;
            make_1star(x), make_2star(y);
        }
    }
    for(int i=1; i<=r; i++)
    {
        ll v1 = get_3star(), v2 = get_2star()-make2to3(), v3 = get_1star()-make1to3();
        ll v4 = get_2star()-make2to1()-make1to3(), v5 = get_1star()-make1to2()-make2to3();
        if(v1 < v2 && v1 < v3 && v1 < v4 && v1 < v5)
        {
            ans += v1;
            int x = qc.top().second; qc.pop();
            make_3star(x);
        }
        else if(v2 < v3 && v2 < v4 && v2 < v5)
        {
            ans += v2;
            int x = qb.top().second, y = qbc.top().second;
            qb.pop(), qbc.pop();
            make_2star(x), make_3star(y);
        }
        else if(v3 < v4 && v3 < v5)
        {
            ans += v3;
            int x = qa.top().second, y = qac.top().second;
            qa.pop(), qac.pop();
            make_1star(x), make_3star(y);
        }
        else if(v4 < v5)
        {
            ans += v4;
            int x = qb.top().second, y = qba.top().second, z = qac.top().second;
            qb.pop(), qba.pop(), qac.pop();
            make_2star(x), make_1star(y), make_3star(z);
        }
        else 
        {
            ans += v5;
            int x = qa.top().second, y = qab.top().second, z = qbc.top().second;
            qa.pop(), qab.pop(), qbc.pop();
            make_1star(x), make_2star(y), make_3star(z);
        }
    }
    printf("%lld\n", ans);

    return 0;
}

 

标签：ch,2022NOIPA,int,long,34,while,maxn,联测,getchar
From： https://www.cnblogs.com/Catherine2006/p/16922979.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99