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

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 '
'
#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+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef ONLINE_JUDGE
const int N = 1e6+10;
#else
const int N = 111;
#endif

int d, s;
int vis[530][5030];
pii pre[530][5030];
void bfs() {
    queue<pii> q;
    q.push(pii(0,0));
    vis[0][0] = 1;
    while (q.size()) {
        int x=q.front().x,y=q.front().y;
        q.pop();
        REP(i,0,9) if (y+i<=s) { 
            int xx=(x*10+i)%d,yy=y+i;
            if (!vis[xx][yy]) {
                vis[xx][yy] = 1;
                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[0][s]) return puts("-1"),0;
    dfs2(0,s),hr;
}
View Code

B.

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 '
'
#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+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
int n,k,m,cnt;
ll ans;
vector<pii> s[N];
struct {ll c,s;} tr[N<<2];
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 = 0;
    REP(i,1,m) {
        int l=rd(),r=rd(),c=rd(),p=rd();
        s[l].pb(pii(p,c)), s[r+1].pb(pii(p,-c));
        mx = max(mx, p);
    }
    REP(i,1,n) {
        for (auto &&t:s[i]) update(1,1,mx,t.x,t.y);
        ans += find(1,1,mx,k);
    }
    printf("%lld
", ans);
}
View Code

  

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 '
'
#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+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef ONLINE_JUDGE
const int N = 1e6+10;
#else
const int N = 111;
#endif

int n;
priority_queue<int> g[N];

int main() {
    scanf("%d", &n);
    int tot = 0, ans = 0;
    REP(i,1,n) { 
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push(y);
        if (x==11) ++tot,ans+=y;
    }
    int sz = min(g[10].size(),g[1].size());
    REP(i,0,sz-1) { 
        ans+=g[10].top()+g[1].top();
        g[10].pop(),g[1].pop();
    }
    int now = g[10].size()?10:1;
    REP(i,1,tot) g[now].push(0);
    REP(i,1,tot) g[0].push(0);
    REP(i,1,tot) {
        if (g[now].top()>g[0].top()) {
            ans += g[now].top();
            g[now].pop();
        }
        else {
            ans += g[0].top();
            g[0].pop();
        }
    }
    printf("%d
", ans);
}
View Code

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 '
'
#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+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 2e5+10;
int n, m, k, f[N];
char s[N];
const int N1 = 30, N2 = 110, N3 = 210, N4 = 410;
const int N5 = 1010, N6 = 2010, N7 = 4010;
const int N8 = 8010, N9 = 16010, N10 = 30010;
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(0);
    REP(j,1,*f) if (j!=i) b |= b<<f[j];
    PER(j,0,min(n,f[i])) {
        int t = max(0,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+1);
    REP(i,'A','Z') f[i]=0;
    REP(i,1,k) ++f[s[i]];
    if (n>m) swap(n,m);
    *f = 0;
    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
", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) work();
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/uid001/p/10807083.html