WC2015 题解

阅读原文时间：2023年07月10日阅读：2

K小割

题目链接：WC2015 K小割

题目很清楚了，已经不能说的更简洁了……

这道题出题人挺毒的，你需要针对不同的部分分施用不同的做法。

第\(1\)部分：暴力枚举每条边是否割掉，并保留所有合法的割，更新答案，最后\(sort\)一下（从小到大），输出即可。

复杂度\(O(2^m\times n)\)，可以规避\(K\)过大的限制。
第\(2\)部分：采用优先队列。

对于除\(s,t\)外的每个点都分别有且仅有一条边与\(s,t\)相连。那么对于每一个点都必须至少割掉其中的一条边。设两条边的权值为\(a,b (a<b)\)，那么对于每个点的选择有\(\{a,b,a+b\}\) 三种，我们可以通过对于每个点选择的升级/降级，来达到不同的状态。

我们将点以\((b-a)\)为第一关键字（从第一级升到第二级的代价），\(a\)为第二关键字排序（从第二级升到第三级的代价）。

对于每个状态我们有三种选择

（1）将当前点的状态升级

（2）当前点保持不变，将该点的后一个点升级，并将当前点改为他后面的点。

（3）将当前点降级，将该点的后一个点升级，并将当前点改为他后面的点（需要注意的是在降级的时候只能是从\(b->a\)，不能是从\(a+b->b\)，否则会出现重复的状态，因为\(a+b->b\)的改变其实可以转化成选择（2））

总之在更新状态的时候需要时刻注意，不要更新到之前已经得到的状态，如果开始后一个点的升级，那么当前点就不能再改变了。
第\(3\)部分：采用最小割。

我们可以先跑最大流，求出最小割。

然后，我们可以按如下方式求出次小割：

\((1)\) 强制割集中的某条边不选，然后求此时的最小割；

\((2)\) 选择不再割集中的某条边，然后割掉。

对于第（2）种产生方式，必然是选择不在割集中的边权最小的边来更新答案。那么我们如何确定割集呢？从s开始走剩余流量不为0的边，将所有能遍历到的点打访问标记，如果一条边的两个端点x[i]有标记，y[i]没有标记，那么该边在最小割的割集中。

第一种情况，对于每一条边来说，如果这条边不割，那么\(s->x[i]，y[i]->t\)都其中一个必须不连通，我们可以在做完最小割的残量网络上对于\(s->x[i],y[i]->t\)分别求最小割，然后从中选取较小的更新答案。

处理完\((1)(2)\)两种产生方式后，得到的答案就是针对当前割集的次小割。

结合这\(3\)部分，你就可以获得\(AC\)。

混淆与破解

题目链接：WC2015 混淆与破解

这道题还不会，暂时咕着。

未来程序

题目链接：

这是一道提交答案题

题目给定你\(10\)组\(program*.cpp\)和\(program*.in\)，这些都是暴力程序，无法在规定时间内跑出。

你需要优化这\(10\)个程序，并提交对应的\(10\)组\(program*.out\)。

program1

#include
#include
void _() {
unsigned long long a, b, c, d, i;
scanf("%llu %llu %llu", &a, &b, &c);
i = 0;
d = 0;
while (i < b) {
d = d + a;
d = d % c;
i = i + 1;
}
printf("%llu\n", d);
}

int main() {
(); ();
(); ();
_();
```
_();
_();
_();
_();
_();复制
```
}

这个很显然是求\(a\times b \mod c\)，我们用快速乘优化即可。

\(program1.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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');
}

unsigned long long a, b, c;

ull fmul(ull a, ull b, ull c) {
  ull ans = 0;
  while (b > 0) {
    if (b & 1) ans = (ans + a) % c;
    a = (a + a) % c;
    b >>= 1;
  }
  return ans;
}

int main() {
  freopen("program1.in", "r", stdin);
  freopen("program1.out", "w", stdout);

  while (cin >> a >> b >> c) {
    cout << fmul(a, b, c) << '\n';
  }
  return 0;
}复制

program2

