中文题目名称 | 祖孙询问 | 比赛 | 数字 |
英文题目名称 | 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 50010
using namespace std;
int N,n,m,root,num,head[maxn],dep[maxn],fa[maxn][];
struct node{
int v,pre;
}e[maxn*];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';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][]=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+);
}
}
void Get_fa(){
for(int j=;j<=;j++)
for(int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
}
int LCA(int a,int b){
if(dep[a]<dep[b])swap(a,b);
int t=dep[a]-dep[b];
for(int i=;i<=;i++)
if((<<i)&t)a=fa[a][i];
if(a==b)return a;
for(int i=;i>=;i--)
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
return fa[a][];
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
N=init();
int u,v;
for(int i=;i<=N;i++){
u=init();v=init();
if(v==-){
root=u;continue;
}
if(u==-){
root=v;continue;
}
n=max(n,u);n=max(n,v);
Add(u,v);Add(v,u);
}
Dfs(root,-,);Get_fa();
m=init();
for(int i=;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 ;
}
比赛
(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 vs B1)的概率都是均等的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
3 7
1 5
【样例输出】
20.0
【数据规模】
对于30%的数据，n≤50。
对于100%的.据,n≤50000;A[i],B[i]≤50000。
暴力30:
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 50010
using namespace std;
int n,a[maxn],b[maxn];
double ans;
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=init();
for(int i=;i<=n;i++)
a[i]=init();
for(int i=;i<=n;i++)
b[i]=init();
for(int i=;i<=n;i++)
for(int j=;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 ;
}
查分优化:
/*精度有问题...70分*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50010
#define ll long long
using namespace std;
ll n,a[maxn],b[maxn],s1[maxn],s2[maxn],A[maxn],B[maxn];
double ans;
ll init(){
ll x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int main()
{
freopen("mat7.in","r",stdin);
//freopen("mat.out","w",stdout);
n=init();
for(int i=;i<=n;i++)
a[i]=init();
for(int i=;i<=n;i++)
b[i]=init();
sort(a+,a++n);
sort(b+,b++n);
for(int i=;i<=n;i++){
s1[i]=s1[i-]+a[i];
A[i]=A[i-]+a[i]*a[i];
}
for(int i=;i<=n;i++){
s2[i]=s2[i-]+b[i];
B[i]=B[i-]+b[i]*b[i];
}
for(int i=;i<=n;i++){
int p=lower_bound(b+,b++n,a[i])-b-;
ans+=p*a[i]*a[i]+B[p]-*a[i]*s2[p];
}
for(int i=;i<=n;i++){
int p=lower_bound(a+,a++n,b[i])-a-;
ans-=p*b[i]*b[i]+A[p]-*b[i]*s1[p];
}
printf("%.1f",ans/double(n));
return ;
}
数字
(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[],l,f[];
char s[];
int main()
{
//freopen("num.in","r",stdin);
//freopen("num.out","w",stdout);
scanf("%d%s",&n,s);n<<=;
l=strlen(s);
for(int i=;i<l;i++)
f[s[i]-'']=;
for(int i=;i<pow(,n);i++){
x=i;l=;
while(x)data[++l]=x%,x/=;
int s1=,s2=,falg=,s3=,s4=;
for(int j=;j<=l;j++)
if(f[data[j]]==){
falg=;break;
}
if(falg)continue;
for(int j=;j<=l;j++)
if(j&)s1+=data[j];
else s2+=data[j];
for(int j=;j<=l;j++)
if(j<=n/)s3+=data[j];
else s4+=data[j];
if(s1==s2||s3==s4){
ans++;
}
}
printf("%d\n",ans);
return ;
}
正解dp：
/*
递推+容斥原理
ANS=
前n位之和与后n位之和相等的方案数
+奇数位之和与偶数位之和相等的方案数
-前n位之和与后n位之和相等且奇数位之和与偶数位之和相等的方案数
把A∪B改成A+B-A ∩B
A B好求
A ∩B嘛 仔细想一想
设X为前n为奇数之和 Y为后n为奇数之和
x为前n为偶数之和 y为后n为偶数之和
根据题意 有 X+Y==x+y X+x==Y+y
有X==y x==Y
然后dp求就好了
要开long long 但是还不能全开 要不T
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
#define mod 999983
using namespace std;
int n,N,m,c[],vis[],mxx,f[maxn][maxn*];
long long ans,s1,s2;
char s[];
int main()
{
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
cin>>n>>s;
int len=strlen(s);
for(int i=;i<len;i++){
if(vis[s[i]-'']==)
c[++m]=s[i]-'';
vis[s[i]-'']=;mxx=max(mxx,c[m]);
}
f[][]=;
for(int i=;i<n;i++)
for(int j=;j<=mxx*i;j++)
for(int k=;k<=m;k++){
f[i+][j+c[k]]+=f[i][j];
f[i+][j+c[k]]%=mod;
}
for(int i=;i<=n*mxx;i++){
ans+=(long long)f[n][i]*f[n][i];
ans%=mod;
}
ans<<=;ans%=mod;
int a=(n+)>>;
int b=n>>;
for(int i=;i<=a*mxx;i++){
s1+=(long long)f[a][i]*f[a][i];
s1%=mod;
}
for(int i=;i<=b*mxx;i++){
s2+=(long long)f[b][i]*f[b][i];
s2%=mod;
}
ans=(ans-s1*s2%mod+mod)%mod;
cout<<ans;
return ;
}
conclusion
/*
今天题目比较难（蒟蒻我觉得）
T1裸LCA 一遍过编译 一遍A 就是这么自信
（当然考场上还是不要这么浪~要拍拍）
T2又是概率问题
有了昨天的T2的启示 每个元素等价
一块考虑 把题目简化了 然而还是T只有30分...
正解巧妙用了二分+公式推导 然后预处理一下前缀和 平方前缀和什么的
T3 dp+容斥原理 想不出来啊啊啊啊啊
暴力20
思想比较正常 就是 把A∪B改成A+B-A∩B
A B 好求
剩下的就不在我这个蒟蒻的脑洞之内了QAQ
设X为前n为奇数之和 Y为后n为奇数之和
x为前n为偶数之和 y为后n为偶数之和
根据题意 有 X+Y==x+y X+x==Y+y
有X==y x==Y
Orz
还有就是 要开longlong 但不能懒得替换 全部改
否则longlong慢 会T 今天权当暴力大赛了QAQ
其实T2还是有余地搞粗来的
但是吧 qaq 还是太弱
*/