8.05集训

Posted on Edited on In

上午

考试 ### 第一题

click

考试的时候这个题的数据比较大，\(n \leq 2e6\)

考虑枚举圆的直径，搞一个双指针来操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 3e6+66;

int n, a[N], sum[N], res;

inline int thestars() {
   scanf ("%lld",&n);
   for (int i = 1; i <= n; ++ i) {
      scanf ("%lld",a+i);
      sum[i] = sum[i - 1] + a[i];
   }
   int yhm = sum[n]/2, num;
   for (int i = 1; i <= n; ++ i) {
      num = i;
      if (sum[i] > yhm) break;
   }
   int top = num, kaishi = 0;
   while (kaishi < top || num < n) {
      while (sum[num] - sum[kaishi] > yhm) ++ kaishi;
      if (kaishi == top && num == n) break;
      if (sum[num] - sum[kaishi] == yhm) ++ res;
      ++ num;
   }
   if(res == 0 || sum[n] % 2 == 1) cout<<0<<"\n";
   else cout << res*(res - 1)/2;
   return 0;
}

int youngore = thestars();

signed main() {;}

###第二题

click

状态：\(f[i][j][1/0]\)表示对于\(i\)到\(j\)这段区间的作业还没有提交，下一次将提交\(i(0)\)或\(j(1)\)处的作业

转移：四个式子，\(f[i][j][0]\)与\(f[i][j][1]\)分别可以由左右两边的\(i-1\)和\(j-1\)转移，显然：

\(f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0]+a[i].x-a[i - 1].x, a[i].t))\)

\(f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1]+a[j + 1].x-a[i].x, a[i].t))\)

\(f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0]+a[j].x-a[i - 1].x, a[j].t))\)

\(f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1]+a[j + 1].x-a[j].x, a[j].t))\)

结果：\(min(f[i][i][0], f[i][i][1])+abs(a[c].x-b)\)

给出AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66;

int c, h, b, res = 1<<30;
int f[1250][1250][6];
struct node {int x, t;}a[N];

inline int cmp(node s, node t) {return s.x < t.x;}

inline int thestars() {
   scanf ("%d%d%d", &c, &h, &b);
   for (int i = 1; i <= c; ++ i) cin >> a[i].x >> a[i].t;
   sort(a+1, a+c+1, cmp);
   memset(f, 0x7f, sizeof f);
   f[1][c][0] = max(a[1].x, a[1].t), f[1][c][1] = max(a[c].x, a[c].t);
   for (int i = 1; i <= c; ++ i) {
      for (int j = c; j >= i; -- j) {
         f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0]+a[i].x-a[i - 1].x, a[i].t));
         f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1]+a[j + 1].x-a[i].x, a[i].t));
         f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0]+a[j].x-a[i - 1].x, a[j].t));
         f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1]+a[j + 1].x-a[j].x, a[j].t));
      }
   }
   for (int i = 1; i <= c; ++ i) res = min(res, min(f[i][i][1], f[i][i][0])+abs(a[i].x-b));
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

第三题

恶心程度显然....

给出自己的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 250;

int ta, tb, tc;
int T;

struct node {
   int x, y;
   node(){};
   node(int X, int Y){x = X, y = Y;}
   bool operator!=(const node a) const {return x != a.x || y != a.y;}
   bool operator<(const node a) const {return x == a.x?y<a.y:x<a.x;}
}a[N], b[N<<4], c[N];

int dx[] = {1, 1, 1, 0, -1, -1, -1, 0};
int dy[] = {1, 0, -1, -1, -1, 0, 1, 1};

inline void work() {
   int i, j;
   tb = 0;
   for (i = 1; i <= ta; ++ i) b[++ tb] = a[i];
   for (i = 1; i <= ta; ++ i)
      for (j = 0; j < 8; ++ j)
         b[++ tb] = node(a[i].x + dx[j], a[i].y + dy[j]);
   sort(b + 1, b + tb + 1);
   j = tb, tb = 1;
   for (i = 2; i <= j; ++ i)
      if (b[i] != b[i - 1])
         b[++ tb] = b[i];
}

inline void solve() {
   int i, j, t;
   tc = 0;
   for (i = 1; i <= tb; ++ i) {
      t = 0;
      for(int j = 0;j < 8;j ++){
      if (!(a[ta] < node(b[i].x + dx[j] , b[i].y + dy[j]) 
	|| *lower_bound(a + 1 , a + ta + 1 , node(b[i].x + dx[j] , b[i].y + dy[j]))
	 != node(b[i].x + dx[j] , b[i].y + dy[j])))
         t ++;
      }
      if (t == 3 || (t == 2 && !(a[ta] < b[i] || *lower_bound(a + 1 , a + ta + 1 , b[i]) != b[i])))
         c[++tc] = b[i];
   }
   sort(c + 1, c + tc + 1);
   for (i = 1; i <= tc; ++ i) a[i] = c[i];
   ta = tc;
}