#include
void () {
long long i, n, a, b, c, d, p;
a = 1;
b = 0;
c = 0;
scanf("%lld %lld", &n, &p);
i = 1;
while (i <= n) { i = i + 1; b = a + b; a = 2 * b - a + c; c = 2 * b - a + c; while (a >= p) {
a -= p;
}
while (a < 0) { a += p; } while (b >= p) {
b -= p;
}
while (b < 0) { b += p; } while (c >= p) {
c -= p;
}
while (c < 0) { c += p; } } d = a - 2 * b + c; while (d >= p) {
d -= p;
}
while (d < 0) {
d += p;
}
printf("%lld\n", d);
}
int main() {
();
();
();
();
();
();
();
();
();
_();
return 0;
}

我们发现这其实就是求以\(0\ 1\)开头的斐波那契数列第\(n\)项的平方。

矩阵快速幂优化即可。

\(program2.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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');
}

long long n, mod;

struct Matrix {
  ll v[2][2];
  int n, m;
  Matrix (int _n = 0, int _m = 0) {
    n = _n;
    m = _m;
  }
  void clear() {
    memset(v, 0, sizeof(v));
  }
} ans(2, 1), res(2, 2);
Matrix operator * (Matrix a, Matrix b) {
  Matrix ans(a.n, b.m);
  ans.clear();
  for (rint i = 0; i < a.n; i++) {
    for (rint j = 0; j < b.m; j++) {
      for (rint k = 0; k < a.m; k++) {
        (ans.v[i][j] += a.v[i][k] * b.v[k][j]) %= mod;
      }
    }
  }
  return ans;
}

ll fib(ll n) {
  if (n == 1) return 0;
  if (n == 2) return 1;
  ans.clear(), res.clear();
  ans.v[0][0] = 1, ans.v[1][0] = 0;
  res.v[0][0] = res.v[0][1] = res.v[1][0] = res.v[0][0] = 1;
  n -= 2;
  while (n > 0) {
    if (n & 1) ans = res * ans;
    res = res * res;
    n >>= 1;
  }
  return ans.v[0][0];
}

int main() {
  freopen("program2.in", "r", stdin);
  freopen("program2.out", "w", stdout);
  while (cin >> n >> mod) {
    ll x = fib(n);
    cout << x * x % mod << '\n';
  }
  return 0;
}复制

program3

#include
unsigned long long s0, s1, s2, s3, s4, i, n;
int main() {
scanf("%llu", &n);
i = 0;
while (i <= n) {
s0 = s0 + 1;
s1 = s1 + i;
s2 = s2 + i * i;
s3 = s3 + i * i * i;
s4 = s4 + i * i * i * i;
i = i + 1;
}
printf("%llu\n", s0);
printf("%llu\n", s0);
printf("%llu\n", s1);
printf("%llu\n", s1);
printf("%llu\n", s2);
printf("%llu\n", s2);
printf("%llu\n", s3);
printf("%llu\n", s3);
printf("%llu\n", s4);
printf("%llu\n", s4);
return 0;
}

这是让我们求

\[s0=\sum_{i=1}^{n}1
\]

\[s1=\sum_{i=1}^{n}i
\]

\[s2=\sum_{i=1}^{n}i^2
\]

\[s3=\sum_{i=1}^{n}i^3
\]

\[s4=\sum_{i=1}^{n}i^4
\]

直接套数学公式即可，四次方和公式可别忘了呐~

\(program3.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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');
}

ull n;

int main() {
  freopen("program3.in", "r", stdin);
  freopen("program3.out", "w", stdout);

  while (cin >> n) {
    ull ans = n + 1;
    cout << ans << '\n';
    cout << ans << '\n';
    ans = n * (n + 1) / 2ull;
    cout << ans << '\n';
    cout << ans << '\n';
    ans = n * (n + 1) * (2 * n + 1) / 6ull;
    cout << ans << '\n';
    cout << ans << '\n';
    ans = n * (n + 1) / 2ull;
    ans = ans * ans;
    cout << ans << '\n';
    cout << ans << '\n';
    ull a[5] = {n, n + 1, 2 * n + 1, 3 * n * n + 3 * n - 1};
    ull ne[5] = {2, 3, 5};
    for (rint i = 0; i < 3; i++) {
      for (rint j = 0; j < 4; j++) {
        if (a[j] % ne[i] == 0) {
          a[j] /= ne[i];
          break;
        }
      }
    }
    ans = a[0] * a[1] * a[2] * a[3];
    //ans = n * (n + 1) * (2ull * n + 1ull) / 30ull * (3ull * n * n + 3ull * n - 1ull);
    cout << ans << '\n';
    cout << ans << '\n';
  }
}复制

