2019牛客国庆集训派对day3

E. Grid

大意: 给定$n\cdot m$个点的图, 初始无边, $q$个操作, $(1,a,b)$表示第$a$列到第$b$列全连起来, $(2,a,b)$表示把第$a$行到第$b$行全连起来, 每次操作后输出连通块个数.

直接用$set$暴力模拟即可.

还有一种线段树做法, 设一共$a$行连通, $b$列连通, 可以发现答案是$nm-a(m-1)-b(n-1)+max(0,(a-1)(b-1))$, 可以用线段树维护$a$和$b$即可

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

int n,m,q;

struct _ {

    int l,r;

    bool operator < (const _ &rhs) const {

        return l<rhs.l;

    }

};

set<_> A,B;

//A为行

//B为列

int main() {

    while (~scanf("%d%d%d", &n, &m, &q)) {

        A.clear(),B.clear();

        ll ans = (ll)n*m, suma = , sumb = ;

        while (q--) {

            int op,l,r;

            scanf("%d%d%d",&op,&l,&r);

            if (op==) {

                auto p = A.lower_bound({l,});

                if (p!=A.begin()&&(--p)->r>=l) l = p->l;

                while () {

                    p = A.lower_bound({l,});

                    if (p==A.end()||p->l>r) break;

                    r = max(r, p->r);

                    ans += (p->r-p->l+1ll)*(m-(B.empty()?:sumb));

                    suma -= p->r-p->l+;

                    A.erase(p);

                    if (B.size()&&A.empty()) ans += sumb-;

                }

                suma += r-l+;

                ans -= (r-l+1ll)*(m-(B.empty()?:sumb));

                if (B.size()&&A.empty()) ans -= sumb-;

                A.insert({l,r});

            }

            else {

                auto p = B.lower_bound({l,});

                if (p!=B.begin()&&(--p)->r>=l) l = p->l;

                while () {

                    p = B.lower_bound({l,});

                    if (p==B.end()||p->l>r) break;

                    r = max(r, p->r);

                    ans += (p->r-p->l+1ll)*(n-(A.empty()?:suma));

                    sumb -= p->r-p->l+;

                    B.erase(p);

                    if (A.size()&&B.empty()) ans += suma-;

                }

                sumb += r-l+;

                ans -= (r-l+1ll)*(n-(A.empty()?:suma));

                if (A.size()&&B.empty()) ans -= suma-;

                B.insert({l,r});

            }

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

        }

    }

}

G. 排列

大意: 给定$m$个二元组$(a_i,b_i)$, 给定序列$p$, 求将$p$重排, 使得$\sum\limits_{i=1}^m |p_{a_i}-p_{b_i}|$最小, 输出最小值.

从小到大添入每一个$p$, 这样就能去掉绝对值号, 跑一个状压$dp$就行了.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 1e6+;

int n,m,p[N],g[N],cnt[<<];

ll dp[<<];

void chkmin(ll &a, ll b) {a>b?a=b:;}

int main() {

    REP(i,,(<<)-) cnt[i]=cnt[i>>]+(i&);

    while (~scanf("%d%d", &n, &m)) {

        REP(i,,n-) scanf("%d",p+i),g[i]=;

        REP(i,,m) {

            int a,b;

            scanf("%d%d",&a,&b);

            --a,--b;

            g[a] ^= <<b;

            g[b] ^= <<a;

        }

        sort(p,p+n);

        dp[] = ;

        int mx = (<<n)-;

        REP(i,,mx) dp[i] = 1e18;

        REP(i,,mx-) {

            REP(j,,n-) if (i>>j&^) {

                int x = cnt[i&g[j]], y = cnt[~i&mx&g[j]];

                chkmin(dp[i^<<j],dp[i]+(ll)(x-y)*p[cnt[i]]);

            }

        }

        printf("%lld\n", dp[mx]);

    }

}

巴特西

2019牛客国庆集训派对day3

最新文章

热门文章