首页 > 代码库 > 9.14noip模拟试题
9.14noip模拟试题
中文题目名称 | 祖孙询问 | 比赛 | 数字 |
英文题目名称 | tree | mat | num |
可执行文件名 | tree | mat | num |
输入文件名 | tree.in | mat.in | num.in |
输出文件名 | tree.out | mat.out | num.out |
每个测试点时限 | 1秒 | 1秒 | 1秒 |
测试点数目 | 10 | 10 | 10 |
每个测试点分值 | 10 | 10 | 10 |
附加样例文件 | 有 | 有 | 有 |
题目类型 | 传统 | 传统 | 传统 |
二． 提交源程序文件名
对于pascal语言 | tree.pas | mat.pas | num.pas |
对于C语言 | tree.c | mat.c | num.c |
对于C++语言 | tree.cpp | mat.cpp | num.cpp |
三． 编译命令（不包含任何优化开关）
对于pascal语言 | fpc tree.pas | fpc mat.pas | fpc num.pas |
对于C语言 | gcc –o tree tree.c -lm | gcc –o mat mat.c -lm | gcc –o num num.c -lm |
对于C++语言 | g++ -o tree tree.cpp -lm | g++ -o mat mat.cpp -lm | g++ -o num num.cpp -lm |
四． 运行内存限制
内存上限 | 128M | 128M | 128M |
五． 注意事项
1、 文件名（程序名和输入输出文件名）必须使用小写。
2、 C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3、 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存1G，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。
祖孙询问
(tree.pas/c/cpp)
【问题描述】
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
【输入格式】
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。
第n+2行是一个整数m表示询问个数。
接下来m行，每行两个正整数x和y。
【输出格式】
对于每一个询问，输出1:如果x是y的祖先，输出2:如果y是x的祖先，否则输出0。
【样例输入】
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
【样例输出】
1
0
0
0
2
【数据规模】
对于30%的数据，n,m≤1000。
对于100%的.据,n,m≤40000，每个节点的编号都不超过40000。
LCA:
#include<iostream>#include<cstdio>#include<cstring>#define maxn 50010using namespace std;int N,n,m,root,num,head[maxn],dep[maxn],fa[maxn][25];struct node{ int v,pre;}e[maxn*2];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Add(int from,int to){ num++;e[num].v=to; e[num].pre=head[from]; head[from]=num;}void Dfs(int now,int from,int c){ fa[now][0]=from;dep[now]=c; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(v==from)continue; Dfs(v,now,c+1); }}void Get_fa(){ for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];}int LCA(int a,int b){ if(dep[a]<dep[b])swap(a,b); int t=dep[a]-dep[b]; for(int i=0;i<=20;i++) if((1<<i)&t)a=fa[a][i]; if(a==b)return a; for(int i=20;i>=0;i--) if(fa[a][i]!=fa[b][i]){ a=fa[a][i]; b=fa[b][i]; } return fa[a][0];}int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); N=init(); int u,v; for(int i=1;i<=N;i++){ u=init();v=init(); if(v==-1){ root=u;continue; } if(u==-1){ root=v;continue; } n=max(n,u);n=max(n,v); Add(u,v);Add(v,u); } Dfs(root,-1,0);Get_fa(); m=init(); for(int i=1;i<=m;i++){ u=init();v=init(); if(u==v){ printf("0\n"); continue; } int anc=LCA(u,v); if(anc==u)printf("1\n"); else if(anc==v)printf("2\n"); else printf("0\n"); } return 0;}
比赛
(mat.pas/c/cpp)
【问题描述】
有两个队伍A和B，每个队伍都有n个人。这两支队伍之间进行n场1对1比赛，每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如A队有A1和A2两个人，B队有B1和B2两个人，那么(A1 vs B1,A2 vs B2)和(A1 vs B2,A2 vsB1)的概率都是均等的50%。
每个选手都有一个非负的实力值。如果实力值为X和Y的选手对抗，那么实力值较强的选手所在的队伍将会获得(X-Y)^2的得分。
求A的得分减B的得分的期望值。
【输入格式】
第一行一个数n表示两队的人数为n。
第二行n个数，第i个数A[i]表示队伍A的第i个人的实力值。
第三行n个数，第i个数B[i]表示队伍B的第i个人的实力值。
【输出格式】
输出仅包含一个实数表示A期望赢B多少分。答案保留到小数点后一位（注意精度）。
【样例输入】
2
37
15
【样例输出】
20.0
【数据规模】
对于30%的数据，n≤50。
对于100%的.据,n≤50000;A[i],B[i]≤50000。
暴力30:
#include<iostream>#include<cstdio>#include<cstring>#define maxn 50010using namespace std;int n,a[maxn],b[maxn];double ans;int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); n=init(); for(int i=1;i<=n;i++) a[i]=init(); for(int i=1;i<=n;i++) b[i]=init(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i]>b[j])ans+=(a[i]-b[j])*(a[i]-b[j]); else ans-=(a[i]-b[j])*(a[i]-b[j]); printf("%.1f",ans/double(n)); return 0;}
查分优化:
/*精度有问题...70分*/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 50010#define ll long longusing namespace std;ll n,a[maxn],b[maxn],s1[maxn],s2[maxn],A[maxn],B[maxn];double ans;ll init(){ ll x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}int main(){ freopen("mat7.in","r",stdin); //freopen("mat.out","w",stdout); n=init(); for(int i=1;i<=n;i++) a[i]=init(); for(int i=1;i<=n;i++) b[i]=init(); sort(a+1,a+1+n); sort(b+1,b+1+n); for(int i=1;i<=n;i++){ s1[i]=s1[i-1]+a[i]; A[i]=A[i-1]+a[i]*a[i]; } for(int i=1;i<=n;i++){ s2[i]=s2[i-1]+b[i]; B[i]=B[i-1]+b[i]*b[i]; } for(int i=1;i<=n;i++){ int p=lower_bound(b+1,b+1+n,a[i])-b-1; ans+=p*a[i]*a[i]+B[p]-2*a[i]*s2[p]; } for(int i=1;i<=n;i++){ int p=lower_bound(a+1,a+1+n,b[i])-a-1; ans-=p*b[i]*b[i]+A[p]-2*b[i]*s1[p]; } printf("%.1f",ans/double(n)); return 0;}
数字
(num.c/cpp/pas)
【问题描述】
一个数字被称为好数字当他满足下列条件：
1. 它有2*n个数位，n是正整数(允许有前导0)。
2. 构成它的每个数字都在给定的数字集合S中。
3. 它前n位之和与后n位之和相等或者它奇数位之和与偶数位之和相等
例如对于n=2,S={1,2}，合法的好数字有1111,1122,1212,1221,2112,2121,2211,2222这样8种。
已知n，求合法的好数字的个数mod 999983。
【输入格式】
第一行一个数n。
接下来一个长度不超过10的字符串，表示给定的数字集合。
【输出格式】
一行一个数字表示合法的好数字的个数mod 999983。
【样例输入】
2
0987654321
【样例输出】
1240
【数据规模】
对于20%的数据，n≤7。
对于100%的.据,n≤1000,|S|≤10。
暴力20:
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int n,ans,x,data[20],l,f[11];char s[11];int main(){ //freopen("num.in","r",stdin); //freopen("num.out","w",stdout); scanf("%d%s",&n,s);n<<=1; l=strlen(s); for(int i=0;i<l;i++) f[s[i]-‘0‘]=1; for(int i=0;i<pow(10,n);i++){ x=i;l=0; while(x)data[++l]=x%10,x/=10; int s1=0,s2=0,falg=0,s3=0,s4=0; for(int j=1;j<=l;j++) if(f[data[j]]==0){ falg=1;break; } if(falg)continue; for(int j=1;j<=l;j++) if(j&1)s1+=data[j]; else s2+=data[j]; for(int j=1;j<=l;j++) if(j<=n/2)s3+=data[j]; else s4+=data[j]; if(s1==s2||s3==s4){ ans++; } } printf("%d\n",ans); return 0;}
正解dp 没来得及敲 因为今晚有更重要的事~~
9.14noip模拟试题