8.07集训

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

上午

考试 ### 第一题

\(T\)次询问，每次询问给定\(n\)，求 \(\sum_\limits{i=1}^n \lfloor \dfrac n i \rfloor\)

上来看到\(2s\;1GB\)，直接准备打表…..

于是我开始手算…..

\(n = 1get1,n=2get3,n=3get5,n=4get8,n=5get10,n=6get14,n=7get16,\)

\(n=8get20,n=9get23\)

我注意到，\(n\)为奇数的时候，比她小的偶数的\(ans_{i-1}\)就为\(ans_i-2\)

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

可偏偏\(8,9\)就没有满足这个规律！

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

\(1e7*1e7/1e9\)需要三个多小时

\(1e6*1e6/1e9\)需要四分钟

但是\(1e7\)太诱人了，满分太诱人了，我又考虑各种优化打表程序

直到最后放弃打表\(1e7\)，但是为了\(1e6\)的打表程序，我还搞了搞常数优化

\(45mins \;later\)

我注意到\(n =8get20\)，我仍旧以为是我手算错了，还在草稿纸上，用红笔改为了\(21\)

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

（我的程序是\(7000多KB\)）

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

整除分块只有四十分

考虑\(\lfloor \dfrac ni\rfloor\)的含义：\(1\text~N\)中\(i\)的倍数的数目

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

所求转化为\(\sum_\limits{i=1}^nd(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.小姑娘直接摸出白球，概率\(\dfrac i {i+j}\)
2.小姑娘运气不好，摸到了黑球，小伙子摸出了黑球，扔了一个白球
这时候概率显然：\(\dfrac i {i+j} \times \dfrac{j - 1} {i+j-1} \times\dfrac i {i+j-2} \times f[i-1][j-2]\)
3.小姑娘还是摸出黑球，小伙子摸出了一个黑球，扔掉了一个黑球
这时候概率显然：\(\dfrac i {i+j}\times \dfrac {j-1}{i+j-1} \times \dfrac {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 1e6, 1 \leq m \leq 100, 1 \leq k \leq 500\)

我觉得是一个很好的题，数据给出\(m =1\)，部分\(pts\)的做法，可以很好的引申到正解

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

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

那么我们可以\(O(1)\)求出\(calc(n,x) = (n\%x)\times sum(\lfloor\dfrac nx \rfloor+1) + (x-n\%x)\times sum(\lfloor\dfrac nx \rfloor)\)

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

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

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

则有\(f[i][j]=Min(f[i][j], f[i-1][t]+calc(cnt[i],j-t+1))\)

其中\(cnt[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

一句话题意：给你一些区间，让你在一些区间染色，输出最后的染色结果，数据量\(1e6\)

正着来貌似不太容易，我们尝试想做概率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() {;}