Title set address ICPC Dalian 2016
A - wresting match
Title address A - Wrestling Match
There are n athletes and m games. It is known that x are good athletes and y are bad athletes. Each game is a good athlete and a bad athlete. Ask whether all athletes can be divided into good athletes or bad athletes according to the known information.
Idea: written by teammates, the general idea is to use and check the set. All athletes are divided into two sets according to the competition situation. If there are still people who are not divided into the set, they cannot be sure, output NO, and deduce the conflict situation according to the known information, and output NO
AC Code:
#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("YES\n");
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("NO\n");
return ;
}
for(int i=1; i<=n; i++)
{
int fx=Seek(i);
if(type[fx]==0)
{
flag=1;
printf("NO\n");
return;
}
}
printf("YES\n");
}
int main()
{
int t = 1;
while(~scanf("%d%d%d%d",&n,&m,&x,&y))
{
solve();
}
return 0;
}
C - Game of Taking Stones
Title address C - Game of Taking Stones
There are two piles of several items. Two people take turns to take at least one item from any pile or take the same number of items from two piles. It is stipulated that at least one item should be taken at a time, at most unlimited. The one who takes all the items at last wins.
Idea: it's a typical wizov game, but because the amount of data reaches
1
0
100
10^{100}
10100, large numbers must be used, and the accuracy of the golden section ratio needs to be achieved
1
0
−
100
10^{-100}
10−100. We can refer to the wizov game [algorithm and data structure] - Game Theory
AC Code:
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.2360679774997");
BigDecimal R = new BigDecimal("2.2360679774998");
BigDecimal mid = null;
while(L.subtract(R).compareTo(EPS) < 0)
{
mid = L.add(R).divide(TWO);
if(mid.multiply(mid).subtract(FIVE).abs().compareTo(EPS.abs()) < 0)
break;
if(mid.multiply(mid).subtract(FIVE).compareTo(EPS) < 0)
L = mid;
else
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
Title address D - A Simple Math Problem
Give a and b and find the conditions that x and y satisfy
x+y=a
lcm(x,y)=b
Idea: according to the mathematical conclusion
gcd(X,Y)=gcd(X+Y,Y)=gcd(X,X+Y)=gcd(X+Y,lcm(X,Y))
obtain
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
)
b*gcd(a,b)
b∗gcd(a,b)
Just solve the equation.
#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 %lld\n",k1,k2);
}
else
printf("No Solution\n");
}
return 0;
}
F-detachment mathematical prefix and prefix product
Title address F- Detachment
Give a number x and split it into the sum of multiple numbers a1,a2,..., or keep an X without dismantling
a
1
∗
a
2
∗
...
...
a1*a2*......
The value of a1 * a2 * is the largest.
a
1
!
=
a
2
!
=
a
3......
a1!= a2!=a3......
a1!=a2!=a3......
Idea: you should know that there is such a law
a
∗
b
≥
a
+
b
(
a
≥
2
,
b
≥
2
)
a*b\ge a+b(a\ge2,b\ge2)
A * b ≥ a+b(a ≥ 2,b ≥ 2), that is, for any number, the product of splitting into two numbers greater than or equal to 2 will never be larger than itself. Therefore, we should try to split x into the sum of different numbers as small as possible (excluding 1, of course, because 1 does not contribute to the product), so as to maximize the product of these numbers.
Because of the problem of surplus, several rounds have been made here..
#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("%d\n",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("%lld\n",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 mathematical probability
Title address H - To begin or not to begin
Main idea of the title: there are k black balls and 1 red ball in a black box. Whoever catches the red ball wins. Give the K value and ask whether the first hand has an advantage.
Idea: according to the probability knowledge of mathematics,
We know that when k is odd, the chances of catching the ball by the first hand and the second hand are equal, so the probability is equal and the output is 0
When k is an even number, you have more chances to catch the ball first and have an advantage to output 1
#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("0\n");
else
printf("1\n");
}
return 0;
}
J - Find Small A-ary conversion
Title address J - Find Small A
Give an integer number a, and ask how many 97. 97 after converting a to 256 base
Train of thought: according to the mathematical knowledge, convert the base system.
#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("%d\n",ans);
}
int main()
{
// freopen("in.txt","r",stdin);
int t = 1;
// int t;
//scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}