NOIP模拟52

本文主要是介绍NOIP模拟52，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Point：暴力卡常非常重要，考虑理论复杂度与实际复杂度

T1：

　　显然考虑每一位的贡献即可，打表发现为n >> i，累计即可

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define LL long long
 5 LL n,ans;
 6 signed main () {
 7     scanf ("%lld",&n);
 8     for (I i(0),k(log2(n));i <= k; ++ i)
 9       ans += n >> i;
10     printf ("%lld\n",ans);
11 }

T2：

　　考虑最优策略，由于双方都足够聪明，那么考虑对于当前决策的若干种收益中

（假设收益分别为a1,a2,...,an），那么对手一定会选择使你收益最小的一种决策

（另外比较显然的是投入数越多显然收益越多），由于资金总数相同，那么对于总资金

所造成的收益只有比例之分，而又由于对手总选择是你收益最小的决策，那么当且仅当

你的资金分配使得所有收益相同时才会获得最大收益（否则会获得min(a1,a2...an)）

此时由于存在球数参数，我们将收益设为与球数相关函数发现，当且仅当资金分配与球数

成比例时，每种球的收益相同，因此最优决策即为按比例分配

　　Little Case：由于每次选择最优策略，那么对手每次掉球其实是任意的

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 const I N = 1e6 + 3;
 6 const I mod = 998244353;
 7 I n,ans,a[N],sigma,sum,buc[N],Y[N],p;
 8 inline I read() {
 9     I x(0),y(1); C z(getchar());
10     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
11     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
12     return x * y;
13 }
14 signed main () {
15     n = read(); ans = 1;
16     for (I i(1);i <= n; ++ i) 
17         a[i] = read(), sigma += a[i], p = max (p,a[i]), buc[a[i]] ++ ;
18     Y[1] = 1; for (I i(2);i <= sigma; ++ i) Y[i] = 1ll * (mod - mod / i) * Y[mod % i] % mod;
19     sum = sigma;
20     for (I i(1);i <= sigma; ++ i) {
21         ans = 1ll * n * ans % mod * p % mod * Y[sum] % mod;
22         sum -- , buc[p - 1] ++ ; if (-- buc[p] == 0) p -- ; 
23     }
24     printf ("%d\n",ans);
25 }

当权值范围不大时，可以采用桶+指针维护最大值降低时间复杂度

T3：

　　暴力做法（正解知识点不会）：

首先发现权值范围并不大，那么对于a^k，可以进行预处理得到，那么只需要知道路径长度即可

完全暴力不说，考虑优化，发现sigma意义下，对于相同长度的路径进行了多次遍历，那么考虑

将问题中心由路径转换到长度，考虑统计每种长度的路径有多少条统一计算

比较显然的点分治，通过Dfs遍历出深度的种类与数量组合即可（时间复杂度O(n^2logn)）

可过70pts，考虑事实上在组合过程中可以采用NTT优化，时间复杂度O(nlog^2n)，然而仍然70pts

点分治代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define LLL __int128
 8 const I N = 1e6 + 3;
 9 const I mod = 998244353;
10 I n,t,MA,p[N],num[N];
11 I root,S,size[N],dp[N];
12 I tot,head[N],to[N << 1],nxt[N << 1];
13 LLL ans,pro[N];
14 B jud[N];
15 inline I read() {
16     I x(0),y(1); C z(getchar());
17     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
18     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
19     return x * y;
20 }
21 inline V print (I x){
22     C ch[12]; I len(0);
23     if(x < 0){ putchar('-'); x = ~x + 1; }
24     do { ch[len++]=x % 10+ (1 << 4) + (1 << 5); x /= 10; } while(x);
25     for(I i(len - 1); ~i ; -- i) putchar (ch[i]); 
26 }
27 inline V found (I x,I y) {
28     to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
29     to[++tot] = x, nxt[tot] = head[y], head[y] = tot;
30 }
31 inline I fp (I a) { I ans(1);
32     for (I b(t); b ;b >>= 1, a = 1ll * a * a % mod)
33       if (b & 1) ans = 1ll * ans * a % mod;
34     return ans;
35 }
36 V Find (I x,I father) {
37     dp[x] = 0, size[x] = 1;
38     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (!jud[y] && y != father)
39       Find (y,x), size[x] += size[y], dp[x] = max (dp[x],size[y]);
40     dp[x] = max (dp[x],S - size[x]);
41     if (dp[x] < dp[root]) root = x;
42 }
43 V Dfs (I x,I father,I deep) {
44     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (!jud[y] && y != father) 
45       num[deep + 1] ++ , MA = max (MA,deep + 1), Dfs (y,x,deep + 1);
46 }
47 V Figure (I x) {
48     MA = 0, Dfs (x,0,0);
49     for (I i(1);i <= MA; ++ i) {
50         pro[i + i] += 1ll * num[i] * (num[i] - 1) >> 1;
51         for (I j(i + 1);j <= MA; ++ j) 
52             pro[i + j] += 1ll * num[i] * num[j];
53         pro[i] += num[i], num[i] = 0;
54     }
55     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (!jud[y]) {
56         MA = 0, Dfs (y,x,0);
57         for (I j(1);j <= MA; ++ j) {
58             pro[j + j + 2] -= 1ll * num[j] * (num[j] - 1) >> 1;
59             for (I k(j + 1);k <= MA; ++ k)
60                 pro[j + k + 2] -= 1ll * num[j] * num[k];
61             pro[j + 2] -= num[j], num[j] = 0;
62         }
63     }
64 }
65 V Divide (I x) {
66     jud[x] = 1, Figure (x);
67     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (!jud[y])
68       root = 0, S = size[y], Find (y,x), Divide (root);
69 }
70 signed main () {
71     n = read(), t = read(); dp[root] = S = n;
72     for (I i(0);i < n - 1; ++ i) found (read(),read());
73     for (I i(1);i <= n; ++ i) p[i] = fp (i);
74     Find (1,0), Divide (root);
75     for (I i(1);i <= n; ++ i) (ans += pro[i] * p[i] % mod) %= mod;
76     print (ans);
77 }

