ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2015)

题意：

　　给出一个每个数位都不同的数n，进行一场游戏。每次游戏将n个数的每个数位重组。如果重组后的数比原来的数大则继续游戏，否则算输。如果重组后的数是最大的数则算赢，问赢的概率。

题解：

　　用康拓展开求出n是第几大的数，然后递推后面的概率。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;

char s[];

double ans;

int fac[] = {, , , , , , , , , };

double cal(char *s) {

    int res = ;

    int k = strlen(s);

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

        int cnt = ;

        for(int j = i+; j < k; j++) if(s[j]<s[i]) cnt++;

        res += fac[k-i-]*cnt;

    }

    if(res==fac[k]-) return ;

    double ans = 1.0/fac[k];

    for(int i = res; i < fac[k]-; i++) ans += ans/fac[k];

    return ans;

}

int main() {

    scanf("%d", &t);

    while(t--) {

        scanf("%s", s);

        printf("%.9lf\n", cal(s));

    }

}

B.Unlucky Teacher（模拟）

题意：

　　Q个题目和M个学生的判卷，求出每道题的答案。如果求不出则输出？。

题解：

　　模拟即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;

int q, m;

int num[], state[];

char ans[];

char s1[], s2[];

int main() {

    scanf("%d", &t);

    while(t--) {

        memset(state, , sizeof(state));

        memset(num, , sizeof(num));

        scanf("%d%d", &q, &m);

        while(m--) {

            for(int i = ; i <= q; i++) {

                scanf("%s%s", s1, s2);

                if(s2[]=='T') num[i] = -, ans[i] = s1[];

                else {

                    if((num[i]==-)||((state[i]&(<<s1[]-'A'))>)) continue;

                    state[i] |= <<s1[]-'A';

                    num[i]++;

                    if(num[i]==) {

                        for(int j = ; j < ; j++)

                        if(!(state[i]&(<<j))) {

                            ans[i] = 'A'+j;

                            break;

                        }

                        num[i] = -;

                    }

                }

            }

        }

        for(int i = ; i <= q; i++) {

            if(num[i]>-) printf("?");

            else printf("%c", ans[i]);

            if(i < q) printf(" ");

        }

        puts("");

    }

}

C.Connecting Graph（并查集+二分）

题意：

　　初始有n个点，m次操作。每次操作加一条边或者询问两个点第一次连通的时刻（若不连通输出-1）。

题解：

　　GYM - 100814 C.Connecting Graph

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+;

int t;

int n, m;

int u, v, k;

int f[N], num[N];

vector<pair<int, int> > g[N];

vector<int> c[N];

bool check(int x) {

    int l = , r = g[u].size()-;

    while(l <= r) {

        int mid = l+r>>;

        if(g[u][mid].first <= x) l = mid+;

        else r = mid-;

    }

    int p1 = g[u][r].second;

    l = , r = g[v].size()-;

    while(l <= r) {

        int mid = l+r>>;

        if(g[v][mid].first <= x) l = mid+;

        else r = mid-;

    }

    int p2 = g[v][r].second;

    if(p1==p2) return ;

    return ;

}

int main() {

    scanf("%d", &t);

    while(t--) {

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

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

            num[i] = ;

            f[i] = i;

            c[i].clear();

            g[i].clear();

            c[i].push_back(i);

            g[i].push_back(make_pair(, i));

        }

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

            scanf("%d%d%d", &k, &u, &v);

            if(k&) {

                u = f[u]; v = f[v];

                if(u!=v) {

                    if(num[u]>num[v]) swap(u, v);

                    for(int j = ; j < num[u]; j++) {

                        c[v].push_back(c[u][j]);

                        f[c[u][j]] = v;

                        g[c[u][j]].push_back(make_pair(i, v));

                    }

                    num[v] += num[u];

                    num[u] = ;

                    c[u].clear();

                }

            }

            else {

                int l = , r = i-;

                while(l<=r) {

                    int mid = l+r>>;

                    if(check(mid)) r = mid-;

                    else l = mid+;

                }

                if(check(r+)) printf("%d\n", r+);

                else puts("-1");

            }

        }

    }

}

