牛客暑假多校 2023 第四场

Luckyblock / 2023-07-29 / 原文

写在前面
A
L
F
J
H
写在最后

写在前面

比赛地址：https://ac.nowcoder.com/acm/contest/57358。

那时，天下人的口音，言语，都是一样。

他们往东边迁移的时候，在示拿地遇见一片平原，就住在那里。

他们彼此商量说，来吧，我们要作砖，把砖烧透了。他们就拿砖当石头，又拿石漆当灰泥。

他们说，来吧，我们要建造一座城和一座塔，塔顶通天，为要传扬我们的名，免得我们分散在全地上。

耶和华降临，要看看世人所建造的城和塔。

耶和华说，看哪，他们成为一样的人民，都是一样的言语，如今既作起这事来，以后他们所要作的事就没有不成就的了。

我们下去，在那里变乱他们的口音，使他们的言语彼此不通。

于是，耶和华使他们从那里分散在全地上。他们就停工，不造那城了。

因为耶和华在那里变乱天下人的言语，使众人分散在全地上，所以那城名叫巴别（就是变乱的意思）。

—— 创世纪 - 十一

以下按个人向难度排序。

A

发现 \(t\) 可能会出现在 \(s\) 的内部，或者 \(t+s+t\) 的交界处。一个显然的想法是先构造内部没有 \(t\) 的一段，然后再考虑往两边添加使得交界处没有 \(t\)。

发现构造全 0 或全 1 即可使内部没有 \(t\)，在此基础上再考虑，发现直接令 \(s\) 为全 0 或全 1 即可。可以证明解至少为全 0 或全 1 中的一个。

构造 \(t+s+t\) 后 KMP 判断是否出现 \(t\) 即可。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e3 + 10;
//=============================================================
int n, m;
int fail[kN];
char t[kN], ans[3 * kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void KMP() {
  fail[1] = 0;
  for (int i = 2, j = 0; i <= m; ++ i) {
    while (j && t[i] != t[j + 1]) j = fail[j];
    if (t[i] == t[j + 1]) ++ j;
    fail[i] = j;
  }  
}
bool Check0() {
  int n1 = 2 * m + n;
  for (int i = 1; i <= m; ++ i) ans[i] = t[i];
  for (int i = 1; i <= n; ++ i) ans[m + i] = '0';
  for (int i = 1; i <= m; ++ i) ans[n + m + i] = t[i];
  ans[n1 + 1] = 0;

  for (int i = 2, j = 0; i < n1; ++ i) {
    while (j && ans[i] != t[j + 1]) j = fail[j];
    if (ans[i] == t[j + 1]) ++ j;
    if (j == m) return 0;
  }
  for (int i = 1; i <= n; ++ i) printf("0");
  printf("\n");
  return 1;
}
bool Check1() {
  int n1 = 2 * m + n;
  for (int i = 1; i <= m; ++ i) ans[i] = t[i];
  for (int i = 1; i <= n; ++ i) ans[m + i] = '1';
  for (int i = 1; i <= m; ++ i) ans[n + m + i] = t[i];
  ans[n1 + 1] = 0;

  for (int i = 2, j = 0; i < n1; ++ i) {
    while (j && ans[i] != t[j + 1]) j = fail[j];
    if (ans[i] == t[j + 1]) ++ j;
    if (j == m) return 0;
  }
  for (int i = 1; i <= n; ++ i) printf("1");
  printf("\n");
  return 1;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    scanf("%s", t + 1); m = strlen(t + 1);
    KMP();
    if (Check0()) continue;
    if (Check1()) continue;
    printf("-1\n"); 
  }
  return 0;
}

L

典题，当年在 qbxt 做过。