考场注意理论复杂度与实际复杂度，想到要去打

T4：

　　暴力做法（Geek）：

发现问题与层数相关，于是对每一层分组，可以通过vector记录每一层所有点的dfn

在查询时，根据给出的x，y逐层跳跃遍历，在每一层通过lower_bound确定子树中的点

我的做法是采用树状数组差分求解（区间修改单点查询）

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define V void
 6 #define lowbit(x) (x & -x)
 7 const I N = 3e5 + 3;
 8 I n,q,root,a,b,c,l,r,MA,d[N],size[N],ld[N],rd[N];
 9 I tot,head[N],to[N << 1],nxt[N << 1],cnt1,aux[N];
10 I* BIT[N];
11 vector <I> vec[N];
12 inline I read() {
13     I x(0),y(1); C z(getchar());
14     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
15     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
16     return x * y;
17 }
18 inline V found (I x,I y) {
19     to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
20     to[++tot] = x, nxt[tot] = head[y], head[y] = tot;
21 }
22 V Dfs (I x,I father) {
23     ld[x] = ++cnt1, aux[cnt1] = x, size[x] = 1, MA = max (MA,d[x]);
24     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != father)
25       d[y] = d[x] + 1, Dfs (y,x), size[x] += size[y];
26     rd[x] = ld[x] + size[x] - 1;
27 }
28 inline V secadd (I idx,I x,I y,I z) { y ++ ;
29     for (;x <= BIT[idx][0];x += lowbit(x)) BIT[idx][x] += z;
30     for (;y <= BIT[idx][0];y += lowbit(y)) BIT[idx][y] -= z;
31 }
32 inline I poique (I idx,I x) { I ans(0);
33     for (; x ;x -= lowbit(x)) ans += BIT[idx][x];
34     return ans;
35 }
36 signed main () {
37     n = read(), q = read();
38     for (I i(0);i < n - 1; ++ i) found (read(),read()); d[1] = 1, Dfs (1,0);
39     for (I i(1);i <= cnt1; ++ i) vec[d[aux[i]]].push_back (i);
40     for (I i(1);i <= MA; ++ i) { BIT[i] = new I [vec[i].size () + 1]; 
41         memset(BIT[i],0,sizeof 4 * (vec[i].size () + 1)); BIT[i][0] = vec[i].size ();
42     }
43     while (q -- ) {
44         if (read() & 1) {
45             root = read(), a = read(), b = read(), c = read(); I deep(d[root] + b);
46             while (deep <= MA) {
47                 l = lower_bound (vec[deep].begin (),vec[deep].end (),ld[root]) - vec[deep].begin (); 
48                 if (l == vec[deep].size ()) { deep += a; continue; }
49                 r = upper_bound (vec[deep].begin (),vec[deep].end (),rd[root]) - vec[deep].begin ();
50                 secadd (deep,l + 1,r,c); deep += a;
51             }
52         }  else { root = read();
53             l = lower_bound (vec[d[root]].begin (),vec[d[root]].end (),ld[root]) - vec[d[root]].begin ();
54             printf ("%d\n",poique (d[root],l + 1));
55         }
56     }
57 }

分析题目性质，优化暴力，指针动态开空间，数组注意清零，灵活运用STL

这篇关于NOIP模拟52的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！