D.Frozen Rivers

题意：

　　一棵n个节点的树，每条边代表一条河。从点1开始边以每秒1个单位开始融化。每个点连的边（不包括连向父亲的）有一条融化完时剩下的该点连的边融化速度降为0.5。q次询问，每次询问某个时刻融化到叶子节点的数量。

题解：

　　设minn[u]代表节点u的边中权值最小的那个，将点u所有边的权值加上他们与minn[u]的差值。即每条边的权值翻倍再减去minn[u]。

　　这样处理完之后就省去了0.5的限制。问题变成了求叶子节点到根节点的距离。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+;

const int inf = 0x3f3f3f3f;

int t;

int n, q, p, c;

int tot;

int head[N], to[N], nxt[N], w[N], minn[N];

int cnt;

ll tim, num[N];

void dfs(int u, ll val) {

    if(minn[u]==inf) {

        num[++cnt] = val;

        return ;

    }

    for(int i = head[u]; ~i; i = nxt[i]) {

        w[i] = *w[i]-minn[u];

        dfs(to[i], val+w[i]);

    }

}

int main() {

    scanf("%d", &t);

    while(t--) {

        tot = cnt = ;

        scanf("%d", &n);

        for(int i = ; i <= n; i++) head[i] = -, minn[i] = inf;

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

            scanf("%d%d", &p, &c);

            to[++tot] = i; nxt[tot] = head[p]; head[p] = tot, w[tot] = c;

            minn[p] = min(minn[p], c);

        }

        dfs(, );

        sort(num+, num+cnt+);

        scanf("%d", &q);

        while(q--) {

            scanf("%lld", &tim);

            int ans = upper_bound(num+, num+cnt+, tim)-num-;

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

        }

    }

}

E.Palmyra（dp）

题意：

　　给出n*m的矩阵。从点（1，1）出发，可以向右或者向下移动，最后走到（n，m）。将路途上的点值乘起来，问最后的值拿6进制表示末尾最多有几个0。

题解：

　　题意可以理解为，使最后2的因子数和3的因子数中的最小值最大。

　　dp[i][j][k]表示走到（i，j），3的因子数为k时2的因子数最多是多少。

#include <bits/stdc++.h>

using namespace std;

int t;

int n, m;

int q[][][];

int dp[][][];

int main() {

    scanf("%d", &t);

    while(t--) {

        memset(q, , sizeof(q));

        memset(dp, -, sizeof(dp));

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

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

            for(int j = ; j <= m; j++) {

                scanf("%d", &q[i][j][]);

                int t = q[i][j][];

                while(t% == ) {

                    q[i][j][]++;

                    t /= ;

                }

                while(t% == ) {

                    q[i][j][]++;

                    t /= ;

                }

            }

        }

        dp[][][q[][][]] = q[][][];

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

            for(int j = ; j <= m; j++) {

                int n2 = q[i][j][];

                int n3 = q[i][j][];

                for(int k = ; k + n3 <= ; k++) {

                    if(dp[i][j-][k] != -)

                        dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i][j-][k]+n2);

                    if(dp[i-][j][k] != -)

                        dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i-][j][k]+n2);

                }

            }

        }

        int ans = ;

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

            int nn = min(dp[n][m][i], i);

            ans = max(ans, nn);

        }

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

    }

    return ;

}

F.Geometry

题意：

　　给出长和宽，判断时正方形还是矩形。

题解：

　　判断w是否等于h。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;

int w, h;

int main() {

    scanf("%d", &t);

    while(t--) {

        scanf("%d%d", &w, &h);

        if(w==h) puts("Square");

        else puts("Rectangle");

    }

}