对于同一行同一列，如果对它有多次修改，仅有最后一次修改是有效的，于是考虑倒着做，忽略重复操作的同时，维护后若干的操作已经将多少行/列置 0/1，遇到置 1 操作根据维护的信息累计贡献即可。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, m, q;
int opt1[kN], opt2[kN], opt3[kN];
int tag[2][kN], cnt[2][2];
char s[15];
LL ans;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read(), m = read(), q = read();
  cnt[0][0] = 0, cnt[0][1] = 0, cnt[1][0] = 0, cnt[1][1] = 0;
  for (int i = 1; i <= q; ++ i) {
    scanf("%s", s + 1);
    opt1[i] = s[1] == 'c';
    opt2[i] = read();
    scanf("%s", s + 1);
    opt3[i] = s[2] == 'n' ? 1 : -1; 
  }

  for (int i = q; i; -- i) {
    int type = opt1[i], p = opt2[i], key = opt3[i];
    if (tag[type][p]) continue;
    tag[type][p] = key;
    if (type == 0) {
      if (key == -1) {
        cnt[0][0] ++;
      } else {
        cnt[0][1] ++;
        ans += m - cnt[1][0] - cnt[1][1];
      }
    } else {
      if (key == -1) {
        cnt[1][0] ++;
      } else {
        ++ cnt[1][1];
        ans += n - cnt[0][0] - cnt[0][1];
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}

F

中国人的性情是总喜欢调和折中的，譬如你说，这屋子太暗，须在这里开一个窗，大家一定不允许的。但如果你主张拆掉屋顶，他们就来调和，愿意开窗了。

在某一轮操作中，设中位数为 \(a_m\)，显然大于中位数的会选择删除极小值，小于中位数的会选择删除极大值，仅需特判中位数的选择即可确定本轮删除的对象。

于是模拟上述过程，根据区间长度维护中位数即可。

Code by nebulyu.

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
const int N=1e6+5;
ll ar[N],n;
pli rec[N];
void solve(){
	cin>>n;
	ffor(i,1,n)cin>>ar[i],rec[i]=pli(ar[i],i);
	sort(rec+1,rec+1+n);
	ffor(i,1,n)ar[i]=rec[i].first;
	int l=1,r=n;
	while(l+1<r){
		ll mid=(ar[l]+ar[r])/2;
		int p=upper_bound(ar+1,ar+n+1,mid)-ar;
		int lp=p-l,rp=r-p+1;
		if(rp>lp)++l;else --r;
	}
	cout<<rec[l].second;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

J

给定整数 \(n, m\)，要求构造一数列 \(a\)，满足：

\(a\) 的长度为 \(n\)。

\(\forall 1\le i\le n, -m\le a_i\le m\)。

\(\forall 1\le l< r\le n, \sum_{i=l}^{r} a_i \ge 0\)。

求满足条件的数列 \(a\) 的种类数，答案对 998244353 取模。
\(1\le n,m\le 5000\)。
1S，512MB。

先膜拜 nebulyu。

显然不可能出现连续两个负数，并且对于一个合法的数列，其中负数两侧一定均为正数，且大于该负数的绝对值。

赛时我想到的做法是设 \(f_{i,j}\) 表示最小后缀和为 \(j\) 的合法前缀 \(1\sim i\) 的方案数，显然有 \(-m\le j\le m\)，状态数至多只有 \(2\times n\times m\) 个。初始化 \(f_{1, j}:=1\)，转移时考虑在最后填入一个数的影响：

考虑枚举添加后的最小后缀和 \(j\)。若在最后添加一个正数，则添加后最小后缀和一定不小于 0，否则不合法。则添加前最小后缀和的范围显然为 \([j - m, m]\)；若在最后添加一个负数，则添加后的最小后缀和一定小于 0 且为该负数，为保证合法，添加前最小后缀和的范围显然为 \([-j, m]\)。

则有：

\[f_{i, j} = \begin{cases} &\sum\limits_{k=j-m}^{m} f_{i - 1, k} &(j \ge 0)\\ &\sum\limits_{k = -j}^{m} f_{i - 1, k} &(j < 0) \end{cases}\]

答案即 \(\sum_{j = -m}^{m} f_{n, j}\)。

维护一个后缀和转移即可。实现时可以直接把 \(f\) 的第一维省去。总时间复杂度 \(O(nm)\) 级别。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const LL p = 998244353;
const int kN = 5e3 + 10;
const int d = 5e3;
//=============================================================
int n, m;
LL f[kN << 1], suf[kN << 1];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read(), m = read();
  for (int i = d - m; i <= d + m; ++ i) f[i] = 1;
  for (int i = m + d; i >= d - m; -- i) suf[i] = suf[i + 1] + f[i];
  
  for (int i = 2; i <= n; ++ i) {
    for (int j = 0; j <= m; ++ j) f[d + j] = suf[d + j - m];
    for (int j = 1; j <= m; ++ j) f[d - j] = suf[d + j];
    for (int j = d + m; j >= d - m; -- j) suf[j] = (suf[j + 1] + f[j]) % p;
  }
  printf("%lld\n", suf[-m + d]);
  return 0;
}

H

有 \(n\times n\) 个排列成方阵的边长为 1 的小正方形，给定一种操作：

选择以 \((x, y)\) 为左上角，边长为 \(k\) 的正方形区域，将将整个区域合并为一个大正方形。

合并前区域内的正方形个数 \(c\) 需要满足 \(2\le c\le 50\)。

要求构造一种操作方案，操作次数长度任意，使得经过若干次操作后得到一个 \(n\times n\) 的大正方形。
\(1\le n\le 1000\)。
1S，512MB。

哈，居然不是纯构造，居然是 tama 的乱搞题。

对于一个大小为 \(k\times k\) 的正方形区域，显然当 \(k\le 7\) 时可以直接合并；当 \(k>7\) 时考虑四分解：将其分为左上角的 \(a\times a\) 的正方形、右下角的 \(k - a\times k - a\) 的正方形以及两侧 \(a\times k - a\) 的矩形。递归地考虑，左上角和右下角的较小正方形都可以合并成一个，仅需关注两侧 \(a\times k - a\) 的矩形区域可不可以分成至多 24 个正方形区域。

考虑一种贪心的分解方法，每次从矩形区域较长边 \(p\) 的一端分出一份边长为较短边 \(q\) 的正方形，直到被分出的正方形边长 \(\le 7\)。发现这个过程就是辗转相减，至多拆出 \(\left\lfloor \frac{p}{q} \right\rfloor\)，然后再递归地拆分 \((p\bmod q)\times q\) 的矩阵，据此就可以通过辗转相除法计算拆分出的数量是否 \(\le 24\)。

嘛，虽然不能保证对于每一个 \(a\)，两侧 \(a\times k - a\) 的矩形区域均可以分成至多 24 个正方形区域，不过可以枚举 \(a\) 再对每个 \(a\times k - a\) 进行上述类似辗转相除法的算法，只要能找到一个 \(a\) 使得上述条件成立即可，说明找到了 \(k\times k\) 正方形区域的一种分解方法，之后就可以递归解决问题了。

于是考虑顺序枚举所有满足 \(1\le k\le n\) 的 \(k\times k\) 正方形区域，都对它们进行上述过程并得到它们的一种四分解方案，再据此 DfS + 辗转相减构造 \(n\times n\) 的方案即可。

总时间复杂度上界大概是 \(O(n^2\log (n^2))\) 级别。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
const int kN = 1e3 + 10;
//=============================================================
int n, f[kN];
struct operation {
  int a, b, c;
};
std::vector <operation> ans;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
bool Check(int x_, int y_) {
  if (!y_) return x_ <= 7;
  int cnt = 0, temp;
  while (y_) {
    cnt += x_ / y_;
    temp = y_, y_ = x_ % y_, x_ = temp;
  }
  return cnt <= 24;
}
void Init() {
  n = read();
  for (int i = 1; i <= n; ++ i) f[i] = -1;

  f[1] = 0;
  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= i / 2; ++ j) {
      if (Check(i - j, j)) {
        f[i] = j;
        break;
      }
    }
  }
}
void Dfs(int, int, int);
void Solve2(int, int, int, int);
void Solve1(int x_, int y_, int w_, int h_) {
  if (w_ <= 1) return ;
  for (int i = 0; i < h_ / w_; ++ i) Dfs(x_, y_ + i * w_, w_);
  Solve2(x_, y_ + (h_ / w_) * w_, w_, h_ % w_);
}
void Solve2(int x_, int y_, int w_, int h_) {
  if (h_ <= 1) return ;
  for (int i = 0; i < w_ / h_; ++ i) Dfs(x_ + i * h_, y_, h_);
  Solve1(x_ + (w_ / h_) * h_, y_, w_ % h_, h_);
}
void Dfs(int x_, int y_, int h_) {
  if (h_ == 1) return ;
  ans.push_back((operation) {x_, y_, h_});
  if (f[h_] == 0) return ;
  int h1 = h_ - f[h_], h2 = f[h_];
  Solve1(x_ + h1, y_, h2, h1), Solve2(x_, y_ + h1, h1, h2);
  Dfs(x_, y_, h1), Dfs(x_ + h1, y_ + h1, h2);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  Init();
  Dfs(1, 1, n);
  printf("%d\n", ans.size());
  for (int i = ans.size() - 1; i >= 0; -- i) {
    printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
  }
  return 0;
}