8.07集训

Posted on 2020-08-07 Edited on 2020-11-14 In 暑假日常

上午

考试 ### 第一题

$T$ 次询问，每次询问给定 $n$ ，求 $\sum_{i = 1}^{n} ⌊ \frac{n}{i} ⌋$

上来看到 $2 s 1 G B$ ，直接准备打表…..

于是我开始手算…..

$n = 1 g e t 1, n = 2 g e t 3, n = 3 g e t 5, n = 4 g e t 8, n = 5 g e t 10, n = 6 g e t 14, n = 7 g e t 16,$

$n = 8 g e t 20, n = 9 g e t 23$

我注意到， $n$ 为奇数的时候，比她小的偶数的 $a n s_{i - 1}$ 就为 $a n s_{i} - 2$

于是我开始验证，嗯， $2, 3$ 满足， $4, 5$ 满足， $6, 7$ 满足，我没有验证 $8, 9$ ！

可偏偏 $8, 9$ 就没有满足这个规律！

于是在我自以为正确的规律下，开始计算打表时间，计算最多可以达到多少

$1 e 7 * 1 e 7 / 1 e 9$ 需要三个多小时

$1 e 6 * 1 e 6 / 1 e 9$ 需要四分钟

但是 $1 e 7$ 太诱人了，满分太诱人了，我又考虑各种优化打表程序

直到最后放弃打表 $1 e 7$ ，但是为了 $1 e 6$ 的打表程序，我还搞了搞常数优化

$45 m i n s l a t e r$

我注意到 $n = 8 g e t 20$ ，我仍旧以为是我手算错了，还在草稿纸上，用红笔改为了 $21$

交上去之后，首先是找不到源程序，搞得我一头雾水，后来把源程序的内存限制改为了 $10000 K B$

（我的程序是 $7000 多 K B$ ）

我的代码能编译了，结果一片红，那一刻，我心里是真的凉

整除分块只有四十分

考虑 $⌊ \frac{n}{i} ⌋$ 的含义： $1 ~ N$ 中 $i$ 的倍数的数目

那么所求的就是 $1 ~ N$ 中所有数的倍数的数目，反过来就是 $1 ~ N$ 所有数的约数的数目

所求转化为 $\sum_{i = 1}^{n} d (i)$ ，其中 $d (i)$ 是 $i$ 的约数的个数

线性筛可以满分

关于线性筛约数，我还不会，甩个链接click1 click2

#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int Tn = 4e7+66;

int N, T, p, cnt;
int res, last = -2;
int a[Tn], v[Tn], f[Tn];
LL sum[Tn]; int prime[Tn];

inline int thestars() {
   scanf ("%d%d%d", &N, &T, &p);
   f[1] = 1;
   for (int i = 2; i <= N; ++ i) {
      if (!v[i]) {
         a[i] = 1;
         f[i] = 2;
         prime[++ cnt] = i;
      }
      for (int j = 1; j <= cnt && i * prime[j] <= N; ++ j) {
         int now = i * prime[j];
         v[now] = 1;
         if (i % prime[j] == 0) {
            a[now] = a[i] + 1;
            f[now] = f[i]/(a[i]+1)*(a[i]+2);
            break;
         } else a[now] = 1, f[now] = f[i]*2;
      }
   }
   for (int i = 1; i <= N; ++ i) sum[i] = sum[i - 1] + f[i];
   for (int i = 1; i <= T; ++ i) res ^= (last = sum[(last+i+p)%N+1]);
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

第二题

一句话题意：小伙子和小姑娘玩一个游戏：在一个装有 $w$ 个白球， $b$ 个黑球的袋子里，轮流摸球，摸到一个就扔一个，谁先拿到白球谁赢。小伙子为了赢，于是作弊：自己拿完球之后，如果袋子里面还有球，他就再拿一个扔掉，无论这个是白球或者黑球，他第二次摸的这个不计输赢

算小姑娘赢的概率

（概率dp）

设 $f [i] [j]$ 表示袋子里还有 $i$ 个白球和 $j$ 个黑球时，Alice获胜的概率

则Alice获胜有三种情况：

1.小姑娘直接摸出白球，概率 $\frac{i}{i + j}$
2.小姑娘运气不好，摸到了黑球，小伙子摸出了黑球，扔了一个白球
这时候概率显然： $\frac{i}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2} \times f [i - 1] [j - 2]$
3.小姑娘还是摸出黑球，小伙子摸出了一个黑球，扔掉了一个黑球
这时候概率显然： $\frac{i}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2} \times f [i] [j - 3]$

#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e3+66;

int w, b;
double f[N][N];

inline int thestars() {
   scanf ("%d%d", &w, &b);
   for (int i = 1; i <= w; ++ i) f[i][0] = 1;
   for (int i = 0; i <= b; ++ i) f[0][i] = 0;
   for (int i = 1; i <= w; ++ i) {
      for (int j = 1; j <= b; ++ j) {
         f[i][j] += (double)i/(i + j);
         if (j > 1) {
            f[i][j] += f[i - 1][j - 2]*j/(i + j)*(j - 1)/(i + j - 1)*i/(i + j - 2);
            if (j > 2) f[i][j] += f[i][j - 3]*j/(i + j)*(j - 1)/(i + j - 1)*(j - 2)/(i + j -2);
         }
      }
   }
   printf ("%.10lf\n", f[w][b]);
   return 0;
}

int youngore = thestars();

signed main() {;}

第三题

一句话题意：有 $n$ 个人要参观 $m$ 个村庄，一开始每一个村庄都没有人，当一个人进入之后，会产生一个惊叹值，大小等于此人进去之后，该村庄的总人数

现在有 $k$ 次清空村庄的机会，清空操作只能在一个人进入村庄并且产生惊叹值之后进行，求最小的惊叹值总和

