2021“MINIEYE杯”中国大学生算法设计超级联赛（1）【解题报告】

本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛（1）【解题报告】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Replay

Problem A. Mod, Or and Everything

题目大意

$T$ 组输入，每组一个整数 $n$，求 $(nmod1)OR(nmod2)OR\cdots OR(nmodn)$.

$1\le T\le 5000,1\le n\le 10^{12}$.

分析

分析个啥，直接打表找规律.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;void work()
{
//    for(int i = 1; i <= 100; ++i)
//    {
//        int s = 0;
//        for(int j = 1; j <= i; ++j) s |= i % j;
//        printf("%d: %d\n", i, s);
//    }ll n; scanf("%lld", &n);if(n == 1){printf("0\n");return;}for(ll i = 0; ; ++i){if(((1ll<<i) < n) && n <= ((1ll<<i+1))){printf("%lld\n", (1ll<<i) - 1);break;}}
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();return 0;
}

Problem B. Rocket land

Problem C. Puzzle loop

题目大意

$T$ 组输入，每组输入一个大小为 $(n-1)\times (m-1)$ 的地图，地图字符集为 { ′ 0 ′ , ′ 1 ′ , ′ . ′ } \{'0', '1', '.'\} {′0′,′1′,′.′}.

${}^{\prime }{0}^{\prime }$ 表示该格子周围四条边有偶数条红边.

${}^{\prime }{1}^{\prime }$ 表示该格子周围四条边有奇数条红边.

${}^{\prime }{.}^{\prime }$ 表示该格子周围四条边无限制.

要求红边形成若干个边不相交的环，求方案数.

$1\le T\le 100,1\le n,m\le 17$.

分析

红边实质上就是若个干不相交的欧拉路嘛，因此要求每个交点的度为偶数，这样便满足了形成若干个边不相交的环这一条件.

此外对每个格子的四条边建异或方程.

于是得到异或方程组，高斯消元即可.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e6;
const int N = (int)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bool a[2 * (N + 1) * (N + 1) + 5][2 * N * (N + 1) + 5];inline int id(int x1, int y1, int x2, int y2)
{if(x1 > x2) swap(x1, x2);if(y1 > y2) swap(y1, y2);if(x1 == x2) return (x1 - 1) * m + y1;else         return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}void build()
{row = 0, col = (n + 1) * m + n * (m + 1);for(int i = 1; i <= n + 1; ++i){for(int j = 1; j <= m + 1; ++j){++row;for(int k = 1; k <= col + 1; ++k) a[row][k] = 0;for(int k = 0, x, y; k < 4; ++k){x = i + dx[k], y = j + dy[k];if(x < 1 || x > n + 1 || y < 1 || y > m + 1)    continue;a[row][id(x, y, i, j)] = 1;}}}for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){if(s[i][j] == '.') continue;++row;for(int k = 1; k <= col + 1; ++k) a[row][k] = 0;a[row][id(i, j, i, j + 1)] = 1;a[row][id(i, j, i + 1, j)] = 1;a[row][id(i, j + 1, i + 1, j + 1)] = 1;a[row][id(i + 1, j, i + 1, j + 1)] = 1;a[row][col + 1] = s[i][j] - '0';}}
//    for(int i = 1; i <= row; ++i)
//    {
//        bool f = 0;
//        for(int j = 1; j <= col; ++j)
//        {
//            if(!a[i][j])    continue;
//            if(f) printf(" ^ ");
//            printf("x(%d)", j);
//            f = 1;
//        }
//        printf(" = 0\n");
//    }
}int gauss(int n, int m)
{int c, r;for(c = 1, r = 1; c <= m; ++c){int t = r;for(int i = r; i <= n; ++i){if(a[i][c])   t = i;}if(!a[t][c]) continue;for(int i = c; i <= m + 1; ++i) swap(a[t][i], a[r][i]);for(int i = 1; i <= n; ++i){if(i == r)  continue;if(a[i][c]){for(int j = m + 1; j >= c; --j){a[i][j] ^= a[r][j];}}}++r;}for(int i = r; i <= n; ++i){if(a[i][m + 1])   return -1;//无解}return m - r + 1;//自由元个数
}ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s;
}void work()
{scanf("%d %d", &n, &m);--n, --m;for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);build();int r = gauss(row, col);if(r == -1) printf("0\n");else        printf("%lld\n", quick(2, r));
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

