2016 ACM/ICPC亚洲区大连站

大连站"/>

2016 ACM/ICPC亚洲区大连站

The 2016 ACM-ICPC Asia Dalian Regional Contest [Cloned]

【A - Wrestling Match】

【题目大意】
有一个球队，队员有好坏之分，给你总人数n，m个对立关系，x个已知的好队员和y个已知的坏队员，问你能否将所有人分为两组，一组好一组坏

【解题思路】
二分图染色裸题

【AC代码】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 10010;
vector<int> G[maxn]; //存图
struct Edge {int from, to;
}edge[maxm]; //存边
int vis[maxn]; //记录颜色
bool flag = true; //记录答案
inline void init() { //初始化memset(vis, 0, sizeof(vis));flag = true;for (int i = 0; i <= 1000; ++i) {G[i].clear();}
}
inline void bfs(int s, int col) { //染色queue<int> que;que.push(s);vis[s] = col;while (!que.empty()) {int u = que.front();que.pop();for (int i = 0; i < G[u].size(); ++i) {int  v = G[u][i];if (vis[v] == vis[u]) {flag = false;return;}else if (!vis[v]) {vis[v] = -vis[u];que.push(v);}}}
}
int main() {int n, m, x, y;while (~scanf("%d%d%d%d", &n, &m, &x, &y)) {init();for (int i = 1; i <= m; ++i) {int u, v;scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);edge[i].from = u;edge[i].to = v;}for (int i = 1; i <= x; ++i) {int temp;scanf("%d", &temp);if (vis[temp] == -1) { //好队员被染成坏的flag = false;}bfs(temp, 1);}for (int i = 1; i <= y; ++i) {int temp;scanf("%d", &temp); if (vis[temp] == 1) { //坏队员被染成好的flag = false;}bfs(temp, -1);}if (!flag) {puts("NO");continue;}for (int i = 1; i <= m; ++i) {if (!vis[edge[i].from] && !vis[edge[i].to]) { //对还没有被染色的边的节点染色bfs(edge[i].from, 1);}}if (!flag) {puts("NO");continue;}for (int i = 1; i <= n; ++i) {if (!vis[i]) {  //有孤立节点flag = false;break;}}if (!flag) {puts("NO");continue;}puts("YES");}return 0;
}

【B - Regular Number】

【题目大意】
给你n行，每行m个数字，数字的行数为其优先级，输出母串中所有满足数字优先级的长度为n的字串

Sample Input
4
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524

Sample Output
9755
7554
0524

【解题思路】
使用bitset进行字符串匹配

设a[i][j]=1表示数字i可以出现在第j位上

b[i]=1表示当前0至i-1位已经符合优先级，即前i-1个数字已经匹配完成，现在判断当前数字是否能够作为第i位

那么问题来了，如何进行匹配

对母串从前往后遍历，首先我们优先考虑s[i]能否作为第一位，那么我们将b[0]置为1，让b = b&a[s[i]]如果b[0] == 1，那么s[i]就能够作为第0位，然后考虑s[i+1]能否作为第1位，由于b[i]表示前i-1位是否匹配，那么在找第1位的时候，我们可以让b左移1位，表示现在正在找第1位
0000001
0000010
当第0位匹配成功
假设前k-1位匹配成功
那么对于第k位，当前匹配到s[i]，我们令b &= a[s[i]]，如果b[k]等于1，说明匹配成功，b左移一位，进行第k+1位的匹配，否则b[k] = 0，说明匹配失败，重新从第0位开使匹配
当第n-1位匹配成功，那么该字串符合要求

需要注意，在匹配时，最重要的是第0位的匹配，我们在每一次匹配前都要将b[0]置为1，看s[i]能否最为第0位，这是匹配的前提

【AC代码】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 10;
bitset<1010> a[11];
char s[maxn];
int main() {int n;while (~scanf("%d", &n)) {for (int i = 0; i <= 10; ++i) {a[i].reset();  //记得重置}for (int i = 0; i < n; ++i) {int m;scanf("%d", &m);for (int j = 1; j <= m; ++j) {int x;scanf("%d", &x);a[x][i] = 1;  //x在第i位上可用}}scanf(" %s", &s);bitset<1010> b;for (int i = 0; s[i] != '\0'; ++i) {b <<= 1;  //左移b[0] = 1;  //b[0]置1b &= a[s[i] - '0']; //匹配if (b[n - 1]) {  //n-1位匹配成功，输出字串char temp = s[i + 1];s[i + 1] = '\0';puts(s + i - n + 1);s[i + 1] = temp;}}}return 0;
}

【C - Game of Taking Stones】

【题目大意】
高精度威佐夫博弈

【解题思路】
Java大数~~（好麻烦的亚子，为什么16年没有python）~~

【AC代码】

import java.util.*;
import java.math.*;
class Main
{private static BigDecimal sqrt(BigDecimal x, int n)  //高精浮点数开根号（库里居然没有？？）{BigDecimal ans = BigDecimal.ZERO;BigDecimal eps = BigDecimal.ONE;for (int i = 0; i < n; ++i){while (ans.pow(2)pareTo(x) < 0){ans = ans.add(eps);}ans = ans.subtract(eps);eps = eps.divide(BigDecimal.TEN);}return ans;};private static void Solve(BigDecimal a, BigDecimal b)  //威佐夫博弈，黄金分割比{BigDecimal c = sqrt(new BigDecimal(5), 120);c = c.add(BigDecimal.ONE).divide(new BigDecimal(2));if (b.subtract(a).multiply(c).setScale(0, BigDecimal.ROUND_DOWN).equals(a)){System.out.println(0);}elseSystem.out.println(1);};public static void main(String[] args){Scanner input = new Scanner(System.in);while (input.hasNext()){BigDecimal a = input.nextBigDecimal();BigDecimal b = input.nextBigDecimal();if (apareTo(b) == 1){Solve(b, a);}else Solve(a, b);}};
};

【D - A Simple Math Problem】

【题目大意】
给定a和b，找到两个数x，y使得
1.x + y = a
2.lcm(x, y) = b

【解题思路】
设 x = cn，y = cm
则有
c * (n + m) = a
n * m * c = b
且 gcd(n, m) = 1
那么显然
gcd(n * m, n + m) = 1（可以用反证法推出x = y = 1）
故 gcd(a, b) = c = gcd(x, y)
那么得到方程组
x + y = a
x * y = b * gcd(a, b)
化简可以得到一个一元二次方程，根据判别式判断是否有解以及解是否为整数即可

【AC代码】

#include <bits/stdc++.h>
using namespace std;
inline int gcd(int x, int y) {if (y == 0) return x;return gcd(y, x % y);
}
int main() {int a, b;while (~scanf("%d%d", &a, &b)) {int m = a > b ? gcd(a, b) : gcd(b, a);int temp = a * a - 4 * m * b;if (temp < 0) {  //判别式小于零puts("No Solution");}else {int k = sqrt(temp);if (k * k != temp || (a - k) % 2 != 0) {  //解不为整数puts("No Solution");}else {int x = (a - k) / 2;int y = (a + k) / 2;printf("%d %d\n", x, y);}}}return 0;
}

【H - To begin or not to begin】

【题目大意】
盒子里有k个黑球和一个红球，问你先手和后手谁更有优势先摸到红球（摸到不放回）
For each case, output:
1, if the player who starts drawing has an advantage
2, if the player who starts drawing has a disadvantage
0, if Alice’s and Bob’s chances are equal, no matter who

【解题思路】
先手获胜的通项公式为：
P = [(k + 2) / 2] / (k + 1)

（具体推导参考：）

若k为偶数
设 k = 2 * m
P = (m + 1) / (2 * m + 1)
1 - P = m / (2 * m + 1)
显然 P > 1 - P，先手优势，输出1

若k为奇数
设 k = 2 * m + 1
P = (m + 1) / (2 * m + 2) = 1 - P
先手与后手优势相同，输出0

【AC代码】

#include <bits/stdc++.h>
using namespace std;
int main() {int k;while (~scanf("%d", &k)) {if (k & 1) puts("0");else puts("1");}return 0;
}

【I - Convex】

【题目大意】
给定n个点，所有点到原点的距离为m，给定每个点与其相邻点与原点连线的角度，问你所有相邻点连起来的图形面积是多少

【解题思路】
将相邻两点与原点连成三角形，对Si = m * m * sin(angle) 求和

【AC代码】

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);  //acos(-1) = 3.1415926
int main() {int n, m;while (~scanf("%d%d", &n, &m)) {double angle, sum = 0;for (int i = 1; i <= n; ++i) {scanf("%lf", &angle);angle = angle / 180 * PI; //角度转弧度sum += sin(angle);  //对角度求和最后乘以距离的平方}double ans = sum * m * m * 0.5;printf("%.3f\n", ans);}return 0;
}

【J - Find Small A】

【题目大意】
这题题意理解起来着实有点麻烦，给你n个整数，每个整数二进制下为32位，而字符常量二进制下为，那么32位的整型每8位代表一个字符，问你所有32位整型拆分成4个8位后有几个字符‘a’（ACSII为97）

【解题思路】
对于每一个整数，将其拆分为4个8位，考虑整型在二进制下的0 - 8位如果等于97，就说明可以代表一个a，即对于整数x，( x % (1 << 8) ) == 97，为什么是(1 << 8)，因为考虑的是0 - 8位所代表的十进制数，然后将x左移8位进行下一个字符的判断，直至x为0

【AC代码】

#include <bits/stdc++.h>
using namespace std;
int main() {int n;scanf("%d", &n);int ans = 0;for (int i = 1; i <= n; ++i) {int x;scanf("%d", &x);while (x) {if (x % 256 == 97) { //(1 << 8) = 256++ans;}x >>= 8;}}printf("%d\n", ans);return 0;
}