J
Description
输入一个数，输出其1.15倍，保留两位小数
Solution
read&write
E
Description
给出两时间，计算其差值。
Solution
模拟即可
C
Description
给出一个$n\leq100000$,求$n!的约数的约数个数$
Solution
数论不会gcd，通过样例模拟了两遍，发现$4!=2^3*3$,素因子分开解决，$2^3时其因子有可能有2^0,2^1,2^2,2^3，而这些数的因子有4*2^0,3*2^1,2*2^2,1*2^3$
嗯?等差数列累加和！！$\sum=1+2+3+4=(3+1)(3+2)/2$，那后面素因子3怎么搞，互不相干，分步计算法则，直接乘喽。
1 #include <algorithm>
2 #include <cctype>
3 #include <cmath>
4 #include <cstdio>
5 #include <cstdlib>
6 #include <cstring>
7 #include <iostream>
8 #include <map>
9 #include <queue>
10 #include <set>
11 #include <stack>
12 #if __cplusplus >= 201103L
13 #include <unordered_map>
14 #include <unordered_set>
15 #endif
16 #include <vector>
17 #define lson rt << 1, l, mid
18 #define rson rt << 1 | 1, mid + 1, r
19 #define LONG_LONG_MAX 9223372036854775807LL
20 #define ll LL
21 using namespace std;
22 typedef long long ll;
23 typedef long double ld;
24 typedef unsigned long long ull;
25 typedef pair<int, int> P;
26 int n, m, k;
27 const int maxn = 1e6 + 10;
28 const ll mod = 10000007;
29 const ll inv2 = 7486194;
30 template <class T>
31 inline T read()
32 {
33 int f = 1;
34 T ret = 0;
35 char ch = getchar();
36 while (!isdigit(ch))
37 {
38 if (ch == '-')
39 f = -1;
40 ch = getchar();
41 }
42 while (isdigit(ch))
43 {
44 ret = (ret << 1) + (ret << 3) + ch - '0';
45 ch = getchar();
46 }
47 ret *= f;
48 return ret;
49 }
50 template <class T>
51 inline void write(T n)
52 {
53 if (n < 0)
54 {
55 putchar('-');
56 n = -n;
57 }
58 if (n >= 10)
59 {
60 write(n / 10);
61 }
62 putchar(n % 10 + '0');
63 }
64 template <class T>
65 inline void writeln(const T &n)
66 {
67 write(n);
68 puts("");
69 }
70 int vis[maxn], prime[maxn], pcnt, num[maxn];
71 ll qpow(ll a, ll n)
72 {
73 ll res = 1;
74 while (n)
75 {
76 if (n & 1)
77 res = res * a % mod;
78 a = a * a % mod;
79 n >>= 1;
80 }
81 return res;
82 }
83 ll f(ll n, int p)//阶乘因子
84 {
85 if (n == 0)
86 return 0;
87 return f(n / p, p) + n / p;
88 }
89 void init()
90 {
91 for (int i = 2; i < maxn; i++)
92 {
93 if (!vis[i])
94 prime[pcnt++] = i;
95 for (int j = 0; j < pcnt && i * prime[j] <= maxn; j++)
96 {
97 vis[i * prime[j]] = 1;
98 if (i % prime[j] == 0)
99 break;
100 }
101 }
102 }
103
104 int main(int argc, char const *argv[])
105 {
106 #ifndef ONLINE_JUDGE
107 // freopen("in.txt", "r", stdin);
108 // freopen("out.txt", "w", stdout);
109 #endif
110 init();
111 while (~scanf("%d", &n) && n)
112 {
113 memset(num, 0, sizeof(int) * (n + 1));
114 for (int i = 2; i <= n; i++)
115 if (!vis[i])
116 num[i] = f(n, i);
117 ll res = 1;
118 for (int i = 2; i <= n; i++)
119 if (num[i])
120 {
121 if (num[i] & 1)
122 res = res * ((num[i] + 1) >> 1) * (num[i] + 2) % mod;
123 else
124 res = res * ((num[i] + 2) >> 1) * (num[i] + 1) % mod;
125 }
126 writeln(res);
127 }
128 return 0;
129 }F
Description
给出一个n个点的树，$n\leq10000$,m个查询，每次查询k条路径，问k条路径里的公共点个数
Solution
树上路径，先整个树剖。emmm，公共点怎么求？每个点开一个set，最后set求交集，set_intersection,
写好交，wa2。你说超时我都能理解，wa算什么本事。debug了一个小时，还是一直wa，顶不住了，换思路。
我已经把路径存到了线段树里，那么每一条查询边进来的时候路径上的点权值+1，最后查询线段树里权值为k的点不就完了吗(其实想了很久)
每次查询完后清空当前查询加的权值，防止后续影响。
见代码
1 /*
2 gym102040F 树剖+区间覆盖
3 */
4 #include <algorithm>
5 #include <cctype>
6 #include <cmath>
7 #include <cstdio>
8 #include <cstdlib>
9 #include <cstring>
10 #include <iostream>
11 #include <map>
12 #include <queue>
13 #include <set>
14 #include <stack>
15 #if __cplusplus >= 201103L
16 #include <unordered_map>
17 #include <unordered_set>
18 #endif
19 #include <vector>
20 #define lson rt << 1
21 #define rson rt << 1 | 1
22 #define LONG_LONG_MAX 9223372036854775807LL
23 #define ll LL
24 using namespace std;
25 typedef long long ll;
26 typedef long double ld;
27 typedef unsigned long long ull;
28 typedef pair<int, int> P;
29 int n, m, k, mod;
30 const int maxn = 1e5 + 10;
31 template <class T>
32 inline T read()
33 {
34 int f = 1;
35 T ret = 0;
36 char ch = getchar();
37 while (!isdigit(ch))
38 {
39 if (ch == '-')
40 f = -1;
41 ch = getchar();
42 }
43 while (isdigit(ch))
44 {
45 ret = (ret << 1) + (ret << 3) + ch - '0';
46 ch = getchar();
47 }
48 ret *= f;
49 return ret;
50 }
51 template <class T>
52 inline void write(T n)
53 {
54 if (n < 0)
55 {
56 putchar('-');
57 n = -n;
58 }
59 if (n >= 10)
60 {
61 write(n / 10);
62 }
63 putchar(n % 10 + '0');
64 }
65 template <class T>
66 inline void writeln(const T &n)
67 {
68 write(n);
69 puts("");
70 }
71 int dfn[maxn], head[maxn], siz[maxn], dep[maxn];
72 int fa[maxn], top[maxn], a[maxn], son[maxn], w[maxn], cnt, tot, root;
73 struct node
74 {
75 int to, nxt;
76 } edg[maxn << 1];
77 struct nodeT
78 {
79 int l, r;
80 int lazy, minx, maxx;
81 } tr[maxn << 2];
82 inline void pushup(int rt)
83 {
84 tr[rt].maxx = max(tr[lson].maxx, tr[rson].maxx);
85 tr[rt].minx = min(tr[lson].minx, tr[rson].minx);
86 }
87 inline void pushdown(int rt)
88 {
89 ll len = tr[rt].r - tr[rt].l + 1;
90 if (tr[rt].lazy)
91 {
92 tr[lson].minx += tr[rt].lazy; //注意此题是区间加，固懒标记也应该是累加而不是覆盖
93 tr[rson].maxx += tr[rt].lazy;
94 tr[lson].maxx += tr[rt].lazy;
95 tr[rson].minx += tr[rt].lazy;
96 tr[lson].lazy += tr[rt].lazy;
97 tr[rson].lazy += tr[rt].lazy;
98 tr[rt].lazy = 0;
99 }
100 }
101 void build(int rt, int l, int r)
102 {
103 tr[rt].l = l;
104 tr[rt].r = r;
105 tr[rt].lazy = 0;
106 tr[rt].maxx = tr[rt].minx = 0;
107 if (l == r)
108 return;
109 int mid = l + r >> 1;
110 build(lson, l, mid);
111 build(rson, mid + 1, r);
112 }
113 void modify(int rt, int L, int R, int v)
114 {
115 int l = tr[rt].l;
116 int r = tr[rt].r;
117 if (l >= L && r <= R)
118 {
119 tr[rt].lazy += v;
120 tr[rt].maxx += v;
121 tr[rt].minx += v;
122 return;
123 }
124 pushdown(rt); //当前区间没有在之前返回代表当前区间并非包含于待查询区间，在向左右区间查询时需要先将懒标记下放
125 int mid = l + r >> 1;
126 if (L <= mid)
127 modify(lson, L, R, v);
128 if (R > mid)
129 modify(rson, L, R, v);
130 pushup(rt); //更新父区间
131 }
132 int query(int rt, int L, int R, int k)
133 {
134 int l = tr[rt].l;
135 int r = tr[rt].r;
136 if (l >= L && r <= R && tr[rt].minx == tr[rt].maxx && tr[rt].minx == k)
137 return r - l + 1;
138 if (l > R || r < L || tr[rt].maxx < k)
139 return 0;
140 pushdown(rt); //和update同理
141 int mid = l + r >> 1;
142 int ans = 0;
143 if (L <= mid)
144 ans += query(lson, L, R, k);
145 if (R > mid)
146 ans += query(rson, L, R, k);
147 return ans;
148 }
149 void add(int x, int y)
150 {
151 edg[tot].nxt = head[x];
152 edg[tot].to = y;
153 head[x] = tot++;
154 }
155 void dfs1(int u, int p)
156 {
157 fa[u] = p;
158 dep[u] = dep[p] + 1;
159 siz[u] = 1;
160 int maxsz = -1;
161 for (int i = head[u]; ~i; i = edg[i].nxt)
162 {
163 int v = edg[i].to;
164 if (v == p)
165 continue;
166 dfs1(v, u);
167 siz[u] += siz[v];
168 if (siz[v] > maxsz)
169 {
170 maxsz = siz[v];
171 son[u] = v;
172 }
173 }
174 }
175 void dfs2(int u, int t)
176 {
177 dfn[u] = ++cnt;
178 top[u] = t;
179 w[cnt] = 0;
180 if (!son[u])
181 return;
182 dfs2(son[u], t);
183 for (int i = head[u]; ~i; i = edg[i].nxt)
184 {
185 int v = edg[i].to;
186 if (v == fa[u] || v == son[u])
187 continue;
188 dfs2(v, v);
189 }
190 }
191 inline void mchain(int x, int y, int z)
192 { //修改一条链
193 while (top[x] != top[y])
194 {
195 if (dep[top[x]] < dep[top[y]])
196 swap(x, y);
197 modify(1, dfn[top[x]], dfn[x], z);
198 x = fa[top[x]];
199 }
200 if (dep[x] > dep[y])
201 swap(x, y);
202 modify(1, dfn[x], dfn[y], z);
203 }
204 int main(int argc, char const *argv[])
205 {
206 #ifndef ONLINE_JUDGE
207 freopen("in.txt", "r", stdin);
208 #endif
209 int t = read<int>();
210 for (int cas = 1; cas <= t; cas++)
211 {
212 printf("Case %d:\n", cas);
213 n = read<int>();
214 memset(head, -1, sizeof(int) * (n + 1));
215 memset(dfn, 0, sizeof(int) * (n + 1));
216 memset(son, 0, sizeof(int) * (n + 1));
217 memset(siz, 0, sizeof(int) * (n + 1));
218 memset(fa, 0, sizeof(int) * (n + 1));
219 memset(top, 0, sizeof(int) * (n + 1));
220 memset(dep, 0, sizeof(int) * (n + 1));
221 memset(w, 0, sizeof(int) * (n + 1));
222 tot = cnt = 0;
223 for (int i = 1; i < n; i++)
224 {
225 int x = read<int>(), y = read<int>();
226 add(x, y);
227 add(y, x);
228 }
229 dfs1(1, 0);
230 dfs2(1, 1);
231 build(1, 1, n);
232 m = read<int>();
233 while (m--)
234 {
235 int k = read<int>();
236 vector<P> cood;
237 cood.clear();
238 for (int j = 0; j < k; j++)
239 cood.emplace_back(read<int>(), read<int>());
240 for (int j = 0; j < k; j++)
241 mchain(cood[j].first, cood[j].second, 1);
242 writeln(query(1, 1, n, k));
243 for (int j = 0; j < k; j++)
244 mchain(cood[j].first, cood[j].second, -1);
245 }
246 }
247 return 0;
248 }