program4

#include

const int N = 5000, inf = 0x3F3F3F3F;
int n, m, type;
bool data[N + 11][N + 11];

int seed;
int next_rand(){
static const int P = 1000000007, Q = 83978833, R = 8523467;
return seed = ((long long)Q * seed % P * seed + R) % P;
}

void generate_input(){
std::cin >> n >> m >> type;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) data[i][j] = bool((next_rand() % 8) > 0);
}

long long count1(){
long long ans = 0LL;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(data[i][j])
for(int k = 0; k < n; k++)
for(int l = 0; l < m; l++)
if(data[k][l] && (k != i || l != j))
ans++;
return ans;
}

int abs_int(int x){
return x < 0 ? -x : x;
}

long long count2(){
long long ans = 0LL;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(data[i][j]){ int level = inf; for(int k = 0; k < n; k++) for(int l = 0; l < m; l++) if(!data[k][l]){ int dist = abs_int(k - i) + abs_int(l - j); if(level > dist)
level = dist;
}
ans += level;
}
return ans;
}

int main(){
std::cin >> seed;
for(int i = 0; i < 10; i++){
generate_input();
std::cout << (type == 1 ? count2() : count1()) << std::endl;
}
return 0;
}

这道题如果\(type=0\)，那么就是求有多少对二元组\(((x_i,y_i),(x_j,y_j))\ (i≠j)\)，满足\(data_{x_i,y_i}=1\)且\(data_{x_j,y_j}=1\)。

如果\(type=1\)，那么就是求每一个\(x_i,y_i\)满足\(data_{x_i,y_i}=1\)，离它曼哈顿距离最近的\(data_{x_j,y_j}=0\)距离之和。

显然直接\(dp\)即可。

\(program4.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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 N = 5005;
int data[N][N];
int seed, n, m, type;

int next_rand() {
  static const int P = 1000000007, Q = 83978833, R = 8523467;
  return seed = ((long long)Q * seed % P * seed + R) % P;
}
void generate_input() {
  cin >> n >> m >> type;
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= m; j++) {
      data[i][j] = bool((next_rand() % 8) > 0);
    }
  }
}
long long count1() {
  long long ans = 0ll;
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= m; j++) {
      if (data[i][j] == 1) {
        ans++;
      }
    }
  }
  return ans * (ans - 1);
}
int dp1[N][N];
int dp2[N][N];
int dp3[N][N];
int dp4[N][N];
long long count2() {
  mset(dp1, 0x3f), mset(dp2, 0x3f), mset(dp3, 0x3f), mset(dp4, 0x3f);
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= m; j++) {
      if (!data[i][j]) dp1[i][j] = 0;
      else dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + 1;
    }
  }
  for (rint i = 1; i <= n; i++) {
    for (rint j = m; j >= 1; j--) {
      if (!data[i][j]) dp2[i][j] = 0;
      else dp2[i][j] = min(dp2[i - 1][j], dp2[i][j + 1]) + 1;
    }
  }
  for (rint i = n; i >= 1; i--) {
    for (rint j = 1; j <= m; j++) {
      if (!data[i][j]) dp3[i][j] = 0;
      else dp3[i][j] = min(dp3[i + 1][j], dp3[i][j - 1]) + 1;
    }
  }
  for (rint i = n; i >= 1; i--) {
    for (rint j = m; j >= 1; j--) {
      if (!data[i][j]) dp4[i][j] = 0;
      else dp4[i][j] = min(dp4[i + 1][j], dp4[i][j + 1]) + 1;
    }
  }
  long long ans = 0ll;
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= m; j++) {
      if (data[i][j]) {
        ans += min(min(dp1[i][j], dp2[i][j]), min(dp3[i][j], dp4[i][j]));
      }
    }
  }
  return ans;
}