G.It is all about wisdom（最短路+二分）

题意：

　　给出一个图，图中的每条边有使用的最低限制值和花费。问从1走到n在总花费小于k的前提下的最小限制值是多少。

题解：

　　标准的二分套最短路的题型。二分最小的限制值即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+;

const int inf = 0x3f3f3f3f;

int t;

int n, m, k;

int u, v, c, l, r;

int vis[N], dis[N];

struct node {

    int to, v, lim;

    node(int a, int b, int c) {

        to = a; v = b; lim = c;

    }

};

vector<node> g[N];

bool check(int x) {

    queue<int> q;

    for(int i = ; i <= n; i++) vis[i] = , dis[i] = inf;

    q.push();

    vis[] = ;

    dis[] = ;

    while(!q.empty()) {

        int v = q.front();

        q.pop();

        vis[v] = ;

        int len = g[v].size();

        for(int i = ; i < len; i++) {

            if(g[v][i].lim > x) continue;

            if(g[v][i].v+dis[v] < dis[g[v][i].to]) {

                dis[g[v][i].to] = g[v][i].v+dis[v];

                if(!vis[g[v][i].to]) {

                    q.push(g[v][i].to);

                    vis[g[v][i].to] = ;

                }

            }

        }

    }

    if(dis[n] < k) return ;

    return ;

}

int main() {

    scanf("%d", &t);

    while(t--) {

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

        r = ;

        for(int i = ; i <= n; i++) g[i].clear();

        while(m--) {

            scanf("%d%d%d%d", &u, &v, &c, &l);

            g[u].push_back(node(v, c, l));

            g[v].push_back(node(u, c, l));

            r = max(r, l);

        }

        l = ;

        while(l<=r) {

            int mid = l+r>>;

            if(check(mid)) r = mid-;

            else l = mid+;

        }

        if(check(r+)) printf("%d\n", r+);

        else puts("-1");

    }

}

I.Salem

题意：

　　给出n个数，求数对中最大的hamming距离。

题解：

　　每两个数求一下异或之后二进制下1个数量即可，输出最大值。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t, n;

int a[];

int main() {

    scanf("%d", &t);

    while(t--) {

        int ans = ;

        scanf("%d", &n);

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

            scanf("%d", &a[i]);

            for(int j = ; j < i; j++) {

                int p = a[i]^a[j], cnt = ;

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

                    if(p&(<<k)) cnt++;

                }

                ans = max(ans, cnt);

            }

        }

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

    }

}

J.Game

题意：

　　给出合并规则表。两个人轮流进行操作，每次选择从最左面或者最右面开始每两个合并成一个。如果最后剩的是元音字符，就是Salah获胜。否则Marzo获胜。

题解：

　　暴力维护每一种情况。用1表示S获胜，0表示M获胜。

　　当S操作时，若两种情况存在1，则当前为1。

　　当M操作时，若两种情况存在0，则当前为0。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e4+;

int t;

int tot;

int len[N];

char s[N][N];

char g[][];

char cmp[] = {'a', 'e', 'i', 'o', 'u'};

bool dfs(int num, int k) {

    if(len[num] < ) {

        char c;

        if(len[num]==) c = s[num][];

        else c = g[s[num][]-'a'][s[num][]-'a'];

        for(int i = ; i < ; i++) if(c==cmp[i]) return true;

        return false;

    }

    ++tot;

    for(int i = ; i < len[num]; i+=) {

        if(i==len[num]-) s[tot][i/] = s[num][i];

        else s[tot][i/] =  g[s[num][i]-'a'][s[num][i+]-'a'];

    }

    len[tot] = (len[num]+)/;

    bool res = dfs(tot, k^);

    if(len[num]&) {

        ++tot;

        s[tot][] = s[num][];

        for(int i = ; i < len[num]; i+=) {

            s[tot][i/+] =  g[s[num][i]-'a'][s[num][i+]-'a'];

        }

        len[tot] = (len[num]+)/;

        if(k) res &= dfs(tot, k^);

        else res |= dfs(tot, k^);

    }

    return res;

}

