7.29NOIP模拟赛
T1
YSG (1s,64MB,ysg.in,ysg.out)
描述
ysg,yxy,azw 三人正在刷题。
他们每做一题的时间都是一个有理数。
如果在某一时刻，三人同时做完一道 题，那么，他们会开始谈笑风生。
现在，他们想知道，从时刻 0 开始，至少要等多久才能谈笑风生。
输入格式
一行 6 个整数 a1,b1,a2,b2,a3,b3，其中 ysg 每做一道题的时间是 a1/b1，
yxy 是 a2/b2，azw 是 a3/b3。不保证 a，b 互质。
输出格式
一行 2 个数 c,d，表示第一次谈笑风生是在时刻 c/d。其中 c，d 互质。
输入样例
3 6 4 5 3 1
输出样例
12 1
样例解释
在时刻 12，ysg 做了 24 道题，yxy 做了 15 道题，azw 做了 4 道题，他们开始 谈笑风生。
备注
对于 30%的数据，b1=b2=b3=1。 对于 100%的数据，a1,a2,a3,b1,b2,b3<=100
题解：
先将三个分数化简，
再三个分数通分（可以求最小公倍数，也可以分母直接相乘），同时乘以d，
求出通分后的数的最小公倍数c，
c/d化简一下即为答案
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 int a1,b1,a2,b2,a3,b3;
6 inline int gcd(int x,int y){
7 if(y>x) swap(x,y);
8 if(y==0) return x;
9 return gcd(y,x%y);
10 }
11 inline void huajian(int &x,int &y){
12 int g=gcd(x,y);
13 x/=g; y/=g;
14 }
15 inline int get_lcm(int a,int b,int c){
16 int l1=a*b/gcd(a,b);
17 return l1*c/gcd(l1,c);
18 }
19 int main()
20 {
21 freopen("ysg.in","r",stdin);
22 freopen("ysg.out","w",stdout);
23 scanf("%d%d%d%d%d%d",&a1,&b1,&a2,&b2,&a3,&b3);
24 huajian(a1,b1);
25 huajian(a2,b2);
26 huajian(a3,b3);
27 int lcm1=get_lcm(b1,b2,b3);
28 int lcm2=get_lcm(a1*lcm1/b1,a2*lcm1/b2,a3*lcm1/b3);
29 huajian(lcm1,lcm2);
30 printf("%d %d
",lcm2,lcm1);
31 fclose(stdin); fclose(stdout);
32 return 0;
33 }
T2
YXY (1s,128MB,yxy.in,yxy.out)
问题描述
ysg,yxy,azw 三人正在刷题。
OJ 上一共有 n 道题，然而因为有的题的算法有人不会，所以他们决定每人做一道题。
现在他们已经分配好了做题任务，把每道题都指定给一个人做
但是如果有 人做的题数量比其他人多，他就会感觉不爽。
为了避免这种情况，他们只好选一些题不做，但是为了美观，他们做的题目 必须是连续一段。
他们现在想知道，有多少种选择的方案满足条件。
输入格式
输入数据有 n 行，每行一个字符串，为”ysg”,”yxy”,”azw”中的一个，
第 i 行代 表做第 i 题的人的名字。
输出格式
输出有多少种选择的方案
输入样例
ysg
yxy
azw
azw
yxy
azw
yxy
ysg
yxy
ysg
ysg
输出样例
3
样例说明
有三种方案，选 1~3 一段，选 6~8 一段，选 3~11 一段，
每一段内三个名字，出现次数一样多
数据范围
对于 20%的数据，n <= 100。
对于 40%的数据，n <= 1000。
对于 100%的数据，n <= 100000
题解：
40pts：
搞三个前缀和数组，分别维护三个名字的出现次数，
O(n^2)查询，若一段区间内三个名字的出现次数相同，ans++
100pts：
从左到右扫一遍，记录两个值：
delta1：以now为结尾的前缀中ysy出现的次数-yxy出现的次数
delta2：以now为结尾的前缀中yxy出现的次数-azw出现的次数
显然，若在两个不同的位置l和r，delta1(l)==delta(r)且delta2(l)==delta2(r),
说明从l到r三个名字出现的次数是一样的，ans++
用map维护即可
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<map>
5 using namespace std;
6 #define N 100000
7 map<int,int> a[N*2+20];
8 int n,d1=N,d2=N,ans;
9 int main()
10 {
11 a[N][N]=1; char s[5];
12 while(scanf("%s",s)!=EOF){
13 if(s[0]=='y')
14 if(s[1]=='s')
15 d1++;
16 else {
17 d1--; d2++;
18 }
19 else d2--;
20 ans+=a[d1][d2];
21 a[d1][d2]++;
22 }
23 printf("%d
",ans);
24 return 0;
25 }
T3
AZW (2s,256MB,azw.in,azw.out)
问题描述
ysg,yxy,azw 三人正在刷题。
在他们刷题的 oj 上，除第 0 题外，每道题都有一个父亲(父亲的编号不一定 比他自己小)，
所以可以把这些题看成一个树形的结构。
他们在接下来的 m 天中，每天要么做一道新题，要么浏览一些题。
浏览的方法是：
先选两道题 x,y，然后把这两道题之间路径上的题全部浏览一遍。
在浏览的时候，他们有时会发现一道题似曾相识，可又想不起何时做过，
原来是他们做这道题的时间太过久远，以致记忆的模糊。
具体来说，如果一道题做 题时间距离浏览的时间已经超过了他们当天的记忆力，
他们就会出现这样的情况 (具体看样例)。
所以，现在对于每次浏览，他们想知道，这次浏览会看多少道题，以及有多少题似曾相识。
输入格式
第一行一个数 n，代表 oj 上有 n+1 题(从 0 到 n)。
第二行 n 个数，表示第 i 道题的父亲的编号。
第三行一个数 m，代表一共 m 天 接下来 m 行，先是一个数 1 或者 2，如果是 1，后面接三个数 x,y,c，表示当 天的浏览从 x 到 y，当天记忆力为 c，否则后面接一个数 x，表示当天做了第 x 题
输出格式
对于每次浏览，输出一行两个数，表示这次浏览会看多少道题，以及有多少 题似曾相识。
输入样例
7
0 1 1 2 2 3 3
6
1 4 7 0
2 1
2 4
2 7
1 4 7 1
1 4 7 3
输出样例
5 0
5 2
5 1
样例说明
3 次都是浏览 5 道题，分别是 4 号、2 号、1 号、3 号和 7 号。
其中，对于第 1 天，所有题都没有做过；
对于第 5 天，有 2 道题似曾相识，分别是 1 号和 4 号， 7 号虽然做过，但只隔 1 天，刚好等于记忆力，所以还想得起；
对于第 6 天，只有 1 号似曾相识。
数据范围
对于 20%的数据，n <= 100，m<=100。
对于 40%的数据，n <= 2000，m<=2000。
另有 20%的数据，没有做题的操作
另有 20%的数据，虽有做题操作，但每天的记忆力都是 0
对于100%的数据，n <= 200000，m<=200000，保证一道题不会做两遍
题解：
40pts：dfs暴力在树上走，每路过一个点就看他是不是之前做过，是在什么时候做的。
60pts：40+加上求lca，
80pts：60+树链剖分/dfs序，求路径上有多少做过的题
100pts：就是相当于先把每个点是在什么时候被做的预处理出来，然后每次询问一条链上面被做时间小于一个给定数的点有多少个，用树上主席树。
别人的代码：
1 #include<cstdio>
2 #include<vector>
3 #include<algorithm>
4 #define N 200011
5 using namespace std;
6
7 int n,m,a1[N],a2[N],a3[N],a4[N];
8 int cc[N],c[20*N][2],z[20*N],t;
9 vector<int>g[N];
10 int s[N],f[20][N],d[N];
11 int lca(int u,int v){
12 if(d[u]<d[v])swap(u,v);
13 for(int i=17;~i;i--)
14 if(1<<i<=d[u]-d[v])
15 u=f[i][u];
16 if(u==v)return u;
17 for(int i=17;~i;i--)
18 if(f[i][u]^f[i][v])
19 u=f[i][u],v=f[i][v];
20 return f[0][u];
21 }
22 int cx(int o,int p){
23 int ans=0;
24 for(int l=1,r=m;l^r;)
25 if(p>l+r>>1)ans+=z[c[o][0]],
26 o=c[o][1],l=(l+r>>1)+1;
27 else o=c[o][0],r=l+r>>1;
28 return ans;
29 }
30 int main(){
31 scanf("%d",&n);
32 t=++n;
33 for(int i=2;i<=n;i++){
34 scanf("%d",&f[0][i]);
35 g[++f[0][i]].push_back(i);
36 }
37 scanf("%d",&m);
38 for(int i=1;i<=n;i++)
39 cc[i]=m;
40 for(int i=1;i<=m;i++){
41 scanf("%d",&a1[i]);
42 if(a1[i]==1)scanf("%d%d%d",&a2[i],&a3[i],&a4[i]),a2[i]++,a3[i]++;
43 else scanf("%d",&a2[i]),cc[++a2[i]]=i;
44 }
45 d[1]=1;
46 for(s[s[0]=1]=1;s[0];){
47 int u=s[s[0]--];
48 z[u]=z[f[0][u]]+1;
49 for(int o=u,oo=f[0][u],l=1,r=m;l^r;){
50 int w=cc[u]>l+r>>1;
51 if(w)l=(l+r>>1)+1;
52 else r=l+r>>1;
53 c[o][w^1]=c[oo][w^1];
54 o=c[o][w]=++t,oo=c[oo][w];
55 z[o]=z[oo]+1;
56 }
57 for(int i=0;i<g[u].size();i++)
58 d[g[u][i]]=d[u]+1,s[++s[0]]=g[u][i];
59 }
60 for(int k=0;1<<k<n;k++)
61 for(int i=1;i<=n;i++)
62 f[k+1][i]=f[k][f[k][i]];
63 for(int i=1;i<=m;i++)
64 if(a1[i]==1){
65 int u=a2[i],v=a3[i],w=lca(u,v),p=i-a4[i];
66 printf("%d %d
",d[u]+d[v]-2*d[w]+1,cx(u,p)+cx(v,p)-cx(w,p)-cx(f[0][w],p));
67 }
68 }