2020牛客暑期多校训练营（第六场）

比赛地址：

https://ac.nowcoder.com/acm/contest/5671

E Easy Construction

题目地址：

https://ac.nowcoder.com/acm/contest/5671/E

基本思路：

首先我们给出的 $n,k$ 一定要满足 $(\sum_{i=1}^{n}i)\equiv k(mod \ n)$ ，否者则必不可能构造出来，直接输出 $-1$ ,
然后我们考虑符合条件的情况怎么构造,我们考虑一种构造方法它能在每种区间长度下从整个序列的和中刚好剔除掉几个 $n$ 的倍数。
所以我们考虑这样构造，假设有 $1$ ~ $n$ 个数，我们这样排列 $1,n - 1,2, n - 2, 3 , n - 3, ... n$
剔除掉一个数的情况，也就是区间长为 $n - 1$ 的情况，我们剔除掉最后一位 $n$ ,区间长度为 $n - 2$ 的情况，我们剔除掉前两位 $(1 + (n - 1) = n)$ ,区间长为 $n - 3$ 的，我们剔除前两位和最后一位 $(1 + (n - 1) + n = 2n)$ ,依次类推我们就能发现这样的构造是一定满足条件的。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

int n,k;
signed main() {
  IO;
  cin >> n >> k;
  int tmp = (n + 1) * n / 2;
  if (tmp % n != k) {
    cout << -1 << '\n';
    return 0;
  }
  vector<int> ans;
  int l = 1, r = n - 1;
  while (l < r) {
    ans.push_back(l);
    ans.push_back(r);
    l++, r--;
  }
  if (l == r) ans.push_back(l);
  ans.push_back(n);
  for(auto it : ans ) cout << it << ' ';
  cout << '\n';
  return 0;
}

C Combination of Physics and Maths

题目地址：

https://ac.nowcoder.com/acm/contest/5671/C

基本思路：

通过题意我们有一个基本思路，就是我们可以枚举选择哪一行做底，然后对于这一行中的每一列，之前的行都选肯定是最优的，
因此我们只要考虑在每一行作为底的情况里，如何最优的选择列能使得答案最大,
我们考虑每一列，设这一列之前数的和为 $a$ ,最底这一行的数为 $b$ ，那么这一列的值应该为 $\frac{a}{b}$
我们假设 $\frac{a}{b}$ 为这一行的最优的一列，也就意味着对于另一个值为 $\frac{c}{d}$ 的列,我们满足： $\frac{c}{d} \leq \frac{a}{b}$ ，那我们如果把两列合并，那么答案变成 $\frac{a + c}{b + d}$ ，
我们可以证明 $\frac{c}{d} \leq \frac{a + c}{b + d} \leq \frac{a}{b}$ ( $a,b,c,d$ 均为正实数)，简单证明如下：

$\frac{c}{d} \leq \frac{a}{b} \Rightarrow \frac{c}{d} - \frac{a}{b} \leq 0 \Rightarrow \frac{cb - ad}{db}\leq 0 \Rightarrow cb - ad \leq 0$

我们直接证明 $\frac{a + c}{b + d} \leq \frac{a}{b}$ 这部分：

$\frac{a + c}{b + d} - \frac{a}{b} = \frac{b(a + c) - a(b + d)}{b(b + d)} = \frac{cb - ad}{b(b + d)} \leq 0$
即 $\frac{a + c}{b + d} \leq \frac{a}{b}$ 证得,左边部分同理。

我们知道了上面的东西,实际上就是告诉我们在每一行中,只要选择值最大的那一列就是这一行的最优解了,
因此做个简单的前缀和，枚举行，在每一行中找最大的那一列更新答案就好了。
(实际比赛中，我们带几个值就能得到上面的结论，并不用严格证明)

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 210;
int n,m,a[maxn][maxn];
int sum[maxn][maxn];
signed main() {
  IO;
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) cin >> a[i][j];
    rep(j, 1, m) {
      rep(i, 1, n) sum[j][i] = sum[j][i - 1] + a[i][j];
    }
    double ans = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) ans = max(ans, (double) sum[j][i] / (double) a[i][j]);
    }
    printf("%.8lf\n", ans);
  }
  return 0;
}

B Binary Vector

题目地址：

https://ac.nowcoder.com/acm/contest/5671/B

基本思路：

有一说一并没有看懂题，我们直接根据样例能够推出这样一个递推式(反正就是能得到XD)：

$f(1) = \frac{1}{2}$
$f(n) = f(n-1) * (\frac{2^{n} - 1}{2^{n}})$

然后说一下这玩意怎么求比较快，我们直接令 $f(1) = 500000004 = \frac{1}{2}$ (样例给出)
然后我们一遍预处理，处理出 $2^{n}$ ,和 $\frac{1}{2^{n}}$ , $\frac{1}{2^{n}}$ 直接用 $500000004$ 去求就行了，省去了求逆元的过程,
所以我们在三次循环里就能预处理出所有答案， $O(1)$ 查询即可。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int mod = 1e9 + 7;
const int maxn = 2e7 + 10;
int ans[maxn],pw[maxn],inv[maxn];
signed main() {
  IO;
  ans[1] = 500000004;
  pw[0] = inv[0] = 1;
  for (int i = 1; i < maxn; i++) {
    pw[i] = 1ll * pw[i - 1] * 2ll % mod;
    inv[i] = 1ll * inv[i - 1] * ans[1] % mod;
  }
  for (int i = 2; i < maxn; i++) {
    ans[i] = 1ll * ans[i - 1] * (pw[i] - 1) % mod * inv[i] % mod;
  }
  for (int i = 2; i < maxn; i++) ans[i] ^= ans[i - 1];
  int t = read();
  while (t--) {
    int x = read();
    print(ans[x]);
    puts("");
  }
  return 0;
}

