10.30 NOIp 模拟赛
时间 | 空间 | 测试点 | 评测方式 | |
挖掘机(dig.*) | 1s | 256M | 10 | 传统 |
黑红树(brtree.*) | 2s | 256M | 10 | 传统 |
藏宝图(treas.*) | 2s | 256M | 10 | 传统 |
天神下凡(god.*) | 3s | 256M | 10 | 传统 |
评测环境：windows xp
——by zhber
*请认真阅读有关时间和空间的限制，以免出现不必要的错误
挖掘机(dig.*)
背景
附中机房谁最虚？高二一班***！感觉很顺，是吧？
题目描述
今天，丧尸czy开着挖掘机去上学(……)。但是他发现他的mz满天下，所以一路上他碰到了好多他的mz。一开始他以1km/min的速度(=60km/h……)开着挖掘机前进。他发现他只会在恰好到达某一时刻或者到达某个距离遇到mz。每次遇到mz，czy都会毫不犹豫的把她们顺路捎走(^_^)。但是他实在是太虚了，以至于当有i个mz时他的速度下降到1/(i+1)。具体说，一开始czy以1km/min速度前进，有1个mz的时候速度变为1/2 km/min，有2个时变为1/3 km/min……以此类推。现在问题来了，给出每个mz在何时出现，请你算出czy到学校要多久。
格式
输入第一行2个数n，m，分别表示mz数和czy与学校的距离(km)
接下来2到n+1行由字符串与数字构成
Dist x表示在距离达到x km时出现一个mz
Time x表示在时间达到x min时出现一个mz
输出一个整数，表示到达学校的时间。如果不能整除，直接输出整数部分即可。
样例输入
2 20
Time 3
Dist 10
样例输出
47
数据范围
对于30%数据，n,m<=50
对于50%数据，n,m<=2000
对于100%数据，n,m<=200000,x<=10^9,保证输入的数字都是整数
/*模拟*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200010
int n,m,t[maxn],d[maxn],cnt1,cnt2,c1=,c2=;
double v,pos,tnow;
char ch[];
int main(){
//freopen("Cola.txt","r",stdin);
freopen("dig.in","r",stdin);
freopen("dig.out","w",stdout);
scanf("%d%d",&n,&m);
int x;
for(int i=;i<=n;i++){
scanf("%s%d",ch,&x);
if(ch[]=='T')t[++cnt1]=x;
if(ch[]=='D')d[++cnt2]=x;
}
sort(t+,t+cnt1+);
sort(d+,d+cnt2+);
v=;
while(n){
double t1=t[c1]-tnow;
if(c1>cnt1)t1=0x7fffffff;
double t2=(double)(d[c2]-pos)*v;
if(c2>cnt2)t2=0x7fffffff;
if(c1>cnt1&&c2>cnt2)break;
if(t1>t2){//接2
pos=d[c2];
if(pos>m)break;
tnow+=t2;
v++;
c2++;
n--;
}
else if(t1<t2){//接1
pos+=(double)t1/v;
if(pos>m)break;
c1++;
tnow+=t1;
v++;
n--;
}
else if(t1==t2){//一起接
pos=d[c2];
if(pos>m)break;
c1++;c2++;
tnow+=t1;
v+=;
n-=;
}
}
if(pos<m)
tnow+=(double)(m-pos)/(double)(/v);
printf("%.0lf",tnow);
}
50分 WA
/*
竟然忘了printf约束精度时会自动四舍五入，啊啊啊
加了一句tnow-=0.5;就好了
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200010
int n,m,t[maxn],d[maxn],cnt1,cnt2,c1=,c2=;
double v,pos,tnow;
char ch[];
int main(){
//freopen("Cola.txt","r",stdin);
freopen("dig.in","r",stdin);
freopen("dig.out","w",stdout);
scanf("%d%d",&n,&m);
int x;
for(int i=;i<=n;i++){
scanf("%s%d",ch,&x);
if(ch[]=='T')t[++cnt1]=x;
if(ch[]=='D')d[++cnt2]=x;
}
sort(t+,t+cnt1+);
sort(d+,d+cnt2+);
v=;
while(n){
double t1=t[c1]-tnow;
if(c1>cnt1)t1=0x7fffffff;
double t2=(double)(d[c2]-pos)*v;
if(c2>cnt2)t2=0x7fffffff;
if(c1>cnt1&&c2>cnt2)break;
if(t1>t2){//接2
pos=d[c2];
if(pos>m)break;
tnow+=t2;
v++;
c2++;
n--;
}
else if(t1<t2){//接1
pos+=(double)t1/v;
if(pos>m)break;
c1++;
tnow+=t1;
v++;
n--;
}
else if(t1==t2){//一起接
pos=d[c2];
if(pos>m)break;
c1++;c2++;
tnow+=t1;
v+=;
n-=;
}
}
if(pos<m)
tnow+=(double)(m-pos)/(double)(/v);
tnow-=0.5;
printf("%.0lf",tnow);
}
100分 模拟
黑红树(brtree.*)
背景
Mz们在czy的生日送他一个黑红树种子……czy种下种子，结果种子很快就长得飞快，它的枝干伸入空中看不见了……
题目描述
Czy发现黑红树具有一些独特的性质。
1、 这是二叉树，除根节点外每个节点都有红与黑之间的一种颜色。
2、 每个节点的两个儿子节点都被染成恰好一个红色一个黑色。
3、 这棵树你是望不到头的（树的深度可以到无限大）
4、 黑红树上的高度这样定义:h(根节点)=0，h[son]=h[father]+1。
Czy想从树根顺着树往上爬。他有p/q的概率到达红色的儿子节点，有1-p/q的概率到达黑色节点。但是他知道如果自己经过的路径是不平衡的，他会马上摔下来。一条红黑树上的链是不平衡的，当且仅当红色节点与黑色节点的个数之差大于1。现在他想知道他刚好在高度为h的地方摔下来的概率的精确值a/b，gcd(a,b)=0。那可能很大，所以他只要知道a,b对K取模的结果就可以了。另外，czy对输入数据加密：第i个询问Qi真正大小将是给定的Q减上一个询问的第一个值a%K.
格式
第一行四个数p,q,T,k，表示走红色节点概率是p/q，以下T组询问，答案对K取模。接下来T行，每行一个数 Q,表示czy想知道刚好在高度Q掉下来的概率（已加密）
输出T行，每行两个整数，表示要求的概率a/b中a%K和b%K的精确值。如果这个概率就是0或1，直接输出0 0或1 1（中间有空格）。
样例输入1样例输入2
2 3 2 1002 3 2 20
14
26
样例输出1样例输出2
0 00 1
5 90 9
数据范围
对于30%数据,p,q<=5,T<=1000,K<=127,对于任意解密后的Q，有Q<=30
对于60%数据,p,q<=20,T<=100000,K<=65535,对于任意解密后的Q,有Q<=1000
对于100%数据,p,q<=100,T<=1000000, K<=1000000007,对于任意解密后的Q,有Q<=1000000
对于100%数据,有q>p,即0<= p/q<=1
/*表示对数学期望一窍不通，只会乱写暴力*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
int Q,p,q,t,k;
long long a,b;
bool flag;
long long gcd(long long x,long long y){
if(y==)return x;
return gcd(y,x%y);
}
void dfs(int dep,int R,int B,long long zi,long long mu){
if(dep==Q){
if(abs(R-B)>){
flag=;
a=a*mu+zi*b;
b=b*mu;
long long g=gcd(a,b);
a/=g;b/=g;
}
return;
}
if(abs(R-B)>)return;
long long z1=zi*p,m1=mu*q;
int g1=gcd(z1,m1);
z1/=g1,m1/=g1;
dfs(dep+,R+,B,z1,m1);
long long z2=zi*(q-p),m2=mu*q;
int g2=gcd(z2,m2);
z2/=g2,m2/=g2;
dfs(dep+,R,B+,z2,m2);
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("brtree.in","r",stdin);
freopen("brtree.out","w",stdout);
scanf("%d%d%d%d",&p,&q,&t,&k);
while(t--){
scanf("%d",&Q);
Q=Q-(a%k);
a=,b=;flag=;
dfs(,,,p,q);
dfs(,,,q-p,q);
a-=b;
a=a%k;b=b%k;
if(!flag)a=,b=;
cout<<a<<' '<<b<<endl;
}
}
0分 瞎暴力TLE
/*
只有在偶数高度上才会掉下去，因为走到偶数边时，红点一定等于黑点，所以走到哪里都无所谓。故把树两个高度分为一层。只有走两个红或两个黑才会掉下去。初始化出生存概率，乘1000000遍，随便问。
所以问奇数高度输出0 0，问偶数：上一层活着*这一层死。
活的概率都约分到最简而减少约分次数。
取模后虽然值变了，但是取模意义下的精确值，并无影响。
由于只会在偶数高度死掉，也就是只有走过偶数个红黑点才会死掉，所以在走过偶数个红黑点活着的条件是走过的红点数=黑点数
走过红点概率为p/q，黑点概率为(q-p)/q,可以先走黑点也可以先走红点，所以live的概率为(2*P*(q-p))/q*q
在走过偶数个点后死掉的条件是连着走了两个红点或连着走了两个黑点
分别对应的概率为(p*p)/(q*q)和((q-p)^2)/(q*q)，加起来即可
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll p,q,t,K,live[],die[];
ll shang[],xia[];
ll a=,b=;
ll gcd(ll x,ll y){return (x%y)== ? y:gcd(y,x%y);}
ll read()
{
ll sum=,f=;char x=getchar();
while(x<''||x>''){if(x=='-')f=-;x=getchar();}
while(x>=''&&x<='')sum=sum*+x-'',x=getchar();
return sum*f;
}
int main()
{
//freopen("Cola.txt","r",stdin);
freopen("brtree.in","r",stdin);
freopen("brtree.out","w",stdout);
p=read();q=read();t=read();K=read();
live[]=*p*(q-p);live[]=q*q;
ll l=gcd(live[],live[]);
live[]/=l;live[]/=l;
die[]=p*p*+q*q-*p*q;die[]=q*q;
l=gcd(die[],die[]);
die[]/=l;die[]/=l;
shang[]=;xia[]=;
for(int i=;i<=;i++){
shang[i]=(shang[i-]*live[])%K;
xia[i]=(xia[i-]*live[])%K;
}
ll x;
while(t--){
x=read();
x-=a;
if(x==||(x&)){
printf("0 0\n");
a=;
continue;
}
else{
x/=;
a=(shang[x-]*die[])%K;
b=(xia[x-]*die[])%K;
printf("%I64d %I64d\n",a,b);
}
}
}
100分 概率dp
藏宝图(treas.*)
背景
Czy爬上黑红树，到达了一个奇怪的地方……
题目描述
Czy发现了一张奇怪的藏宝图。图上有n个点，m条无向边。已经标出了图中两两之间距离dist。但是czy知道，只有当图刚好又是一颗树的时候，这张藏宝图才是真的。如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。
格式
输入数据第一行一个数T,表示T组数据。
对于每组数据，第一行一个n，表示藏宝图上的点的个数。
接下来n行,每行n个数，表示两两节点之间的距离。
输出一行或两行。第一行”Yes”或”No”，表示这是不是真的藏宝图。
若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。
样例输入
2
3
0 7 9
7 0 2
9 2 0
3
0 2 7
2 0 9
7 9 0
样例输出
Yes
1
Yes
3
样例解释:第一棵树的形状是1--2--3。1、2之间的边权是7，2、3之间是2。
第二棵树的形状是2--1--3。2、1之间的边权是2，1、3之间是7。
数据范围
对于30%数据，n<=50,1<=树上的边的长度<=10^9。
对于50%数据，n<=600.
对于100%数据，1<=n<=2500,除30%小数据外任意0<=dist[i][j]<=10^9,T<=5
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 2500
using namespace std;
int map[maxn][maxn],fa[maxn],T,n,cnt,dis[maxn][maxn],d[maxn],v[maxn];
struct node{
int from,to,v;
}e[maxn*maxn/];
bool cmp(node x,node y){
return x.v<y.v;
}
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
bool connect(int x,int y){
int f1=find(x),f2=find(y);
if(f1==f2)return ;
fa[f1]=f2;
return ;
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("treas1.in","r",stdin);
//freopen("treas.out","w",stdout);
scanf("%d",&T);
bool flag;
while(T--){
flag=;
memset(d,,sizeof(d));
memset(v,,sizeof(v));
memset(map,,sizeof(map));
memset(e,,sizeof(e));
memset(dis,,sizeof(dis));
scanf("%d",&n);cnt=;
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&map[i][j]),dis[i][j]=map[i][j];
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(i==k||i==j||j==k)continue;
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i==j)continue;
if(map[i][j]!=dis[i][j]){
printf("No\n");
flag=;
break;
}
}
if(flag)break;
}
if(flag)continue;
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
cnt++;
e[cnt].from=i;e[cnt].to=j;
e[cnt].v=map[i][j];
}
}
sort(e+,e+cnt+,cmp);
int c=;
for(int i=;i<=cnt;i++){
int from=e[i].from,to=e[i].to;
if(connect(from,to)){
c++;
d[from]++;
v[from]+=e[i].v;
d[to]++;
v[to]+=e[i].v;
if(c==n-)break;
}
}
int ans;
double mx=;
for(int i=;i<=n;i++){
if(!d[i])continue;
double now=v[i]/d[i];
if(now>mx){
ans=i;
mx=now;
}
}
printf("Yes\n");
printf("%d\n",ans);
}
}
20分 WA+TLE
/*
longlong毛病多：最大值用9223372036854775807LL，输入必须写qread
说一下本题思路：对于每个点与其它所有点的距离，显然距离最小的点一定与它直接相连
所以按照矩阵构造出最小生成树，对最小生成树bfs得出距离矩阵，与给出的矩阵对比
第二问在建树的过程中得出每个点的度数和连出的边权和最后更新答案
注意特判n=1，dis[i][j]=0(i!=j)的情况
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 2510
#define linf 9223372036854775807LL
using namespace std;
int T,n,num,head[maxn],cnt[maxn],f[maxn];
long long d[maxn][maxn],dis[maxn],sum[maxn];
bool vis[maxn];
struct node{
int to,pre;
long long v;
}e[maxn*];
struct Pair{
int id;
long long dist;
bool operator < (const Pair b)const{
return dist>b.dist;
}
};
long long qread(){
long long i=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}
return i;
}
void Insert(int from,int to,long long v){
e[++num].to=to;
e[num].v=v;
e[num].pre=head[from];
head[from]=num;
}
void Prim(){
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)dis[i]=linf;
priority_queue<Pair>q;
Pair now;
now.id=;now.dist=;
q.push(now);
while(!q.empty()){
now=q.top();q.pop();
if(vis[now.id])continue;vis[now.id]=;
if(f[now.id]){
cnt[f[now.id]]++;cnt[now.id]++;
sum[now.id]+=dis[now.id];sum[f[now.id]]+=dis[now.id];
Insert(now.id,f[now.id],dis[now.id]);
Insert(f[now.id],now.id,dis[now.id]);
}
for(int i=;i<=n;i++){
if(dis[i]>d[i][now.id]&&!vis[i]){
dis[i]=d[i][now.id];
Pair nxt;
nxt.id=i;nxt.dist=dis[i];
f[i]=now.id;
q.push(nxt);
}
}
}
}
void bfs(int s){
for(int i=;i<=n;i++)dis[i]=linf;
queue<int>q;
q.push(s);vis[s]=;dis[s]=;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
if(dis[to]==linf){
dis[to]=dis[now]+e[i].v;
q.push(to);
}
}
}
}
bool Judge(){
for(int i=;i<=n;i++){
bfs(i);
for(int j=;j<=n;j++)
if(dis[j]!=d[i][j]||(i!=j&&d[i][j]==))return ;
}
return ;
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("treas.in","r",stdin);
freopen("treas.out","w",stdout);
T=qread();
while(T--){
memset(e,,sizeof(e));num=;
memset(head,,sizeof(head));
memset(f,,sizeof(f));
memset(sum,,sizeof(sum));
memset(cnt,,sizeof(cnt));
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
d[i][j]=qread();
Prim();
if(!Judge()){printf("No\n");continue;}
else printf("Yes\n");
if(n==){printf("1\n");continue;}
int ans;double mx=;
for(int i=;i<=n;i++){
double now=sum[i]/cnt[i];
if(now>mx)mx=now,ans=i;
}
printf("%d\n",ans);
}
}
100分 最小生成树
天神下凡(god.*)
背景
Czy找到宝藏获得屠龙宝刀和神秘秘籍！现在他要去找经常ntr他的Jmars报仇……
题目描述
Czy学会了一招“堕天一击”，他对一个地点发动堕天一击，地面上就会留下一个很大的圆坑。圆坑的周围一圈能量太过庞大，因此无法通过。所以每次czy发动技能都会把地面分割。Jmars拥有好大好大的土地，几十眼都望不到头，所以可以假设土地的大小是无限大。现在czy对他发动了猛烈的攻击，他想知道在泽宇攻击之后他的土地被切成几份了?
Czy毕竟很虚，因此圆心都在x坐标轴上。另外，保证所有圆两两之间不会相交。
格式
输入第一行为整数n，表示czy放了n次堕天一击。
接下来n行，每行两个整数x[i]，r[i]。表示在坐标（x[i] , 0）放了一次堕天一击，半径为r[i]。
输出一行，表示地面被分割成几块。
样例输入
4
7 5
-9 11
11 9
0 20
样例输出
6
数据范围
对于30%数据，n<=5000
对于100%数据，1<=n<=300000,-10^9<=x[i]<=10^9,1<=r[i]<=10^9.