# 2019杭电ACM暑期集训队-选拔赛0707

## Problem A

### Problem Description

Luna wants to play a boring game.
She has three integers a,b,c in the beginning.
She will play the game k rounds.
Each round she will do exactly 3 steps in order:
1.If a>b then a = a – b.
2.If b>c then b = b – c.
3.If c>a then c = c – a.
She wants you to help her calculate a,b,c after k rounds.

### Input

First line contains an integer T(1≤T≤10) represents the number of test cases.
For each test case:
One line contains four integers a,b,c,k(1≤a,b,c≤1e6,1≤k≤1e9) represents the integers in the beginning and the rounds of the game.

### Output

For each test case, output a line contains three integers represents the integers a,b,c after k rounds.

### Sample Input

2
1 10 100 2
100 10 1 2

### Sample Output

1 10 98
81 8 1

## 模拟

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int a,b,c,k;
void solve(){
scanf("%d%d%d%d",&a,&b,&c,&k);
rep(i,1,k){
if(a>b) a-=b;
if(b>c) b-=c;
if(c>a) c-=a;
if(a==b&&b==c) break;
}
printf("%d %d %d\n",a,b,c);
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## Problem D

### Problem Description

Given a rooted tree with n vertices, where vertex 1 is the root, and vertex i has value a[i].

For a vertex set , we define function f:

f(s)={a[LCA(s)]0s is not emptytoherwise
LCA(s) denotes the LeastcommonAncestor of the vertices in s.

We denote the set of all the n vertices in the tree by S, your task is to calculate the following sum:

### Input

First line contains an integer n(1≤n≤1e5) represents the number of vertices in the tree.
The second line contains positive integers a1,…,an(1≤ai≤1e5).
Next lines , each contains two integers u,v(u≠v,1≤u,v≤n), indicating that there is an edge between u and v.

### Output

Output the answer in one line. Since the answer may be large, you need to modulate the answer to 1e9+7.

### Sample Input

3
5 9 4
1 2
2 3

### Sample Output

42

## 每个点的单点贡献是sum（pow_2[SIZE[v]]-1）

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
ll ans=0;
struct node{
int v,next;
}g[maxn<<1];
}
void init(){
cnt=pow_2[0]=1; ans=0;
rep(i,1,n) pow_2[i]=(2ll*pow_2[i-1])%mod;
}
void dfs(int x,int fa){
SIZE[x]=1; ll tot=0;
int v=g[i].v;
if(v!=fa){
dfs(v,x);
SIZE[x]+=SIZE[v];
tot=(tot+pow_2[SIZE[v]]-1)%mod;
}
}
ll res=1ll*a[x]*(pow_2[SIZE[x]]-tot-1+mod)%mod;
ans=(ans+res)%mod;
}
void solve(){
init();
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n-1){
int u,v;scanf("%d%d",&u,&v);
}
dfs(1,0);
printf("%lld\n",ans);
}
int main(){
while(~scanf("%d",&n)) solve();
}


## Problem E

### Problem Description

The Stick Kingdom will start a war to the Hammer Kingdom! The power of the stick army is the number of 1*1 grids made up of sticks. The king of Stick Kingdom would give you the grids he needed, and you should tell him the minimum number of sticks he needed.
Note: it’s very difficult for sticks to stand up, so the grids must be made on a 2-D plane.

### Input

First line contains an integer T(1≤T≤1e3) represents the number of test cases.
For each test case:
The first line contains an integer n(1≤n≤1e9) represents the number of grids the king needed.

### Output

For each test case, output a line contains an integer represents the minimum number of sticks the king needed.

### Sample Input

4
1
2
3
4

### Sample Output

4
7
10
12