inline int thestars() {
   cin >> ta >> T;
   for (int i = 1; i <= ta; ++ i) cin >> a[i].x >> a[i].y;
   sort(a + 1, a + ta + 1);
   while (T --) work(), solve();
   printf("%d\n", ta);
   for (int i = 1; i <= ta; ++ i)
      printf ("%d %d\n", a[i].x, a[i].y);
   return 0;
}

int youngore = thestars();

signed main() {;}

#下午

讲课，数论与概率期望

关于数学的知识比较杂，首先是一些前置知识

%

\((a+b)\;mod\;p = (a\;mod\;p\;+b\;mod\;p)\;mod\;p\)

\((a*b)\;mod\;p = (a\;mod\;p\;*b\;mod\;p)\;mod\;p\)

\(a\;mod\;p=b\;mod\;p\Longleftrightarrow\;p\mid(a-b)\)

快速幂

ksm_递归 
#define int long long
inline int ksm(int a, int b, int mod) {
   if (!b) return a%mod;
   if (b&1) return a*ksm(a, b-1, mod);
   int tmp = ksm(a, (b>>1), mod)%mod;
   return tmp*tmp%mod;
}
ksm_for 
inline int ksm(int a, int b, int mod) {
   int res = 1;
   while(b) {
      if (b&1) res = res*a%mod;
      a = a*a%mod;
      b >>= 1;
   }
   return res;
}

基本算术定理

质因子分解的办法：

  • 试除法：枚举
  • 试除法的优化（埃拉托色尼筛法）：预处理指数，枚举倍数
  • 欧拉筛：在埃氏筛的基础上进行优化，线性筛的基础上记录下每个数的最小质因子

给出埃氏筛代码：

埃氏筛 
memset (v, 1, sizeof v);
v[1] = 0;
for (int i = 2; i <= N; ++ i) {
   if (v[i]) prime[++ cnt] = i;
   for (int j = 1; j <= cnt && i*prime[j] <= N; ++ j)
      v[i*prime[j]] = 0;
}

给出欧拉筛代码：

欧拉筛 
memset (v, 1, sizeof v);
v[1] = 0;
for (int i = 2; i <= N; ++ i) {
   if (v[i]) prime[++ cnt] = i;
   for (int j = 1; j <= cnt && i*prime[j] <= N; ++ j) {
      v[i*prime[j]] = 0;
      if (i%prime[j] == 0) break;
   }
}

考虑欧拉筛是如何优化的？在埃氏筛中，每一个数字可能会被多次筛到，浪费了时间复杂度，而欧拉筛中每个只会被筛到一次，且是由他的最小质因子筛出来的

考虑如下：

\(i = 2\)筛出\(4\)，\(i =3\)筛出\(6,9\)，\(i=4\)筛出\(8\)，\(i=5\)筛出\(10,15,25\)，\(i=6\)筛出\(12\)

显然每个被\(i\)筛出的数的最小质因子都是\(i\)

枚举约数的办法：

  • 1.试除法：枚举\(1\)到\(\sqrt n\)
  • 2.筛法：预处理，枚举\(1\)到\(n\)的数，再枚举其倍数，则这个数是倍数的约数，可以用\(vector\)存起来，由调和级数可知复杂度为\(O(n*ln_n)\)

公约数与公倍数

设\(A=p^{a_1}_1p^{a_2}_2...p^{a_n}_n,B = p^{b_1}_1p^{b_2}_2...p^{b_n}_n\)

因此：

\(gcd(A,B) = p^{min(a_1,b_1)}_1p^{min(a_2,b_2)}_2...p^{min(a_n,b_n)}_n\)

$ lcm(A, B) = p^{max(a_1,b_1)}_1p^{max(a_2,b_2)}_2...p^{max(a_n,b_n)}_n$

\(gcd(A,B)*lcm(A,B) = A*B\)

GCD 
inline int gcd(int a, int b){return !b?a:gcd(b,a%b);}

下面是一些例题：

核聚变反应程度

click

巧题，次大公约数一定是最大公约数除掉最小的质因数

甩一个题解

给出AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e5+66;

int n, len, a[N];
vector<int>q;

inline int gcd(int a, int b){return !b?a:gcd(b,a%b);}

inline int thestars() {
   scanf ("%lld", &n);
   for (int i = 1; i <= n; ++ i) scanf ("%lld", &a[i]);
   int now = a[1];
   for (int i = 2; i * i <= now; ++ i) {
      if (now%i == 0) {
         while (now%i == 0) now /= i;
	 q.push_back(i);
         ++ len;
      }
   }
   if (now > 1) q.push_back(now), ++ len;
   for (int i = 1; i <= n; ++ i) {
      int tmp = gcd(a[1], a[i]);
      if (tmp == 1) printf ("-1 ");
      else {
         for (int i = 0; i < len; ++ i) {
            if (tmp%q[i] == 0) {
               printf ("%lld ", tmp/q[i]);
                  break;
            }
         }
      }
   }
   return 0;
}

