2020牛客暑期多校训练营（第二场）A、B、C、D、F、G、J题解及补题
程序员文章站
2022-04-01 13:02:59
...
文章目录
2020牛客暑期多校训练营（第二场）题解及补题
比赛过程
一共出了三题。首先打卡了D题，出的不算快，然后同时开了F和C，F没有想到单调队列，靠猜想混过的，导致TLE、WA了n发，然后继续做C。过了之后开B，没想到好思路。这场比赛较第一场交流上好了一点，赛后补了A、B、G、J。
题解
A
题意
给你n个字符串，求 ∑ i = 0 n ∑ j = 0 n f ( s i , s j ) 2 \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n}f(s_{i},s_{j})^2 i=0∑nj=0∑nf(si,sj)2(mod998244353)，其中 f ( s i , s j ) f(s_{i},s_{j}) f(si,sj)的意思是字符串 s i s_{i} si的前缀和字符串 s j s_{j} sj 后缀最长相等部分。
解法
哈希每个字符串的前缀后缀，用map记录前缀哈希值出现的个数，然而会出现重复的现象，前缀的前缀可能会多算，我们用kmp的next数组，将大前缀中减去小前缀的贡献即可。
代码
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define mst(a, b) memset((a), (b), sizeof(a))
#define mp(a, b) make_pair(a, b)
#define pi acos(-1)
#define endl '\n'
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define lowbit(x) x &(-x)
#define all(x) (x).begin(), (x).end()
#define sf(x) scanf("%d", &x)
#define pf(x) printf("%d", x)
#define debug(x) cout << x << endl
#define mod(x) (x % mod + mod) % mod
template <typename T>
void read(T &x)
{
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch))
{
if (ch == '-')
f *= -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
}
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1e6 + 7;
const int maxm = 8800;
const int mod = 1e9 + 7;
const int M = 998244353;
const int P = 13331;
#define IO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int kmpNext[maxn];
string s[maxn];
ll cnt[maxn];
map<ll, int> Hash[maxn];
ll num[maxn];
char b[maxn];
ll val[maxn];
void preKMP(char x[], int m)
{
int j;
j = 0;
for (int i = 2; i <= m; ++i)
{
while (j && x[i] != x[j + 1])
j = kmpNext[j];
if (x[j + 1] == x[i])
++j;
kmpNext[i] = j;
}
}
int main()
{
IO;
int n;
cin >> n;
int maxx = 0;
for (int i = 1; i <= n; ++i)
{
cin >> s[i];
maxx = max(maxx, (int)s[i].size());
ll h = 0;
for (int j = 0; j < s[i].size(); ++j)
{
h = (h * P % mod + (s[i][j] - 'a' + 1)) % mod;
++Hash[j + 1][h];
}
}
num[0] = 1;
for (int i = 1; i <= maxx; ++i)
num[i] = 1LL * num[i - 1] * P % mod;
for (int i = 1; i <= n; ++i)
{
ll h = 0;
reverse(all(s[i]));
int t = 0;
for (int j = 0; j < s[i].size(); ++j)
b[++t] = s[i][j], val[t] = 0;
preKMP(b, t);
for (int j = 0; j < s[i].size(); ++j)
{
h = (h + 1LL * (s[i][j] - 'a' + 1) * num[j]) % mod;
if (Hash[j + 1].find(h) != Hash[j + 1].end())
{
cnt[j + 1] += Hash[j + 1][h];
val[kmpNext[j + 1]] += Hash[j + 1][h];
}
}
for (int j = 1; j <= s[i].size(); ++j)
cnt[j] -= val[j];
}
ll ans = 0;
for (int i = 1; i <= maxx; ++i)
ans = (ans + 1LL * i * i * cnt[i]) % M;
cout << ans << endl;
return 0;
}
B
题意
在一个二维平面上，给出n个点，找到一个过原点的圆，并且包含尽可能多的给定的点，输出最多可以有多少个点在圆上。
解法
二重循环枚举两个点，和原点联立计算圆心，把这些圆心用vector保存下来，sort一遍判断最多有多少个圆心是一样的。假设有 m a x x maxx maxx 个重复的圆心，由于我们是以组合数的方式枚举两个点，所以有 C c n t 2 = m a x x C_{cnt}^{2}=maxx Ccnt2=maxx 其中 c n t cnt cnt 即为在圆上点的数量。
代码
#pragma region
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
#define debug() W(" ");
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { x = getchar(); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &... tail) { _R(head), R(tail...); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) { _W(x.F), putchar(' '), _W(x.S); }
template <class T>
void _W(const vector<T> &x) {
for (auto i = x.begin(); i != x.end(); _W(*i++))
if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &... tail) { _W(head), putchar(sizeof...(tail) ? ' ' : '\n'), W(tail...); }
#pragma endregion
const int maxn = 2005;
int n;
const double eps = 1e-8;
inline int sgn(double x) { return abs(x) < eps ? 0 : (x > 0 ? 1 : -1); }
inline bool equ(const double &A, const double &B) { return !sgn(A - B); }
struct Point { // Point & Vector
double x, y;
Point(const double &x = 0, const double &y = 0) : x(x), y(y) {}
friend Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(const double &c, const Point &a) {
return Point(c * a.x, c * a.y);
}
friend Point operator*(const Point &a, const double &c) {
return Point(c * a.x, c * a.y);
}
friend Point operator/(const Point &a, const double &c) {
return Point(a.x / c, a.y / c);
}
friend Point rotate(const Point &v, double theta) { // 向量逆时针旋转theta弧度
return Point(v.x * cos(theta) - v.y * sin(theta), v.x * sin(theta) + v.y * cos(theta));
}
friend Point rotateAroundPoint(Point &v, Point &p, double theta) {
return rotate(v - p, theta) + p;
}
friend bool operator==(const Point &a, const Point &b) {
return !sgn(a.x - b.x) && !sgn(a.y - b.y);
}
friend bool operator<(const Point &a, const Point &b) {
return sgn(a.x - b.x) < 0 || (!sgn(a.x - b.x) && sgn(a.y - b.y) < 0);
}
double norm() { return sqrt(x * x + y * y); } // 向量模
friend double det(const Point &a, const Point &b) { // 向量叉积
return a.x * b.y - a.y * b.x;
}
friend double dot(const Point &a, const Point &b) { // 向量点积
return a.x * b.x + a.y * b.y;
}
friend double dis(const Point &a, const Point &b) { // 两点间距离
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
friend Point intersection(Point u1, Point u2, Point v1, Point v2) { // 线段交点, 线段有交点才可用
return u1 + (u2 - u1) * det(u1 - v1, v1 - v2) / det(u1 - u2, v1 - v2);
}
double arg() { return atan2(y, x); } // 返回弧度
friend double arg_2(Point u, Point v) {
return acos(dot(u, v) / (u.norm() * v.norm()));
} // 两向量之间的夹角
friend double arg_3(const Point &a, const Point &b, const Point &c) {
return arg_2(a - b, c - b);
} // ∠abc
} a[maxn];
double X, Y, r;
void solve(Point a, Point b, Point c) { //三点共圆圆心公式
if (2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x) == 0 && 2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x) == 0) {
X = Y = 1e18;
r = -1;
return;
}
X = ((a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y) * (a.y - c.y) - (a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y) * (a.y - b.y)) / (2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x));
Y = ((a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y) * (a.x - c.x) - (a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y) * (a.x - b.x)) / (2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x));
r = sqrt((X - a.x) * (X - a.x) + (Y - a.y) * (Y - a.y));
}
int main() {
R(n);
if (n == 1) {
W(1);
return 0;
}
rep(i, 1, n) R(a[i].x, a[i].y);
Point zero;
vector<pair<double, double>> v;
rep(i, 1, n) rep(j, i + 1, n) {
solve(zero, a[i], a[j]);
if (r != -1) v.push_back({X, Y});
}
if (v.size() == 0) {
W(1);
return 0;
}
sort(v.begin(), v.end());
int maxx = 1, t = 1;
rep(i, 1, int(v.size()) - 1) {
if (v[i - 1] == v[i]) {
t++;
maxx = max(maxx, t);
} else
t = 1;
}
rep(i, 1, n) if (i * (i - 1) == maxx * 2) {
W(i);
return 0;
}
}
C
题意
给定一棵无根树，连接其中两个节点组成一条链，使树中的每一条边至少被一条链覆盖。 输出最少的链数量+其中任何一个解决方案。
解法
一条链最多可以覆盖两个叶子节点，那么链的数量至少为$\left \lceil \frac{s}{2} \right \rceil $,其中
s
s
s 为叶子节点的数量。那么只需要考虑叶子节点相连接就可以了。
首先dfs遍历这棵树，得到以dfs序排序的叶子节点，记为
l
1
,
l
2
,
⋯
l
s
l_1,l_2,\cdots l_s
l1,l2,⋯ls。不妨假设s为偶数，那么这些结点可以构成
s
2
\frac{s}{2}
2s 条链，分别为
l
1
→
l
s
2
+
1
l_1 \to l_{\frac{s}{2}+1}
l1→l2s+1，
l
2
→
l
s
2
+
2
l_2 \to l_{\frac{s}{2}+2}
l2→l2s+2，
⋯
l
s
2
→
l
s
\cdots l_{\frac{s}{2}} \to l_{s}
⋯l2s→ls。
对于任意一条边，假设这条边的儿子节点所覆盖的叶子节点区间为 $\left [ L,R \right ] $:
∙
\bullet
∙ 如果
R
≤
s
2
R \le \frac{s}{2}
R≤2s，则这条边会被
l
R
→
l
s
2
+
R
l_R \to l_{\frac{s}{2}+R}
lR→l2s+R 覆盖。
∙
\bullet
∙ 如果
L
≥
s
2
L \ge \frac{s}{2}
L≥2s，则这条边会被
l
L
−
s
2
→
l
L
l_{L-\frac{s}{2}} \to l_{L}
lL−2s→lL 覆盖。
∙
\bullet
∙ 否则
L
≤
s
2
≤
R
L \le \frac{s}{2} \le R
L≤2s≤R ，那么这条边至少会被
l
1
→
l
s
2
+
1
l_1 \to l_{\frac{s}{2}+1}
l1→l2s+1 或
l
s
2
→
l
s
l_{\frac{s}{2}} \to l_{s}
l2s→ls 覆盖。
如果s为奇数，只需要将最后一条边与任意一个叶子节点相连即可。
代码
#pragma region
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rep(i, a, n) for (long long i = a; i <= n; ++i)
#define per(i, a, n) for (long long i = n; i >= a; --i)
#define debug() W(" ");
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { x = getchar(); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &... tail) { _R(head), R(tail...); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) { _W(x.F), putchar(' '), _W(x.S); }
template <class T>
void _W(const vector<T> &x) {
for (auto i = x.begin(); i != x.end(); _W(*i++))
if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &... tail) { _W(head), putchar(sizeof...(tail) ? ' ' : '\n'), W(tail...); }
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
template <typename T>
void read(T &x) {
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch)) {
if (ch == '-') f *= -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
}
#pragma endregion
const int maxn = 2e5 + 5;
vector<int> g[maxn], lea;
vector<pii> ans;
void dfs(int u, int fa) {
if (g[u].size() == 1) lea.push_back(u);
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
}
}
int main() {
int n;
R(n);
rep(i, 1, n - 1) {
int u, v;
R(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
W((lea.size() + 1) / 2);
int haf = lea.size() / 2;
rep(i, 0, haf - 1) W(lea[i], lea[i + haf]);
if (lea.size() & 1) W(lea.front(), lea.back());
}
D
题意
给出时分秒形式的两个时间，计算两个时间之间有多少秒。
解法
时间转换成秒，相减取绝对值即可。
代码
#pragma region
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (long long i = a; i <= n; ++i)
#define per(i, a, n) for (long long i = n; i >= a; --i)
#define debug() W(" ");
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { x = getchar(); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &... tail) { _R(head), R(tail...); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) { _W(x.F), putchar(' '), _W(x.S); }
template <class T>
void _W(const vector<T> &x) {
for (auto i = x.begin(); i != x.end(); _W(*i++))
if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &... tail) { _W(head), putchar(sizeof...(tail) ? ' ' : '\n'), W(tail...); }
#pragma endregion
const int maxn = 55;
int main() {
char ch;
int h1, h2, m1, m2, s1, s2;
R(h1, ch, m1, ch, s1);
R(h2, ch, m2, ch, s2);
int t1 = h1 * 3600 + m1 * 60 + s1;
int t2 = h2 * 3600 + m2 * 60 + s2;
W(abs(t2 - t1));
}
E
题意
解法
代码
//将内容替换成代码
F
题意
给一个 n ∗ m n*m n∗m 的矩阵，其中 a i , j = l c m ( i , j ) a_{i,j}=lcm(i,j) ai,j=lcm(i,j) 。求该矩阵中每个 k ∗ k k*k k∗k 大小的子矩阵最大值的和。
解法
比赛的时候猜想最大值不会出现在离右下角的点太远的距离，暴力计算出这个矩阵之后遍历每个子矩阵右下角
7
∗
7
7*7
7∗7 大小的矩阵元素，并求最大值累加即为答案。
真做法:先用类似欧拉筛的方法求出
g
c
d
(
i
,
j
)
gcd(i,j)
gcd(i,j) ，然后
l
c
m
(
i
,
j
)
=
i
/
g
c
d
(
i
,
j
)
∗
j
lcm(i,j)=i/gcd(i,j)*j
lcm(i,j)=i/gcd(i,j)∗j ，再用单调队列，一次横排，一次竖排，记录每个区间中最大值的下标，最后求和即可。
代码
#pragma region
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
#define debug() printf(" ");
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { x = getchar(); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &... tail) { _R(head), R(tail...); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) { _W(x.F), putchar(' '), _W(x.S); }
template <class T>
void _W(const vector<T> &x) {
for (auto i = x.begin(); i != x.end(); _W(*i++))
if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &... tail) { _W(head), putchar(sizeof...(tail) ? ' ' : '\n'), W(tail...); }
#pragma endregion
const int maxn = 5005;
int n, m, k, a[maxn][maxn], b[maxn][maxn];
void solve(int n, int m) {
vector<int> q(maxn);
rep(i, 1, n) {
int l = 1, r = 0;
rep(j, 1, k - 1) {
while (l <= r && a[i][q[r]] <= a[i][j]) --r;
q[++r] = j;
}
rep(j, k, m) {
while (l <= r && q[l] + k <= j) ++l;
while (l <= r && a[i][q[r]] <= a[i][j]) --r;
q[++r] = j;
b[j - k + 1][i] = a[i][q[l]];
}
}
}
int main() {
R(n, m, k);
rep(i, 1, n) rep(j, 1, m) {
if (!a[i][j])
for (int k1 = i, k2 = j; k1 <= n && k2 <= m; k1 += i, k2 += j)
a[k1][k2] = k1 / i;
}
rep(i, 1, n) rep(j, 1, m) a[i][j] = i / a[i][j] * j;
solve(n, m);
rep(i, 1, m - k + 1) rep(j, 1, n) a[i][j] = b[i][j];
solve(m - k + 1, n);
ll ans = 0;
rep(i, 1, n - k + 1) rep(j, 1, m - k + 1) ans += b[i][j];
W(ans);
}
G
题意
分别给两个大小为 n n n和 m m m的数组，求大小为 n n n的数组A有多少个大小为 m m m的区间使得区间内每个位置的数都大于大小为 m m m的数组B对应位置的数字。
解法
记录每个数的位置然后按大小从大到小排列，大小相等位置靠前的在前。遍历B数组的每一个数用一个bitset temp记录A数组中比当前数字大的位置变为1 。bitset ans每次与temp右移当前B数组中数字的位置的个数与运算。最后ans个1的个数为符合要求的区间个数。
代码
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define mst(a, b) memset((a), (b), sizeof(a))
#define mp(a, b) make_pair(a, b)
#define pi acos(-1)
#define endl '\n'
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define lowbit(x) x &(-x)
#define all(x) (x).begin(), (x).end()
#define sf(x) scanf("%d", &x)
#define pf(x) printf("%d", x)
#define debug(x) cout << x << endl
#define mod(x) (x % mod + mod) % mod
template <typename T>
void read(T &x)
{
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch))
{
if (ch == '-')
f *= -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
}
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const int maxn = 2e5 + 7;
const int maxm = 8800;
const int mod = 1e9 + 7;
#define IO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
struct node
{
int val, pos;
bool operator<(const node &a) const
{
if (val == a.val)
return pos < a.pos;
return val > a.val;
}
};
node a[maxn], b[maxn];
bitset<maxn> temp, ans;
int main()
{
IO;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> a[i].val;
a[i].pos = i;
}
for (int i = 1; i <= m; ++i)
{
cin >> b[i].val;
b[i].pos = i;
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
ans.set();
for (int i = 1, j = 1; i <= m; ++i)
{
while (j <= n && a[j].val >= b[i].val)
{
temp.set(a[j].pos, 1);
++j;
}
ans &= temp >> (b[i].pos);
}
cout << ans.count() << endl;
return 0;
}
H
题意
解法
代码
//将内容替换成代码
I
题意
解法
代码
//将内容替换成代码
J
题意
要求构造出序列P，让初始排列A={1，2，3，4…n}依照P序列跳转k次后得到给定排列。
解法
把A的每一个环求出来，对每一个环求 i n v i = k − 1 ( m o d r i ) inv_{i} = k-1(mod r_{i}) invi=k−1(modri) ,即当前环需要转 i n v i inv_{i} invi次，就可以得到一个合法解。
代码
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 111;
ll flag[maxn];
ll a[maxn];
ll ans[maxn];
ll putt[maxn];
int main() {
ll n, k;
scanf("%lld%lld", &n, &k);
for (ll i = 1; i <= n; ++i) {
scanf("%lld", a + i);
}
ll num = 0;
for (ll i = 1; i <= n; ++i) {
if (!flag[i]) {
num = 0;
ll tp = a[i];
while (!flag[tp]) {
flag[tp] = 1;
putt[num++] = tp;
tp = a[tp]; // zhao huan
}
ll inv;
for (ll j = 0; j < num; ++j) {
if (k * j % num == 1) {
inv = j;
}
}
for (ll j = 0; j < num; ++j) {
ans[putt[j]] = putt[(j + inv) % num];
}
}
}
for (ll i = 1; i < n; ++i) printf("%lld ", ans[i]);
printf("%lld\n", ans[n]);
return 0;
}
K
题意
解法
代码
//将内容替换成代码
下一篇： php变量范围,php全局变量与静态变量