K K-Bag

题目地址：

https://ac.nowcoder.com/acm/contest/5671/K

基本思路：

根据题意我们比较容易想到，满足条件的序列,我们不管头尾，中间一定要是一个 $k$ 排列，一个 $k$ 排列这样摆放的过程,
但是我们并不清楚我们的头尾在什么位置结束/开始会更优,
因此我们考虑一种尺取加 $dp$ 的策略,首先在序列开头只要不出现重复的元素，那么很明显这些位置都可以作为头部结束的位置，
我们将这些位置的 $dp[i]$ 都设为 $true$ ,然后我们通过尺取法，快速找到序列里所有满足 $k$ 排列的那些区间的结束位置,
因为如果我们头部从一个位置 $pos$ 结束,要是序列符合条件的话必须满足 $pos + k + k + k + ...$ 这样的形式,这里面的每个 $k$ 都是满足条件的 $k$ 排列区间因此假设 $r$ 是现在一个 $k$ 排列区间的结尾,存在这样的一个转移 $dp[r] \ |= dp[r - k]$ 。
这样实际上我们就是处理出了从头部起,所有符合条件区间能到达的位置,然后我们再从尾部出发，如果能找到一个从尾部开始的位置，和这些从头部起满足条件的位置相接，那么整条序列就会是满足条件的序列了。
在尺取过程中,我们要采用 $unordered\_map$ ， $unordered\_set$ 记录信息,否者会超时,具体实现细节看代码。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 5e5 + 10;
int n,k,a[maxn];
bool dp[maxn];
unordered_map<int, int> memo;
unordered_set<int> st;
signed main() {
  IO;
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    memo.clear(); st.clear();
    for (int i = 1; i <= n; i++) cin >> a[i], dp[i] = false;
    int pos;
    for(pos = 1 ; pos <= n ; pos++){// 找到头部能够衍生到的最远位置;
      if(memo[a[pos]]) break;
      memo[a[pos]] = 1; st.insert(a[pos]);
    }
    for (int i = 1; i < pos; i++) dp[i] = true; // 这些位置都能作为头部的结束;
    for (int i = pos ; i <= min(n, k); i++) {
      memo[a[i]]++, st.insert(a[i]);
    }
    for (int r = k + 1; r <= n; r++) {
      int l = r - k; //在[l,r] 这段区间内尺取;
      memo[a[l]]--;
      if (!memo[a[l]]) st.erase(a[l]);
      memo[a[r]]++;
      st.insert(a[r]);
      if ((int) st.size() == k) dp[r] |= dp[l]; //是一个符和条件的k排列结尾的位置,状态转移;
    }
    memo.clear();
    bool v = true;
    for(pos = n ; pos >= 1 ; pos--){ //从尾部出发找是否有符合条件位置和之前的满足条件的位置相接;
      if(dp[pos]) break; //相接了,说明整个序列条件;
      if(memo[a[pos]]) {v = false; break; }
      memo[a[pos]] = 1;
    }
    if (v) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

G Grid Coloring

题目地址：

https://ac.nowcoder.com/acm/contest/5671/G

基本思路：

来了来了,把坑填了不咕咕咕了,
其实这题的构造比较简单,我们先考虑不可能的情况,首先如果总共要染色的边数 $2 * (n + 1) * n$ 不能被 $k$ 整除,那么就无论如何都不能满足条件 $1$ ,同时 $n = 1$ 和 $k = 1$ 的情况也是一定不能染色出来的,这点画个图就能理解了。
那么对于其余情况,我们考虑如何构造,首先只要 $n$ 不被 $k$ 整除,我们只要循环的按顺序横着染色,再竖着染色就行了,
然后如果是 $n$ 被 $k$ 整除的情况,我们就能发现直接顺着染就会产生同色环,这时候其实我们只要把横行和竖行岔开了放就行了,
简单的我们直接借用奇偶行岔开就行了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

int n,k;
signed main() {
  IO;
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    int all = 2ll * (n + 1) * n;
    if (n == 1 || k == 1 || all % k != 0) {
      cout << -1 << '\n';
      continue;
    }
    int cnt = 0;
    if (n % k != 0) {
      for (int i = 1; i <= 2ll * (n + 1); i++) {
        for (int j = 1; j <= n; j++) {
          cout << cnt + 1 << ' ';
          cnt = (cnt + 1) % k;
        }
        cout << '\n';
      }
    } else {
      for (int i = 1; i <= 2ll * (n + 1); i++) {
        for (int j = 1; j <= n; j++) {
          cout << (i + j) % k + 1 << ' ';
        }
        cout << '\n';
      }
    }
  }
  return 0;
}