int youngore = thestars();

signed main() {;}

Divisors

click

开桶记录每个数字出现多少次

其中\((1,4)(4,1)\)算两次

给出AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 3e6+250;

int n, res, maxn;
int a[N], b[N];

inline int thestars() {
   scanf ("%d", &n);
   for (int i = 1; i <= n; ++ i) {
      scanf ("%d", &a[i]);
      ++ b[a[i]];
      maxn = max(a[i], maxn);
   }
   for (int i = 1; i <= maxn; ++ i) {
      if (b[i]) {
         res += b[i]*(b[i]-1);
         for (int j = i<<1; j <= maxn; j += i)
            if (b[j])
            res += b[i]*b[j];
      }
   }
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

扩展欧几里得

是求方程\(𝑎𝑥+𝑏𝑦=gcd(𝑎,𝑏)\)的一组整数解的一种算法

对于一个方程：\(a*x+b*y=gcd(a,b)\)，我们有如下推导

设有式子\(a*x_1+b*y_1=gcd(a,b)\)

根据欧几里得算法可得：\(b*x_2+(a\%b)*y_2=gcd(b,a\%b)\)

观察\(b*x_2+(a\%b)*y_2\)，这个式子,我们可以将\((a\%b)\)写作\((a-\lfloor\frac{a}{b}\rfloor*b)\)

将括号打开常数\(a,b\)合并,合并之后的结果为 \(a*y_2+b*(x_2-\lfloor\frac{a}{b}\rfloor*y_2)\)

由于欧几里得算法的原理\(gcd(a,b)==gcd(b,a\%b)\)

我们将两式子联立,对比系数即可得到\(x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor*y_2\)

附通解的求法：设得到的特殊解为\(x = x_0, y = y_0\)

则通解为\(x = x_0+\dfrac {b} {gcd(a,b)}*t, y = y_0 - \dfrac{a}{gcd(a, b)}*t\)，其中\(t\)为正整数

考虑证明。

给出代码：

EXgcd 
inline void calc (int a, int b, int &x, int &y) {
   if (!b) x = 1, y = 666;
   else calc (b, a%b, y, x), y -= a/b*x;
}

同余方程

click

原式子\(ax \equiv 1 \pmod b\Longleftrightarrow ax+by=1\)

题目保证有解，根据裴蜀定理可以知道\(gcd(a,b) =1\)，直接用\(EXgcd\)就可以

给出AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, b, x, y;

inline void calc (int a, int b, int &x, int &y) {
   if (!b) x = 1, y = 666;
   else calc (b, a%b, y, x); y -= a/b*x;
}

main () {
   cin >> a >> b;
   calc (a, b, x, y);
   x = (x%b+b)%b;
   cout << x;
   return 0;
}
/*
1121324517 2000000000
*/

PS:y尽量从0开始，因为从0开始的话不容易爆\(int\)

乘法逆元

click

若\(a*x\equiv 1 (mod\;b )\) 并且\(a ,b\) 互质.我们就称\(x\) 为 \(a\) 在\(mod \;b\)意义下的乘法逆元,记为\(a^{-1}\)

求逆元的click

  • 1.扩展欧几里得
  • 2.费马小定理
  • 3.线性求逆元

仪仗队

把左下角看作$(0,0) \(，右上角看作\)(n-1,n-1)$ ，那么能看到当且仅当横纵坐标互质

然后我们手动盖住上半部分，但是得漏出对角线，答案就是\(1 + \sum_\limits{i=1}^{n-1}\phi(i)\)，又因为上半部分对称相等，所以重复算了\(1\)，因此要减去\(1\),又因为左右两边的\(2\)没有算，因此要加2

所以总答案为：\(2*\sum_\limits{i=1}^{n-1}\phi(i) + 1\)

沙拉公主的困惑

click

由于\(N!\) 是\(M!\) 的倍数，而若\(a\) 与\(b\) 互质则\(a+b\) 与\(b\) 互质，故\(N!\) 中每$M! \(个便有\)φ(M!)$ 个与$M! $互质

然后答案呼之欲出：

\(\dfrac {N!} {M!}* \phi(M!) = \dfrac {N!} {M!}*M!*\sum_\limits {p_i \mid M!} \dfrac {p_i-1} {p_i} = N!*\sum_\limits{p_i<=M} \dfrac{p_i-1}{p_i}\)

然后手玩逆元

欧拉定理

Longge问题

click

枚举最大公约数为d ，则数目就是\(\dfrac N d\) ，答案为\(\sum_\limits{d\mid N}d*\phi(\dfrac N d)\)

因此枚举约数再求欧拉，时间复杂度大概是O(算不出来但是能过)

复杂度\(O(玄)\)

(我不会…..)

接下来是矩阵乘法

斐波那契数列

click

主要是我不会打矩形....

路径计数

矩阵的\(k\)次方就是答案

晚上

写博客补坑