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

朱雀 2021-11-10 15:44 309阅读 0赞

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

题目链接：[https://ac.nowcoder.com/acm/contest/881\#question][https_ac.nowcoder.com_acm_contest_881_question]

--------------------

A：

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

B：

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

C：

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

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

![1625007-20190719214335270-678562426.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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

D：

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

给出std。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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\n", result);
    45   }
    46 }

E：

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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\n",ans); 
    32     }
    33     return 0;
    34 }

code via. tqlwsl

解释可以看这篇博客：[https://blog.csdn.net/qq\_39239844/article/details/96475068][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\]。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

F：

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

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

G：

神仙题。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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：

线性基。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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\n", result);
    81   }
    82 }

STD

I：

二维平面上每个点有两个属性a和b，你需要将这些点划分成两个集合A,B，其中A中没有点在B中任意一个点的右下方（非严格），贡献定义为A中点的a属性和B中点的b属性和的和，求最大贡献。

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

考虑dp。dp\[i\]\[j\]代表前i个点，j为第i个点所在横坐标的纵坐标分割线(即折线经过点(xi,j))的最大贡献。因为这条直线单调不下降，所以满足：

dp\[i\+1\]\[j\]j=yi=maxk<=j(dp\[i\]\[k\])\+bi

dp\[i\+1\]\[j\]1<=j<yi=dp\[i\]\[j\]\+ai

dp\[i\+1\]\[j\]yi<j<=tot=dp\[i\]\[j\]\+bi

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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\n", query(1, 1, m, 1, m));
    117     }
    118     return 0;
    119 }

J：

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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(">")

转载于:https://www.cnblogs.com/JHSeng/p/11209641.html

[https_ac.nowcoder.com_acm_contest_881_question]: https://ac.nowcoder.com/acm/contest/881#question
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/822f183692044545976688c69fde58a6.png
[https_www.cnblogs.com_Dillonh_p_11209476.html]: https://www.cnblogs.com/Dillonh/p/11209476.html
[231650139846199.png]: /images/20211109/821de8e6df09484b8e834d08cbeac14e.png
[1625007-20190719214335270-678562426.png]: /images/20211109/d944e3222a4f453f871a9007e29443b9.png
[https_www.cnblogs.com_Dillonh_p_11215846.html]: https://www.cnblogs.com/Dillonh/p/11215846.html
[https_blog.csdn.net_nickwzk_article_details_96472362]: https://blog.csdn.net/nickwzk/article/details/96472362
[https_blog.csdn.net_qq_39239844_article_details_96475068]: https://blog.csdn.net/qq_39239844/article/details/96475068