bitset 优化

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e6;
const int N = (int)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bitset<614> a[2 * (N + 1) * (N + 1) + 5];inline int id(int x1, int y1, int x2, int y2)
{if(x1 > x2) swap(x1, x2);if(y1 > y2) swap(y1, y2);if(x1 == x2) return (x1 - 1) * m + y1;else         return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}void build()
{row = 0, col = (n + 1) * m + n * (m + 1);for(int i = 1; i <= n + 1; ++i){for(int j = 1; j <= m + 1; ++j){++row;a[row].reset();for(int k = 0, x, y; k < 4; ++k){x = i + dx[k], y = j + dy[k];if(x < 1 || x > n + 1 || y < 1 || y > m + 1)    continue;a[row].set(id(x, y, i, j));}}}for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){if(s[i][j] == '.') continue;++row;a[row].reset();a[row].set(id(i, j, i, j + 1));a[row].set(id(i, j, i + 1, j));a[row].set(id(i, j + 1, i + 1, j + 1));a[row].set(id(i + 1, j, i + 1, j + 1));a[row].set(col + 1, s[i][j] - '0');}}
//    for(int i = 1; i <= row; ++i)
//    {
//        bool f = 0;
//        for(int j = 1; j <= col; ++j)
//        {
//            if(!a[i][j])    continue;
//            if(f) printf(" ^ ");
//            printf("x(%d)", j);
//            f = 1;
//        }
//        printf(" = 0\n");
//    }
}int gauss(int n, int m)
{int c, r;for(c = 1, r = 1; c <= m; ++c){int t = r;for(int i = r; i <= n; ++i){if(a[i][c])   t = i;}if(!a[t][c]) continue;swap(a[t], a[r]);for(int i = 1; i <= n; ++i){if(i == r)  continue;if(a[i][c]) a[i] ^= a[r];}++r;}for(int i = r; i <= n; ++i){if(a[i][m + 1])   return -1;//无解}return m - r + 1;//自由元个数
}ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s;
}void work()
{scanf("%d %d", &n, &m);--n, --m;for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);build();int r = gauss(row, col);if(r == -1) printf("0\n");else        printf("%lld\n", quick(2, r));
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem D. Another thief in a Shop

题目大意

$T$ 组输入，每组给 $n$ 和 $k$.

有 $n$ 个物品，价值分别为 $a[1],a[2],\cdots ,a[n]$，每件物品有无穷多件.

求拼凑出总价值为 $k$ 的方案数.

$1\le T\le 100,1\le n\le 100,1\le k\le 10^{18},1\le a[i]\le 10$.

分析

设 $f[i][j]$ 表示考虑了前 $i$ 个物品，总价值为 $j$ 的方案数.

则有状态转移方程 $\begin{array}{r}f[i][j]=\sum _{l=0}^{\lfloor \frac{j}{a[i]}\rfloor }f[i-1][j-l\times a[i]]\end{array}$.

接下来这一步被题解惊艳到了，拉格朗日插值！！！

但体会一下也就明白了，还是很妙的感觉.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e2;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;int n; ll k;
int a[M + 5];
int f[N + 5];
int y[M + 5];
int pre[M + 5];
int suf[M + 5];
int fac[M + 5];
int inv[M + 5];
int invfac[M + 5];void init()
{fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;for(int i = 2; i <= M; ++i){fac[i] = 1ll * fac[i - 1] * i % mod;inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;}
}int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}int Lagrange(int n, ll k)
{if(k <= n + 1) return y[k];pre[0] = 1;     for(int i = 1; i <= n + 1; ++i) pre[i] = (k - i) % mod * pre[i - 1] % mod;suf[n + 2] = 1; for(int i = n + 1; i >= 1; --i) suf[i] = (k - i) % mod * suf[i + 1] % mod;int ans = 0, cur;for(int i = 1; i <= n + 1; ++i){cur = 1ll * pre[i - 1] * suf[i + 1] % mod * invfac[i - 1] % mod * invfac[n + 1 - i] % mod;if(n + 1 - i & 1) cur *= -1;cur = 1ll * cur * y[i] % mod;ans = (ans + cur) % mod;}ans = (ans % mod + mod) % mod;return ans;
}void work()
{scanf("%d %lld", &n, &k);int lcm = 1;for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), lcm = lcm / gcd(lcm, a[i]) * a[i];memset(f, 0, sizeof(f)); f[0] = 1;int r = lcm * n;for(int i = 1; i <= n; ++i){for(int j = a[i]; j <= r; ++j) f[j] = (f[j] + f[j - a[i]]) % mod;}for(int i = k % lcm; i < r; i += lcm) y[i / lcm + 1] = f[i];printf("%d\n", Lagrange(n - 1, k / lcm + 1));
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);init();int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem E. Minimum spanning tree

