2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)（9/11）

2022-10-07 12:19:26

$$2017-2018\ ACM-ICPC\ German\ Collegiate\ Programming\ Contest (GCPC 2017)$$

$A.Drawing\ Borders$

$B.Buildings$

Polya定理搞一搞

//#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);};

using LL = int_fast64_t;

const LL MOD = 1e9+7;

int n,m,c;

LL qpow(LL a, LL b){

    LL ret = 1;

    while(b){

        if(b&1) ret = ret * a % MOD;

        b >>= 1;

        a = a * a % MOD;

    }

    return ret;

}

LL inv(LL x){ return qpow(x,MOD-2); }

int main(){

    ____();

    cin >> n >> m >> c;

    LL ret = 0;

    for(int i = 0; i < m; i++) ret = (ret + qpow(qpow(c,n*n),__gcd(i,m))) % MOD;

    ret = (ret * inv(m)) % MOD;

    cout << ret << endl;

    return 0;

}

$C.Joyride$

DP,$dp[i][j]$表示当前时间为$i$，且当前在$j$号点处的最小花费，分两种情况转移

在原地不动，位置不变
去另一个位置

//#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 = 1111;

int x,n,m,t,f[MAXN][MAXN];

const int INF = 0x3f3f3f3f;

pair<int,int> pr[MAXN];

vector<int> G[MAXN];

int main(){

    ____();

    cin >> x >> n >> m >> t;

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

        int u, v;

        cin >> u >> v;

        G[u].emplace_back(v);

        G[v].emplace_back(u);

    }

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

    memset(f,0x3f,sizeof(f));

    if(x<pr[1].first){

        cout << "It is a trap." << endl;

        return 0;

    }

    f[pr[1].first][1] = pr[1].second;

    for(int c = pr[1].first; c < x; c++){

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

            if(c+pr[u].first<=x) f[c+pr[u].first][u] = min(f[c+pr[u].first][u],f[c][u]+pr[u].second);

            for(int v : G[u]){

                int cost = t + pr[v].first;

                if(c+cost>x) continue;

                f[c+cost][v] = min(f[c+cost][v],f[c][u]+pr[v].second);

            }

        }

    }

    int ret = f[x][1];

    if(ret==INF) cout << "It is a trap." << endl;

    else cout << ret << endl;

    return 0;

}

$D.Pants\ On\ Fire$

Floyd传递闭包

//#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 = 222;

map<string,int> msk;

int n,m,ID;

bool G[MAXN][MAXN];

int main(){

    ____();

    cin >> n >> m;

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

        int u,v;

        string s;

        cin >> s;

        if(!msk.count(s)) msk.insert(make_pair(s,++ID));

        u = msk.at(s);

        cin >> s >> s >> s >> s;

        if(!msk.count(s)) msk.insert(make_pair(s,++ID));

        v = msk.at(s);

        G[u][v] = true;

    }

    for(int k = 1; k <= ID; k++) for(int i = 1; i <= ID; i++) for(int j = 1; j <= ID; j++){

        G[i][j] = (G[i][j] or (G[i][k] and G[k][j]));

    }

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

        int u, v;

        string s;

        cin >> s;

        if(!msk.count(s)) msk.insert(make_pair(s,++ID));

        u = msk.at(s);

        cin >> s >> s >> s >> s;

        if(!msk.count(s)) msk.insert(make_pair(s,++ID));

        v = msk.at(s);

        if(G[u][v]) cout << "Fact" << endl;

        else if(G[v][u]) cout << "Alternative Fact" << endl;

        else cout << "Pants on Fire" << endl;

    }

    return 0;

}

$E.Perpetuum\ Mobile$

建图spfa判正环，可以对权值取$log$就可以转换为权值加和

//#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 = 888;

int n,m,vis[MAXN],inq[MAXN];

double dist[MAXN];

vector<pair<int,double> > G[MAXN];

