【HNOI模拟By lyp】Day1

1 xlk
1.1 题目描述
　　给定一棵大小为 n 的无根树，求满足以下条件的四元组 (a, b, c, d) 的个数：
　　1. 1 ≤ a < b ≤ n
　　2. 1 ≤ c < d ≤ n
　　3. 不存在一个点，使得这个点同时在点 a 到点 b 的最短路和点 c 到点 d 的最短路上。
1.2 输入格式
　　第一行一个数 n 。
　　接下来 n − 1 行，每行两个数 s, t ，表示一条连接 a 和 b 的边。
1.3 输出格式
　　输出满足条件的四元组的个数。
1.4 样例输入
　　4
　　1 2
　　2 3
　　3 4
1.5 样例输出
　　2
1.6 数据范围
　　对于 30% 的数据，满足 n ≤ 50 ；
　　对于 100% 的数据，满足 1 ≤ n ≤ 80000 。

xlk
容斥。

对于每棵子树，求出一条链在子树外，一条链过子树根的方案数。这样会算重。于是再枚举每棵子树，减去一条链过根，一条链在某棵子树内的方案数。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define LY(p) freopen (p".in", "r", stdin); freopen (p".out", "w", stdout)
 8 #define LL long long
 9 #define dbl double
10 #define ld long double
11 #ifdef WIN32
12 #define LLD "%I64d"
13 #else
14 #define LLD "%lld"
15 #endif
16 #define N 80010
17 int n, x, y;
18 int h[N], ent;
19 int siz[N];
20 LL f[N], g[N], ans;
21 
22 struct edge {
23     int v, n;
24 
25     edge (int y = 0, int t = 0): v(y), n(t) {}
26 } e[N << 1];
27 
28 void link (int x, int y) {e[++ ent] = edge (y, h[x]), h[x] = ent;}
29 
30 void dfs (int o, int ft) {
31     siz[o] = 1;
32     LL d = 0;
33     for (int x = h[o], y; y = e[x].v, x; x = e[x].n)
34         if (y != ft) {
35             dfs (y, o);
36             ans += g[o] * g[y] + f[o] * siz[y] + siz[o] * f[y];
37             f[o] += d * siz[y] + siz[o] * g[y] + f[y];
38             g[o] += siz[o] * siz[y] + g[y];
39             siz[o] += siz[y];
40             d += g[y];
41         }
42 }
43 
44 int main()
45 {
46     LY("xlk");
47     scanf ("%d", &n);
48     for (int i = 1; i < n; i++)
49         scanf ("%d %d", &x, &y), link (x, y), link (y, x);
50 
51     dfs (1, 0);
52     printf (LLD, ans << 1);
53     return 0;
54 }

View Code

2 wwwwodddd
2.1 题目描述
定义一个数 x 是 Happy Number ，当且仅当求该数字所有数位的平方和，得到的新数再次求所
有数位的平方和，如此重复进行，最终结果为 � 。
例如 19 就是个 Happy Number ：
19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6²+ 8² = 100
100 → 1² + 0² + 0² = 1
给定 L, R ，求 [L, R] 内 Happy Number 的个数。
2.2 输入格式
　　第一行一个正整数 T ，表示数据组数。
　　接下来 T 行，每行两个正整数，表示 L, R 。
2.3 输出格式
　　对于每组测试数据，输出一个整数表示这个区间内 Happy Number 的个数。
2.4 样例输入
　　2
　　2 6
　　1 10
2.5 样例输出
　　0 3
2.6 数据范围
　　对于 30% 的数据，满足 R ≤ 10⁵ ；
　　对于 100% 的数据，满足 1 ≤ L ≤ R ≤ 10¹⁸, 1 ≤ T ≤ 200 。

wwwwodddd
数位 dp 。

显然任意数经过一次变换后一定会小于 2000 ，于是预处理出 f[i][j] 表示 i 位数，平方和为 j 的个数，再预处理出 [0, 2000] 内所有的 Happy Number ，数位 dp 即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define LY(p) freopen (p".in", "r", stdin); freopen (p".out", "w", stdout)
 8 #define LL long long
 9 #define dbl double
