A. 丁神去谷歌 2014新生暑假个人排位赛02
题目描写叙述
丁神要去Google上班了，去之前丁神想再做一道水题，但时间不多了，所以他希望题目做起来既水又快。如今一共同拥有
输入格式
输入第一行为数据组数
输出格式
对于每组数据，输出相应的题目编号，每一个输出占一行。
输入例子
1
2
3 5
4 8输出例子
2#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
struct Num
{
int a,b,id;
}num[111111];
bool cmp(Num my,Num s)
{
return my.a==s.a?my.id<s.id:my.a<s.a;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/in.txt","r",stdin);
//freopen();
#endif
int T;
scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&num[i].a,&num[i].b);
num[i].id=i;
}
Num ans=num[1];
for(int i=1;i<=n;i++)
{
if((num[i].b*1.0/num[i].a)>(ans.b*1.0/ans.a))
{
ans=num[i];
}
else if((num[i].b*1.0/num[i].a)==(ans.b*1.0/ans.a))
{
if(num[i].a<ans.a)
{
ans=num[i];
}
else if (num[i].a==ans.a)
{
if(num[i].id<ans.id)
ans=num[i];
}
}
}
printf("%d
",ans.id);
}
return 0;
}B. 丁神又去谷歌 2014新生暑假个人排位赛02
题目描写叙述
丁神又要去Google上班了，这一次丁神想多做几道水题，并使题目的总水量最大.丁神同一时刻仅仅能在水一道题，仅仅有做完这道题才干得到它的水值，丁神的总时间为
输入格式
输入第一行为数据组数
输出格式
对于每组数据，输出相应的最大总水量，每一个输出占一行。
输入例子
1
10 2
8 16
6 12输出例子
16#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N=111111;
long long w[N];
long long v[N];
long long dp[1111];
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/in.txt","r",stdin);
//freopen();
#endif
long long T,t,n;
cin>>T;
while(T--)
{
memset(dp,0,sizeof(dp));
cin>>t>>n;
//cout<<"n::"<<t<<endl;
for(long long i=0;i<n;i++)
{
cin>>w[i]>>v[i];
}
for(long long i=0;i<n;i++)
{
for(long long j=t;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[t]<<'
';
}
return 0;
}
C. goblin 2014新生暑假个人排位赛02
题目描写叙述
现有一段横向长度为N的山脉，当中每段有一个独一无二的高度Hi(1到N之间的正整数）。如今你想知道对于长度为N的山脉，可能有这种山脉多少种。这种山脉是：某个位置要么比两边的高度都低，要么比两边的高度都高。两座山脉 A和 B 不同当且仅当存在一个 i，使得 Ai≠Bi。因为这个数目可能非常大，你仅仅对它除以 P 的余数感兴趣。
输入格式
输入以EOF为结束，每组仅含一行，两个正整数 N, P。 3≤N≤4200，P≤10^9
输出格式
对于每组数据输出仅含一行，一个非负整数，表示你所求的答案对 P 取余之后的结果。
输入例子
4 7输出例子
3
说明：共同拥有 10 种可能的山脉，它们是：
1324 1423 2143 2314 2413
3142 3241 3412 4132 4231 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=4333;
int c[N][N];
int g[N];
int n,p;
int main()
{
while(scanf("%d%d",&n,&p)!=EOF)
{
memset(g,0,sizeof(g));
c[1][0]=1;
c[1][1]=1;
g[0]=g[1]=1%p;g[2]=1%p;g[3]=2%p;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0||j==i)
c[i][j]=1;
else
c[i][j]=(c[i-1][j]%p+c[i-1][j-1]%p)%p;
}
}
/*for(int i=1;i<=8;i++)
{
for(int j=1;j<=i;j++)
cout<<"i::"<<i<<"j::"<<j<<' '<<c[i][j]<<endl;
}*/
for(int j=3;j<=n;j++)
{
for(int i=0;i<=j-1;i+=2)
{
//cout<<g[j+1]<<endl;
g[j+1]=(g[j+1]+((long long)c[j][i]%p*(long long)g[i]%p*(long long)g[j-i])%p)%p;
//g[j+1]/=2;
if(((j+1)&1)&&i==0)
g[j+1]=g[j+1]*2%p;
}
}
printf("%d
",(g[n]*2)%p);
}
return 0;
}D. 学姐逗学弟 2014新生暑假个人排位赛02
题目描写叙述
学弟们来了之后，学姐每天都很高兴的和学弟一起玩耍。这一天，学姐想出了这样一个游戏，她画了一棵树，树上共同拥有
输入格式
输入第一行为一个整数
输出格式
假设学姐能胜利，输出"MengMengDa!"，否则输出"So sad..."。没有引號。
输入例子
1
3 1
1 1
1输出例子
MengMengDa!everySG，正好前一天晚上看了EVERYSG。先算各个节点的SG值，再算各个节点的步数（赢的节点的步数是儿子节点中输的节点中的最大步数+1，输的节点的步数是儿子节点中赢的节点中的最小步数+1）。节点仅仅关心有没有石头而不关心有几个石头，由于有几个石头都是一样的。找出给出的节点中最长的步数，奇数则先手赢，偶数则后手赢
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
#define N 111111
vector<int> G[N];
int getLosestep(int x);
int fa[N];
int sg[N];
int step[N];
int getsg(int x)
{
if(sg[x]!=-1)
return sg[x];
bool vis[11111];
memset(vis,0,sizeof(vis));
for(int i=0;i<G[x].size();i++)
{
vis[getsg(G[x][i])]=true;
}
for(int i=0;i<11111;i++)
{
if(!vis[i])
{
return sg[x]=i;
}
}
}
/*int getWinstep(int x)
{
int ans=0;
if(winstep[x]!=-1)
return winstep[x];
for(int i=0;i<G[x].size();i++)
{
if(sg[G[x][i]==0])
{
ans=max(ans,getLosestep(G[x][i]));
ans++;
}
}
return winstep[x]=ans;
//cout<<"x::"<<
}
int getLosestep(int x)
{
int ans=(1<<29);
if(losestep[x]!=-1)
return losestep[x];
for(int i=0;i<G[x].size();i++)
{
if(sg[G[x][i]!=0])
{
ans=min(ans,getWinstep(G[x][i]));
ans++;
}
}
if(ans==(1<<29))
ans=0;
return losestep[x]=ans;
}*/
int getstep(int x)
{
if(step[x]!=-1)
return step[x];
//if(G[x].size()==0)
//return 0;
if(sg[x]==0)
{
if(step[x]!=-1)
return step[x];
int ans=1<<29;
if(G[x].size()==0)
return step[x]=0;
for(int i=0;i<G[x].size();i++)
{
if(sg[G[x][i]]!=0)
{
ans=min(ans,getstep(G[x][i]));
}
}
return step[x]=ans+1;
}
else
{
if(step[x]!=-1)
return step[x];
int ans=0;
if(G[x].size()==0)
return step[x]=0;
for(int i=0;i<G[x].size();i++)
{
if(sg[G[x][i]]==0)
{
ans=max(ans,getstep(G[x][i]));
}
}
return step[x]=ans+1;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/in.txt","r",stdin);
//freopen();
#endif
int T;
scanf("%d",&T);
while(T--)
{
for(int i=0;i<N;i++)
G[i].clear();
//memset(winstep,-1,sizeof(winstep));
//memset(losestep,-1,sizeof(losestep));
memset(step,-1,sizeof(step));
memset(sg,-1,sizeof(sg));
int n,m;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
}
for(int i=2;i<=n;i++)
{
G[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++)
getsg(i);
//getWinstep(1);
//getLosestep(1);
//getWinstep(1);
//getLosestep(1);
for(int i=1;i<=n;i++)
getstep(i);
int longwin=0;
int shortlose=0;
for(int i=1;i<=m;i++)
{
int pos;scanf("%d",&pos);
if(sg[pos]==0)
{
shortlose=max(shortlose,step[pos]);
}
else
{
longwin=max(longwin,step[pos]);
}
}
/*if(shortlose==(1<<29)) shortlose=0;
//cout<<"sg::"<<sg[1]<<endl;
//cout<<"l,s::"<<longwin<<","<<shortlose<<endl;*/
if(longwin>shortlose)
puts("MengMengDa!");
else
puts("So sad...");
}
return 0;
}E. 木头人足球赛 2014新生暑假个人排位赛02
题目描写叙述
木头人星的行动速度是地球上乌龟的
输入格式
第一行为组数
输出格式
每组数据一行，假设 Mays 队10号队员直接能够射门得分，则输出“Shoot!”；假设10号队员不能成功射门，输出"Poor Mays!".
输入例子
1
104 34
1 24 2.928
48 25 2.605
15 41 1.312
39 42 2.454
3 12 2.080
18 39 1.564
10 36 2.530
97 13 1.589
101 57 1.844
84 39 2.561
0 33 1.831输出例子
Shoot!