前情提要

成绩表


选手	总分	A	B	C	D
方**	400	100	100	100	100
陈**	307	100	100	100	7
陈**	300	100	100	100	0
朱**	299	100	99	100	0
黄**	280	100	100	80	0
李**	275	100	100	68	7
李**	269	100	100	68	1
梁**	268	100	100	68	0
完*	224	100	100	24	0
何*	219	100	100	19	0
黄嘉玮	210	100	100	0	10
许**	200	100	100	0	0
杜钊瑞	184	100	65	19	0
王书**	165	100	65	0	0
袁**	164	100	5	59	0
沈**	163	100	63	0	0
陈鑫	147	50	62	24	11
俞**	133	82	32	19	0
石**	128	56	63	9	0
张一田	120	50	63	0	7
余柏翰	111	50	56	5	0
张芮嘉	110	100	0	10	0
葛**	84	0	63	14	7
贺彦博	80	0	61	19	0
张**	56	56	0	0	0

描述

题解

T1

这就是个简单题……，我记错求 gcd 的时间复杂度了，于是没用，用了一个的算法，悲（。

code

#include <bits/stdc++.h>
#define N 100100
#define M 32000
using namespace std;
int n;
int a[N], g[N], rg[N];
int gcd(int x, int y) {
  return y == 0 ? x : gcd(y, x % y);
}
int ans = 1;
int main() {
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
	}
  for (int i = 1; i <= n; ++i) {
    g[i] = gcd(a[i], g[i - 1]);
    rg[n - i + 1] = gcd(a[n - i + 1], rg[n - i + 2]);
  }
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, gcd(g[i - 1], rg[i + 1])); 
  }
  printf("%d\n", ans);
}

T2

就直接按顺序先从小到大尝试往前排（从大到小也行），然后过程中记录有没有走过，最后记录一下步数是不是且是否按顺序就行。

我也这么想的，但是没有记录走没有走过，也没有判断步数，呵。

code

#include <bits/stdc++.h>
#define N 200010
using namespace std;
int n;
int p[N];
int rev[N];
bool vis[N];
int mem[N], cnt;
int main() {
	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", p + i);
		rev[p[i]] = i;
	}
	for (int i = n; i > 0; --i) {
    if (rev[i] < i) {
      for (int j = rev[i]; j < i; ++j) {
        if (vis[j]) {
          puts("-1");
          return 0;
        }
        mem[cnt++] = j;
        swap(rev[i], rev[p[j + 1]]);
        swap(p[j], p[j+1]);
        vis[j] = 1;
      }
    }
	}
  for (int i = 1; i <= n; ++i) {
    if (p[i] != i) {
      puts("-1");
      return 0;
    }
  }
  if (cnt != n - 1) {
    puts("-1");
    return 0;
  }
  for (int i = 0; i < cnt; ++i) {
    printf("%d\n", mem[i]);
  }
	return 0;
}

T3

这个的话把平均数看成0，然后你会发现，前后的绝对值都是从到，且前后和相等，相当于就是 dp 一下和到某个数时为某值时的种类数，前后乘一下再乘上中间的减去都是 0 的一种情况就行。但是如果你直接写的话会超时，仔细观察 dp 式子，会发现那个加和像前缀和，并且所有的集合都是不相交的，所以前缀一下再减去超过 k 个的就行。（看得懂我佩服你）

还是代码好理解。

code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
ll m;
ll f[101][510000];
int sum;
int main() {
  freopen("c.in", "r", stdin);
  freopen("c.out", "w", stdout);
  scanf("%d%d%lld", &n, &k, &m);
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    sum += i * k;
    for (int j = 0; j <= sum; ++j) f[i][j] = f[i - 1][j];
    for (int j = i; j <= sum; ++j) f[i][j] = (f[i][j] + f[i][j - i]) % m;
    int tmp = (k + 1) * i;
    for (int j = sum; j >= tmp; --j) f[i][j] = (f[i][j] - f[i][j - tmp] + m) % m;
  }
  for (int i = 1; i <= n; ++i) {
    ll ans = 0;
    for (int j = 0; j <= sum; ++j) {
      ans += f[i - 1][j] * f[n - i][j] % m;
      ans %= m;
    }
    ans = ans * (k + 1) % m;
    ans = (ans + m - 1) % m;
    printf("%lld\n", ans);
  }
  return 0;
}

T4

会发现这道题和 T2 很像，手玩一下会发现如果持续操作同一位置一定会到零。因为在第 i 位操作 a 时，a 会到 (a + i) 位，如果再有交换那个位置的只能是 a，所以最后一定是到0的。考虑倒序来，易证能轻松成功且不影响排好的。

然后我们来将这些数正过来，由于1能到处乱动，且现在的数交换都能到最后一位，所以每次将1移到最后，将数从大到小和1交换就行。

总次数是级别的，不可能不可能。

code

#include <bits/stdc++.h>
using namespace std;
int n, tot;
int a[110], rev[110];
int mem[200001], cnt;
inline void op(int x) {
  mem[cnt++] = rev[x];
  swap(a[rev[x]], a[(rev[x] + x) % n]);
  swap(rev[x], rev[a[rev[x]]]);
}
int main() {
	freopen("d.in", "r", stdin);
	freopen("d.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a + i);
		rev[a[i]] = i;
	}
  for (int i = n - 1; ~i; --i){
    while (a[i] != n - 1 - i) op(a[i]);
  }
  for (int i = 2; i < n; ++i){
    while (a[n - 1] != 1) op(1);
    op(i);
  }
  op(1);
  printf("%d\n", cnt); 
  for (int i = 0; i < cnt; ++i) {
    printf("%d\n", mem[i]);
  }
	return 0;
}

后记

没考好乎，没几天咯，嘻嘻。

Huasushis 's Blog

7.4 测试

前情提要

题解

T1

T2

T3

T4

后记