8.03集训

Posted on Edited on In

上午

###第一题

其中\(n \leq 1e18\)

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e5+66;

int n;

inline int thestars() {
   cin >> n;
   int l = 1, r = sqrt(n)*2+1;
   int mo = 2*n-2;
   while (l < r) {
      int mid = (l + r)>>1;
      if (mid*(mid+1) >= mo) r = mid;
      else l = mid+1;
   }
   cout << l;
   return 0;
}

int youngore = thestars();

signed main() {;}

第二题

有百分之二十的暴力，但是需要LL

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

inline long long read() {
   long long s = 0, f = 1; char ch;
   while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
   for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
   return s * f;
}

const int N = 3e5+66, INF = 214748364000000;

int n, res = INF;
int vis[N];

struct node{int a, t, v;}yhm[N];

inline void dfs(int x, int num, int ans, int fangyu) {
   vis[x] = 1;
   if (num == n) {
      res = min(res, ans);
      return;
   }
   for (int i = 1; i <= n; ++ i) {
      if (!vis[i]) {
         int now_ans = (yhm[i].a-fangyu)*yhm[i].t+ans;
         int now_fangyu = yhm[i].v + fangyu;
         dfs(i, num+1, now_ans, now_fangyu);
         vis[i] = 0;
      }
   }
}

