@Dmaxiya 2018-08-17T10:27:12.000000Z 字数 7061 阅读 897

Codeforces Round #383 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #383 (Div. 2)
过题数：4
排名：181/14510

A. Arpa's hard exam and Mehrdad's naive cheat

题意

求 $1378^n$ 的最后一位数。

数据范围

$0\leq n\leq10^9$

题解

快速幂。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int MOD = 10;
LL n;
LL fast_pow(LL res, LL n) {
    LL ans = 1;
    for(ans = 1; n != 0; n >>= 1) {
        if(n % 2 == 1) {
            ans *= res;
            ans %= MOD;
        }
        res *= res;
        res %= MOD;
    }
    return ans;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%I64d", &n) != EOF) {
        printf("%I64d\n", fast_pow(1378, n) % 10);
    }
    return 0;
}

B. Arpa's obvious problem and Mehrdad's terrible solution

题意

给定一个长度为 $n$ 的序列 $a_1,a_2\cdots a_n$ 和 $x$ ，求这个序列中满足 $a_i\bigoplus a_j=x,1\leq i<j\leq n$ 的所有 $<i,j>$ 有序对个数。其中 $\bigoplus$ 是按位异或运算符。

数据范围

$1\leq n\leq10^5,0\leq x\leq10^5\\1\leq a_i\leq10^5$

题解

利用 $\bigoplus$ 的逆运算是其本身，先对原序列排序，对于每个 $a_i$ 二分找到所有 $a_i\bigoplus x=a_j$ 的 $j$ 的个数，由于这样找到的结果是 $(i,j)$ 的无序对，所以最后的结果要除以 $2$ ，要注意 $x=0$ 的情况，此时 $a_i\bigoplus x=a_i$ ，所以当 $x=0$ 时，对每个 $a_i$ 统计出所有等于 $a_i$ 的无序对个数时，应减去它本身。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, x;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &x) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        sort(num, num + n);
        int *it1, *it2;
        LL ans = 0;
        for(int i = 0; i < n; ++i) {
            it1 = lower_bound(num, num + n, num[i] ^ x);
            it2 = upper_bound(num, num + n, num[i] ^ x);
            ans += it2 - it1;
            if(x == 0) {
                --ans;
            }
        }
        printf("%I64d\n", ans / 2);
    }
    return 0;
}

C. Arpa's loud Owf and Mehrdad's evil plan

题意

给出一个长度为 $n$ 的序列 $crush_1,crush_2\cdots crush_n$ ，表示第 $i$ 个人将 $crush$ 第 $crush_i$ 个人，每一轮每个人往后 $crush$ 一个人（相当于把信息往后一个人传），现在要求经过的最少的轮数，使得满足这样一个条件：经过 $ans$ 轮后，如果第 $x$ 个人的信息正好传达到第 $y$ 个人，那么第 $y$ 个人的信息也正好传达到第 $x$ 个人，如果不存在这样的轮数，输出 $-1$ 。

数据范围

$1\leq n\leq100\\1\leq crush_i\leq n$

题解