题目大意

$T$ 组输入，每组给出一个 $n$.

点的编号为 $1,2,\cdots ,n$，点 $a$ 与 点 $b$ 的权值定义为 $lcm(a,b)$.

求这个图的最小生成树.

$1\le T\le 10^2,2\le n\le 10^7$.

分析

显然合数与它的因子连边，质数与 $2$ 连边最优.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e7;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;int cnt, prime[M + 5];
bool is_prime[M + 5];
ll f[M + 5];void init()
{memset(is_prime, 1, sizeof(is_prime));cnt = is_prime[0] = is_prime[1] = 0;for(int i = 2; i <= M; ++i){if(is_prime[i]) prime[++cnt] = i;for(int j = 1; j <= cnt && i * prime[j] <= M; ++j){is_prime[i * prime[j]] = 0;if(i % prime[j] == 0) break;}}f[2] = 0;for(int i = 3; i <= M; ++i){if(is_prime[i]) f[i] = f[i - 1] + 2 * i;else            f[i] = f[i - 1] + i;}
}void work()
{int n; scanf("%d", &n);printf("%lld\n", f[n]);
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);init();int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();return 0;
}

Problem F. Xor sum

题目大意

$T$ 组输入，每组输入有两个整数 $n$ 和 $k$，接下来 $n$ 个整数表示 $a[1],a[2],\cdots ,a[n]$.

要求找一段区间，使得这段区间的异或和不小于 $k$，若不存在则输出 $-1$，存在则找到满足上述条件最短的区间，若仍不唯一，则输出最靠左的区间.

$1\le T\le 10^2,1\le n\le 10^5,0\le k,a[i]<2^{30}$.

分析

记 $s[i]=a[1]XORa[2]XOR\cdots XORa[i]$.

则区间 $[l,r]$ 异或和不小于 $k$ 等价于 $s[r]XORs[l-1]$ 不小于 $k$.

因此字典树维护 $s[i]$，节点记录当前最新的时间戳，对于两边都能走的情况就选择最新的时间戳走.

详见代码.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e5;
const int N = (int)29;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;struct tnode
{int nx[2], stamp;
} tree[M * 31 + 5];
int cnt;int n, k;void insert(int p, int d, int x, int stamp)
{if(d == -1) return;int v = (x>>d&1);if(!tree[p].nx[v]){tree[p].nx[v] = ++cnt;tree[tree[p].nx[v]].nx[0] = 0;tree[tree[p].nx[v]].nx[1] = 0;tree[tree[p].nx[v]].stamp = 0;}tree[p].stamp = stamp;insert(tree[p].nx[v], d - 1, x, stamp);if(d == 0){tree[tree[p].nx[v]].stamp = stamp;}
}inline int setZero(int x, int k)
{return x&(~(1<<k));
}inline int setOne(int x, int k)
{return x|(1<<k);
}int queryMx(int x, int p, int d)
{for(int i = d, v; i >= 0; --i){v = (x>>i&1);if(tree[p].nx[!v]) p = tree[p].nx[!v], x = setOne(x, i);else               p = tree[p].nx[v], x = setZero(x, i);}return x;
}int mi, l, r;void query(int x, int stamp, bool f = 0)
{int p = 0;for(int i = N, vk, vx; i >= 0; --i){vk = (k>>i&1);vx = (x>>i&1);bool canZero = 0, canOne = 0;if(tree[p].nx[vx])  canZero = queryMx(setZero(x, i), tree[p].nx[vx], i - 1) >= k;if(tree[p].nx[!vx]) canOne = queryMx(setOne(x, i), tree[p].nx[!vx], i - 1) >= k;if(canZero && canOne){if(tree[tree[p].nx[vx]].stamp > tree[tree[p].nx[!vx]].stamp) p = tree[p].nx[vx], x = setZero(x, i);else                                                         p = tree[p].nx[!vx], x = setOne(x, i);}else if(canZero)    p = tree[p].nx[vx], x = setZero(x, i);else if(canOne)     p = tree[p].nx[!vx], x = setOne(x, i);else                return;}if(mi > stamp - tree[p].stamp){mi = stamp - tree[p].stamp;l = tree[p].stamp + 1, r = stamp;}
}void work()
{mi = inf, l = -1, r = -1;cnt = tree[0].nx[0] = tree[0].nx[1] = tree[0].stamp = 0;scanf("%d %d", &n, &k);insert(0, N, 0, 0);int s = 0;for(int i = 1, a; i <= n; ++i){scanf("%d", &a);s ^= a;query(s, i);insert(0, N, s, i);}if(mi == inf) printf("-1\n");else          printf("%d %d\n", l, r);
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();return 0;
}