inline int thestars() {
   n = read();
   for (int i = 1; i <= n; ++ i)
      yhm[i].a = read(), yhm[i].t = read(), yhm[i].v = read();
   for (int i = 1; i <= n; ++ i) {
      memset (vis, 0, sizeof vis);
      dfs(i, 1, yhm[i].a*yhm[i].t, yhm[i].v);
   }
   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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

inline long long read() {
   long long s = 0, f = 1; char ch;
   while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
   for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
   return s * f;
}

const int N = 4e5+66;

int n, res, fangyu;

struct node {int a, t, v; double anzhi;}yhm[N];

inline int cmp(node x, node y){return x.anzhi > y.anzhi;}

inline int thestars() {
   cin >> n;
   for (int i = 1; i <= n; ++ i) {
      yhm[i].a = read(), yhm[i].t = read(), yhm[i].v = read();
      yhm[i].anzhi = (double)yhm[i].v/yhm[i].t;
   }
   sort (yhm+1, yhm+n+1, cmp);
   for (int i = 1; i <= n; ++ i) {
      res += (yhm[i].a - fangyu)*yhm[i].t;
      fangyu += yhm[i].v;
   }
   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
69
70
#include <bits/stdc++.h>
#define LL long long
// #define debug
using namespace std;

const int N = 25;

int n, m, q, res;
int ql[N], qr[N], qs[N], qt[N], base[N];
int dis[N][N], f[600000][N];

inline void shuru() {
   cin >> n >> m >> q;
   memset(dis, 0x3f, sizeof dis);
   for (int i = 1; i <= n; ++ i) dis[i][i] = 0;
   for (int i = 1; i <= m; ++ i) {
      int u, v, w;
      cin >> u >> v >> w;
      dis[u][v] = min(dis[u][v], w);
   }
   for (int k = 1; k <= n; ++ k)
      for (int i = 1; i <= n; ++ i)
         for (int j = 1; j <= n; ++ j)
            dis[i][j] = min(dis[i][k]+dis[k][j], dis[i][j]);
   base[0] = 1;
   for (int i = 1; i <= q; ++ i) {
      cin >> qs[i] >> qt[i] >> ql[i] >> qr[i];
      base[i] = base[i - 1]*3;
   }
   memset(f, 0x3f, sizeof f); f[0][1] = 0;
}

inline void jiejue() {
   for (int i = 1; i < base[q]; ++ i) {
      for (int j = 1; j <= n; ++ j) {
         for (int k = 1; k <= q; ++ k) {
            if (i%base[k]/base[k - 1] == 1)//qu chu
               f[i][qs[k]] = min(f[i][qs[k]],max((f[i - base[k - 1]][j] + dis[j][qs[k]]), ql[k]));
            else if (i%base[k]/base[k - 1] == 2 &&f[i - base[k - 1]][j] + dis[j][qt[k]] <= qr[k])
               f[i][qt[k]] = min(f[i][qt[k]],f[i - base[k - 1]][j] + dis[j][qt[k]]);
         }
      }
   }
}

inline void shuchu() {
   for (int i = 0; i < base[q]; ++ i) {
      for (int j = 1; j <= n; ++ j) {
         if (f[i][j] != 0x3f3f3f3f) {
            int now(0);
            for (int k = 1; k <= q; ++ k)
               if (i%base[k]/base[k - 1] == 2)
                  ++ now;
                  res = max(res, now);
         }
      }
   }
   cout << res;
}

inline int thestars() {
   shuru();
   jiejue();
   shuchu();
   return 0;
}

int youngore = thestars();

signed main() {;}

下午

rqj学长讲课

二分

click

我从来只写一种二分：

二分 
while (l < r) {
   int mid = (l+r+1)>>1;
   if (a[mid] >= x) r = mid - 1;
   else l = mid;
}

二分有好多种写法，李某东dalao说，只有百分之十的程序员能写对二分。。。

二分查找：在一个从小到大的序列中balabala...

考虑：为什么一定是从小到大？因为二分无论是查找还是二分答案都必须利用序列的有序性

有以下典型例题：

挑石头

click

"最小距离最大值"典型二分答案，刚刚在rqj奆佬的指导下，改变了二分写法，这种二分结束后\(l == r\)，\(l,r\)都是答案

给出一组\(Hack\)数据：65343245 0 0

（时隔半年，再写一次二分答案，感觉手生了好多，顿时又有些感动，我第一次学二分答案，到现在已经过去两三年了吧）

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 LL long long
#define debug
using namespace std;

const int N = 1e5+66;

int n, m; LL L, res;
int a[N];

inline int pd(int x) {
   int an(0), last(0);
   for (int i = 1; i <= n+1; ++ i)
      (a[i]-last<x)? ++ an : last = a[i];
   // printf("pd %d = %d\n", x, m >= an);
   return m>=an;
}

inline int thestars() {
   cin >> L >> n >> m;
   for (int i = 1; i <= n; ++ i) cin >> a[i];
   a[n + 1] = L;
   LL l = 1, r = L;
   while (l < r) {
      LL mid = (l+r+1)>>1;
      if (pd(mid)) l = mid;
      else r = mid - 1;
   }
   cout << l;
   return 0;
}

int youngore = thestars();

signed main() {;}

自动做题机子

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
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e5+66, inf = 1e18+250;

int n, k, res_min = -1, res_max = -1;
int a[N];

inline int pd(int x) {
   int an(0), tmp(0);
   for (int i = 1; i <= n; ++ i) {
      tmp += a[i];
      if (tmp < 0) tmp = 0;
      if (tmp >= x) ++ an, tmp = 0; 
   }
   return an;
}

inline int thestars() {
   cin >> n >> k;
   for (int i = 1; i <= n; ++ i) cin >> a[i];
      int l = 1, r = inf;
      while (l < r) {
         int mid = (l+r) >> 1;
         if (pd(mid) <= k) {
            r = mid;
            if (pd(mid) == k) res_min = mid;
      }
      else l = mid + 1;
   }
   l = 0, r = inf;
   while (l < r) {
      int mid = (l+r+1) >> 1;
      if (pd(mid) >= k) {
         l = mid;
         if (pd(mid) == k) res_max = mid;
      }
      else r = mid-1;
   }
   if (res_min == -1) puts("-1");
   else cout << res_min << ' ' << res_max;
   return 0;
}

int youngore = thestars();

signed main() {;}

注意：

如果要二分答案求一个尽量小的值：

find min 
int l = 1, r = inf;
while (l < r) {
   int mid = (l+r)>>1;
   if (pd(mid)) r = mid;
   else l = mid+1;
}

如果二分答案求一个尽量大的值：

find max 
int l = 1, r = inf;
while (l < r) {
   int mid = (l+r+1)>>1;
   if (pd(mid)) l = mid;
   else r = mid - 1;
}

扑克

click

首先，我们可以发现，\(J\) 和 \(1,2,⋯ ,n\)其实没什么区别，假如我们把 \(J\) 看成 \(0\) 号牌，那么，相当于这 \(n+1\) 种牌中任意 \(n\) 种各一张可以组成一套牌。

然后，\(n\) 种各一张可以转化为 \(n+1\) 种各拿一张再取回去一张。

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e5+66, inf = 600000000;

int n, m;
int a[N];

inline int pd(int x) {
   int an(0);
   for (int i = 0; i <= n; ++ i)
      an += max(x - a[i], 0ll);
   return x>=an;
}

inline int thestars() {
   cin >> n >> a[0];
   for (int i = 1; i <= n; ++ i)
      cin >> a[i];
   int l = 0, r = inf;
   while (l < r) {
      int mid = (l+r+1)>>1;
      if(pd(mid)) l = mid;
      else r = mid - 1;
   }
   cout << l;
   return 0;
}

int youngore = thestars();

signed main() {;}

在实数域的二分也有道题：

极品飞车

click

已知\(\begin{aligned} \sum_{i=1} ^n \dfrac {d_i} {s_i+c} = t\end{aligned}\)求\(c\)\((d_i>0, s_i+c>0)\)

其中精度要求\(1e\)\(-6\)

左边函数是单调递减的，因此可二分求解，

常用板子：

1
2
3
4
5
6
while (r - l > eps) {
    double mid = (l+r)/2;
    if (pd(mid)) l = mid;
    else r = mid;
}
其中eps = 1e-6

小技巧：\(while(cnt--)\)其中cnt = 100

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 LL long long
#define debug
using namespace std;

const int N = 1e5+66;
const double eps = 1e-6;

int n, t;
int d[N];
double s[N];

inline int thestars() {
   while (scanf ("%d%d", &n, &t) != EOF) {
      int cnt = 100, i;
      double l = 1e8, r = 1e8, res, mid;
      for (i = 1; i <= n; ++ i) {
         cin >> d[i] >> s[i];
         l = min(l, s[i]);
      }
      l = -l;
      while (cnt --) {
         mid = (l+r)/2, res = 0;
         for (int i = 1; i <= n; ++ i) res += d[i]/(s[i]+mid);
         if (res < t) r = mid;
         else l = mid;
      }
      printf ("%.9lf\n", l);
   }
   return 0;
}

int youngore = thestars();

signed main() {;}

关于分治，分而治之嘛

有一些关于主定理的东西，但是noip不考，详见click

无聊序列

click

考虑如果这个区间中存在某个数，使得它在整段区间中出现次数为1，那么对于所有包含该数的子区间，该数都出现且仅出现1次。所以只需要分治处理这个数左右两端的子区间即可；如果这个区间中不存在这样的数，那么它就是不合法的

具体：从左右两端向中间扫，扫到了就停止。这样找一次的复杂度一定是2倍较短区间长度

\(20.08.10update\)

PS:题意太操蛋了，大致意思就是说，如果在某一个区间里面，发现某一个数出现了一次，那么这个区间就叫做不无聊的序列，

比如\({1,2,3,2,3}\)尽管2,3都出现了他娘的两次，但是1出现了一次，所以这个区间还是他娘的不无聊序列

那我们就记这个数上一次出现的位置，和下一次出现的位置，特判\(pres[linr] \; < \; l\) && \(nex[linr] \; > \; r\)就好了

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 2e5+66;

int a[N], pres[N], nex[N];
map<int, int>mp;

inline int work(int l, int r) {
   if (l == r || l > r) return 1;
   int linl = l, linr = r;
   while (linl < linr) {
      -- linr;
      if (pres[linr] < l && nex[linr] > r)
         if (work(l, linr - 1) && work(linr + 1, r))
            return 1;
      ++ linl;
      if (pres[linl] < l && nex[linl] > r)
         if (work(l, linl - 1) && work(linl + 1, r))
            return 1;
   }
   return 0;
}

inline int thestars() {
   int T, i, j, n;
   scanf ("%d", &T);
   while (T --> 0) {
      mp.clear();
      scanf ("%d", &n);
      for (i = 1; i <= n; ++ i) {
         scanf ("%d", &a[i]);
         pres[i] = 0, nex[i] = n+1;
      }
      for (int i = 1; i <= n; ++ i) {
         if (mp.find(a[i]) != mp.end()) {
            pres[i] = mp[a[i]];
            nex[mp[a[i]]] = i;
         }
         mp[a[i]] = i;
      }
      if (work(1, n)) puts("non-boring");
      else puts("boring");
   }
   return 0;
}

int youngore = thestars();

signed main() {;}

关于贪心嘛，一般都不是正解，但是应用面十分的广泛

线段覆盖

click

右端点排个序就好了，证明也很简单，从左往右放，右端点越小，妨碍越小

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66;

int n, res;

struct node {int s, t;}a[N];
inline int cmp(node x, node y){return x.t < y.t;}

inline int thestars() {
   scanf ("%d", &n);
   for (int i = 1; i <= n; ++ i)
      scanf ("%d%d", &a[i].s, &a[i].t);
   sort(a + 1, a + n + 1, cmp);
   int end = a[1].t; res = 1;
   for (int i = 2; i <= n; ++ i) {
      if (end <= a[i].s) {
         ++ res, end = a[i].t;
      }
   }
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

国王游戏

click

对于相邻的\(i\)和\(j\)，令\(i,j\) 比\(j,i\) 更优，

则有\(max(\dfrac 1 {b[i]},\dfrac {a[i]}{b[j]})<max(\dfrac 1 {b[j]}, \dfrac{a[j]} {b[i]})\)

又因为\(\dfrac {a[i]}{b[j]}>\dfrac 1 {b[j]}\)，\(\dfrac{a[j]} {b[i]}>\dfrac 1 {b[i]}\)，

因此必须有\(\dfrac{a[j]} {b[i]} > \dfrac {a[i]}{b[j]}>\)化简后得\(a[i]*b[i]<a[j]*b[j]\)

于是贪心策略就是按照\(a*b\)从小到大排序，之后计算即可

代码没写

护花

click

一眼贪心，随便推一下就可以得到\(\dfrac {t[i]} {d[i]}\)

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 = 1e6+66;

int n, sum[N];

struct node {int t, d; double paixu;}a[N];

inline int cmp(node x, node y) {return x.paixu < y.paixu;}

inline int thestars() {
   cin >> n;
   for (int i = 1; i <= n; ++ i) {
      cin >> a[i].t >> a[i].d;
      a[i].paixu = (double)a[i].t/a[i].d;
   }
   sort(a + 1, a + n + 1, cmp);
   int res = 0, shijian = 0;
   for (int i = 2; i <= n; ++ i) {
      shijian += a[i - 1].t*2;
      res += shijian*a[i].d;
   }
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

贪心也经常与堆一起用

合并果子

click

设有a、b、c，令a+b+a+b+c 是所有合并方案中最小的，推出a<c且b<c

也可以用于“反悔“

HUR-Warehouse Store

click

我们肯定是维护一个堆，如果发现当前的客户满足不了了，就尝试踢掉原来的最大的一个

贪心证明：是当前的剩余尽量多，保证后面可以满足更多客户

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 3e5+66;

int n, num;
int a[N], b[N], v[N];

priority_queue<pair<int, int> >q;

inline int thestars() {
   scanf ("%lld", &n);
   for (int i = 1; i <= n; ++ i) scanf ("%lld", &a[i]);
   for (int i = 1; i <= n; ++ i) scanf ("%lld", &b[i]);
   int res = 0;
   for (int i = 1; i <= n; ++ i) {
      res += a[i];
      if (res >= b[i]) {
         res -= b[i];
         q.push(make_pair(b[i], i));
         v[i] = 1;
      } else {
         if (!q.empty() && q.top().first > b[i]) {
            int t = q.top().second; q.pop();
            res = res + b[t] - b[i];
            q.push(make_pair(b[i], i));
            v[t] = 0, v[i] = 1;
         }
      }
   }
   for (int i = 1; i <= n; ++ i) if (v[i]) ++ num;
   printf ("%lld\n", num);
   for (int i = 1; i <= n; ++ i) 
      if (v[i])
         cout << i << ' ';
   return 0;
}

int youngore = thestars();

signed main() {;}

建筑抢修

click

可以推出按\(second\)从小到大排序，排完序之后和上个题一摸一样啊

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e6+66;

priority_queue<int>q;

int n, num;

struct node {int s, t;}a[N];
inline int cmp (node x, node y) {return x.t < y.t;}

inline int thestars() {
   scanf ("%lld", &n);
   for (int i = 1; i <= n; ++ i)
      scanf ("%lld%lld", &a[i].s, &a[i].t);
   sort(a + 1, a + n + 1, cmp);
   int res = 0;
   for (int i = 1; i <= n; ++ i) {
      if (res + a[i].s <= a[i].t) {
         res += a[i].s;
         q.push(a[i].s);
         ++ num;
      } else if (!q.empty() && q.top() > a[i].s) {//为什么不写成res - q.top() + a[i].s <= a[i].t，留给读者自己思考
         res = res - q.top() + a[i].s; q.pop();
         q.push(a[i].s);
      }
   }
   cout << num;
   return 0;
}

int youngore = thestars();

signed main() {;}

合并果子nb版本

click

考虑一个队列存排序结果（当然是桶排），另一个存合并结果，每次取出队首，这题需要快读和LL

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e7+66;

queue<int>q1, q2;

int n, res;
int a[N], b[N>>6];

inline int read() {
   int x = 0, f = 1; char ch;
   while (! isdigit(ch = getchar())) (ch == '-') && (f = -f);
   for (x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
   return x * f;
}

inline int Find() {
   int x;
   if ((q1.front() < q2.front() && !q1.empty()) || q2.empty()) {
      x = q1.front();
      q1.pop();
   } else {
      x = q2.front();
      q2.pop();
   }
   return x;
}

inline int thestars() {
   n = read();
   for (int i = 1; i <= n; ++ i) {
      a[i] = read();
      ++ b[a[i]];
   }
   for (int i = 1; i <= N>>6; ++ i) {
      while (b[i]) {
         -- b[i];
         q1.push(i);
      }
   }
   for (int i = 1; i < n; ++ i) {
      int x = Find();
      int y = Find();
      q2.push(x + y);
      res += x + y;
   }
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

还有一类比较难的数位贪心，整体思路是需要从高位到低位贪心，证明显然。这种题目常见与二进制位运算中

起床困难综合症

click

位运算的主要特点是不用进位

\(x_0\)的第k位应该填1而不是零，当且仅当满足一下两个条件： 1.用已经填好的最高位的数加上当前的\(1<<k\)不超过m 2.(lyd原话：)用每个参数的第k位参加运算，若初值为1，则n次运算之后结果为1 若初值为0，则n次运算之后为0

其实我现在还是不太明白第二点在表达什么...

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 LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66;

int n, m;
pair<string, int>a[N];

inline int calc(int bit, int now) {
   for (int i = 1; i <= n; ++ i) {
      int x = (a[i].second>>bit)&1;
      if (a[i].first == "AND") now &= x;
      else if (a[i].first == "OR") now |= x;
      else now ^= x;
   }
   return now;
}

inline int thestars() {
   cin >> n >> m;
   for (int i = 1; i <= n; ++ i) {
      char ch[5]; int x;
      scanf ("%s%d", ch, &x);
      a[i] = make_pair(ch, x);
   }
   int val = 0, ans = 0;
   for (int bit = 30; bit >= 0; -- bit) {
      int res0 = calc(bit, 0);
      int res1 = calc(bit, 1);
      if (val + (1<<bit) <= m && res0 < res1) 
         val += (1<<bit), ans += res1 << bit;
      else ans += res0 << bit;
   }
   cout << ans;
   return 0;
}

int youngore = thestars();

signed main() {;}

or xor

click

不会….

晚上

补坑 写博客 做题