首页 > 代码库 > 2016ACM/ICPC亚洲区大连站-重现赛
2016ACM/ICPC亚洲区大连站-重现赛
题目链接:http://acm.hdu.edu.cn/search.php?field=problem&key=2016ACM%2FICPC%D1%C7%D6%DE%C7%F8%B4%F3%C1%AC%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B4%F3%C1%AC%BA%A3%CA%C2%B4%F3%D1%A7%A3%A9&source=1&searchmode=source
A.染色乱搞。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef struct Edge { 5 int to, next; 6 }Edge; 7 8 const int maxn = 1010; 9 int n, m, x, y; 10 int know[maxn], vis[maxn], color[maxn]; 11 int ecnt, head[maxn]; 12 Edge e[maxn*maxn]; 13 14 void init() { 15 ecnt = 0; 16 memset(head, -1, sizeof(head)); 17 memset(know, 0, sizeof(know)); 18 memset(vis, 0, sizeof(vis)); 19 memset(color, 0, sizeof(color)); 20 } 21 22 void adde(int u, int v) { 23 e[ecnt].to = v, e[ecnt].next = head[u]; 24 head[u] = ecnt++; 25 } 26 27 bool dfs(int u) { 28 for(int i = head[u]; ~i; i=e[i].next) { 29 int v = e[i].to; 30 if(color[v] == color[u]) return 0; 31 if(vis[v]) continue; 32 vis[v] = 1; 33 color[v] = 3 - color[u]; 34 if(!dfs(v)) return 0; 35 } 36 return 1; 37 } 38 39 int main() { 40 // freopen("in", "r", stdin); 41 int u, v; 42 while(~scanf("%d%d%d%d",&n,&m,&x,&y)) { 43 init(); 44 for(int i = 0; i < m; i++) { 45 scanf("%d%d",&u,&v); 46 adde(u, v); adde(v, u); 47 know[u] = know[v] = 1; 48 } 49 for(int i = 0; i < x; i++) { 50 scanf("%d", &u); 51 color[u] = 1; know[u] = 1; 52 } 53 for(int i = 0; i < y; i++) { 54 scanf("%d", &u); 55 color[u] = 2; know[u] = 1; 56 } 57 bool flag = 0; 58 for(int i = 1; i <= n; i++) { 59 if(!know[i]) { 60 flag = 1; 61 break; 62 } 63 } 64 if(flag) { 65 puts("NO"); 66 continue; 67 } 68 for(int i = 1; i <= n; i++) { 69 if(color[i]) { 70 vis[i] = 1; 71 if(!dfs(i)) { 72 flag = 1; 73 break; 74 } 75 } 76 } 77 for(int i = 1; i <= n; i++) { 78 if(!color[i]) { 79 vis[i] = 1; 80 color[i] = 1; 81 if(!dfs(i)) { 82 flag = 1; 83 break; 84 } 85 } 86 } 87 if(!flag) puts("YES"); 88 else puts("NO"); 89 } 90 return 0; 91 }
C.威佐夫博弈+大数,根号5用mathmatica跑出来的,其实可以用二分打表。
1 import java.math.BigDecimal; 2 import java.math.BigInteger; 3 import java.math.MathContext; 4 import java.math.RoundingMode; 5 import java.util.Scanner; 6 7 public class Main { 8 9 public static void main(String[] args) { 10 Scanner in = new Scanner(System.in); 11 BigDecimal n, m; 12 BigDecimal sqrt5 = new BigDecimal("2.2360679774997896964091736687312762354406183596115257242708972454105209256378048994144144083787822749695081761507737835"); 13 while(in.hasNextBigDecimal()) { 14 n = in.nextBigDecimal(); m = in.nextBigDecimal(); 15 if(m.equals(n.max(m))) { 16 BigDecimal x = n; 17 n = m; 18 m = x; 19 } 20 BigDecimal k = n.subtract(m); 21 BigDecimal p = new BigDecimal(1); 22 n = p.add(sqrt5).multiply(k); 23 n = n.divide(new BigDecimal(2)); 24 if(n.toBigInteger().equals(m.toBigInteger())) System.out.println("0"); 25 else System.out.println("1"); 26 } 27 } 28 }
D.找到规律gcd(a,b)=gcd(x,y)以后,就是解方程了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 LL a, b, x, y; 6 7 LL gcd(LL x, LL y) { 8 return y == 0 ? x : gcd(y, x % y); 9 } 10 int main() { 11 // freopen("in", "r", stdin); 12 while(~scanf("%I64d%I64d",&a,&b)) { 13 LL g = gcd(a, b); 14 LL k = b * g; 15 if(a * a - 4 * k < 0 || (LL)sqrt(a*a-4*k) != sqrt(a*a-4*k)) puts("No Solution"); 16 else { 17 LL delta = (LL)sqrt(a * a - 4 * k); 18 printf("%I64d %I64d\n", (a-delta)/2, (a+delta)/2); 19 } 20 } 21 return 0; 22 }
H.奇数就无所谓,偶数的话先手有优势。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int k; 5 6 int main() { 7 // freopen("in", "r", stdin); 8 while(~scanf("%d", &k)) { 9 if(k & 1) puts("0"); 10 else puts("1"); 11 } 12 return 0; 13 }
I.余弦定理求出第三条边,高用角的一半的余弦乘一下斜边,面积加起来。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 11; 5 const double pi = 3.141592653; 6 int n, d; 7 int th; 8 double ret; 9 10 double f(int th) { 11 return d*cos(pi*th/2.0/180.0)*sqrt(2.0*d*d-2.0*d*d*cos(pi*th/180.0))/2.0; 12 } 13 14 int main() { 15 // freopen("in", "r", stdin); 16 while(~scanf("%d%d",&n,&d)) { 17 ret = 0.0; 18 for(int i = 1; i <= n; i++) { 19 scanf("%d", &th); 20 ret += f(th); 21 } 22 printf("%.3lf\n", ret); 23 } 24 return 0; 25 }
J.拆成四部分挨个看看是不是97。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 110; 5 int n; 6 int a; 7 8 int f(int x) { 9 int cnt = 0; 10 int q = 4; 11 while(q--) { 12 if((x % 256) == 97) cnt++; 13 x >>= 8; 14 } 15 return cnt; 16 } 17 18 int main() { 19 // freopen("in", "r", stdin); 20 while(~scanf("%d", &n)) { 21 int ret = 0; 22 for(int i = 1; i <= n; i++) { 23 scanf("%d", &a); 24 ret += f(a); 25 } 26 printf("%d\n", ret); 27 } 28 return 0; 29 }
2016ACM/ICPC亚洲区大连站-重现赛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。