A. Array and Peaks

给出一个permutation，判断能不能随意排列数组，使得peak有恰好k个。peak是指该位置的数大于相邻两个数。

思路：由k的数量为限制，k必须小于等于(n - 1) / 2。然后将前k个数放到后面即可，例如1 2 3 4 5，可以放成这样：1 5 2 4 3。

AC Code：

#include typedef long long ll;
const int N = 2e5 + 5;
int t, n, k;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> k;if(k > (n - 1) / 2) {std::cout << -1 << '\n';continue;}int num = 1;for(int i = n; i > k; i --) {if(num <= k)std::cout << num ++ << ' ';std::cout << i << ' ';}std::cout << '\n';}return 0;
}

B. AND Sequences

给出一个数组a，有多少种a的排列方式使得a数组满足上述条件。

思路：容易想到，第一个数二进制位为0的位置，后面的也必须有0，为1的地方后面必须全为1，最后一个数也是如此。所以显然，第一个数和最后一个数都是0最多的，且为1的位置其他的数也都是1，也就是两个数相等且为所有数的与和。我们可以设这个数的个数为k，则答案是。

AC Code：

#include typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int t, n;
int a[N], cnt[35];template
struct ModInt {const static int mod = T;int x;ModInt(int x = 0) : x(x % mod) {}ModInt(ll x) : x(int(x % mod)) {} int val() { return x; }ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }ModInt operator / (const ModInt &a) const { return *this * a.inv(); }void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }void operator /= (const ModInt &a) { *this = *this / a; }friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x;}ModInt pow(int64_t n) const {ModInt res(1), mul(x);while(n){if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}ModInt inv() const {int a = x, b = mod, u = 1, v = 0;while (b) {int t = a / b;a -= t * b; std::swap(a, b);u -= t * v; std::swap(u, v);}if (u < 0) u += mod;return u;}};
typedef ModInt mint;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;std::map mp;for(int i = 1; i <= n; i ++) {std::cin >> a[i];mp[a[i]] ++;}int num = a[1];for(int i = 1; i <= n; i ++) {num &= a[i];}ll cnt = mp[num];mint ans = 1;for(int i = 1; i <= n - 2; i ++) {ans *= i;}ans *= (cnt * (cnt - 1));std::cout << ans << '\n';}return 0;
}

C. Add One

给出一个数字n，进行m次操作，每次操作都对于n的每一位d用d+1替换，求m次操作后得到的数字长度是多少，答案对1e9+7取模。

思路：竟然是个dp问题。考虑令f[i]表示对10进行i次操作得到的数字长度为多少位，显然f[0~8] = 2，f[9] = 3，当i >= 10时，等于10时，是2110，分开来看，可以将21看做是对10操作了1次，10是对10操作了0次，这样得到递推式：f[i] = f[i - 9] + f[i - 10]。

AC Code：

#include typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int t, n, m;template
struct ModInt {const static int mod = T;int x;ModInt(int x = 0) : x(x % mod) {}ModInt(ll x) : x(int(x % mod)) {} int val() { return x; }ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }ModInt operator / (const ModInt &a) const { return *this * a.inv(); }void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }void operator /= (const ModInt &a) { *this = *this / a; }friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x;}ModInt pow(int64_t n) const {ModInt res(1), mul(x);while(n){if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}ModInt inv() const {int a = x, b = mod, u = 1, v = 0;while (b) {int t = a / b;a -= t * b; std::swap(a, b);u -= t * v; std::swap(u, v);}if (u < 0) u += mod;return u;}};
typedef ModInt mint;
mint f[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;for(int i = 0; i <= 8; i ++) {f[i] = 2;}f[9] = 3;for(int i = 10; i <= 200005; i ++) {f[i] = f[i - 9] + f[i - 10];}while(t --) {std::cin >> n >> m;mint ans = 0;while(n) {int num = n % 10;if(num + m < 10)ans += 1;elseans += f[num + m - 10];n /= 10;}std::cout << ans << '\n';}return 0;
}

D. GCD and MST

给出一个具有n个点的无向图和一个长为n的数组a，如果a[i] ~a[j]之前所有的数的gcd等于这之间的最小值，则i和j点之间有一条长为这个最小值的边；若i与j的差值为1，则两点之间有一条长为p的边，求这张图上的最小生成树。

思路：一个假的图论题。首先发现，其实长度为p的边已经在图中生成了一棵生成树，但不一定是最小的，所以要尽可能用第一种方式替换长度为p的边。所以可以结构体存一下每个点的值和原位置，按照大小排序，从小到大遍历，每次采用双指针向两边扩展，得到一个尽可能大的范围，在答案中减去减少的值。

AC Code：

#include typedef long long ll;
const int N = 2e5 + 5;
ll t, n, p;
ll a[N];
bool vis[N];struct node {ll num;int pos;bool operator < (const node &a) const {return num < a.num; }
} e[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> p;for(int i = 1; i <= n; i ++) {vis[i] = false;std::cin >> a[i];e[i] = {a[i], i};}std::sort(e + 1, e + 1 + n);ll ans = (n - 1) * p;for(int i = 1; i <= n; i ++) {if(e[i].num >= p) break;if(vis[e[i].pos]) continue;int l = e[i].pos, r = l;vis[l] = true;while(l > 1 && !vis[l - 1] && a[l - 1] % e[i].num == 0) vis[l --] = true;while(r < n && !vis[r + 1] && a[r + 1] % e[i].num == 0) vis[r ++] = true;ans -= (r - l) * (p - e[i].num);}std::cout << ans << '\n';}return 0;
}

os：看到题解额时候就觉得2000分的题其实也还好（逃