Problem G. Pass!

题目大意

$T$ 组输入，每组有两个整数 $n$ 和 $x$.

一共有 $n$ 个人和 $1$ 个球，初始球在第 $1$ 人脚下，每秒拥有球的那个人会把球传给另一个人.

经过 $t$ 秒后，球又回到了第 $1$ 个人脚下，方案数为 $x$.

现在给出 $x$ 要求反解最小非负整数 $t$.

分析

设 $f[i][0]$ 表示第 $i$ 秒末球不在第 $1$ 个人脚下的方案数，
$f[i][1]$ 表示第 $i$ 秒末球在第 $1$ 个人脚下的方案数.

则有如下转移方程：

$$\{\begin{array}{rl}f[0][1]& =1\\ f[i][0]& =(n-2)f[i-1][0]+(n-1)f[i-1][1]\\ f[i][1]& =f[i-1][0]\end{array}\to \{\begin{array}{rl}f[1][0]& =n-1\\ f[2][0]& =(n-1)(n-2)\\ f[i][0]& =(n-2)f[i-1][0]+(n-1)f[i-2][0]i\ge 3\end{array}$$

学了一下二阶线性递推式的通项求法，夙愿清单减减.

于是可以得到 $f[i][0]$ 的解析式为 $f[i][0]=\frac{(n-1{)}^2}{n}(n-1{)}^{i-1}+\frac{n-1}{n}(-1{)}^{i-1}$.

又由 $f[i][1]=f[i-1][0]$ 得

$$\begin{array}{rl}f[i][1]& =f[i-1][0]\\ & =\frac{(n-1{)}^2}{n}(n-1{)}^{i-2}+\frac{n-1}{n}(-1{)}^{i-2}i\ge 0\\ & =\{\begin{array}{rl}\frac{(n-1{)}^i}{n}& -\frac{n-1}{n}i为奇数\\ \frac{(n-1{)}^i}{n}& +\frac{n-1}{n}i为偶数\end{array}\\ & =\{\begin{array}{rl}\frac{(n-1{)}^{2k+1}}{n}& -\frac{n-1}{n}i=2k+1,k\ge 0\\ \frac{(n-1{)}^{2k}}{n}& +\frac{n-1}{n}i=2k,k\ge 0\end{array}\\ & \stackrel{即解}{⟶}\{\begin{array}{rl}(n-1{)}^{2k}& \equiv \frac{nx+n-1}{n-1}(modp)\\ (n-1{)}^{2k}& \equiv nx-n+1(modp)\end{array}\end{array}$$

至此套上 BSGS 即可.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;struct hashTable
{const static int M = (int)1e5;const static int N = (int)31601;int head[N + 5], cnt;struct node{int v, w, nx;} a[M + 5];void init(){cnt = 0;memset(head, -1, sizeof(head));}void add(int v, int w){for(int i = head[w % N]; ~i; i = a[i].nx){if(a[i].w == w){a[i].v = v;return;}}a[cnt].v = v;a[cnt].w = w;a[cnt].nx = head[w % N];head[w % N] = cnt++;}int tofind(int w){for(int i = head[w % N]; ~i; i = a[i].nx){if(a[i].w == w) return a[i].v;}return -1;}
} H;struct LOG
{ll quick(ll a, ll b, ll p = mod){ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s;}ll inv(ll n, ll p = mod){return quick(n, p - 2, p);}int k = 31596, t;void init(int a, int p){H.init();for(int i = 0, j = 1; i < k; ++i){H.add(i, j);j = 1ll * j * a % p;}t = quick(a, k, p);}int BSGS(int a, int b, int p){a = (1ll * a % p + p) % p, b = (1ll * b % p + p) % p;if(b == 1)  return 0;for(int i = 1, j = t * inv(b, p) % p, h; i <= k; ++i){h = H.tofind(j);if(~h && 1ll * k * i > h && !((1ll * k * i - h)&1)) return 1ll * k * i - h;j = 1ll * j * t % p;}return -1;}
} B;int n, x;int calOdd()
{int a = (1ll * n * x % mod + n - 1 + mod) % mod * B.inv(n - 1) % mod;int x = B.BSGS(n - 1, a, mod);if(x == -1) return inf;return x + 1;
}int calEven()
{int a = (1ll * n * x % mod - n + 1 + mod) % mod;int x = B.BSGS(n - 1, a, mod);if(x == -1) return inf;return x;
}void work()
{scanf("%d %d", &n, &x);B.init(n - 1, mod);int odd = calOdd(), even = calEven();int mi = min(odd ,even);if(mi == inf)   printf("-1\n");else            printf("%d\n", mi);
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem H. Maximal submatrix

题目大意

$T$ 组输入，每组输入一个 $n\times m$ 的矩阵.

求一个最大子矩阵，这个子矩阵每一列中的元素递增，输出最大子矩阵的大小.

$1\le T\le 10,1\le n,m\le 2000$.

分析

单调栈经典题了.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)2e3;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;int n, m;
int a[M + 5][M + 5];
int b[M + 5][M + 5];int s[M + 5], w[M + 5], p;int cal(int a[])
{a[m + 1] = p = 0;int ans = 0;for(int i = 1; i <= m + 1; ++i){if(a[i] > s[p]){s[++p] = a[i], w[p] = 1;}else{int width = 0;while(s[p] > a[i]){width += w[p];ans = max(ans, width * s[p]);p--;}s[++p] = a[i], w[p] = width + 1;}}return ans;
}void work()
{scanf("%d %d", &n, &m);for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);for(int j = 1; j <= m; ++j){b[1][j] = 1;for(int i = 2; i <= n; ++i){if(a[i][j] >= a[i - 1][j]) b[i][j] = b[i - 1][j] + 1;else                       b[i][j] = 1;}}int mx = 0;for(int i = 1; i <= n; ++i){mx = max(mx, cal(b[i]));}printf("%d\n", mx);
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();return 0;
}

Problem I. KD-Graph

题目大意

$T$ 组输入，每组输入 $n,m,k$ 表示 $n$ 个点 $m$ 条边的有权联通无向图.

接下来 $m$ 行，每行三个整数 $u,v,w$ 表示无向边的两个端点和边权.

一个图被称为 KD 图当且仅当 $n$ 个点可以不重不漏地分成 $K$ 组且组内两两点之间存在一条路径，满足这条路径的最大边权小于等于 $D$，不同组的每两点则不存在这样的路径.

要求计算最小的非负整数 $D$，若不存在输出 $-1$.

分析

赛时一开始二分 + BFS，结果 TLE…

换成二分 + 并查集，常数小了点，得到 AC.

代码实现

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;inline int read()
{int x = 0, f = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e5;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;int n, m, k;struct enode
{int u, v, w;
} Edge[N + 5];int fa[M + 5];
int rk[M + 5];int tofind(int x)
{if(x == fa[x])  return x;return fa[x] = tofind(fa[x]);
}int cal(int lim)
{for(int i = 1; i <= n; ++i) fa[i] = i;for(int i = 1, u, v; i <= m; ++i){u = Edge[i].u, v = Edge[i].v;if(Edge[i].w <= lim){u = tofind(u), v = tofind(v);if(u != v){if(rk[u] > rk[v]) swap(u, v);fa[u] = v, rk[v] = max(rk[v], rk[u] + 1);}}}int cnt = 0;for(int i = 1; i <= n; ++i) if(fa[i] == i)  ++cnt;return cnt;
}void work()
{n = read(), m = read(), k = read();int l = 0, r = 0, mid;for(int i = 1; i <= m; ++i){Edge[i].u = read(), Edge[i].v = read(), Edge[i].w = read();r = max(r, Edge[i].w);}while(l < r){mid = (l + r) >> 1;if(cal(mid) <= k)   r = mid;else                l = mid + 1;}if(cal(r) == k) printf("%d\n", r);else            printf("-1\n");
}int main()
{
//    cout << 5 * log2(inf) * (M + 2 * N) << "\n";
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T = read();for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem J. zoto

题目大意

$T$ 组输入，每组输入 $n,m$ 表示二维平面上有 $n$ 个整数点和 $m$ 次询问.

接下来 $n$ 行，每行一个非负整数 $fx[i]$，表示有一个整数点 $(i,fx[i])$.

接下来 $m$ 行，每行四个整数 $x0,y0,x1,y1$ 表示查询 $(x0,y0)$ 与 $(x1,y1)$ 围成的矩阵里有多少个不同的 $y$ 值.

$1\le T\le 5,1\le n,m,x0,x1\le 10^5,0\le fx[i],y0,y1\le 10^5$.

分析

一开始用莫队 + 线段树喜提 TLE.

正解是莫队 + 分块.

分块支持 $O(1)$ 修改 + $O(\sqrt{10^5})$ 查询.

小收获：莫队的修改次数很多，查询次数较少，应选择修改较快的数据结构进行维护.

代码实现

#include <bits/stdc++.h>
using namespace std;inline int read()
{int x = 0, f = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}void print(int n)
{if(n < 0){putchar('-');print(-n);}else{if(n > 9) print(n / 10);putchar(n % 10 + '0');}
}typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e5;
const int N = (int)320;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;int n, m, xblock, yblock, yblockCnt;
int a[M + 5];
int ans[M + 5];struct qnode
{int l, r, a, b, id;bool operator<(const qnode& b)const{return l / xblock == b.l / xblock ? (r == b.r ? 0 : ((l / xblock) & 1) ^ (r < b.r)) : l < b.l;}
} q[M + 5];int id[M + 5];
int num[M + 5];
int nums[N + 5];
int mx;void init()
{yblock = (int)sqrt(mx), yblockCnt = (mx + yblock) / yblock;for(int i = 0; i <= mx; ++i){id[i] = i / yblock;num[i] = 0;}for(int i = 0; i < yblockCnt; ++i) nums[i] = 0;
}void add(int x)
{if(++num[a[x]] == 1) ++nums[id[a[x]]];
}void del(int x)
{if(--num[a[x]] == 0) --nums[id[a[x]]];
}int query(int l, int r)
{int ans = 0;if(id[r] - id[l] + 1 <= 2){for(int i = l; i <= r; ++i) if(num[i]) ++ans;}else{for(int i = l; i <= n && id[i] == id[l]; ++i) if(num[i]) ++ans;for(int i = r; i >= 1 && id[i] == id[r]; --i) if(num[i]) ++ans;for(int i = id[l] + 1; i < id[r]; ++i) ans += nums[i];}return ans;
}void work()
{n = read(), m = read(); xblock = (int)sqrt(n);for(int i = 1; i <= n; ++i) a[i] = read();mx = 1;for(int i = 1; i <= m; ++i){q[i].l = read(), q[i].a = read(), q[i].r = read(), q[i].b = read();mx = max(mx, q[i].b);q[i].id = i;}init();sort(q + 1, q + m + 1);int l = 1, r = 0;for(int i = 1; i <= m; ++i){while(r < q[i].r) add(++r);while(r > q[i].r) del(r--);while(l < q[i].l) del(l++);while(l > q[i].l) add(--l);ans[q[i].id] = query(q[i].a, q[i].b);}for(int i = 1; i <= m; ++i) print(ans[i]), putchar('\n');
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem K. Necklace of Beads

题目大意

$T$ 组输入，每组给出 $n$ 和 $k$.

有红蓝绿三种颜色的珠子，红蓝珠子有无穷多个，绿色珠子只有 $k$ 个，要求串成 $n$ 个珠子的项链.

两个项链如果可以通过旋转得到则认为是一种方案.

求方案数.

$1\le T\le 10,1\le n,k\le 10^6$.

分析

显然Burnside 引理，于是

$$\begin{array}{rl}ANS& =\frac{1}{n}\sum _{i=0}^{n-1}\sum _{j=0}^{\lfloor \frac{k}{n/gcd(n,i)}\rfloor }f(gcd(n,i),j)\\ & =\frac{1}{n}\sum _{d=1}^n\phi (\frac{n}{d})\sum _{j=0}^{\lfloor \frac{k}{n/d}\rfloor }f(d,j)\end{array}$$

$f(n,m)$ 表示长度为 $n$ 的环，绿色珠子有 $m$ 个的合法方案数.

$g(n,m)$ 表示长度为 $n$ 的序列，选 $m$ 个互不相邻位置的方案数.

对绿色珠子的位置分类讨论：

1. 假设绿色珠子放在 $1$ 号位置，则 $2,n$ 这两个位置不能放绿色珠子，并且绿色珠子把环分割为 $m$ 段，每段的方案数为 $2$，因此总方案数为 $g(n-3,m-1)\times 2^m$.
2. 假设绿色珠子放在 $n$ 号位置，根据对称性，方案数同 $1.$
3. 除上述两种情况之外，方案数为 $g(n-2,m)\times 2^m$.

因此 $f(n,m)=g(n-3,m-1)\times 2^{m+1}+g(n-2,m)\times 2^m$.

由插空法可得 $g(n,m)=\left(\genfrac{}{}{0ex}{}{n-m+1}{m}\right)$.

$O(10^6)$ 预处理出欧拉函数和阶乘，逆元，阶乘逆元.

时间复杂度 $O(10^6+T\sqrt{n})$.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)1e6;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;bool is_prime[M + 5];
int cnt, prime[M + 5];
int phi[M + 5];
int fac[M + 5], inv[M + 5], invfac[M + 5];void init()
{phi[1] = 1;memset(is_prime, 1, sizeof(is_prime));cnt = is_prime[0] = is_prime[1] = 0;fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;for(int i = 2; i <= M; ++i){fac[i] = 1ll * fac[i - 1] * i % mod;inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;if(is_prime[i]){prime[++cnt] = i;phi[i] = i - 1;}for(int j = 1; j <= cnt && i * prime[j] <= M; ++j){is_prime[i * prime[j]] = 0;if(i % prime[j] == 0){phi[i * prime[j]] = phi[i] * prime[j];break;}phi[i * prime[j]] = phi[i] * (prime[j] - 1);}}
}int c(int n, int m)
{if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}void work()
{int n, k; scanf("%d %d", &n, &k);int ans = 0;for(int d = 1, two, r, f, dd; 1ll * d * d <= n; ++d){if(n % d)   continue;two = 1, r = 1ll * k * d / n, f = (!(d&1)) * 2;for(int j = 1; j <= r; ++j){two = 2ll * two% mod;f = (f + 2ll * two * c(d - j - 1, j - 1) + 1ll * two * c(d - j - 1, j)) % mod;}ans = (ans + 1ll * f * phi[n / d]) % mod;if(d * d == n)  continue;dd = n / d;two = 1, r = 1ll * k * dd / n, f = (!(dd&1)) * 2;for(int j = 1; j <= r; ++j){two = 2ll * two% mod;f = (f + 2ll * two * c(dd - j - 1, j - 1) + 1ll * two * c(dd - j - 1, j)) % mod;}ans = (ans + 1ll * f * phi[n / dd]) % mod;}ans = 1ll * ans * inv[n] % mod;printf("%d\n", ans);
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);init();int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){
//        printf("Case #%d:\n", ca);work();}
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛（1）【解题报告】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---