从 $i$ 往 $crush_i$ 连一条有向边，那么这个有向图上所有边一定都在环上，如果存在不在环上的点，那么这个点所在的链的起点一定无法收到消息，所以这样的序列就是不满足条件的序列，所以不满足条件的图，就是存在入度为 $0$ 的节点，（因为每个点的出度一定都等于 $1$ ，所以如果存在链，一定是由入度为 $0$ 的点到达的）这种情况下输出 $-1$ 。
其他情况下，序列构成的有向图一定是一个个简单环，在环上的信息传递，如果环上节点的个数为奇数个（设为 $cnt$ ），要使 $x$ 和 $y$ 之间能互相传达信息，至少要经过 $cnt$ 轮，如果环上节点数为偶数个，则满足条件的最少的轮数应该是 $\frac{cnt}{2}$ ，对所有的环的最少轮数取最小公倍数，就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, x;
LL ans;
bool vis[maxn];
int num[maxn], fa[maxn], deg[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        vis[i] = false;
        fa[i] = i;
        num[i] = 1;
        deg[i] = 0;
    }
}
int Find(int x) {
    return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy) {
        fa[xx] = yy;
        num[yy] += num[xx];
    }
}
LL gcd(LL x, LL y) {
    return (y == 0? x: gcd(y, x % y));
}
LL lcm(LL x, LL y) {
    return x / gcd(x, y) * y;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = 1;
        Init();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            unit(x, i);
            ++deg[x];
        }
        bool flag = true;
        for(int i = 1; i <= n; ++i) {
            if(deg[i] == 0) {
                flag = false;
                break;
            }
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            int f = Find(i);
            if(!vis[f]) {
                vis[f] = true;
                if(num[f] % 2 == 0) {
                    ans = lcm(ans, num[f] / 2);
                } else {
                    ans = lcm(ans, num[f]);
                }
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

D. Arpa's weak amphitheater and Mehrdad's valuable Hoses

题意

$Mehrdad$ 想要邀请一些女生来到他的舞会，每个女生都有对应的美丽值 $b_i$ 和重量 $w_i$ ，这个剧场只能容纳下总重量为 $w$ 的人。其中有 $m$ 对女生 $(x_i,y_i)$ 互为朋友，且某个女生的朋友的朋友也是这个女生的朋友，为了不让她们伤心，同一群朋友中，要么最多邀请其中的一个，要么全都邀请，问在总重量不超过 $w$ 的情况下，能够邀请到的最大的总的美丽值 $b$ 。

数据范围

$1\leq n\leq1000,0\leq m\leq\min(\frac{n\times(n-1)}{2},10^5),1\leq w\leq1000\\ 1\leq w_i\leq1000,1\leq b_i\leq10^6\\1\leq x_i,y_i\leq n,x_i\neq y_i$

题解

用个并查集把互为朋友的女生放到同一个 $vector$ 里，然后跑个分组背包。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int n, m, W, u, v, Index, ii;
int fa[maxn];
int w[maxn], b[maxn];
int w_tot[maxn], b_tot[maxn];
int dp[2][maxn];
vector<int> G[maxn];
void Init() {
    ii = 1;
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
        G[i].clear();
    }
    for(int i = 0; i <= W; ++i) {
        dp[0][i] = dp[1][i] = 0;
    }
}
int Find(int x) {
    return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy) {
        fa[xx] = yy;
        b_tot[yy] += b_tot[xx];
        w_tot[yy] += w_tot[xx];
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &m, &W) != EOF) {
        Init();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            w_tot[i] = w[i];
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &b[i]);
            b_tot[i] = b[i];
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            unit(u, v);
        }
        for(int i = 1; i <= n; ++i) {
            G[Find(i)].push_back(i);
        }
        for(int i = 1; i <= n; ++i) {
            int len = G[i].size();
            if(len == 0) {
                continue;
            }
            Index = ii;
            ii = (Index + 1) % 2;
            memcpy(dp[Index], dp[ii], sizeof((dp[Index])));
            for(int j = 0; j < len; ++j) {
                for(int k = w[G[i][j]]; k <= W; ++k) {
                    dp[Index][k] = max(dp[Index][k], dp[ii][k - w[G[i][j]]] + b[G[i][j]]);
                }
            }
            for(int k = w_tot[i]; k <= W; ++k) {
                dp[Index][k] = max(dp[Index][k], dp[ii][k - w_tot[i]] + b_tot[i]);
            }
        }
        printf("%d\n", dp[Index][W]);
    }
    return 0;
}

E. Arpa's overnight party and Mehrdad's silent entering

题意

有 $n$ 对情侣坐在一个圆桌上，这个圆桌有 $2n$ 个座位，第 $i$ 对情侣的座位为 $(a_i,b_i)$ ，桌上总共有两种食物分别用 $1$ 和 $2$ 表示，现在要求一种满足以下条件的食物的分配方案：

每个人都有一种食物；

每个男生的食物都要和他伴侣的食物不相同；

餐桌上任意连续的三个人之间至少有两个人的食物不同，其中第 $2n$ 个座位和第 $1$ 个座位是相邻的。

如果不存在满足条件的方案，则输出 $-1$ 。

数据范围

$1\leq n\leq10^5\\1\leq a_i,b_i\leq2n$

题解

如果不管第 $3$ 个条件，这就是一个二分图染色，给出第三个条件后，可以通过构造，将这题转化为一个二分图，构造的方法就是，将座位 $2i$ 与 $2i+1$ 之间连边，这样把整张图展开就是一个一个的环，且每个环上节点的个数都是偶数，所以无论如何，染色方案一定是合法的，不可能出现 $-1$ 的情况。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n;
bool vis[maxn];
int color[maxn], u[maxn], v[maxn];
vector<int> G[maxn];
queue<int> que;
void Init() {
    for(int i = 1; i <= 2 * n; ++i) {
        G[i].clear();
        color[i] = 0;
        vis[i] = false;
    }
    for(int i = 1; i <= 2 * n; i += 2) {
        G[i].push_back(i + 1);
        G[i + 1].push_back(i);
    }
}
void bfs(int s) {
    color[s] = 1;
    que.push(s);
    while(!que.empty()) {
        int tmp = que.front();
        que.pop();
        vis[tmp] = true;
        int len = G[tmp].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[tmp][i];
            if(color[pos] == 0) {
                color[pos] = 3 - color[tmp];
                que.push(pos);
            }
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        Init();
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &u[i], &v[i]);
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        for(int i = 1; i <= 2 * n; ++i) {
            if(!vis[i]) {
                bfs(i);
            }
        }
        for(int i = 0; i < n; ++i) {
            printf("%d %d\n", color[u[i]], color[v[i]]);
        }
    }
    return 0;
}

Codeforces Round #383 (Div. 2)

A. Arpa's hard exam and Mehrdad's naive cheat

题意

数据范围

题解

过题代码

B. Arpa's obvious problem and Mehrdad's terrible solution

题意

数据范围

题解

过题代码

C. Arpa's loud Owf and Mehrdad's evil plan

题意

数据范围

题解

过题代码

D. Arpa's weak amphitheater and Mehrdad's valuable Hoses

题意

数据范围

题解

过题代码

E. Arpa's overnight party and Mehrdad's silent entering

题意

数据范围

题解

过题代码

内容目录