数据范围与提示：

对于 $40 %$ 的数据： $m = 1$

对于 $60 %$ 的数据： $n \leq 1000$

对于 $80 %$ 的数据： $n \leq 50000$

对于 $100 %$ 的数据： $1 \leq n \leq 1 e 6, 1 \leq m \leq 100, 1 \leq k \leq 500$

我觉得是一个很好的题，数据给出 $m = 1$ ，部分 $p t s$ 的做法，可以很好的引申到正解

当 $m = 1$ 我们显然要将机会平均分配

设 $c a l c (n, x)$ 表示一个村庄内 $n$ 个人平均分成 $x$ 段的最小惊叹值（用 $k$ 次机会，会将村庄分成 $k + 1$ 段）

那么我们可以 $O (1)$ 求出 $c a l c (n, x) = (n % x) \times s u m (⌊ \frac{n}{x} ⌋ + 1) + (x - n % x) \times s u m (⌊ \frac{n}{x} ⌋)$

其中 $s u m [x] = \frac{x (x + 1)}{x}$ 。比较科学的解释是：从 $1$ 加到 $x$ ，每一个数的和

当 $m \neq 1$ 的时候，显然要用分组背包啊

设 $f [i] [j]$ 表示前 $i$ 个村庄使用 $j$ 次机会的最小惊叹值

则有 $f [i] [j] = M i n (f [i] [j], f [i - 1] [t] + c a l c (c n t [i], j - t + 1))$

其中 $c n t [i]$ 是桶，答案就是： $f [m] [k]$

时间复杂度： $O (n + m \times k^{2})$

#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e5+66;

int n, m, k;
int tong[N];
int f[110][600];

inline int sum(int x) {return x*(x+1)/2;}

inline int calc(int x, int y) {return (x%y)*sum(x/y+1) + (y-x%y)*sum(x/y);}

inline int thestars() {
   cin >> n >> m >> k;
   for (int i = 1; i <= n; ++ i) {
      int x;
      scanf ("%lld", &x);
      ++ tong[x];
   }
   memset(f, 0x3f, sizeof f);
   f[0][0] = 0;
   for (int i = 1; i <= m; ++ i) {
      for (int j = 0; j <= k; ++ j) {
         for (int z = 0; z <= j; ++ z) {
            f[i][j] = min(f[i][j], f[i - 1][z]+calc(tong[i], j - z + 1));
         }
      }
   }
   cout << f[m][k];
   return 0;
}

int youngore = thestars();

signed main() {;}

下午

讲课，主要讲的数据结构

晚上

做题，上例题

疯狂的馒头

click

一句话题意：给你一些区间，让你在一些区间染色，输出最后的染色结果，数据量 $1 e 6$

正着来貌似不太容易，我们尝试想做概率dp一样，反着搞

因为倒着搞的话，每个颜色就固定了，不会再被更新，这样一个位置最多只需要染一次，染过就不需要再染

并查集的一个经典神助攻：删除一个数后快速找到它后面第一个没有删除的数（处理完一个位置后快速找打它后面第一个需要处理的位置）用并查集维护这个点往后最近的白色馒头是谁，然后时光倒流，直接往它的fa处跳就行了

这样就能保证每个位置只被染一次，时间复杂度 $O (n + m)$

这个神助攻经常被用来“每个位置最多只会被处理一次”和“标记”和“快速找到最近的满足条件的位置”，常和离线、预处理、“正难则反”等结合，非常腻害

#include <bits/stdc++.h>
#define LL long long
// #define debug
using namespace std;

const int T = 1e7+66;

int N, M, p, q;
int a[T], fa[T];

inline int Find(int x) {return tmp = fa[x]==x?fa[x]=x:fa[x]=Find(fa[x]);}

inline int thestars() {
   cin >> N >> M >> p >> q;
   for (int i = 1; i <= N + 1; ++ i) fa[i] = i;
   for (int i = M; i; -- i){
      int l = ((LL)i * p + q)%N+1;
      int r = ((LL)i * q + p)%N+1;
      if (l > r) swap(l, r);
      for (int j = Find(l); j <= r; j = Find(j)){
         a[j] = i, fa[j] = Find(j+1);
      }
   }
   for (int i = 1; i <= N; ++ i) cout << a[i] << '\n';
   return 0;
}

int youngore = thestars();

signed main() {;}

区改区查

click

具体分析详见7.29

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define int long long
#define debug
using namespace std;

const int N = 1e6+66;

int n, q;
int sum1[N], sum2[N];

inline void jia (int x, int val) {
   for (int i = x; i <= n; i += lowbit(i))
      sum1[i] += val, sum2[i] += val*x;
}
inline void qujianjia (int l, int r, int val) {jia(l, val), jia(r+1, -val);}
inline int chaxun(int x) {
   int res(0);
   for (int i = x; i; i -= lowbit(i))
      res += (x + 1)*sum1[i] - sum2[i];
   return res;
}
inline int qujianchaxun(int l, int r) {return chaxun(r) - chaxun(l-1);}

inline int thestars() {
   scanf ("%lld%lld", &n, &q);
   for (int i = 1; i <= n; ++ i) {
      int x;
      scanf ("%lld", &x);
      qujianjia(i, i , x);
   }
   for (int i = 1; i <= q; ++ i) {
      int opt, l, r, x;
      scanf ("%lld", &opt);
      if (opt&1) {
         scanf ("%lld%lld%lld", &l, &r, &x);
         qujianjia(l, r, x);
      } else {
         scanf ("%lld%lld", &l, &r);
         cout << qujianchaxun(l, r) << '\n';
      }
   }
   return 0;
}

int youngore = thestars();

signed main() {;}