首页 > 代码库 > 2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）（6/10）
2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）（6/10）
1001题意：n个人，给m对敌对关系，X个好人，Y个坏人。现在问你是否每个人都是要么是好人，要么是坏人。
先看看与X，Y个人有联通的人是否有矛盾，没有矛盾的话咋就继续遍历那些不确定的人关系，随便取一个数3，与其相连的就是4，间隔就要相同，dfs搜过去就可以判断了
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 5e5+10, maxn = 1e3+20, mod = 1e9+7, inf = 2e9;int vis[N],t,head[N],n,m,x,y,z,cal[N],xx[N],yy[N];int flag;struct ss{int to,next;}e[N * 2];void add(int u,int v) {e[t].next = head[u]; e[t].to = v; head[u] = t++;}void dfs(int u,int fa) { cal[u] = 1; for(int i = head[u]; i!=-1; i = e[i].next) { int to = e[i].to; if(to == fa) continue; if(vis[u] == 0) vis[u] = 3; if(vis[to] == vis[u]) { flag = 1; return ; } if(cal[to]) continue; if(vis[u] == 3) vis[to] = 4; else if(vis[u] == 4) vis[to] = 3; else if(vis[u] == 1) vis[to] = 2; else if(vis[u] == 2) vis[to] = 1; dfs(to,u); }}int main() { while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF) { t = 1; memset(head,-1,sizeof(head)); for(int i = 1; i <= m; ++i) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } memset(cal,0,sizeof(cal)); memset(vis,0,sizeof(vis)); for(int i = 1; i <= x; ++i) scanf("%d",&xx[i]),vis[xx[i]] = 1; for(int i = 1; i <= y; ++i) scanf("%d",&yy[i]),vis[yy[i]] = 2; flag = 0; for(int i = 1; i <= x; ++i) { if(!cal[i]) dfs(xx[i],-1); } for(int i = 1; i <= y; ++i) { if(!cal[i]) dfs(yy[i],-1); } if(flag) { puts("NO"); continue; } for(int i = 1; i<= n; ++i) { if(!cal[i]) { dfs(i,-1); } } for(int i = 1; i <= n; ++i) { if(!vis[i]) flag = 1; } if(flag) puts("NO"); else puts("YES"); } return 0;}
1003题意：两堆石子，你可以任选一堆去掉任意个数，你也可从两堆中同时去掉任意个数，最后全部取完的人胜
石子的数量是10^100.高精度的威佐夫博弈，需要黄金比例精确到100位，队友javaA。
import java.util.*;import java.math.*;public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); BigInteger k=new BigInteger("6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374"); BigInteger p=new BigInteger("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"); while(cin.hasNext()) { BigInteger nn=cin.nextBigInteger(); BigInteger mm=cin.nextBigInteger(); BigInteger n=nn.min(mm); BigInteger m=nn.max(mm); BigInteger j=n.multiply(k); j=j.divide(p); BigInteger l=j.multiply(k.add(new BigInteger("1"))); l=l.divide(p); if(n.equals(l)==false) j=j.add(new BigInteger("1")); n=n.add(j); if(n.equals(m)) System.out.println("0"); else System.out.println("1"); } }}
1004题意：给定a,b; 求出满足 LCM(X,Y) = b && X+Y = a的一组解，或者是无解
公式转化：b*gcd(X,Y) = X*Y,X+Y=a;
我们可以知道gcd(X,Y) 必然是a的因子！，那么我们为了枚举gcd(X,Y)就直接去枚举a的因子就是了
枚举以后就相当于求解一个二元一次方程的整数解了；
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 5e5+10, maxn = 1e3+20, mod = 1e9+7, inf = 2e9;LL a,b,p[N],ans1,ans2;int ok;int check(LL a,LL B,LL gc) { if(a*a - 4*B < 0) return 0; LL tmp = (int)(sqrt(a*a - 4*B)+0.00001); if(tmp*tmp != a*a - 4*B) return 0; LL fi = a+tmp; if(fi>=0&&fi%2==0) fi/=2; else fi = -1; LL se = a-tmp; if(se>=0&&se%2==0) se/=2; else se = -1; if(fi <= 0 && se <= 0) return 0; if(fi > 0) { LL x = a - fi; if((__gcd(fi,x)==gc)&&x * fi == B) { ans1 = fi,ans2 = x; if(ans1>ans2) swap(ans1,ans2); ok = 1; return 1; } } if(se > 0) { LL x = a - se; if((__gcd(x,se)==gc)&&x * se == B) { ans1 = se,ans2 = x; if(ans1>ans2) swap(ans1,ans2); ok = 1; return 1; } } return 0;}int main() { while(scanf("%I64d%I64d",&a,&b)!=EOF) { ok = 0; for(int i = 1; i * i <= a; ++i) { if(a % i == 0) { if(check(a,b*i,i)) break; if(check(a,b*(a/i),a/i)) break; } } if(ok) printf("%I64d %I64d\n",ans1,ans2); else puts("No Solution"); }}
1006题意：给你一个x，然后你要构造一个数组a，满足∑a = x， 任意的i,j( i != j) a[i] != a[j];问你 最大的 s = a1*a2*a3*......*an是多少；
要使得乘积最大，那么相乘的数越多显然S是越大的。。。。
假设x = 7, 那么我们构造出一个数组 2 3 2，到这里有重复的数了，我们就把最后面的2平分到前面 2,3 -> 3，4
假设x = 8，那么我们构造出一个数组 2 3 3，到这里有重复的数了，我们就把最后面的3平分到前面 2,3 -> 3，4 到这里，还有一个1，我们就分到最后一个数上去 -> 3 5
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long ll;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 5e5+10, maxn = 1e3+20, mod = 1e9+7, inf = 2e9;ll sum[N];ll pre[N];ll quick_pow(ll x,ll y){ ll ans=1; while(y) { if(y&1)ans*=x,ans%=mod; y>>=1; x*=x; x%=mod; } return ans;}int main() { sum[1]=2; for(int i = 2;i<44725 ; ++i) { sum[i]=sum[i-1]+i+1; } int cnt=44720,T; pre[0]=1; for(int i=1;i<44725;i++) { pre[i]=(pre[i-1]*(i+1))%mod; } scanf("%d",&T); while(T--) { ll x; scanf("%lld",&x); if(x == 1LL) { puts("1"); continue; } int pos=upper_bound(sum+1,sum+cnt+1,x)-sum-1; ll m=x-sum[pos]; if(m == pos+1) { ll ans=pre[pos]; ans=(ans*(pos+3))%mod; ans=(ans*quick_pow(2,mod-2))%mod; printf("%lld\n",ans); continue; } ll ans = pre[pos - m]; if(m!=0) ans = ans * ((pre[pos+1]*quick_pow((pre[pos-m+1]),mod-2))% mod )% mod; if(x==1) printf("1\n"); else printf("%lld\n",ans); } return 0;}
1008题意：k个黑球，1个白球，每次每人只能取一球，先取到红球的人胜利，问先取的人是否为有利，或者是平等
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10,MOD=1e9+7;int main(){ int x; while(~scanf("%d",&x)) { if(x&1) printf("0\n"); else printf("1\n"); } return 0;}
1009题意：N个角度，长度为D，求出这n个线段围成的面积
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 4e5+10, maxn = 1e3+20, mod = 1e9+7, inf = 2e9;double d;int n;int main() { while(scanf("%d%lf",&n,&d)!=EOF) { double ans = 0.0; double x; for(int i = 1; i <= n; ++i) { scanf("%lf",&x); ans += d*d*sin(x/180 * Pi)/2; } printf("%.3f\n",ans); } return 0;}
2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）（6/10）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。