【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
容斥。

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

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LY(p) freopen (p".in", "r", stdin); freopen (p".out", "w", stdout)

 #define LL long long

 #define dbl double

 #define ld long double

 #ifdef WIN32

 #define LLD "%I64d"

 #else

 #define LLD "%lld"

 #endif

 #define N 80010

 int n, x, y;

 int h[N], ent;

 int siz[N];

 LL f[N], g[N], ans;

 struct edge {

     int v, n;

     edge (int y = , int t = ): v(y), n(t) {}

 } e[N << ];

 void link (int x, int y) {e[++ ent] = edge (y, h[x]), h[x] = ent;}

 void dfs (int o, int ft) {

     siz[o] = ;

     LL d = ;

     for (int x = h[o], y; y = e[x].v, x; x = e[x].n)

         if (y != ft) {

             dfs (y, o);

             ans += g[o] * g[y] + f[o] * siz[y] + siz[o] * f[y];

             f[o] += d * siz[y] + siz[o] * g[y] + f[y];

             g[o] += siz[o] * siz[y] + g[y];

             siz[o] += siz[y];

             d += g[y];

         }

 }

 int main()

 {

     LY("xlk");

     scanf ("%d", &n);

     for (int i = ; i < n; i++)

         scanf ("%d %d", &x, &y), link (x, y), link (y, x);

     dfs (, );

     printf (LLD, ans << );

     return ;

 }

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 即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LY(p) freopen (p".in", "r", stdin); freopen (p".out", "w", stdout)

 #define LL long long

 #define dbl double

 #define ld long double

 #ifdef WIN32

 #define LLD "%I64d"

 #else

 #define LLD "%lld"

 #endif

 bool vis[], hap[];

 int T, m, now = ;

 LL L, R, f[][][];

 int C (int o) {

     int s = ;

     while (o)

         s += (o % ) * (o % ), o /= ;

     return s;

 }

 int dfs (int o) {

     if (vis[o]) return hap[o];

     vis[o] = ;

     return hap[o] = (o > ? dfs (C (o)) : );

 }

 void prep() {

     m = ;

     for (int i = ; i <= m; i++)

         dfs (i);

 }

 LL work (LL s) {

     memset (f, , sizeof (f));

     f[now][][] = ;

     for (int nt = , ns = ; s; s /= ) {

         nt = s % ;

         for (int s = ; s <= ns; s++)

             for (int r = ; r <= ; r++)

                 if (f[now][s][r])

                     for (int i = ; i <= ; i++)

                         f[now ^ ][s + i * i][i > nt || (r && i == nt)] += f[now][s][r];

         memset (f[now], , sizeof (f[now])), now ^= ;

         ns += ;

     }

     LL ans = ;

     for (int s = ; s <= m; s++)

         if (hap[s])

             ans += f[now][s][];

     return ans;

 }

 int main()

 {

     LY("wwwwodddd");

     prep();

     scanf ("%d", &T);

     for (int TT = ; TT <= T; TT++) {

         scanf (LLD LLD, &L, &R);

         printf (LLD"\n", work (R) - work (L - ));

     }

     return ;

 }

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
显然区间具有可加性。于是就是一个普通的序列维护题。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LY(p) freopen (p".in", "r", stdin); freopen (p".out", "w", stdout)

 #define LL long long

 #define dbl double

 #define ld long double

 #ifdef WIN32

 #define LLD "%I64d"

 #else

 #define LLD "%lld"

 #endif

 #define N 100010

 int n, m, opt, x, k, L, R;

 int val[N];

 struct SplayTree {

     struct node {

         int ch[], fa, siz;

         int rev;

         LL val, lsum, rsum, sum;

     };

     int siz, rt;

     node a[N << ];

     SplayTree(): siz(), rt() {}

     int newnode (int v, int ft) {

         return siz ++, a[siz].val = a[siz].sum = a[siz].lsum = a[siz].rsum = v, a[siz].rev = , a[siz].siz = , a[siz].fa = ft, siz;

     }

     void update (int o) {

         a[o].siz = a[ a[o].ch[] ].siz + a[ a[o].ch[] ].siz + ;

         a[o].sum = a[ a[o].ch[] ].sum + a[ a[o].ch[] ].sum + a[o].val;

         a[o].lsum = a[ a[o].ch[] ].lsum + a[ a[o].ch[] ].lsum + (a[o].val + a[ a[o].ch[] ].sum) * (a[ a[o].ch[] ].siz + );

         a[o].rsum = a[ a[o].ch[] ].rsum + a[ a[o].ch[] ].rsum + (a[o].val + a[ a[o].ch[] ].sum) * (a[ a[o].ch[] ].siz + );

     }

     void rev (int o) {

         a[o].rev ^= ;

         swap (a[o].lsum, a[o].rsum);

         swap (a[o].ch[], a[o].ch[]);

     }

     void push (int o) {

         if (a[o].rev)

             rev (a[o].ch[]), rev (a[o].ch[]), a[o].rev = ;

     }

     void rotate (int o, int d) {

         int f = a[o].fa, ff = a[f].fa, fd = (a[ff].ch[] == f);

         a[f].ch[d ^ ] = a[o].ch[d], a[ a[o].ch[d] ].fa = f;

         a[o].ch[d] = f, a[f].fa = o;

         a[ff].ch[fd] = o, a[o].fa = ff;

         update (f);

         if (rt == f) rt = o;

     }

     void splay (int o, int ft = ) { // note that the way to find the node

         for (int f, ff, d, fd; a[o].fa != ft;) {

             f = a[o].fa, ff = a[f].fa;

             d = a[f].ch[] == o, fd = a[ff].ch[] == f;

             if (ff == ft)

                 rotate (o, d ^ );

             else

                 if (d == fd)

                     rotate (f, fd ^ ), rotate (o, d ^ );

                 else

                     rotate (o, d ^ ), rotate (o, fd ^ );

         }

         update (o); // remember it

     }

     int find (int k) {

         int o = rt;

         while () {

             push (o); // push the tag while searching the node

             if (k == a[ a[o].ch[] ].siz + )

                 return o;

             if (k < a[ a[o].ch[] ].siz + )

                 o = a[o].ch[];

             else

                 k -= a[ a[o].ch[] ].siz + , o = a[o].ch[];

         }

     }

     int get (int L, int R) { // original rank

         int l, r;

         r = find (R +  + ), splay (r); // all rank + 1

         l = find (L -  + ), splay (l, r); // all rank + 1

         return l;

     }

     void insert (int k, int v) {

         int o = get (k, k - );

         a[o].ch[] = newnode (v, o);

         splay (o);

     }

     void remove (int k) {

         int o = get (k, k);

         a[o].ch[] = ;

         splay (o);

     }

     void reverse (int L, int R) {

         int o = a[get (L, R)].ch[];

         rev (o), push (o);

         splay (o);

     }

     LL query (int L, int R) {

         int o = a[get (L, R)].ch[];

         LL s = a[o].lsum - a[o].rsum;

         push (o), splay (o);

         return s;

     }

     void build (int &o, int ft, int *val, int l, int r) {

         if (l > r) return;

         int mid (l + r >> );

         o = newnode (val[mid], ft);

         build (a[o].ch[], o, val, l, mid - );

         build (a[o].ch[], o, val, mid + , r);

         update (o);

     }

     void init (int *val, int n) {

         rt = newnode (, ), a[rt].ch[] = newnode (, rt);

         build (a[ a[rt].ch[] ].ch[], a[rt].ch[], val, , n);

         splay (a[rt].ch[]);

     }

 } *T = new SplayTree;

 int main()

 {

     LY("zradiance");

     scanf ("%d %d", &n, &m);

     for (int i = ; i <= n; i++)

         scanf ("%d", val + i);

     T-> init (val, n);

     for (int i = ; i <= m; i++) {

         scanf ("%d", &opt);

         if (opt == )

             scanf ("%d %d", &k, &x), T-> insert (k, x);

         if (opt == )

             scanf ("%d", &k), T-> remove (k);

         if (opt == )

             scanf ("%d %d", &L, &R), T-> reverse (L, R);

         if (opt == )

             scanf ("%d %d", &L, &R), printf (LLD"\n", T-> query (L, R));

     }

     return ;

 }

以上题解fromZZD

巴特西

【HNOI模拟By lyp】Day1

最新文章

热门文章