Educational Codeforces Round 43

Educational Codeforces Round 43

A. Minimum Binary Number

显然可以把所有\(1\)合并成一个

注意没有\(1\)的情况

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){

    int n;

    string s;

    cin >> n >> s;

    int c0 = 0, c1 = 0;

    for(int x : s) if(x=='0') c0++; else c1++;

    if(!c1) cout << 0 << endl;

    else{

        cout << 1;

        while(c0--) cout << 0;

    }

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

B. Lara Croft and the New Game

就摁模拟它怎么走的就好了，有点小麻烦

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

typedef long long int LL;

void solve(){

    LL n, m, k;

    cin >> n >> m >> k;

    if(k<n) cout << k + 1 << ' ' << 1 << endl;

    else{

        k -= n;

        int num = k / (m-2+m);

        int lft = k % (m-2+m);

        int x = n - 2 * num;

        if(!lft) cout << x << ' ' << 2 << endl;

        else{

            if(lft<=m-2) cout << x << ' ' << 2 + lft << endl;

            else{

                lft -= m - 1;

                x -= 1;

                cout << x << ' ' << m - lft << endl;

            }

        }

    }

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

C. Nested Segments

把所有线段先按左端点从小到大排序，左端点相同的按右端点从大到小排，然后扫一遍，这样就不用管左端点的大小关系了，只要维护遍历过程中右端点最右的位置和相应线段的编号即可

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 3e5+7;

int n;

pair<pair<int,int>,int> seg[MAXN];

void solve(){

    ____();

    cin >> n;

    for(int i = 1; i <= n; i++){

        cin >> seg[i].first.first >> seg[i].first.second;

        seg[i].second = i;

    }

    sort(seg+1,seg+1+n,[&](pair<pair<int,int>, int> a, pair<pair<int,int>,int > b){

        if(a.first.first==b.first.first) return a.first.second > b.first.second;

        else return a.first.first < b.first.first;

    });

    int rm = 0, id = 0;

    for(int i = 1; i <= n; i++){

        if(seg[i].first.second>rm){

            rm = seg[i].first.second;

            id = seg[i].second;

        }else{

            cout << seg[i].second << ' ' << id << endl;

            return;

        }

    }

    cout << -1 << ' ' << -1 << endl;

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

D. Degree Set

一开始有\(d_n+1\)个点，要构造出度数集合为\(d_1,d_2,\cdots,d_n\)的图

把编号\(1-d_1\)的点向其他所有点连边，那么\(1-d_1\)的点的度数为\(d_n-1\)，其他点的度数为\(d_1\)

保留\(1-d_1\)的点和\(d_{n-1}+2-d_n+1\)的点

剩下的\(d_1+1-d_{n-1}+1\)的点（一共\(d_{n-1}-d_1+1\)个点），需要构造一个度数集合为\(d_2-d_1,d_3-d_1,\cdots,d_{n-1}-d_1\)的图，可以发现是一个小规模的原问题，递归解决即可

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e3+7;

void solve(){

    ____();

    static int n, d[MAXN]; cin >> n;

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

    vector<pair<int,int> > edges;

    int l = 1, r = n, D = 0;

    for(int l = 1, r = n, D = 0; l <= r; D += d[l], l++, r--){

        for(int i = 1; i <= d[l]; i++) for(int j = i + 1; j <= d[r] + 1; j++) edges.push_back({i+D,j+D});

        for(int i = l + 1; i <= r - 1; i++) d[i] -= d[l];

    }

    printf("%d\n",edges.size());

    for(auto &e : edges) printf("%d %d\n",e.first,e.second);

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

E. Well played!

显然把生命翻倍给同一个随从是最优的

那么枚举给的这个随从即可

注意没有心火(攻击等于生命)的情况

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

typedef long long int LL;

const int MAXN = 2e5+7;

int n, a, b;

pair<LL,LL> cre[MAXN];

LL pre[MAXN];

void solve(){

    ____();

    cin >> n >> a >> b;

    b = min(n,b);

    for(int i = 1; i <= n; i++) cin >> cre[i].first >> cre[i].second;

    sort(cre+1,cre+1+n,[&](pair<LL,LL> &a, pair<LL,LL> &b){

        return a.first - a.second > b.first - b.second;

    });

    for(int i = 1; i <= n; i++) pre[i] = pre[i-1] + max(0ll,cre[i].first - cre[i].second);

    LL sum = 0, ret = 0;

    for(int i = 1; i <= n; i++) sum += cre[i].second;

    ret = sum + pre[b];

    sum += pre[b];

    for(int i = 1; i <= b; i++){

        LL ts = sum - max(0ll,cre[i].first-cre[i].second);

        ts -= cre[i].second;

        ret = max(ret,ts+(cre[i].first<<a));

    }

    if(b){

        for(int i = b + 1; i <= n; i++){

            LL ts = sum - max(0ll,cre[b].first-cre[b].second);

            ts -= cre[i].second;

            ret = max(ret,ts+(cre[i].first<<a));

        }

    }

    cout << ret << endl;

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

F. Minimal k-covering

考虑网络流建图，所有边从左半图连右半图，容量为\(1\)，源点向左半图所有点连边，容量为\(deg[x]-k\)，右半图的点向汇点连边，容量为\(deg[y]-k\)，然后有流量的边边即为需要删掉的边

从大到小枚举\(k\)，每次从源点到左半图的点增加\(1\)容量的边，右半图的点向汇点增加\(1\)容量的边，增广一次即可

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 4e3+7;

const int INF = 0x3f3f3f3f;

#define S 0

#define T MAXN - 1

set<int> edges;

struct EDGE{

    int to,cap,rev,id;

    EDGE(){};

    EDGE(int to, int cap, int rev, int id):to(to),cap(cap),rev(rev),id(id){};

};

vector<EDGE> G[MAXN];

int iter[MAXN],rk[MAXN];

void ADDEDGE(int u, int v, int cap, int id){

    G[u].push_back(EDGE(v,cap,(int)G[v].size(),id));

    G[v].push_back(EDGE(u,0,(int)G[u].size()-1,-id));

}

bool bfs(){

    memset(rk,0,sizeof(rk));

    memset(iter,0,sizeof(iter));

    rk[S] = 1;

    queue<int> que;

    que.push(S);

    while(!que.empty()){

        int u = que.front();

        que.pop();

        for(auto e : G[u]){

            if(!e.cap or rk[e.to]) continue;

            rk[e.to] = rk[u] + 1;

            que.push(e.to);

        }

    }

    return rk[T]!=0;

}

int dfs(int u, int flow){

    if(u==T) return flow;

    for(int &i = iter[u]; i < (int)G[u].size(); i++){

        auto &e = G[u][i];

        if(!e.cap or rk[e.to]!=rk[u]+1) continue;

        int d = dfs(e.to,min(e.cap,flow));

        if(d){

            e.cap -= d;

            G[e.to][e.rev].cap += d;

            if(e.id){

                if(e.id>0) edges.erase(e.id);

                else edges.insert(-e.id);

            }

            return d;

        }

    }

    return 0;

}

void Dinic(){

    while(bfs()){

        int d = dfs(S,INF);

        while(d) d = dfs(S,INF);

    }

}

int n1, n2, m, deg1[MAXN], deg2[MAXN];

void solve(){

    ____();

    cin >> n1 >> n2 >> m;

    for(int i = 1; i <= m; i++){

        int u, v; cin >> u >> v;

        ADDEDGE(u,v+n1,1,i);

        deg1[u]++; deg2[v]++;

    }

    for(int i = 1; i <= m; i++) edges.insert(i);

    int mindeg = min(*min_element(deg1+1,deg1+1+n1),*min_element(deg2+1,deg2+1+n2));

    vector<vector<int> > vec(mindeg,vector<int>());

    for(int i = 1; i <= n1; i++) ADDEDGE(S,i,deg1[i]-mindeg,0);

    for(int i = 1; i <= n2; i++) ADDEDGE(i+n1,T,deg2[i]-mindeg,0);

    for(int k = mindeg; k; k--){

        Dinic();

        for(int e : edges) vec[k-1].push_back(e);

        for(int i = 1; i <= n1; i++) ADDEDGE(S,i,1,0);

        for(int i = 1; i <= n2; i++) ADDEDGE(i+n1,T,1,0);

    }

    puts("0");

    for(int i = 0; i < mindeg; i++){

        printf("%d",vec[i].size());

        for(int x : vec[i]) printf(" %d",x);

        puts("");

    }

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

巴特西

Educational Codeforces Round 43

最新文章

热门文章