状态一般般，7题平均水平
Problem A
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
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
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
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;
int n,a[maxn],pow_2[maxn],SIZE[maxn],head[maxn],cnt;
ll ans=0;
struct node{
int v,next;
}g[maxn<<1];
void add(int u,int v){
g[cnt]={v,head[u]};head[u]=cnt++;
}
void init(){
rep(i,0,n) head[i]=0;
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;
for(int i=head[x];i;i=g[i].next){
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);
add(u,v);add(v,u);
}
dfs(1,0);
printf("%lld\n",ans);
}
int main(){
while(~scanf("%d",&n)) solve();
}
Problem E
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
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
Hint
签到
#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
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
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
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
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
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Problem Description
Please calculate [cos2((n−1)!+1n∗π)].
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();
}