## 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
void solve(){
scanf("%d",&n);
int a=(int)sqrt(n),b=n-a*a,ans=2*(a+1)*a+b*2;
if(b>a) ans++;
if(b) ans++;
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## Problem F

### Problem Description

Little G is now the king of the country! As a king who has nothing to do, he wants to redesign his capital roads.

Little G’s capital can be regarded as an undirected positive weight connected graph of N points. And we know the shortest path length dis[i][j] between these points.

Little G wants to construct a new undirected positive weight graph, let the shortest path length between two pairs in the new graph be the same as that of the original graph, and the number of edges is the least.

Little G needs you to tell him the minimum number of edges of the new graph.

### Input

First line contains an integer N(1≤N≤300).
Next gives a N*N matrix, represents dis[i][j](0≤dis[i][j]≤2000000).
It is guaranteed that dis[i][j] = dis[j][i] and dis[i][i]=0.

### Output

Output one line contains one integer represents the answer.

### Sample Input

3
0 1 1
1 0 1
1 1 0

### Sample Output

3


### Hint

Completed graph must be constructed to satisfy the conditions. So the sample answer is 3.

## Floyd判断一下即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,dis[330][330],vis[330][330];
ll ans=0;
void fl(){
rep(i,1,n){
rep(j,1,n){
rep(k,1,n){
if(i==j||j==k||k==i)continue;
if(dis[i][j]+dis[j][k]==dis[i][k]&&vis[i][k]==0) ans--,vis[i][k]=1;
}
}
}
}
void solve(){
rep(i,1,n) rep(j,1,n) scanf("%d",&dis[i][j]),vis[i][j]=0;
ans=n*(n-1);
fl();
printf("%lld\n",ans/2);
}
int main(){
while(~scanf("%d",&n)) solve();
}


## Problem G

### Problem Description

A light comes from point s, passed from point e, and finally go to infinite far.
There is a light given by its s and e.
You’re given a point, and your task is to judge if the point is on this light.

### Input

First line contains an integer T(1≤T≤1e5) represents the number of test cases.
For each test case:
The first line contains four integers sx,sy,ex,ey of the light.
The second line contains two integers px,py of the point.
(1≤sx,sy,ex,ey,px,py≤1000 and (sx,sy)!=(ex,ey))

### Output

For each test case, if the point is on the light, output “YES” in a single line; otherwise, output “NO” in a single line.

### Sample Input

4
2 2 3 3
2 2
2 2 3 3
1 1
7 7 11 10
855 643
7 7 7 8
7 9

### Sample Output

YES
NO
YES
YES

## 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int sx,sy,ex,ey,xx,yy;
void solve(){
scanf("%d%d%d%d%d%d",&sx,&sy,&ex,&ey,&xx,&yy);
if((xx==sx&&yy==sy)||(xx==ex&&yy==ey)){printf("YES\n");return;}
int a=xx-sx,b=yy-sy,c=ex-sx,d=ey-sy;
if(a*d==b*c&&a*c>=0) printf("YES\n");
else printf("NO\n");
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## Problem I

### Problem Description

iG is the most powerful team in the game League of Legends. Now you’re given a string only contains lowercase or uppercase letters, you should convert all “ig”, “IG” and “Ig” including in the string to “iG”.

### Input

Only one line contains a string S(1≤|S|≤100,000),S only contains lowercase or uppercase letters.

### Output

Output a string represents the answer.

### Sample Input

GGIGismostpowerfulignbIgignbnb

### Sample Output

GGiGismostpowerfuliGnbiGiGnbnb

## 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int len;
char str[maxn];
void solve(){
len=strlen(str+1);
rep(i,1,len-1){
if(str[i]=='i'&&str[i+1]=='g'){
str[i]='i';str[i+1]='G';
}
else if(str[i]=='I'&&str[i+1]=='g'){
str[i]='i';str[i+1]='G';
}
else if(str[i]=='I'&&str[i+1]=='G'){
str[i]='i';str[i+1]='G';
}
}
rep(i,1,len) printf("%c",str[i]);
printf("\n");
}
int main(){
while(~scanf("%s",str+1)) solve();
}


## Problem J

### Input

First line contains an integer represents the number T(1≤T≤1000) of test cases.
For each test case:
The first line contains an integer n(2≤n≤1e9) represents the number of grids the king needed.

### Output

For each test case, output a line contains an integer represents the answer.

### Sample Input

3
3
4
5

### Sample Output

1
0
1

### Hint

[x] means the maximum integer not greater than x.
n! means 1*2*…*(n-1)*n.

## 打表易得n为素数时[(n-1)!+1]%n=0

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
const double pi=acos(-1.0);
int n;
int ck(int x){
rep(i,2,(int)sqrt(x)) if(x%i==0) return 0;
return 1;
}
void solve(){
scanf("%d",&n);
if(ck(n)) printf("1\n");
else printf("0\n");
}
int main(){
int T;cin>>T;
while(T--) solve();
}