int main() {
  freopen("program4.in", "r", stdin);
  freopen("program4.out", "w", stdout);

  cin >> seed;
  for (rint i = 0; i < 10; i++) {
    generate_input();
    cout << (type == 1 ? count2() : count1()) << endl;
  }
  return 0;
}复制

program5

#include

const int N = 5011;
int n, m;
bool data[N][N];

int seed;
int next_rand(){
static const int P = 1000000007, Q = 83978833, R = 8523467;
return seed = ((long long)Q * seed % P * seed + R) % P;
}

void generate_input(){
std::cin >> n >> m;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) data[i][j] = bool((next_rand() % 8) > 0);
}

bool check(int x1, int y1, int x2, int y2){
bool flag = true;
for(int i = x1; i <= x2; i++)
for(int j = y1; j <= y2; j++)
if(!data[i][j])
flag = false;
return flag;
}

long long count3(){
long long ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
for(int k = i; k < n; k++)
for(int l = j; l < m; l++)
if(check(i, j, k, l))
ans++;
return ans;
}

int main(){
std::cin >> seed;
for(int i = 0; i < 10; i++){
generate_input();
std::cout << count3() << std::endl;
}
```
return 0;复制
```
}

题目问你有多少个内部全是\(1\)的矩阵。

我们先表示：

\(h_{i,j}\)表示\((i,j)\)这个点往上连续\(1\)的最长长度。

\(l_{i,j}\)表示从\((i,j)\)开始第一个满足\(h_{i,l_{i,j}}\le h(i,j)\)的点，如果不存在，令\(l_{i,j}=0\)。

\(r_{i,j}\)表示从\((i,j)\)开始第一个满足\(h_{i,r_{i,j}}\le h(i,j)\)的点，如果不存在，令\(r_{i,j}=m+1\)。

那么，对于\((i,j)\)为矩形底的贡献，就是\(val=(j-l_{i,j})*(r_{i,j}-j)*h_{i,j}\)。

考虑一下，这样做如何保证答案不重不漏。

不重：当且仅当在同一行存在两个数\(l_{i,j_1}=l_{i,j_2}\)并且\(r_{i,j_1}=r_{i,j_2}\)的时候，才有可能算重矩形。

但是这种情况是不存在的，因为\(l_{i,j}\)满足了左边第一个小于等于的，右边第一个小于的，显然无法构造出这种情况。

不漏：对于一个矩形，总有一个\(l_{i,j},r_{i,j}\)能框住一个矩形的两边，故这个矩形一定能被计算到。

我们可以通过一个单调栈来计算\(l_{i,j}\)和\(r_{i,j}\)，复杂度\(O(n^2)\)。

但是我写代码的时候\(sb\)了，所以用了一个单调队列来维护，但本质上是一样的。

\(program5.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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 N = 5005;
int a[N][N], h[N][N], l[N][N], r[N][N];
int seed, n, m;
int next_rand() {
  static const int P = 1000000007, Q = 83978833, R = 8523467;
  return seed = ((long long)Q * seed % P * seed + R) % P;
}
void generate_input() {
  cin >> n >> m;
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= m; j++) {
      a[i][j] = bool((next_rand() % 8) > 0);
    }
  }
}

deque <int> deq;

void push_l(int i, int j) {
  while (!deq.empty() && h[i][deq.back()] > h[i][j]) r[i][deq.back()] = j, deq.pop_back();
  deq.push_back(j);
}
void push_r(int i, int j) {
  while (!deq.empty() && h[i][deq.back()] >= h[i][j]) l[i][deq.back()] = j, deq.pop_back();
  deq.push_back(j);
}

long long count3() {
  for (rint j = 1; j <= m; j++) {
    for (rint i = 1; i <= n; i++) {
      if (a[i][j]) h[i][j] = h[i - 1][j] + 1;
      else h[i][j] = 0;
    }
  }
  long long ans = 0ll;
  for (rint i = 1; i <= n; i++) {
    while (!deq.empty()) deq.pop_back();
    for (rint j = 1; j <= m; j++) {
      push_l(i, j);
    }
    while (!deq.empty()) r[i][deq.back()] = m + 1, deq.pop_back();
    for (rint j = m; j >= 1; j--) {
      push_r(i, j);
    }
    while (!deq.empty()) l[i][deq.back()] = 0, deq.pop_back();
    for (rint j = 1; j <= m; j++) {
      //printf("l[%d][%d] = %d, r[%d][%d] = %d\n", i, j, l[i][j], i, j, r[i][j]);
      //printf("h[%d][%d] = %d\n", i, j, h[i][j]);
      ans += 1ll * (j - l[i][j]) * (r[i][j] - j) * h[i][j];
    }
  }
  return ans;
}

