2021"MINIEYE杯"中超(1)
1.1001 Mod, Or and Everything
考点：二进制
思路：分析两个例子：
n = 8， 那么有8 mod 8 == 0，8 mod 7 == 1，8 mod 6 == 2，8 mod 5 == 3，8 mod 4 == 0
之后再往下mod的话，所有值都是已经出现过的了，也就是说如果样例是8的话，那么答案那就是0|1|2|3的结果。
n = 9， 如上例分析，最后结果应该为0|1|2|3|4的结果。
综上我们可以知道如果输入为n，那么答案应该是0|1|...|(n - 1) / 2。接着想一下|运算，即有1出1，而且因为|运算的各个值是从小到大来的，所以只需考虑最大值的位数即可，如n=9时，最大|运算的数是4即(100)，那么前两位都可以取到1，因为有4说明有3，2，1也参与了运算。
结论：只需考虑参加或运算的数中的最大值，统计max的位数，结果就是1 << 位数 - 1
不开long long见神仙。
#include <iostream>
using namespace std;
typedef long long LL;
int t;
LL x;
LL cal(LL u)//统计位数
{
int cnt = 0;
while (u)
{
cnt ++ ;
u >>= 1;
}
return cnt;
}
int main()
{
cin >> t;
while (t -- )
{
cin >> x;
cout << (1ll << cal((x - 1) / 2)) - 1 << endl;
}
return 0;
}
2.1005 Minimum spanning tree
看数据范围，不可能是prim / kruskal，就想着找规律。
边权为lcm(a, b)即a * b / gcd(a, b)。点从2开始，每个质数最佳情况是连2，边权为2 * prime，合数只需连接自己的任意一个质因子即可，边权值与合数相等。所以ans = 质数 * 2 + 合数
提交的时候记得选G++， 选C++会tle....
做法：线性筛
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10000000;
typedef long long LL;
int t;
bool st[N + 5];
int primes[N + 5], cnt;
LL n;
int main()
{
for (int i = 2; i <= N; i ++ )//线性筛
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= N / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
cin >> t;
while (t -- )
{
cin >> n;
LL ans = 0;
for (LL i = 3; i <= n; i ++ )
if (!st[i]) ans += i * 2;
else ans += i;
cout << ans << endl;
}
return 0;
}
3.1006 Xor sum
看到区间异或，就想到异或前缀和 + trie树，但是用的不熟练，比赛没做出来。
思路：把题面转化成求s[l - 1] ^ s[r] >= k的最短距离，我们枚举右边终点，左边s[0] ~ s[i - 1]都是已经插入到trie树上的，之所以s[0] = 0也在树中是因为可能存在一种情况是整个序列异或在一起，所以我们要插入0来保证这种情况取得到。对于k，我们可以看它的二进制表示，从高位开始，假如某一位k的二进制是1，那么此时异或结果一定要是1才可以，如果k本位是0，那么如果此时异或结果可以是1，那么就说明有一个合法方案，取此方案。
要用pos来储存每个点在序列中的位置。每次初始化放在插入时，否则会超时。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 3200010, M = 1e5 + 10;
int t;
int son[N][2], idx;//trie树
int pos[N];//每个结点对应的序列下标
int n, k;
int s[M];//异或前缀和
void solve()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &s[i]);
s[i] ^= s[i - 1];
}
int l = -1, r = n;//存答案
int idx = 1;//trie起点
son[1][0] = son[1][1] = 0;//初始化
pos[1] = -1;
for (int i = 0; i <= n; i ++ )//依次询问s[i]并插入s[i]
{
int p = 1;
int ans = -1;
for (int j = 31; j >= 0; j -- )
{
int u = (s[i] >> j) & 1;
if ((k >> j) & 1)//k本位为1
p = son[p][u ^ 1];//只能走这里,如果没路,就break掉
else
{
if (son[p][u ^ 1])//如果异或结果是1
ans = max(ans, pos[son[p][u ^ 1]]);//记录靠右的左边界
p = son[p][u];//另一个分支记录过答案了,不需要进入那个分支
}
if (!p) break;
}
if (p) ans = max(ans, pos[p]);
if (ans >= 0 && (i - ans < r - l)) r = i, l = ans;//如果记录到了新方案,就取更优
p = 1;//插入操作
for (int j = 31; j >= 0; j -- )
{
int u = (s[i] >> j) & 1;
if (!son[p][u])//如果没有这个分支
{
son[p][u] = ++ idx;//插入字典树
son[idx][0] = son[idx][1] = 0;
pos[idx] = -1;
}
p = son[p][u];
pos[p] = max(pos[p], i);
}
}
if (l >= 0) printf("%d %d
", l + 1, r);
else printf("-1
");
}
int main()
{
scanf("%d", &t);
while (t -- ) solve();
return 0;
}
4.1008 Maximal submatrix
前置知识：直方图中最大的矩形(知识点涉及：单调栈)
各矩形高分别为：2 1 4 5 1 3 3，那么我们从h[1]开始，假设矩形高为h[i]，向左右扩展直至扩展不了，蓝色框住的部分即为从h[1]扩展的情况，绿色部分为h[2]扩展的情况，依此类推。依次扩展结束后，我们将所得矩形面积取一个max即为答案。
换句话说，对于每个h[i]，我们要找到它左边第一个比它低的位置，找到右边第一个比它低的位置，然后所得到的这个范围是L，那么此次得到的矩形面积即为L * h[i]。那么每次求左边(右边)第一个比它低的位置我们可以用单调栈来维护。假设i < j，且h[i] >= h[j]，那么h[k] (k > j)寻找左边第一个比它小的高度时一定访问不到h[i]，因为h[j]一定是比它更优的，所以我们可以用栈来维护序列，将大于等于h[i]的栈顶弹出。
题目大意:输入n个矩形高度，求最大矩形面积。
code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int h[N], stk[N], le[N], ri[N];
void get_len(int k[])
{
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt > 0 && h[stk[tt]] >= h[i]) tt -- ;
k[i] = stk[tt];
stk[++ tt] = i;
}
}
int main()
{
while (cin >> n, n)
{
for (int i = 1; i <= n; i ++ ) cin >> h[i];
get_len(le);
reverse(h + 1, h + n + 1);
get_len(ri);
//这里注意h已经翻转了,所以le[]对应的要翻转一下!
long long ans = 0;
for (int i = 1, j = n; i <= n; i ++ , j -- )
ans = max(ans, 1ll * h[i] * (n - ri[i] - le[j]));
cout << ans << endl;
}
return 0;
}
本题思路：
本题让我们求不下降子序列构成的矩形的最大面积，我们可以统计出h[i, j]与h[i - 1, j]的大小关系，然后对于每一排跑一遍上面求正方图中最大矩形面积的代码然后取max即可。
code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10;
int t;
int h[N][N];
int hh[N][N];
int n, m;
int stk[N], l[N], r[N];
void get_len(int q[], int ro)
{
int tt = 0;
for (int i = 1; i <= m; i ++ )
{
while (tt > 0 && hh[ro][stk[tt]] >= hh[ro][i]) tt -- ;
q[i] = stk[tt];
stk[++ tt] = i;
}
}
int main()
{
scanf("%d", &t);
while (t -- )
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &h[i][j]);
for (int i = 1; i <= n; i ++ )//转化为正方图问题
for (int j = 1; j <= m; j ++ )
if (h[i][j] >= h[i - 1][j]) hh[i][j] = hh[i - 1][j] + 1;
else hh[i][j] = 1;
//for (int i = 1; i <= n; i ++ )
// for (int j = 1; j <= m; j ++ ) printf("%d%c", hh[i][j], j == m ? '
': ' ');
int ans = 0;
for (int i = 1; i <= n; i ++ )//对每一行求一次最大面积
{
get_len(l, i);
reverse(hh[i] + 1, hh[i] + m + 1);
get_len(r, i);
for (int j = 1, k = m; j <= m; j ++ , k -- )
{
ans = max(ans, hh[i][j] * (m - l[k] - r[j]));
//cout << hh[i][j] * (m - l[k] - r[j]) << ' ';
}
}
printf("%d
", ans);
}
return 0;
}
5.1009 KD-Graph
思路：要求将点分成k组，然后组内存在len <= D的边，组间不存在len <= D的边。我们可以删除大于D的边，然后统计连通块个数即可，换个思路我们可以连接小于等于D的边，然后统计连通块个数，如果权值为w的所有边都连接完了此时连通块数目是k的话那么输出答案就是w。如果对于某个权值w，没连接它时连通块大于k个，连完之后小于k个，那么没有答案，输出-1。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int t;
int p[N];
int n, m, k;
struct node
{
int l, r, w;
bool operator< (const node& A)const
{
return w < A.w;
}
}seg[N * 5];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void solve()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &seg[i].l, &seg[i].r, &seg[i].w);
for (int i = 1; i <= n; i ++ ) p[i] = i;
sort(seg + 1, seg + m + 1);
//for (int i = 1; i <= m; i ++ ) cout << seg[i].l << ' ' << seg[i].r << ' ' << seg[i].w << endl;
int cnt = n, ans = 0;
for (int i = 1; i <= m; i ++ )
{
if (seg[i].w != seg[i - 1].w)//与前面的不同权重,有答案则跳出
{
if (cnt == k)
{
printf("%d
", ans);
return;
}
}
if (find(seg[i].l) == find(seg[i].r)) continue;//已经在一个连通块中
cnt -- ;//否则连通块数量 --
p[find(seg[i].l)] = find(seg[i].r);
ans = seg[i].w;
}
printf("%d
", cnt == k ? ans : -1);
}
int main()
{
scanf("%d", &t);
while (t -- ) solve();
return 0;
}