int main() {

    scanf("%d", &t);

    while(t--) {

        tot = ;

        for(int i = ; i < ; i++) scanf("%s", g[i]);

        scanf("%s", s[]);

        len[] = strlen(s[]);

        if(dfs(, )) puts("Salah");

        else puts("Marzo");

    }

}

K.PhD math

题意：

　　给出a，b，n，p（a<b）。求a/b的前n位数中有多少字串整除p。

题解：

　　从1扫到n。维护每一位新增的余数。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6+;

int t;

ll a, b;

int n, p;

int bit[N];

int v1[], v2[];

ll ans;

int main() {

    scanf("%d", &t);

    while(t--) {

        ans = ;

        memset(v1, , sizeof(v1));

        memset(v2, , sizeof(v2));

        scanf("%lld%lld%d%d", &a, &b, &n, &p);

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

            a *= ;

            bit[i] = a/b;

            a = a%b;

        }

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

            for(int j = ; j < p; j++) {

                if(i&) v1[j] = ;

                else v2[j] = ;

            }

            for(int j = ; j < p; j++) {

                if(i&) v1[(j*+bit[i])%p] += v2[j];

                else v2[(j*+bit[i])%p] += v1[j];

            }

            if(i&) v1[bit[i]%p]++, ans += v1[];

            else v2[bit[i]%p]++, ans += v2[];

        }

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

    }

}

L.Candy Jars（博弈）

题意：

　　N个罐子，每个罐子有一定数量的糖。两个人轮流操作，每次选定一罐，把其他罐中的糖都扔掉。然后把选定罐中的糖任意分配给每个罐，但要保证每个罐中都有糖。不能操作者判输。

题解：

　　只要有一个罐子糖数必胜则操作者必胜。

　　当所有罐子糖数小于N时无法给所有罐子分配糖，必输。

　　当存在罐子糖数在[N，N(N-1)]时，可以把糖分成必输态，即分成所有罐子糖数小于N的状态，这时必胜。

　　然后举例发现N(N-1)是一个循环节，取模就可以了。

#include <bits/stdc++.h>

using namespace std;

int t, n;

int k;

int main() {

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        int ans = ;

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

            scanf("%d", &k);

            k %= n*(n-);

            if(k== || k > n-) ans = ;

        }

        if(ans) puts("Alice");

        else puts("Bob");

    }

}

M.Building Force Fields（dp）

题意：

　　按x升序给出n个点的二维坐标，并保证没有两个点x坐标相同。可以在任意两个点之间连边，最后要保证每个点都在连边之下（或在连边上）。问最小的连边总长。

题解：

　　dp[i]表示第i个点结尾的最小总连边长。

　　转移是枚举i向第j（1<=j<i）个点连边，要保证连边上方无点。即第i和第j个点的斜率比第i个点和（j，i）范围内的点的斜率都小。最后取最小值。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t, n;

double dp[];

struct node {

    ll x, y;

}a[];

double dis(int n1, int n2) {

    return sqrt((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x)+(a[n1].y-a[n2].y)*(a[n1].y-a[n2].y));

}

int main() {

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        for(int i = ; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y);

        dp[] = dis(, );

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

            int pos = i-;

            dp[i] = min(dp[i-], dp[i-])+dis(i, i-);

            for(int j = i-; j >= ; j--) {

                if((a[i].y-a[pos].y)*(a[i].x-a[j].x) >= (a[i].y-a[j].y)*(a[i].x-a[pos].x)) {

                    dp[i] = min(dp[i], min(dp[j-], dp[j])+dis(i, j));

                    pos = j;

                }

            }

        }

        printf("%.6lf\n", dp[n]);

    }

}

巴特西

ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2015)

最新文章

热门文章