NOIP模拟 17.8.20

NOIP模拟17.8.20

A.阶乘
【题目描述】
亲爱的xyx同学正在研究数学与阶乘的关系，但是他喜欢颓废，于是他就制作了一个和阶乘有关系的数学游戏：
给出两个整数 n,m，令 t = !n，每轮游戏的流程如下
1.如果 m不能整除t ，即 t mod m ≠ 0，跳到第三步；如果能整除，跳到第二步
2.令 t = t/m，xyx的得分+1并返回第一步
3.游戏结束
xyx共进行T轮游戏，他想知道每轮他的得分是多少
【输入描述】
第一行一个整数 T，表示游戏轮数
接下来 T行，每行两个正整数n,m ，含义见题目描述
【输出描述】
共T 行，每行输出一个整数，表示xyx该轮游戏得到的分数
【样例输入】

4
2 3
3 3
23456 5
8735373 10
【样例输出】
0
1
5861
2183837
【限制与约定】
对于30% 的数据， n,m ≤ 20
对于60% 的数据， n,m ≤ 1e6
对于 100%的数据， n,m ≤ 1e9 ,T ≤ 10,1 < m <= 15

【题解】

此题极好

n! = 1*2*3*4*5*...*n

把m分解，设第i个质因数为pi,假设n中有k个pi

n! = 1*2*3..*pi*...*2pi*...*3pi*...*kpi...*n

然后我们让n/=pi，可以得到

n/pi! = 1*2*3*...*pi*...*2pi*...*3pi*...*(k - n/p - 1)pi*...*n/pi

证明比较显然，k*p每次-p就到达下一个p的倍数，于是，n每次-p，(n-p)!就

少一个p。干脆直接n不断/p就好了

最终结果要除以m中pi的数量

