【题目记录】——ICPC大连2016A - Wrestling Match 并查集C - Game of Taking Stones 威佐夫博弈高精度D - A Simple Math Problem 数学F- Detachment 数学前缀和前缀积H - To begin or not to begin 数学概率J - Find Small A 进制转换K - Guess the number

106 阅读 0 评论 70 点赞

我是靠谱客的博主孤独小懒猪，这篇文章主要介绍【题目记录】——ICPC大连2016A - Wrestling Match 并查集C - Game of Taking Stones 威佐夫博弈高精度D - A Simple Math Problem 数学F- Detachment 数学前缀和前缀积H - To begin or not to begin 数学概率J - Find Small A 进制转换K - Guess the number，现在分享给大家，希望可以做个参考。

文章目录

A - Wrestling Match 并查集
C - Game of Taking Stones 威佐夫博弈高精度
D - A Simple Math Problem 数学
F- Detachment 数学前缀和前缀积
H - To begin or not to begin 数学概率
J - Find Small A 进制转换
K - Guess the number

题目集地址 ICPC大连2016

A - Wrestling Match 并查集

题目地址A - Wrestling Match
题目大意:有n个运动员，m场比赛，已知其中x个是好运动员，y个是坏运动员，每一场比赛都是一个好运动员和一个坏运动员进行，问根据已知信息能不能将所有运动员区分成好运动员或者坏运动员。
思路:队友写的，大致思路就是使用并查集，根据比赛情况将所有运动员分为两个集合，如果还有人没有被分到集合里，此人无法确定，输出NO，根据已知信息推出冲突情况输出NO
AC代码:

