2019牛客暑期多校训练营第一场

牛客多校还是挺难的。三个人各种白给。

题目链接：https://ac.nowcoder.com/acm/contest/881#question

A：

题意就是找到两个数组第一次出现极小值位置不一样的情况。拿样例来说：a={3,1,5,2,4}, b={5,2,4,3,1}。a数组在第四个位置出现了极小值，而b数组在第四个位置并没有出现极小值。

故用两个单调递增栈来维护极小值位置最方便。只要两个栈弹出数量不一样就说明出现了极小值位置不一的情况。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int maxn = 1e5 + 10;
22 int n, a[maxn], b[maxn];
23 stack<int>s1, s2;
24 
25 int main() {
26     a[0] = b[0] = 0;
27     while (~scanf("%d", &n)) {
28         rep1(i, 1, n) scanf("%d", &a[i]);
29         rep1(i, 1, n) scanf("%d", &b[i]);
30         while (!s1.empty()) s1.pop();
31         while (!s2.empty()) s2.pop();
32         s1.push(1); s2.push(1);
33         int p;
34         for (p = 2; p <= n; p++) {
35             int num = 0;
36             while (!s1.empty() && a[p] < a[s1.top()]) num++, s1.pop();
37             while (!s2.empty() && b[p] < b[s2.top()]) num--, s2.pop();
38             if (num) break;
39             s1.push(p); s2.push(p);
40         }
41         printf("%d
", p - 1);
42     }
43     return 0;
44 }

View Code

B：

看到一个极好的题解：https://www.cnblogs.com/Dillonh/p/11209476.html

C：

很显然是个约束优化问题，必然是拉格朗日乘数法。

但是官方题解里有个很秀的地方：跟平常的不同，把函数phi(x,y)前面的系数λ变为2λ，从而把原式化为一个每一项为完全平方项的式子再求和。对于每一项，单独求出最值即可。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 int n, m;
22 
23 int main() {
24     while (~scanf("%d%d", &n, &m)) {
25         int a[n], s1 = 0; ll s2 = 0;
26         rep0(i, 0, n) {
27             scanf("%d", &a[i]);
28             s2 += (ll)a[i] * a[i];
29         }
30         sort(a, a + n, greater<int>());
31         pair<ll, ll> ans(0, 1);
32         rep0(i, 0, n) {
33             s1 += a[i], s2 -= (ll)a[i] * a[i];
34             if (i + 1 == n || (s1 - m) >= (i + 1LL)*a[i + 1]) {
35                 auto tmp = mp((ll)(s1 - m) * (s1 - m) + (i + 1LL) * s2, i + 1);
36                 if (tmp.first * ans.second > ans.first * tmp.second)
37                     ans = tmp;
38             }
39         }
40         ans.second *= (ll)m * m;
41         auto g = __gcd(ans.first, ans.second);
42         if (ans.first % ans.second == 0) printf("%lld
", ans.first / ans.second);
43         else printf("%lld/%lld
", ans.first / g, ans.second / g);
44     }
45     return 0;
46 }

View Code

还有一个用贪心做的不错的做法：https://www.cnblogs.com/Dillonh/p/11215846.html

D：

神仙题。可以看wzk大佬的博客：https://blog.csdn.net/nickwzk/article/details/96472362

给出std。

 1 #include <bits/stdc++.h>
 2 
 3 static const int MOD = 1e9 + 7;
 4 
 5 void dfs(std::vector<int> &count, const std::vector<int> &a, int i, int x,
 6          int p) {
 7   if (i < static_cast<int>(a.size())) {
 8     dfs(count, a, i + 1, x, p);
 9     dfs(count, a, i + 1, x ^ a[i], -p);
10   } else {
11     count[x] += p;
12   }
13 }
14 
15 int main() {
16   int n, m, k;
17   while (scanf("%d%d%d", &n, &m, &k) == 3) {
18     std::vector<int> count(1 << k);
19     for (int i = 0; i < n; ++i) {
20       std::vector<int> a(m);
21       for (int j = 0; j < m; ++j) {
22         scanf("%d", &a[j]);
23       }
24       dfs(count, a, 0, 0, 1);
25     }
26     for (int i = 0; i < k; ++i) {
27       for (int msk = 0; msk < 1 << k; ++msk) {
28         if (~msk >> i & 1) {
29           auto &x0 = count[msk];
30           auto &x1 = count[msk | 1 << i];
31           int tmp = x0 - x1;
32           x0 += x1;
33           x1 = tmp;
34         }
35       }
36     }
37     int inv = 1 << m;
38     int result = 0;
39     int three = 1;
40     for (int msk = 0; msk < 1 << k; ++ msk) {
41       result ^= 1LL * three * (count[msk] / inv) % MOD;
42       three = 3LL * three % MOD;
43     }
44     printf("%d
", result);
45   }
46 }

View Code

E：

可以用组合数然后去重的做法。但是如何去重是个难点。在牛客看到个大佬的组合数天秀做法：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int mod=1e9+7;
 4 const int N=1e6+10;
 5 typedef long long ll;
 6 ll fac[N],inv_fac[N];
 7 void exgcd(ll a, int b, ll& d, ll& x, ll& y)
 8 {
 9     if(!b) d = a, x = 1, y = 0;
10     else exgcd(b, a%b, d, y, x), y -= x*(a/b);
11 }
12 ll C(int n,int m,int p)
13 {
14     if(m>n) return 0;
15     if(m>n-m) m=n-m;
16     ll ans=1,tmp=1,g,x,y;
17     for(int i=0;i<m;i++)ans=ans*(n-i)%p, tmp=tmp*(i+1)%p;
18     exgcd(tmp,p,g,x,y);
19     return (ans*(x%p)%p+p)%p;
20 }
21 int main()
22 {
23     int n,m;
24     while (~scanf("%d%d",&n,&m))
25     {
26         ll tmp1=0,tmp2=0;
27         if(n!=0) tmp1=C(2*(n+m),n-1,mod);
28         if(m!=0) tmp2=C(2*(n+m),m-1,mod);
29         ll tmp=C(2*(m+n),n+m,mod);
30         ll ans=((tmp-tmp1-tmp2)%mod+mod)%mod;
31         printf("%lld
",ans); 
32     }
33     return 0;
34 }

code via. tqlwsl

解释可以看这篇博客：https://blog.csdn.net/qq_39239844/article/details/96475068

比较正常的做法是贪心或者dp。

贪心做法：如果字符串中只有n个AB，合法情况是每个B前面要有至少1个A；若除了AB之外还有m个BA，那每个B前面可以有超过n个A，但第一个B前面必须有至少一个A；B与后面A构成BA的时候，相当于A后面的第一个B前面少了一个A。这种做法不是很好写。

dp做法：设二维数组dp[i][j]，第一维是A的个数，第二维是B的个数。dp[i][j]代表合法方案。dp[0][0]=1。

直觉有dp[i][j]=dp[i-1][j]+dp[i][j-1]，但是要对i和j加以限制。只有 i < n || (i - n) < j 的情况才可以放A，只有j < m || (j - m ) < i 的情况才可以放B。这个条件可以从上面的贪心得到。

答案自然就是dp[n+m][n+m]。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int maxn = 2e3 + 10;
22 const int mod = 1e9 + 7;
23 int n, m;
24 ll dp[maxn][maxn];
25 
26 int main() {
27     while (~scanf("%d%d", &n, &m)) {
28         // init
29         rep1(i, 0, n + m) {
30             rep1(j, 0, n + m) {
31                 dp[i][j] = 0;
32             }
33         }
34         dp[0][0] = 1;
35         rep1(i, 0, n + m) {
36             rep1(j, 0, n + m) {
37                 if (i < n || (i - n) < j) // put A
38                     dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
39                 if (j < m || (j - m) < i) // put B
40                     dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
41             }
42         }
43         printf("%lld
", dp[n + m][n + m]);
44     }
45     return 0;
46 }

View Code

F：

样例给了三组毫无作用的数据，恶意满满。

最快的做法是设一个大的三角形(0,0),(10000,0),(0,10000)，枚举三角形内所有的整点并维护最终答案。然后计算答案和三角形面积比例，算出来正好逼近11/2。

实际上11/2这个数很难看出来。计算答案和三角形面积的两倍(设为S。这个用叉乘就可以做到，不仅方便而且比海伦公式精度高，海伦公式会爆long long)的比例，得到21.×××××，再试一下输出10.5S和11S，而答案正好就是11S。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 ll p1, q1, p2, q2, p3, q3;
22 
23 int main() {
24     while (~scanf("%lld%lld%lld%lld%lld%lld", &p1, &q1, &p2, &q2, &p3, &q3)) {
25         pair<ll, ll> x = mp(p2 - p1, q2 - q1), y = mp(p3 - p1, q3 - q1);
26         ll ans = x.first * y.second - y.first * x.second;
27         printf("%lld
", (ll)abs(ans) * 11);
28     }
29     return 0;
30 }

View Code

G：

神仙题。

  1 #include <bits/stdc++.h>
  2 
  3 struct Solver {
  4   using Hash = uint64_t;
  5   static const Hash MAGIC = 1e6 + 3;
  6 
  7   Solver(int n)
  8       : n(n), bsize(get_sqrt(n)), event(n, -1), power(bsize + 1),
  9         hashes(n + 1, std::vector<Hash *>(bsize)) {
 10     std::vector<int> a(n);
 11     for (int i = 0; i < n; ++i) {
 12       scanf("%d", &a[i]);
 13     }
 14     power[0] = 1;
 15     for (int i = 1; i <= bsize; ++i) {
 16       power[i] = power[i - 1] * MAGIC;
 17     }
 18     blocks.emplace_back(bsize + 1);
 19     for (int i = 0; i < bsize; ++i) {
 20       hashes[n][i] = blocks.back().data();
 21     }
 22     {
 23       blocks.emplace_back(bsize + 1);
 24       auto block = blocks.back().data();
 25       block[n % bsize] = -1;
 26       for (int i = bsize - 1; i >= 0; --i) {
 27         block[i] += block[i + 1] * MAGIC;
 28       }
 29       hashes[n][n / bsize] = block;
 30     }
 31     {
 32       std::vector<int> next(n + 1, n);
 33       for (int i = n - 1; i >= 0; --i) {
 34         hashes[i] = hashes[i + 1];
 35         int j = next[a[i]];
 36         next[a[i]] = i;
 37         if (j < n) {
 38           event[j] = i;
 39           blocks.emplace_back(bsize + 1);
 40           int block_id = j / bsize;
 41           int base = block_id * bsize;
 42           auto block = blocks.back().data();
 43           Hash hh = 0;
 44           for (int k = bsize - 1; k >= 0; --k) {
 45             hh = hh * MAGIC + char_at(i, base + k);
 46             block[k] = hh;
 47           }
 48           hashes[i][block_id] = block;
 49         }
 50       }
 51     }
 52 
 53     std::vector<int> order(n);
 54     std::iota(order.begin(), order.end(), 0);
 55     std::sort(order.begin(), order.end(), [this](int x, int y) {
 56       int length = get_lcp(x, y);
 57       return char_at(x, x + length) < char_at(y, y + length);
 58     });
 59     long long result = n * (n + 1LL) / 2;
 60     for (int i = 1; i < n; ++i) {
 61       result -= get_lcp(order[i - 1], order[i]);
 62     }
 63     std::cout << result << std::endl;
 64   }
 65 
 66   static inline int get_sqrt(int n) {
 67     int b = 0;
 68     while (b * b <= n) {
 69       b++;
 70     }
 71     return b;
 72   }
 73 
 74   int char_at(int s, int i) const {
 75     if (i >= n) {
 76       return -1;
 77     }
 78     return s <= event[i] ? i - event[i] : 0;
 79   }
 80 
 81   int get_LCP(int x, int y) const {
 82     if (x == y) {
 83       return n - x;
 84     }
 85     int length = 0;
 86     while (char_at(x, x + length) == char_at(y, y + length)) {
 87       length++;
 88     }
 89     return length;
 90   }
 91 
 92   int get_lcp(int x, int y) const {
 93     int length = 0;
 94     if (x % bsize > y % bsize) {
 95       std::swap(x, y);
 96     }
 97     auto &hashx = hashes[x];
 98     auto &hashy = hashes[y];
 99     int xi = x / bsize;
100     int yi = y / bsize;
101     int xr = x % bsize;
102     int yr = y % bsize;
103     if (xr == yr) {
104       if (hashx[xi][xr] == hashy[yi][yr]) {
105         length += bsize - xr;
106         xi++, yi++;
107         xr = yr = 0;
108         while (hashx[xi][0] == hashy[yi][0]) {
109           xi++, yi++;
110           length += bsize;
111         }
112       }
113     } else {
114       while (true) {
115         if (hashx[xi][xr] - power[bsize - yr] * hashx[xi][xr + bsize - yr] ==
116             hashy[yi][yr]) {
117           xr += bsize - yr;
118           length += bsize - yr;
119           yi++, yr = 0;
120         } else {
121           break;
122         }
123         if (hashy[yi][yr] - power[bsize - xr] * hashy[yi][yr + bsize - xr] ==
124             hashx[xi][xr]) {
125           yr += bsize - xr;
126           length += bsize - xr;
127           xi++, xr = 0;
128         } else {
129           break;
130         }
131       }
132     }
133     int xx = xi * bsize + xr;
134     int yy = yi * bsize + yr;
135     while (char_at(x, xx) == char_at(y, yy)) {
136       xx++, yy++, length++;
137     }
138     return length;
139   }
140 
141   int n, bsize;
142   std::vector<int> event;
143   std::vector<Hash> power;
144   std::vector<std::vector<Hash *>> hashes;
145   std::vector<std::vector<Hash>> blocks;
146 };
147 
148 int main() {
149   int n;
150   while (scanf("%d", &n) == 1) {
151     Solver{n};
152   }
153 }

STD

H：

线性基。

 1 #include <bits/stdc++.h>
 2 
 3 using Long = long long;
 4 
 5 static const int D = 60;
 6 static const int MOD = 1e9 + 7;
 7 
 8 void add(int &x, int a) {
 9   x += a;
10   if (x >= MOD) {
11     x -= MOD;
12   }
13 }
14 
15 struct Basis {
16   Basis()
17   {
18     std::fill(index.begin(), index.end(), -1);
19   }
20 
21   bool update(Long x, int i) {
22     for (int j = 0; j < D; ++j) {
23       if (~index[j] && (x >> j & 1)) {
24         x ^= basis[j];
25       }
26     }
27     if (!x) {
28       return true;
29     }
30     int j = __builtin_ctzll(x);
31     assert(index[j] == -1);
32     index[j] = i;
33     basis[j] = x;
34     return false;
35   }
36 
37   std::array<int, D> index;
38   std::array<Long, D> basis;
39 };
40 
41 int main() {
42   int n;
43   while (scanf("%d", &n) == 1) {
44     std::vector<Long> a(n);
45     for (int i = 0; i < n; ++i) {
46       scanf("%lld", &a[i]);
47     }
48     Basis o;
49     int nullity = 0;
50     int two = 5e8 + 4;
51     for (int i = 0; i < n; ++i) {
52       if (o.update(a[i], i)) {
53         nullity++;
54         add(two, two);
55       }
56     }
57     int result = 1LL * nullity * two % MOD;
58     std::vector<Long> aa;
59     for (int i : o.index) {
60       if (~i) {
61         aa.push_back(a[i]);
62         a[i] = 0;
63       }
64     }
65     Basis b;
66     for (int i = 0; i < n; ++i) {
67       b.update(a[i], i);
68     }
69     for (int i = 0; i < static_cast<int>(aa.size()); ++i) {
70       Basis bb = b;
71       for (int j = 0; j < static_cast<int>(aa.size()); ++j) {
72         if (i != j) {
73           bb.update(aa[j], j);
74         }
75       }
76       if (bb.update(aa[i], i)) {
77         add(result, two);
78       }
79     }
80     printf("%d
", result);
81   }
82 }

STD

I：

二维平面上每个点有两个属性 $a$

首先把点排序(x从小到大，y从大到小)之后离散化。划分完之后，一定存在一条单调不下降的折线使得 $A$

$A$

$d p [i + 1] [j]_{j = y_{i}} = m a x_{k <= j} (d p [i] [k]) + b_{i}$

$d p [i + 1] [j]_{1 <= j < y_{i}} = d p [i] [j] + a_{i}$

  1 /* basic header */
  2 #include <bits/stdc++.h>
  3 /* define */
  4 #define ll long long
  5 #define dou double
  6 #define pb emplace_back
  7 #define mp make_pair
  8 #define sot(a,b) sort(a+1,a+1+b)
  9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
 10 #define rep0(i,a,b) for(int i=a;i<b;++i)
 11 #define eps 1e-8
 12 #define int_inf 0x3f3f3f3f
 13 #define ll_inf 0x7f7f7f7f7f7f7f7f
 14 #define lson (curpos<<1)
 15 #define rson (curpos<<1|1)
 16 #define mid (curl+curr>>1)
 17 /* namespace */
 18 using namespace std;
 19 /* header end */
 20 
 21 const int maxn = 1e5 + 10;
 22 
 23 struct Point {
 24     int x, y, a, b;
 25     bool operator<(const Point &rhs) const {
 26         if (x == rhs.x) return y > rhs.y;
 27         return x < rhs.x;
 28     }
 29 } p[maxn];
 30 int n, b[maxn];
 31 ll lazy[maxn << 2], segt[maxn << 2];
 32 
 33 void pushup(int curpos) {
 34     segt[curpos] = max(segt[lson], segt[rson]);
 35 }
 36 
 37 void pushdown(int curpos) {
 38     if (lazy[curpos]) {
 39         lazy[lson] += lazy[curpos];
 40         segt[lson] += lazy[curpos];
 41         lazy[rson] += lazy[curpos];
 42         segt[rson] += lazy[curpos];
 43         lazy[curpos] = 0;
 44     }
 45 }
 46 
 47 void build(int curpos, int curl, int curr) {
 48     segt[curpos] = lazy[curpos] = 0;
 49     if (curl == curr)
 50         return;
 51     build(lson, curl, mid);
 52     build(rson, mid + 1, curr);
 53 }
 54 
 55 void update(int curpos, int curl, int curr, int pos, ll val) {
 56     if (curl == curr) {
 57         segt[curpos] = val;
 58         return;
 59     }
 60     pushdown(curpos);
 61     if (pos <= mid)
 62         update(lson, curl, mid, pos, val);
 63     else
 64         update(rson, mid + 1, curr, pos, val);
 65     pushup(curpos);
 66 }
 67 
 68 void update(int curpos, int curl, int curr, int ql, int qr, ll val) {
 69     if (ql <= curl && curr <= qr) {
 70         segt[curpos] += val;
 71         lazy[curpos] += val;
 72         return;
 73     }
 74     pushdown(curpos);
 75     if (ql <= mid)
 76         update(lson, curl, mid, ql, qr, val);
 77     if (qr > mid)
 78         update(rson, mid + 1, curr, ql, qr, val);
 79     pushup(curpos);
 80 }
 81 
 82 ll query(int curpos, int curl, int curr, int ql, int qr) {
 83     if (ql <= curl && curr <= qr)
 84         return segt[curpos];
 85     pushdown(curpos);
 86     ll ans = -1e18;
 87     if (ql <= mid)
 88         ans = max(ans, query(lson, curl, mid, ql, qr));
 89     if (qr > mid)
 90         ans = max(ans, query(rson, mid + 1, curr, ql, qr));
 91     return ans;
 92 }
 93 
 94 int main() {
 95     while (~scanf("%d", &n)) {
 96         rep1(i, 1, n) {
 97             scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i].a, &p[i].b);
 98             b[i] = p[i].y;
 99         }
100         sot(p, n);
101         b[n + 1] = 0;
102         sot(b, n + 1);
103         int m = unique(b + 1, b + n + 2) - b - 1;
104         build(1, 1, m);
105         rep1(i, 1, n) {
106             int y = lower_bound(b + 1, b + m + 1, p[i].y) - b;
107             ll r = query(1, 1, m, 1, y);
108             update(1, 1, m, y, r + p[i].b);
109             if (y > 1) {
110                 update(1, 1, m, 1, y - 1, p[i].a);
111             }
112             if (y < m) {
113                 update(1, 1, m, y + 1, m, p[i].b);
114             }
115         }
116         printf("%lld
", query(1, 1, m, 1, m));
117     }
118     return 0;
119 }

View Code

J：

签到题。比较两个分数的大小。Python题，Java题，C++用__int128也可以过。

 1 import sys
 2  
 3 for line in sys.stdin:
 4     (x, y, a, b) = line.split()
 5     x = int(x)
 6     y = int(y)
 7     a = int(a)
 8     b = int(b)
 9     if (x * b == a * y):
10         print("=")
11     elif (x * b < a * y):
12         print("<")
13     else:
14         print(">")

View Code

2019牛客暑期多校训练营 第一场

2019牛客暑期多校训练营第一场