bool spfa(){

    queue<int> que;

    memset(inq,0,sizeof(inq));

    fill(dist,dist+MAXN,0);

    fill(vis,vis+MAXN,1);

    for(int i = 1; i <= n; i++) que.push(i);

    while(!que.empty()){

        int u = que.front();

        que.pop();

        vis[u] = false;

        for(auto e : G[u]){

            int v = e.first;

            double d = e.second;

            if(dist[u]+d>dist[v]){

                dist[v] = dist[u] + d;

                if(!vis[v]){

                    vis[v] = true;

                    inq[v]++;

                    if(inq[v]>=n) return true;

                    que.push(v);

                }

            }

        }

    }

    return false;

}

int main(){

    cin >> n >> m;

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

        int u, v;

        double conv;

        cin >> u >> v >> conv;

        G[u].emplace_back(make_pair(v,log(conv)));

    }

    if(spfa()) cout << "inadmissible" << endl;

    else cout << "admissible" << endl;

    return 0;

}

$F.Plug\ It\ In$

暴力枚举，每次跑二分图匹配，这样的复杂度是$n^3$，会T

考虑加上新的点之后，之前的匹配是不变的，所以可以先把之前的匹配保存下来，每次枚举的时候找增广路即可

//#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 = 1507;

vector<int> G[MAXN];

int m,n,k,match[MAXN],tot,pmt[MAXN];

bool vis[MAXN];

bool dfs(int u){

    vis[u] = true;

    for(int v : G[u]){

        if(match[v]==-1 or (!vis[match[v]] and dfs(match[v]))){

            match[v] = u;

            return true;

        }

    }

    return false;

}

void hungary(){

    memset(match,255,sizeof(match));

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

        memset(vis,false,sizeof(vis));

        if(dfs(i)) tot++;

    }

}

int main(){

    ____();

    cin >> m >> n >> k;

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

        int u, v;

        cin >> u >> v;

        G[u].emplace_back(v);

    }

    hungary();

    for(int i = 1; i <= n; i++) pmt[i] = match[i];

    int add = 0;

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

        int tmp = 0;

        for(int j = 1; j <= n; j++) match[j] = pmt[j];

        G[m+1].clear();

        copy(G[i].begin(),G[i].end(),back_inserter(G[m+1]));

        memset(vis,false,sizeof(vis));

        if(dfs(m+1)){

            tmp++;

            G[m+2].clear();

            copy(G[m+1].begin(),G[m+1].end(),back_inserter(G[m+2]));

            memset(vis,false,sizeof(vis));

            if(dfs(m+2)) tmp++;

        }

        add = max(add,tmp);

    }

    cout << tot + add << endl;

    return 0;

}

$G.Water\ Testing$

皮克定理，顶点为整点的多边形的面积S=多边形内部整点数A+(多边形边上整点数B/2)-1

多边形面积可以用向量差积来求

所以$A=S+1-B/2$

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

using LL = int_fast64_t;

int n;

pair<LL,LL> pt[MAXN];

pair<LL,LL> vect(const pair<LL,LL> &A, const pair<LL,LL> &B){

    return make_pair(B.first-A.first,B.second-A.second);

}

LL xpro(const pair<LL,LL> &A, const pair<LL,LL> &B){

    return A.first * B.second - B.first * A.second;

}

LL cal(const pair<LL,LL> &A, const pair<LL,LL> &B){

    return __gcd(abs(A.first-B.first),abs(A.second-B.second)) - 1;

}

int main(){

    ____();

    cin >> n;

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

    LL dbarea = 0;

    for(int i = 2; i < n; i++) dbarea += xpro(vect(pt[1],pt[i]),vect(pt[1],pt[i+1]));

    dbarea = dbarea < 0 ? - dbarea : dbarea;

    LL tot = n;

    for(int i = 1; i < n; i++) tot += cal(pt[i],pt[i+1]);

    tot += cal(pt[1],pt[n]);

    cout << (dbarea-tot+2)/2 << endl;

    return 0;

}

$H.Ratatoskr$