复制代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,x,y,f[12424];
int type[12424];
int Seek(int x)
{
return f[x]==x?x:f[x]=Seek(f[x]);
}
void Union(int x,int y)
{
int fx=Seek(x),fy=Seek(y);
if(fx!=fy)
f[fx]=fy;
}
void solve()
{
bool flag=0;
int xx=x,yy=y;
memset(type,0,sizeof(type));
for(int i=1; i<=2*n; i++)
{
f[i]=i;
}
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
if(Seek(a)==Seek(b))
flag=1;
Union(a,b+n);
Union(b,a+n);
}
if(n==1)
{
printf("YESn");
return ;
}
if(x==0&&y==0)
{
int fx=Seek(1),fxx=Seek(1+n);
type[fx]=1;
type[fxx]=-1;
}
while(x--)
{
int a;
scanf("%d",&a);
int fx=Seek(a),fxx=Seek(a+n);
if(type[fx]==-1||type[fxx]==1)
flag=1;
type[fx]=1;
type[fxx]=-1;
}
while(y--)
{
int a;
scanf("%d",&a);
int fx=Seek(a),fxx=Seek(a+n);
if(type[fx]==1||type[fxx]==-1)
flag=1;
type[fx]=-1;
type[fxx]=1;
}
if(flag)
{
printf("NOn");
return ;
}
for(int i=1; i<=n; i++)
{
int fx=Seek(i);
if(type[fx]==0)
{
flag=1;
printf("NOn");
return;
}
}
printf("YESn");
}
int main()
{
int t = 1;
while(~scanf("%d%d%d%d",&n,&m,&x,&y))
{
solve();
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,x,y,f[12424];
int type[12424];
int Seek(int x)
{
return f[x]==x?x:f[x]=Seek(f[x]);
}
void Union(int x,int y)
{
int fx=Seek(x),fy=Seek(y);
if(fx!=fy)
f[fx]=fy;
}
void solve()
{
bool flag=0;
int xx=x,yy=y;
memset(type,0,sizeof(type));
for(int i=1; i<=2*n; i++)
{
f[i]=i;
}
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
if(Seek(a)==Seek(b))
flag=1;
Union(a,b+n);
Union(b,a+n);
}
if(n==1)
{
printf("YESn");
return ;
}
if(x==0&&y==0)
{
int fx=Seek(1),fxx=Seek(1+n);
type[fx]=1;
type[fxx]=-1;
}
while(x--)
{
int a;
scanf("%d",&a);
int fx=Seek(a),fxx=Seek(a+n);
if(type[fx]==-1||type[fxx]==1)
flag=1;
type[fx]=1;
type[fxx]=-1;
}
while(y--)
{
int a;
scanf("%d",&a);
int fx=Seek(a),fxx=Seek(a+n);
if(type[fx]==1||type[fxx]==-1)
flag=1;
type[fx]=-1;
type[fxx]=1;
}
if(flag)
{
printf("NOn");
return ;
}
for(int i=1; i<=n; i++)
{
int fx=Seek(i);
if(type[fx]==0)
{
flag=1;
printf("NOn");
return;
}
}
printf("YESn");
}
int main()
{
int t = 1;
while(~scanf("%d%d%d%d",&n,&m,&x,&y))
{
solve();
}
return 0;
}

C - Game of Taking Stones 威佐夫博弈高精度

题目地址C - Game of Taking Stones
题目大意:有两堆各若干物品，两个人轮流从任意一堆中至少取出一个或者从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜。
思路：威佐夫博弈的典型，不过因为数据量达到了 $10^{100}$ ,必须使用大数，还有就是黄金分割比的精度需要达到 $10^{-100}$ 。关于威佐夫博弈可以参考【算法与数据结构】——博弈论
AC代码:

复制代码

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
BigDecimal TWO = BigDecimal.valueOf(2);
BigDecimal FIVE = BigDecimal.valueOf(5);
double d=Math.pow(10,-100);
BigDecimal EPS = BigDecimal.valueOf(d);
BigDecimal L = new BigDecimal("2");
BigDecimal R = new BigDecimal("3");
BigDecimal mid = null;
while(R.subtract(L).compareTo(EPS) > 0)
{
mid = L.add(R).divide(TWO);
if(mid.multiply(mid).compareTo(FIVE) < 0)
L=mid;
if(mid.multiply(mid).compareTo(FIVE) > 0)
R = mid;
}
BigDecimal GOLD = mid.add(BigDecimal.ONE).divide(TWO);
BigDecimal a,b;
String str1,str2;
Scanner input = new Scanner(System.in);
while(input.hasNext())
{
str1 = input.next();
str2 = input.next();
a = new BigDecimal(str1);
b = new BigDecimal(str2);
if(solve(a,b,GOLD))
{
System.out.println("1");
}
else{
System.out.println("0");
}
}
}
static boolean solve(BigDecimal a,BigDecimal b,BigDecimal gold)
{
BigDecimal d = a.subtract(b);
if(d.compareTo(BigDecimal.valueOf(0))==-1){
d=d.multiply(BigDecimal.valueOf(-1));
}
d = d.multiply(gold);
BigInteger dd = d.toBigInteger();
d = new BigDecimal(dd.toString());
if (!d.equals(a.min(b)))
return true;
else
return false;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
BigDecimal TWO = BigDecimal.valueOf(2);
BigDecimal FIVE = BigDecimal.valueOf(5);
double d=Math.pow(10,-100);
BigDecimal EPS = BigDecimal.valueOf(d);
BigDecimal L = new BigDecimal("2");
BigDecimal R = new BigDecimal("3");
BigDecimal mid = null;
while(R.subtract(L).compareTo(EPS) > 0)
{
mid = L.add(R).divide(TWO);
if(mid.multiply(mid).compareTo(FIVE) < 0)
L=mid;
if(mid.multiply(mid).compareTo(FIVE) > 0)
R = mid;
}
BigDecimal GOLD = mid.add(BigDecimal.ONE).divide(TWO);
BigDecimal a,b;
String str1,str2;
Scanner input = new Scanner(System.in);
while(input.hasNext())
{
str1 = input.next();
str2 = input.next();
a = new BigDecimal(str1);
b = new BigDecimal(str2);
if(solve(a,b,GOLD))
{
System.out.println("1");
}
else{
System.out.println("0");
}
}
}
static boolean solve(BigDecimal a,BigDecimal b,BigDecimal gold)
{
BigDecimal d = a.subtract(b);
if(d.compareTo(BigDecimal.valueOf(0))==-1){
d=d.multiply(BigDecimal.valueOf(-1));
}
d = d.multiply(gold);
BigInteger dd = d.toBigInteger();
d = new BigDecimal(dd.toString());
if (!d.equals(a.min(b)))
return true;
else
return false;
}
}

D - A Simple Math Problem 数学