int main() {
  freopen("program5.in", "r", stdin);
  freopen("program5.out", "w", stdout);

  cin >> seed;
  for (rint i = 0; i < 10; i++) {
    generate_input();
    cout << count3() << endl;
  }
  return 0;
}复制

program6

#include
unsigned long long a, b, c, t, k, n;
unsigned long long rd() {
t = (t * t * a + b) % c;
return t;
}

int main() {
int i;
for (i = 0; i <= 9; i++) {
scanf("%llu %llu %llu %llu", &n, &a, &b, &c);
t = 0;
k = 1;
while (k <= n) {
k = k + 1;
rd();
}
printf("%llu\n", t);
}
}

这道题让你计算\(n\)次\(t=(t*t*a+b)\%c\)，很显然直接做是不行的。

我们考虑用\(Floyd\)判圈法。

形象的说，就是乌龟赛跑。乌龟每次走\(1\)步，兔子每次跑\(2\)步，如果这个\(t\)的取值存在循环，即图存在环，那么乌龟和兔子就会相遇。

具体见这篇博客，有讲两种判圈算法。

\(program6.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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');
}

ull n, a, b, c;

void nxt(ull &t) {
  t = (t * t * a + b) % c;
}

int main() {
  freopen("program6.in", "r", stdin);
  freopen("program6.out", "w", stdout);

  for (rint t = 0; t <= 9; t++) {
    scanf("%llu%llu%llu%llu", &n, &a, &b, &c);
    int tot = 0;
    ull x = 0, y = 0;
    do {
      tot++;
      nxt(x), nxt(y), nxt(y);
    } while (x != y);
    cerr << "meet\n";
    int cycle = 0;
    do {
      cycle++;
      nxt(x);
    } while (x != y);
    cerr << "cycle = " << cycle << '\n';
    int turns = (n - tot) % cycle;
    while (turns--) {
      nxt(y);
    }
    printf("%llu\n", y);
  }
  return 0;
}复制

program7

#include
#include
#include
using namespace std;
char s[20][20];
bool check() {
for (int i = 0; i <= 15; i++) {
bool v[16];
memset(v, false, sizeof(v));
for (int j = 0; j <= 15; j++) {
v[s[i][j] - 'A'] = true;
}
for (int j = 0; j <= 15; j++) {
if (!v[j]) {
return false;
}
}
}
for (int i = 0; i <= 15; i++) {
bool v[16];
memset(v, false, sizeof(v));
for (int j = 0; j <= 15; j++) {
v[s[j][i] - 'A'] = true;
}
for (int j = 0; j <= 15; j++) {
if (!v[j]) {
return false;
}
}
}
for (int i = 0; i <= 15; i++) {
bool v[16];
memset(v, false, sizeof(v));
for (int j = 0; j <= 15; j++) {
v[s[i / 4 * 4 + j / 4][i % 4 * 4 + j % 4] - 'A'] = true;
}
for (int j = 0; j <= 15; j++) {
if (!v[j]) {
return false;
}
}
}
return true;
}

bool dfs(int x, int y) {
if (x == 16 && y == 0) {
return check();
}
if (s[x][y] == '?') {
for (char i = 'A'; i <= 'P'; i++) {
s[x][y] = i;
if (dfs(x, y)) {
return true;
}
s[x][y] = '?';
}
return false;
} else {
return dfs(x + (y + 1) / 16, (y + 1) % 16);
}
}

void solve(int points) {
for (int i = 0; i <= 15; i++) {
scanf("%s", s[i]);
}
if (dfs(0, 0)) {
for (int k = 0; k <= points - 1; k++) {
for (int i = 0; i <= 15; i++) {
printf("%s", s[i]);
}
putchar('\n');
}
} else {
for (int k = 0; k <= points - 1; k++) {
printf("NO SOLUTION.\n");
}
}
}
int main() {
solve(1);
solve(2);
solve(3);
solve(4);
return 0;
}