取一个min即可

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #define min(a, b) ((a) < (b) ? (a) : (b))
 6 
 7 inline void read(long long &x)
 8 {
 9     x = 0;char ch = getchar(), c = ch;
10     while(ch < '0' || ch > '9')c = ch, ch = getchar();
11     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
12     if(c == '-')x = -x;
13 }
14 
15 const long long INF = 0x3f3f3f3f;
16 
17 long long n,m,t,ans;
18 
19 int main()
20 {
21     read(t);
22     register long long k,tmp,p;
23     for(;t;--t)
24     {
25         read(n), read(m);
26         ans = INF;
27         for(register int i = 2;i <= m;++ i)
28         {
29             if(m % i == 0)
30             {
31                 k = 0, p = n, tmp = 0;
32                 while(m % i == 0)m /= i, ++ k;
33                 while(p)tmp += p/i, p/= i;
34                 ans = min(ans, tmp/k);
35             }
36         }
37         printf("%I64d
", ans);
38     }
39     return 0;
40 }

B.妹子
【题目描述】
亲爱的xyx同学正在研究数学与妹子的关系，但是他喜欢颓废，于是他就制作了一个和妹子有关系的数学游戏：
有一棵树，树上每个点i 有一个权值ai ，每轮游戏中xyx和妹子会各自选择一个点，然后对于树上所有的点来说，如果它与
xyx所选点的距离更近，那么xyx就会得到等于该点权值的分数；如果它与妹子所选点的距离更近，那么妹子就会得到等
于该点权值的分数；如果距离相等，那么xyx和妹子都不会得到分数。
xyx想知道，每轮游戏中，他和妹子得到的分数分别是多少
两点间的距离定义为该两点最短路径所经过的边的权值之和
【输入描述】
第一行一个整数 n，表示树的顶点数。
接下来n -1行，每行两个整数 u,v,w，表示第i 条边连接点 u,v，边权为w
接下来一行共 n个整数，表示树上每个点 i的权值ai 。
接下来一行一个整数 m，表示游戏轮数
接下来 m行，每行两个整数x,y ，分别表示xyx所选的点和妹子所选的点
【输出描述】
共 m行，每行输出两个整数，表示xyx得到的分数和妹子得到的分数，中间用一个空格隔开。
【样例输入】
3
1 2 1
1 3 1
10 1 1
2
2 3
1 3
【样例输出】
1 1
11 1
【限制与约定】
对于10% 的数据， n,m ≤ 100
对于30%的数据， n,m ≤ 1000
对于另外15% 的数据，第 i条边连接点i,i+1
对于另外15% 的数据，树和询问保证随机生成
对于 100%的数据，n ≤ 100000,m ≤ 50000,1 ≤ x, y,u, v ≤ n,1 ≤ w,ai ≤ 10

【题解】

此题极好+1

考察细节，参见代码

“点的类型可以看成是单调的（属于x->谁都不属于->属于y）
设dis[x]表示x到根的距离，每次询问中dis[x]>dis[y]，他们的lca为p
那么点的类型边界一定在p->x的路径上

由于在链上存在单调性，可以二分+倍增找深度差为k的父亲来做
复杂度O(n log^2 n)
也可以倍增+从高到低确定二进制位，这一位是1时如果已经不受x控制，则这一位一定为0；反之这一位为0（贪心思路）
复杂度O(n log n)”
——张浩南

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 
  6 inline void read(long long &x)
  7 {
  8     x = 0;char ch = getchar(),c = ch;
  9     while(ch < '0' || ch > '9')c = ch, ch = getchar();
 10     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
 11     if(c == '-')x = -x;
 12 }
 13 
 14 const long long MAXN = 200000 + 10;
 15 
 16 struct Edge
 17 {
 18     long long u,v,next,w;
 19     Edge(long long _u, long long _v, long long _next, long long _w){u = _u;v = _v;next = _next;w = _w;}
 20     Edge(){}
 21 }edge[MAXN << 1];
 22 
 23 long long n,m,b[MAXN],value[MAXN],sum[MAXN],path[MAXN],p[25][MAXN],deep[MAXN],fa[MAXN],head[MAXN],cnt;
 24 
 25 inline void insert(long long a, long long b, long long c)
 26 {
 27     edge[++cnt] = Edge(a,b,head[a],c);
 28     head[a] = cnt;
 29 }
 30 
 31 void dfs(long long u)
 32 {
 33     b[u] = 1;
 34     sum[u] = value[u];
 35     for(register long long pos = head[u];pos;pos = edge[pos].next)
 36     {
 37         long long v = edge[pos].v;
 38         if(b[v])continue;
 39         path[v] = path[u] + edge[pos].w;
 40         deep[v] = deep[u] + 1;
 41         dfs(v);
 42         fa[v] = u;
 43         p[0][v] = u;
 44         sum[u] += sum[v];
 45     }
 46 } 
 47 
 48 //p[0]是点 p[1]是路径长度 
 49 inline void yuchuli()
 50 {
 51     long long M = 0;
 52     while((1 << M) <= n)++ M;
 53     -- M;
 54     for(register long long i = 1;i <= M;++ i)
 55         for(register long long j = 1;j <= n;++ j)
 56             p[i][j] = p[i - 1][p[i - 1][j]];
 57 }
 58 
 59 long long lca(long long va, long long &vb)
 60 {
 61     int flag = 0;
 62     if(deep[va] < deep[vb])
 63     {
 64         long long tmp = va;
 65         va = vb;
 66         vb = tmp;
 67         flag = 1;
 68     }
 69     long long M = 1;
 70     while((1 << M) + deep[vb] <= deep[va])++ M;
 71     -- M;
 72     for(register long long i = M;i >= 0;-- i)
 73         if((1 << i) + deep[vb] <= deep[va])
 74             va = p[i][va];
 75     if(va == vb)return va;
 76     M = 1;
 77     while((1 << M) + deep[vb] <= n)++ M;
 78     -- M;
 79     for(register long long i = M;i >= 0;-- i)
 80         if(p[i][va] != p[i][vb])
 81         {
 82             va = p[i][va];
 83             vb = p[i][vb];
 84         }
 85     if(flag)vb = va;
 86     return p[0][va];
 87 }
 88 
 89 int main()
 90 {
 91     read(n);
 92     register long long tmp1, tmp2, tmp3;
 93     for(register long long i = 1;i < n;++ i)
 94     {
 95         read(tmp1),read(tmp2),read(tmp3);
 96         insert(tmp1, tmp2, tmp3);
 97         insert(tmp2, tmp1, tmp3);
 98     }
 99     for(register long long i = 1;i <= n;++ i) read(value[i]);
100     deep[1] = 0;
101     dfs(1);
102     yuchuli();
103     read(m);
104     register long long a,b,ans1,ans2,lenth,sa,sb,c,ok,M = 0;
105     while((1 << M) <= n)++ M;
106     -- M;
107     for(register long long i = 1;i <= m;++ i)
108     {
109         read(a),read(b);
110         if(a == b)
111         {
112             printf("0 0
");
113             continue;
114         }
115         ok = 0;
116         if(path[a] < path[b])
117         {
118             int tmp = a;
119             a = b;
120             b = tmp;
121             ok = 1;
122         }
123         sa = a, sb = b;
124         c = lca(sa, sb);
125         ans1 = ans2 = 0;
126     /*    if(c != 0)*/
127             lenth = path[a] + path[b] - (path[c] << 1);
128 /*        else
129             lenth = path[a] - path[b];*/
130         for(register int i = M;i >= 0;-- i)
131             if(((path[a] - path[p[i][sa]]) * 2) < lenth)
132                 sa = p[i][sa];
133         if(((path[a] - path[p[0][sa]]) << 1) == lenth)
134         {
135             if(p[0][sa] == c)
136             {
137                 if(ok)
138                     printf("%lld %lld
", sum[sb], sum[sa]);
139                 else
140                     printf("%lld %lld
", sum[sa], sum[sb]);
141                 continue;
142             }
143             else
144             {
145                 if(ok)
146                     printf("%lld %lld
", sum[1] - sum[fa[sa]], sum[sa]);
147                 else
148                     printf("%lld %lld
", sum[sa], sum[1] - sum[fa[sa]]);
149                 continue;
150             } 
151         }
152         else
153         {
154             if(ok)
155                 printf("%lld %lld
", sum[1] - sum[sa], sum[sa]);
156             else
157                 printf("%lld %lld
", sum[sa], sum[1] - sum[sa]);
158             continue;
159         }
160     }
161     return 0;
162 }

这题我调了很久，最后发现我本以为最不可能错的LCA居然写挂了，其他地方都没错。。。

C.在
【题目描述】
亲爱的xyx同学正在研究数学与存在的关系，但是他喜欢颓废，于是他就制作了一个和存在有关系的数学游戏：
有一个集合，游戏开始时里面有一些数，xyx每次可以选择集合中的两个数（这两个数可以是同一个数）相减，然后把它
们差的绝对值放入集合中（如果集合中已存在该数则不放入），经过任意次这样的操作后，xyx会给出一个数字 k，问它
是否能存在在集合中，如果能，那么游戏成功，反之失败。
（换句话说，xyx想知道这样不断操作下去，是否能凑出数字 k）
xyx有一个数列 a，他每次会给出三个数 l,r,x，即把所有的ai(l ≤ i ≤ r) 放入集合中，并且想要知道当 k = x时游戏是否成功
有多组询问且询问之间相互独立，你可以认为每次询问后xyx就把游戏中的集合清空了
【输入描述】
第一行两个整数n 和 m，分别表示数字集合的大小和询问次数。
第二行共 n个整数，表示数列 a，第 i个数是 ai。
接下来 m行，每行三个整数 l,r,x，含义见题目描述
【输出描述】
共 m行，每行一个字符串，表示对应询问的答案，如果游戏成功输出”win”，反之输出”lose”。（不输出引号）
【样例输入】
7 5
3 6 4 2 7 1 8
1 2 3
3 7 0
3 4 2
3 4 5
2 3 3
【样例输出】
win
win
win
lose
lose
【限制与约定】
对于20% 的数据， ai,x ∈ [0,1]
对于另外20% 的数据，保证 ai 随机生成
对于另外 20%的数据， l = 1
对于100% 的数据， n,m ≤ 100000,0 ≤ x,ai ≤ 10 ,1 ≤ l ≤ r ≤ n

【题解】

此题一般

当时场外试了几组数据，然后就看出来了

其实能不能凑出k，取决于两个条件：

1、数列中存在大于等于k的数

2、数列的gcd为k的因数

很显然，数列每个数都可以写作p*gcd的性质，他们加减，仍是p*gcd

每次写st表都要手推。。。所以注释里保存了我手推的过程，便于大家学习。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #define max(a, b) ((a) > (b) ? (a) : (b)) 
 6 
 7 inline void read(int &x)
 8 {
 9     x = 0;char ch = getchar(),c = ch;
10     while(ch < '0' || ch > '9')c = ch, ch = getchar();
11     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
12     if(c == '-')x = -x;
13 }
14 
15 const int MAXN = 100000 + 10;
16 
17 
18 /*
19 data[i][j]表示区间[j, j + 2^i - 1] 
20 data[i][j] = gcd(data[i - 1][j], data[i - 1][j + 2^(i - 1)]
21 [j, j + 2^(i - 1) - 1]  [j + 2 ^ (i - 1), j + 2^ i - 1]
22 
23 [l,r]
24 2 ^ M  <= r - l + 1 < 2 ^ (M + 1)
25 data[M][l], data[M][r - 2^M +  1]
26 */
27 int n,m,num[MAXN],data[2][22][MAXN],lo[MAXN],pow2[30];
28 
29 inline int gcd(int a, int b)
30 {
31     return b == 0 ? a : gcd(b, a % b);
32 }
33 
34 inline void yuchuli()
35 {
36     int M = lo[n];
37     for(register int i = 1;i <= M;++ i)
38         for(register int j = 1;j <= n;++ j)
39         {
40             data[1][i][j] = gcd(data[1][i - 1][j], data[1][i - 1][j + pow2[i - 1]]);
41             data[0][i][j] = max(data[0][i - 1][j], data[0][i - 1][j + pow2[i - 1]]);
42         }
43 }
44 
45 int findma(int l, int r)
46 {
47     return max(data[0][lo[r - l + 1]][l], data[0][lo[r - l + 1]][r - pow2[lo[r - l + 1]] +  1]);
48 }
49 
50 int findgcd(int l, int r)
51 {
52     return gcd(data[1][lo[r - l + 1]][l], data[1][lo[r - l + 1]][r - pow2[lo[r - l + 1]] +  1]);
53 }
54 
55 int main()
56 {
57     read(n);read(m);
58     lo[2] = 1;
59     for(register int i = 3;i <= n;++ i)lo[i] = lo[i >> 1] + 1;
60     pow2[0] = 1;
61     for(register int i = 1;i <= 25;++ i)pow2[i] = pow2[i - 1] << 1;
62     for(register int i = 1;i <= n;++ i)read(num[i]), data[0][0][i] = data[1][0][i] = num[i];
63     yuchuli();
64     register int l,r,k;
65     for(register int i = 1;i <= m;++ i)
66     {
67         read(l),read(r),read(k);
68         int ma = findma(l, r);
69         if(ma < k)
70         {
71             printf("lose
");
72             continue;
73         }
74         int g = findgcd(l, r);
75         if(g == 0) printf("win
");
76         else if(k % g == 0)
77         {
78             printf("win
");
79             continue;
80         }
81         else
82         {
83             printf("lose
");
84             continue;
85         }
86     } 
87     return 0;
88 }