题目地址D - A Simple Math Problem
题目大意:给出a，b求出x，y满足条件
x+y=a
lcm(x,y)=b
思路:根据数学结论
gcd(X,Y)=gcd(X+Y,Y)=gcd(X,X+Y)=gcd(X+Y,lcm(X,Y))
得到
LCM(X,Y)=XY/gcd(X,Y)=XY/gcd(X+Y,LCM(X,Y))=X*Y/gcd(a,b)
X+Y=a
XY= $b * g c d (a, b)$
解方程即可。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
ll gcd(ll a, ll b){
return b == 0 ? a:gcd(b, a%b);
}
int main()
{
//	freopen("in.txt","r",stdin);
ll a,b;
while(~scanf("%lld%lld",&a,&b))
{
bool flag=true;
ll g = gcd(a,b);
ll data = a*a-4*b*g;
ll k1,k2;
if(data<0)
{
flag=0;
}
ll aa = sqrt(data);
if(aa*aa==data)
{
if((a+aa)%2!=0||(a-aa)%2!=0||(a-aa)<=0||(a+aa)<=0)
{
flag = 0;
}
else
{
k1 = (a+aa)/2;
k2 = (a-aa)/2;
}
}
else
{
flag=false;
}
if(flag) {
printf("%lld %lldn",k1,k2);
}
else
printf("No Solutionn");
}
return 0;
}

F- Detachment 数学前缀和前缀积

题目地址F- Detachment
题目大意:给一个数x，将他拆分成多个数的和a1,a2,……，也可以不拆保留一个x，要求使 $a 1 * a 2 * \dots \dots$ 的值最大。 $a 1! = a 2! = a 3 . . . . . .$
思路：要知道有这样一个规律 $a * b \geq a + b (a \geq 2, b \geq 2)$ ，也就是说对于任意一个数，拆分成2个大于等于2的数的乘积，总是不会比他自己大的，所以我们要尽量将x拆分成尽量小的不同的数的和(当然不包括1，因为1对于乘积不做贡献)，这样就能使这些数的乘积最大。
因为取余的问题，在这里wa了好几发。。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
const int maxj=50000;
ll sum[maxj],cheng[maxj];
ll qpow(ll a, ll n,ll m){
ll ans = 1;
while(n){
if(n&1)
{
ans = a * ans % m;
}
a = a * a % m;
n >>= 1;
}
return ans;
}
void init()
{
cheng[1]=1;
for(int i = 2;i <maxj;i++)
{
sum[i]=sum[i-1]+i;
cheng[i]=cheng[i-1]*i%mod;
}
}
void solve()
{
ll n;
scanf("%lld",&n);
if(n<=4)
{
printf("%dn",n);
return ;
}
int pos = upper_bound(sum+2,sum+maxj,n)-sum-1;
ll ans;
if(sum[pos]==n)
{
ans=cheng[pos];
}
else
{
ll t =n-sum[pos];
if(t==pos)
{
ans = cheng[pos]*qpow(2,mod-2,mod)%mod*(pos+2)%mod;
}
else
{
ans = cheng[pos]*qpow(pos-t+1,mod-2,mod)%mod*(pos+1)%mod;
}
}
printf("%lldn",ans);
}
int main()
{
//	freopen("in.txt","r",stdin);
int t = 1;
//	int t;
scanf("%d",&t);
init();
while(t--)
{
solve();
}
return 0;
}

H - To begin or not to begin 数学概率

题目地址H - To begin or not to begin
题目大意:一个黑盒子里面有k个黑球，1个红球，谁抓到红球谁获胜，给出k值，问先手是否有优势。
思路:根据数学的概率知识，
我们知道k为奇数的时候，先手和后手抓球的机会是相等的，所以几率相等输出0
k为偶数的时候，先手抓球的机会更多，有优势输出1

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n&1)
printf("0n");
else
printf("1n");
}
return 0;
}

J - Find Small A 进制转换

题目地址J - Find Small A
题目大意:给出一个整型数字a，问将a转为256进制后有几个97.
思路:根据数学知识转换进制即可。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
void solve()
{
int n;
scanf("%d",&n);
ll zan=0;
int ans=0;
for(int i=0;i<n;i++)
{
int bi=0;
scanf("%lld",&zan);
bi=zan%256;
zan/=256;
if(bi==97)
ans++;
for(int i=1;i<4;i++)
{
bi=zan%256;
zan/=256;
if(bi==97)
ans++;
}
}
printf("%dn",ans);
}
int main()
{
//	freopen("in.txt","r",stdin);
int t = 1;
//	int t;
//scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}