考虑如何采取最佳决策，对于松鼠，最佳位置就是在两只乌鸦中间，这样不管乌鸦怎么跑，松鼠都可以从起飞的乌鸦的那一边走，对于乌鸦的最佳决策就是两只乌鸦交替向松鼠的方向移动，把松鼠逼到叶子节点即可，所以最差的情况，就是找一个根节点，然后把松鼠逼到叶子节点上，也就是找任意点为根的最大深度的最小值（这个情况下就是先堵住根节点，然后推进到叶子节点）。

还有一种情况就是，一只乌鸦先固定，然后往松鼠存在的那棵子树上逼近即可

//#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 = 88;

vector<int> G[MAXN];

int n,r,h,m,vis[MAXN];

int dfs(int u, int f, int d){

    int maxd = d; vis[u] = true;

    for(int v : G[u]) if(v!=f) maxd = max(maxd,dfs(v,u,d+1));

    return maxd;

}

int giao(int raven){

    memset(vis,0,sizeof(vis));

    for(int v : G[raven]){

        int dep = dfs(v,raven,1);

        if(vis[r]) return dep;

    }

}

int main(){

    ____();

    cin >> n >> r >> h >> m;

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

        int u, v;

        cin >> u >> v;

        G[u].emplace_back(v);

        G[v].emplace_back(u);

    }

    int ret = MAXN;

    for(int i = 1; i <= n; i++) ret = min(ret,dfs(i,0,1));

    ret = min(ret,min(giao(h),giao(m)));

    cout << ret << endl;

    return 0;

}

$I.Uberwatch$

DP，$dp[i]$表示当前时刻为$i$的最多总分，状态转移方程为$dp[i]=max_{j=1}^{i-m}dp[j]+A[i]$

//#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,m,A[MAXN];

struct SegmentTree{

    int maxx[MAXN<<2],l[MAXN<<2],r[MAXN<<2];

    #define ls(rt) rt << 1

    #define rs(rt) rt << 1 | 1

    #define pushup(rt) maxx[rt] = max(maxx[ls(rt)],maxx[rs(rt)])

    void build(int L, int R, int rt){

        l[rt] = L; r[rt] = R;

        if(L+1==R) return;

        int mid = (L + R) >> 1;

        build(L,mid,ls(rt)); build(mid,R,rs(rt));

    }

    void update(int pos, int rt, int x){

        if(l[rt]+1==r[rt]){

            maxx[rt] = x;

            return;

        }

        int mid = (l[rt] + r[rt]) >> 1;

        if(pos<mid) update(pos,ls(rt),x);

        else update(pos,rs(rt),x);

        pushup(rt);

    }

    int qmax(int L, int R, int rt){

        if(l[rt]>=R or L>=r[rt]) return 0;

        if(L<=l[rt] and r[rt]<=R) return maxx[rt];

        return max(qmax(L,R,ls(rt)),qmax(L,R,rs(rt)));

    }

}ST;

int main(){

    ____();

    cin >> n >> m;

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

    ST.build(1,n+1,1);

    for(int t = m + 1; t <= n; t++) ST.update(t,1,ST.qmax(1,t-m+1,1)+A[t]);

    cout << ST.qmax(1,n+1,1) << endl;

    return 0;

}

$J.Word\ Clock$

$K.You Are Fired$

签到

//#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 = 1e4+7;

pair<int,string> pr[MAXN];

int n,d,k;

int main(){

    ____();

    cin >> n >> d >> k;

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

    sort(pr+1,pr+1+n,[](const pair<int,string> &A, const pair<int,string> &B){

        return A.first > B.first;

    });

    vector<string> vec;

    int tot = 0;

    for(int i = 1; i <= min(d,k); i++){

        tot += pr[i].first;

        vec.emplace_back(pr[i].second);

        if(tot>=d) break;

    }

    if(tot<d){

        cout << "impossible" << endl;

        return 0;

    }

    cout << vec.size() << endl;

    for(auto name : vec) cout << name << ", YOU ARE FIRED!" << endl;

    return 0;

}

码农公寓

2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)（9/11）