这是……“字母”独？

给了你一个\(16\times 16\)的矩阵，你需要填上\(A-P\)，使得每行每列以及16个\(4\times 4\)的宫内刚好是\(A-P\)这16个字母。

正着扫当然\(TLE\)，于是我们考虑倒着扫~

倒着扫竟然只要\(3-\)秒，太神仙了！

PS: 看来以后爆搜的题目倒着扫优秀点 /cy

\(program7.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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 N = 50;
char s[N][N];
int pw[N], row[N], col[N], block[N];

int be(int x, int y) {
  return 4 * (x / 4) + (y / 4);
}

int opt = 0;
void dfs(int x, int y) {
  if (x == -1) {
    opt = 1;
    return ;
  }
  if (opt) return ;
  if (!opt && s[x][y] != '?') {
    if (y == 0) dfs(x - 1, 15);
    else dfs(x, y - 1);
  } else {
    for (rint i = 0; i <= 15; i++) {
      if (opt) return ;
      if (!opt && !((row[x] >> i) & 1) && !((col[y] >> i) & 1) && !((block[be(x, y)] >> i) & 1)) {
        row[x] ^= pw[i];
        col[y] ^= pw[i];
        block[be(x, y)] ^= pw[i];
        s[x][y] = 'A' + i;
        if (y == 0) dfs(x - 1, 15);
        else dfs(x, y - 1);
        if (opt) return ;
        s[x][y] = '?';
        row[x] ^= pw[i];
        col[y] ^= pw[i];
        block[be(x, y)] ^= pw[i];
      }
    }
  }
}
void solve(int points) {
  memset(row, 0, sizeof(row));
  memset(col, 0, sizeof(col));
  memset(block, 0, sizeof(block));
  for (rint i = 0; i <= 15; i++) {
    scanf("%s", s[i]);
    for (rint j = 0; j <= 15; j++) {
      if (s[i][j] != '?') {
        row[i] ^= pw[s[i][j] - 'A'];
        col[j] ^= pw[s[i][j] - 'A'];
        block[be(i, j)] ^= pw[s[i][j] - 'A'];
      }
    }
  }
  opt = 0, dfs(15, 15);
  if (opt == 1) {
    for (rint k = 0; k <= points - 1; k++) {
      for (rint i = 0; i <= 15; i++) {
        printf("%s", s[i]);
      }
      putchar('\n');
    }
  } else {
    for (rint k = 0; k <= points - 1; k++) {
      puts("NO SOLUTION.");
    }
  }
}

int main() {
  freopen("program7.in", "r", stdin);
  freopen("program7.out", "w", stdout);

  pw[0] = 1;
  for (rint i = 1; i <= 15; i++) pw[i] = pw[i - 1] << 1;
  solve(1), solve(2), solve(3), solve(4);
  return 0;
}复制

program8

#include
unsigned long long a, b, c, d, e, f, g, n, q, r, s, t, u, v, w, x, y, z;
unsigned long long p = 1234567891;

int main() {
scanf("%llu", &n);
a = 0;
q = 0;
r = 0;
s = 0;
t = 0;
u = 0;
v = 0;
w = 0;
x = 0;
y = 0;
z = 0;
a = 0;
while (a < n) {
a = a + 1;
b = 0;
while (b < n) {
b = b + 1;
c = 0;
while (c < n) {
c = c + 1;
d = 0;
while (d < n) {
d = d + 1;
e = 0;
while (e < n) {
e = e + 1;
f = 0;
while (f < n) {
f = f + 1;
g = 0;
while (g < n) {
g = g + 1;

                            if (a < b && b < c && c < d && d < e && e < f && f < g) {
                                q = q + 1;
                                q = q % p;
                            }                        if (a &lt; b &amp;&amp; c &lt; g &amp;&amp; c &lt; d &amp;&amp; e &lt; f &amp;&amp; a &lt; d) {
                            r = r + 1;
                            r = r % p;
                        }

                        if (a &lt; d &amp;&amp; d &lt; f &amp;&amp; c &lt; f &amp;&amp; c &lt; e &amp;&amp; b &lt; d) {
                            s = s + 1;
                            s = s % p;
                        }

                        if (d &lt; e &amp;&amp; b &lt; d &amp;&amp; a &lt; f &amp;&amp; d &lt; e &amp;&amp; b &lt; g) {
                            t = t + 1;
                            t = t % p;
                        }

                        if (c &lt; f &amp;&amp; b &lt; f &amp;&amp; b &lt; c &amp;&amp; f &lt; g &amp;&amp; b &lt; f) {
                            u = u + 1;
                            u = u % p;
                        }

                        if (b &lt; d &amp;&amp; b &lt; c &amp;&amp; d &lt; f &amp;&amp; c &lt; e &amp;&amp; b &lt; e) {
                            v = v + 1;
                            v = v % p;
                        }

                        if (a &lt; c &amp;&amp; a &lt; b &amp;&amp; c &lt; e &amp;&amp; b &lt; f &amp;&amp; e &lt; g) {
                            w = w + 1;
                            w = w % p;
                        }

                        if (b &lt; d &amp;&amp; b &lt; f &amp;&amp; a &lt; g &amp;&amp; c &lt; g &amp;&amp; a &lt; e) {
                            x = x + 1;
                            x = x % p;
                        }

                        if (b &lt; f &amp;&amp; a &lt; c &amp;&amp; c &lt; d &amp;&amp; a &lt; c &amp;&amp; b &lt; e) {
                            y = y + 1;
                            y = y % p;
                        }

                        if (d &lt; e &amp;&amp; e &lt; f &amp;&amp; a &lt; d &amp;&amp; c &lt; g &amp;&amp; b &lt; d) {
                            z = z + 1;
                            z = z % p;
                        }
                    }
                }
            }
        }
    }
}}
printf("%llu\n", q);
printf("%llu\n", r);
printf("%llu\n", s);
printf("%llu\n", t);
printf("%llu\n", u);
printf("%llu\n", v);
printf("%llu\n", w);
printf("%llu\n", x);
printf("%llu\n", y);
printf("%llu\n", z);
return 0;复制

}

仔细观察，我们就会发现，其实程序就是求了10组组合问题。组合数随便搞搞就可以得到答案。

\(program8.cpp\)

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint 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)

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');
}