10 #define ld long double
11 #ifdef WIN32
12 #define LLD "%I64d"
13 #else
14 #define LLD "%lld"
15 #endif
16 bool vis[1500], hap[1500];
17 int T, m, now = 0;
18 LL L, R, f[2][1500][2];
19 
20 int C (int o) {
21     int s = 0;
22     while (o)
23         s += (o % 10) * (o % 10), o /= 10;
24     return s;
25 }
26 
27 int dfs (int o) {
28     if (vis[o]) return hap[o];
29     vis[o] = 1;
30     return hap[o] = (o > 1? dfs (C (o)) : 1);
31 }
32 
33 void prep() {
34     m = 1458;
35     for (int i = 1; i <= m; i++)
36         dfs (i);
37 }
38 
39 LL work (LL s) {
40     memset (f, 0, sizeof (f));
41     f[now][0][0] = 1;
42     for (int nt = 0, ns = 0; s; s /= 10) {
43         nt = s % 10;
44         for (int s = 0; s <= ns; s++)
45             for (int r = 0; r <= 1; r++)
46                 if (f[now][s][r])
47                     for (int i = 0; i <= 9; i++)
48                         f[now ^ 1][s + i * i][i > nt || (r && i == nt)] += f[now][s][r];
49 
50         memset (f[now], 0, sizeof (f[now])), now ^= 1;
51         ns += 81;
52     }
53     LL ans = 0;
54     for (int s = 1; s <= m; s++)
55         if (hap[s])
56             ans += f[now][s][0];
57     return ans;
58 }
59 
60 int main()
61 {
62     LY("wwwwodddd");
63     prep();
64     scanf ("%d", &T);
65     for (int TT = 1; TT <= T; TT++) {
66         scanf (LLD LLD, &L, &R);
67         printf (LLD"
", work (R) - work (L - 1));
68     }
69     return 0;
70 }

View Code

3 zradiance

3.1 题目描述
给定一个序列 S ，支持以下操作：
• 插入一个数 x ，使得插入后 x 是序列的第 k 个元素
• 删除第 k 个元素
• 翻转区间 [L, R]
• 给定区间 [L, R] ，求

∑ (Sy − Sx)

L≤x≤y≤R
3.2 输入格式
第一行两个整数 n, m ，表示初始时序列长度以及操作数。
第二行 n 个整数，描述初始序列。
接下来 m 行，每行格式为：
• 1 k x
• 2 k
• 3 L R
• 4 L R
意义见题面。
3.3 输出格式
对于每次询问，输出要求表达式的值。
3.4 样例输入
2 5
1 2
4 1 2
1 1 3
2 2
3 1 2
4 1 2
3.5 样例输出
1 1
3.6 数据范围
对于 30% 的数据，满足 n, m ≤ 10³
对于 100% 的数据，满足 n, m ≤ 10⁵

zradiance
显然区间具有可加性。于是就是一个普通的序列维护题。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define LY(p) freopen (p".in", "r", stdin); freopen (p".out", "w", stdout)
  8 #define LL long long
  9 #define dbl double
 10 #define ld long double
 11 #ifdef WIN32
 12 #define LLD "%I64d"
 13 #else
 14 #define LLD "%lld"
 15 #endif
 16 #define N 100010
 17 int n, m, opt, x, k, L, R;
 18 int val[N];
 19 
 20 struct SplayTree {
 21     struct node {
 22         int ch[2], fa, siz;
 23         int rev;
 24         LL val, lsum, rsum, sum;
 25     };
 26 
 27     int siz, rt;
 28     node a[N << 1];
 29 
 30     SplayTree(): siz(0), rt(0) {}
 31 
 32     int newnode (int v, int ft) {
 33         return siz ++, a[siz].val = a[siz].sum = a[siz].lsum = a[siz].rsum = v, a[siz].rev = 0, a[siz].siz = 1, a[siz].fa = ft, siz;
 34     }
 35 
 36     void update (int o) {
 37         a[o].siz = a[ a[o].ch[0] ].siz + a[ a[o].ch[1] ].siz + 1;
 38         a[o].sum = a[ a[o].ch[0] ].sum + a[ a[o].ch[1] ].sum + a[o].val;
 39         a[o].lsum = a[ a[o].ch[0] ].lsum + a[ a[o].ch[1] ].lsum + (a[o].val + a[ a[o].ch[1] ].sum) * (a[ a[o].ch[0] ].siz + 1);
 40         a[o].rsum = a[ a[o].ch[1] ].rsum + a[ a[o].ch[0] ].rsum + (a[o].val + a[ a[o].ch[0] ].sum) * (a[ a[o].ch[1] ].siz + 1);
 41     }
 42 
 43     void rev (int o) {
 44         a[o].rev ^= 1;
 45         swap (a[o].lsum, a[o].rsum);
 46         swap (a[o].ch[0], a[o].ch[1]);
 47     }
 48 
 49     void push (int o) {
 50         if (a[o].rev)
 51             rev (a[o].ch[0]), rev (a[o].ch[1]), a[o].rev = 0;
 52     }
 53 
 54     void rotate (int o, int d) {
 55         int f = a[o].fa, ff = a[f].fa, fd = (a[ff].ch[1] == f);
 56         a[f].ch[d ^ 1] = a[o].ch[d], a[ a[o].ch[d] ].fa = f;
 57         a[o].ch[d] = f, a[f].fa = o;
 58         a[ff].ch[fd] = o, a[o].fa = ff;
 59         update (f);
 60         if (rt == f) rt = o;
 61     }
 62 
 63     void splay (int o, int ft = 0) { // note that the way to find the node
 64         for (int f, ff, d, fd; a[o].fa != ft;) {
 65             f = a[o].fa, ff = a[f].fa;
 66             d = a[f].ch[1] == o, fd = a[ff].ch[1] == f;
 67             if (ff == ft)
 68                 rotate (o, d ^ 1);
 69             else
 70                 if (d == fd)
 71                     rotate (f, fd ^ 1), rotate (o, d ^ 1);
 72                 else
 73                     rotate (o, d ^ 1), rotate (o, fd ^ 1);
 74         }
 75         update (o); // remember it
 76     }
 77 
 78     int find (int k) {
 79         int o = rt;
 80         while (1) {
 81             push (o); // push the tag while searching the node
 82             if (k == a[ a[o].ch[0] ].siz + 1)
 83                 return o;
 84             if (k < a[ a[o].ch[0] ].siz + 1)
 85                 o = a[o].ch[0];
 86             else
 87                 k -= a[ a[o].ch[0] ].siz + 1, o = a[o].ch[1];
 88         }
 89     }
 90 
 91     int get (int L, int R) { // original rank
 92         int l, r;
 93         r = find (R + 1 + 1), splay (r); // all rank + 1
 94         l = find (L - 1 + 1), splay (l, r); // all rank + 1
 95         return l;
 96     }
 97 
 98     void insert (int k, int v) {
 99         int o = get (k, k - 1);
100         a[o].ch[1] = newnode (v, o);
101         splay (o);
102     }
103 
104     void remove (int k) {
105         int o = get (k, k);
106         a[o].ch[1] = 0;
107         splay (o);
108     }
109 
110     void reverse (int L, int R) {
111         int o = a[get (L, R)].ch[1];
112         rev (o), push (o);
113         splay (o);
114     }
115 
116     LL query (int L, int R) {
117         int o = a[get (L, R)].ch[1];
118         LL s = a[o].lsum - a[o].rsum;
119         push (o), splay (o);
120         return s;
121     }
122 
123     void build (int &o, int ft, int *val, int l, int r) {
124         if (l > r) return;
125         int mid (l + r >> 1);
126         o = newnode (val[mid], ft);
127         build (a[o].ch[0], o, val, l, mid - 1);
128         build (a[o].ch[1], o, val, mid + 1, r);
129         update (o);
130     }
131 
132     void init (int *val, int n) {
133         rt = newnode (0, 0), a[rt].ch[1] = newnode (0, rt);
134         build (a[ a[rt].ch[1] ].ch[0], a[rt].ch[1], val, 1, n);
135         splay (a[rt].ch[1]);
136     }
137 } *T = new SplayTree;
138 
139 int main()
140 {
141     LY("zradiance");
142     scanf ("%d %d", &n, &m);
143     for (int i = 1; i <= n; i++)
144         scanf ("%d", val + i);
145     T-> init (val, n);
146     for (int i = 1; i <= m; i++) {
147         scanf ("%d", &opt);
148         if (opt == 1)
149             scanf ("%d %d", &k, &x), T-> insert (k, x);
150         if (opt == 2)
151             scanf ("%d", &k), T-> remove (k);
152         if (opt == 3)
153             scanf ("%d %d", &L, &R), T-> reverse (L, R);
154         if (opt == 4)
155             scanf ("%d %d", &L, &R), printf (LLD"
", T-> query (L, R));
156     }
157     return 0;
158 }

View Code

以上题解fromZZD