2018-2019 ICPC, NEERC, Southern Subregional Contest (codeforces 1070)

2022-11-16 08:54:50

A. 直接从状态(0,0)bfs, 这样一定是最小的

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#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

#ifdef ONLINE_JUDGE

const int N = 1e6+;

#else

const int N = ;

#endif

int d, s;

int vis[][];

pii pre[][];

void bfs() {

    queue<pii> q;

    q.push(pii(,));

    vis[][] = ;

    while (q.size()) {

        int x=q.front().x,y=q.front().y;

        q.pop();

        REP(i,,) if (y+i<=s) {

            int xx=(x*+i)%d,yy=y+i;

            if (!vis[xx][yy]) {

                vis[xx][yy] = ;

                pre[xx][yy]=pii(x,y);

                q.push(pii(xx,yy));

            }

        }

    }

}

void dfs2(int x, int y) {

    if (x||y) {

        dfs2(pre[x][y].x,pre[x][y].y);

        printf("%d",y-pre[x][y].y);

    }

}

int main() {

    scanf("%d%d", &d, &s);

    bfs();

    if (!vis[][s]) return puts("-1"),;

    dfs2(,s),hr;

}

C. 事件差分一下, 然后线段树上二分. 刚开始用map维护前k小, 结果TLE on test 77, 感觉复杂度应该对的啊...可能常数太大. 线段树写的时候要注意不仅价格和会爆$int$, 个数和也会爆.... 十分钟打完, WA了一个多小时才发现是少个$long long$

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#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,k,m,cnt;

ll ans;

vector<pii> s[N];

struct {ll c,s;} tr[N<<];

void update(int o, int l, int r, int p, int c) {

    tr[o].c+=c,tr[o].s+=(ll)p*c;

    if (l!=r) mid>=p?update(ls,p,c):update(rs,p,c);

}

ll find(int o, int l, int r, int k) {

    if (tr[o].c<=k) return tr[o].s;

    if (l==r) return min(tr[o].c,(ll)k)*l;

    if (tr[lc].c>=k) return find(ls,k);

    return tr[lc].s+find(rs,k-tr[lc].c);

}

int main() {

    scanf("%d%d%d", &n, &k, &m);

    int mx = ;

    REP(i,,m) {

        int l=rd(),r=rd(),c=rd(),p=rd();

        s[l].pb(pii(p,c)), s[r+].pb(pii(p,-c));

        mx = max(mx, p);

    }

    REP(i,,n) {

        for (auto &&t:s[i]) update(,,mx,t.x,t.y);

        ans += find(,,mx,k);

    }

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

}

F. 贪心, 11肯定要选, 01和10同时选不会产生负面, 最后从剩余的01或10,和00中选前k大与11匹配.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#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

#ifdef ONLINE_JUDGE

const int N = 1e6+;

#else

const int N = ;

#endif

int n;

priority_queue<int> g[N];

int main() {

    scanf("%d", &n);

    int tot = , ans = ;

    REP(i,,n) {

        int x, y;

        scanf("%d%d", &x, &y);

        g[x].push(y);

        if (x==) ++tot,ans+=y;

    }

    int sz = min(g[].size(),g[].size());

    REP(i,,sz-) {

        ans+=g[].top()+g[].top();

        g[].pop(),g[].pop();

    }

    int now = g[].size()?:;

    REP(i,,tot) g[now].push();

    REP(i,,tot) g[].push();

    REP(i,,tot) {

        if (g[now].top()>g[].top()) {

            ans += g[now].top();

            g[now].pop();

        }

        else {

            ans += g[].top();

            g[].pop();

        }

    }

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

}

J. bitset优化

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#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 = 2e5+;

int n, m, k, f[N];

char s[N];

const int N1 = , N2 = , N3 = , N4 = ;

const int N5 = , N6 = , N7 = ;

const int N8 = , N9 = , N10 = ;

bitset<N1> b1;

bitset<N2> b2;

bitset<N3> b3;

bitset<N4> b4;

bitset<N5> b5;

bitset<N6> b6;

bitset<N7> b7;

bitset<N8> b8;

bitset<N9> b9;

bitset<N10> b10;

#define solve(b) ({REP(i,1,*f) {\

    b.reset();\

    b.set();\

    REP(j,,*f) if (j!=i) b |= b<<f[j];\

    PER(j,,min(n,f[i])) {\

        int t = max(,m-k+n+f[i]-j);\

        if (b[n-j]) ans = min(ans, j*t);\

    }\

}})

void work() {

    scanf("%d%d%d%s", &n, &m, &k, s+);

    REP(i,'A','Z') f[i]=;

    REP(i,,k) ++f[s[i]];

    if (n>m) swap(n,m);

    *f = ;

    REP(i,'A','Z') if (f[i]) f[++*f]=f[i];

    int ans = 1e9;

    if (n>N9) solve(b10);

    else if (n>N8) solve(b9);

    else if (n>N7) solve(b8);

    else if (n>N6) solve(b7);

    else if (n>N5) solve(b6);

    else if (n>N4) solve(b5);

    else if (n>N3) solve(b4);

    else if (n>N2) solve(b3);

    else if (n>N1) solve(b2);

    else solve(b1);

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

}

int main() {

    int t;

    scanf("%d", &t);

    while (t--) work();

}

码农公寓

相关文章