ull n, p = 1234567891;

ull ksm(ull a, ull b) {
  ull res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

int main() {
  freopen("program8.in", "r", stdin);
  freopen("program8.out", "w", stdout);

  scanf("%llu", &n);
  n %= p;
  printf("%I64u\n",n>6?(n*(n-1)%p*(n-2)%p*(n-3)%p*(n-4)%p*(n-5)%p*(n-6)%p*ksm(5040,p-2)%p):0);
  printf("%I64u\n",n>1?((n-1)*(n-1)%p*n%p*n%p*(2*n-1)%p*(2*n%p*n%p-2*n%p+1+p)%p*ksm(60,p-2)%p):0);
  printf("%I64u\n",n>2?(n*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(2*n-1)%p*(7*n-3)%p*ksm(360,p-2)%p):0);
  printf("%I64u\n",n>2?(n*n%p*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(3*n-1)%p*ksm(48,p-2)%p):0);
  printf("%I64u\n",n>3?(n*n%p*n%p*n%p*(n-1)%p*(n-2)%p*(n-3)%p*ksm(24,p-2)%p):0);
  printf("%I64u\n",n>2?(n*n%p*n%p*(n-1)%p*(n-2)%p*(3*n*n%p-6*n%p+1+p)%p*ksm(60,p-2)%p):0);
  printf("%I64u\n",n>3?(n*n%p*(n-1)%p*(n-2)%p*(n-3)%p*(5*n*n%p-9*n%p+1+p)%p*ksm(360,p-2)%p):0);
  printf("%I64u\n",n>1?(n*n%p*(n-1)%p*(n-1)%p*(2*n-1)%p*(5*n%p*n%p-5*n%p+2+p)%p*ksm(144,p-2)%p):0);
  printf("%I64u\n",n>2?(n*n%p*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(2*n-1)%p*ksm(36,p-2)%p):0);
  printf("%I64u\n",n>3?(n*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(n-3)%p*(2*n-3)%p*ksm(240,p-2)%p):0);
  return 0;
}复制