首页 > 其他分享 >"蔚来杯"2022牛客暑期多校训练营7

"蔚来杯"2022牛客暑期多校训练营7

时间：2022-09-07 12:11:37浏览次数：87  
标签：10 ch int 蔚来 多校 long 牛客 include define

A.Floor Tiles in a Park

给定\(W\times H\)的矩阵，问将其分为\(k(k\leqslant5)\)个子矩阵的方案数。两个方案不同，当且仅当其切割方式不同

  • 手玩，画出所有\(k\leqslant 5\)的方案，然后组合数统计
  • 手玩的时候，发现答案也一定由若干组合式构成，可以写成形如\(\sum\limits_{i=0}^4\sum\limits_{j=0}^4A_{i,j}W^iH^j\)的形式，所以我们暴力打表，然后利用高斯消元求出系数即可
/*program from Wolfycz*/
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define UNUSED(x) (void)(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<typename T>inline T read(T x) {
	int f = 1; char ch = getchar();
	for (; ch < '0' || ch>'9'; ch = getchar())	if (ch == '-')	f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar())	x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}
inline void print(int x) {
	if (x < 0)	putchar('-'), x = -x;
	if (x > 9)	print(x / 10);
	putchar(x % 10 + '0');
}
const int P = 998244353;
const int G[6][5][5] = {
	{},
	{
		{1,0,0,0,0},
		{0,0,0,0,0},
		{0,0,0,0,0},
		{0,0,0,0,0},
		{0,0,0,0,0}
	},
	{
		{998244351,1,0,0,0},
		{        1,0,0,0,0},
		{        0,0,0,0,0},
		{        0,0,0,0,0},
		{        0,0,0,0,0}
	},
	{
		{        6,499122171,499122177,0,0},
		{499122171,        4,        0,0,0},
		{499122177,        0,        0,0,0},
		{        0,        0,        0,0,0},
		{        0,        0,        0,0,0}
	},
	{
		{998244330,332748146,499122170,166374059,0},
		{332748146,998244321,499122182,        0,0},
		{499122170,499122182,        0,        0,0},
		{166374059,        0,        0,        0,0},
		{        0,        0,        0,        0,0}
	},
	{
		{      104,249560934,707089806,748683260,291154603},
		{249560934,332748336,499122106,332748122,        0},
		{707089806,499122106,       16,        0,        0},
		{748683260,332748122,        0,        0,        0},
		{291154603,        0,        0,        0,        0}
	}
};
int main() {
	int n = read(0), m = read(0), k = read(0), Ans = 0;
	for (int i = 0, x = 1; i < 5; i++, x = 1ll * x * n % P)
		for (int j = 0, y = 1; j < 5; j++, y = 1ll * y * m % P)
			Ans = (Ans + 1ll * x * y % P * G[k][i][j] % P) % P;
	printf("%d\n", Ans);
	return 0;
}

B.Rotate Sum 3

给定平面上一\(n\)点的整点凸多边形，使其绕着任意对称轴在空间旋转，问扫过的体积大小？

Simpson积分，咕咕咕

C.Constructive Problems Never Die

给定一个长度为\(n\)的数列\(A\)，要求构造一个排列\(P\)，满足\(P_i\neq A_i\)

当\(A\)中所有数相等时无法构造

我们取出\(A\)序列中重复出现的数中任意一个，没有选中的位置随便填入没有选中的数，选中的位置填下一个选中位置的数即可

/*program from Wolfycz*/
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define UNUSED(x) (void)(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<typename T>inline T read(T x) {
    int f = 1; char ch = getchar();
    for (; ch < '0' || ch>'9'; ch = getchar())	if (ch == '-')	f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())	x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}
inline void print(int x) {
    if (x < 0)	putchar('-'), x = -x;
    if (x > 9)	print(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e5;
struct node {
    int V, pos;
    node(int _V = 0, int _pos = 0) { V = _V, pos = _pos; }
    bool operator <(const node& ots)const { return V < ots.V; }
    bool operator ==(const node& ots)const { return V == ots.V; }
}A[N + 10];
int Ans[N + 10];
int main() {
    int Times = read(0);
    while (Times--) {
        int n = read(0);
        for (int i = 1; i <= n; i++) {
            int x = read(0);
            A[i] = node(x, i);
        }
        sort(A + 1, A + 1 + n);
        int T = unique(A + 1, A + 1 + n) - A - 1;
        if (T == 1) {
            printf("NO\n");
            continue;
        }
        unordered_set<int>_V, _pos;
        for (int i = 1; i <= n; i++)
            _V.insert(i), _pos.insert(i);
        for (int i = 1; i <= T; i++)
            _V.erase(A[i].V), _pos.erase(A[i].pos);
        while (!_V.empty()) {
            Ans[*_pos.begin()] = *_V.begin();
            _V.erase(_V.begin());
            _pos.erase(_pos.begin());
        }
        for (int i = 1; i < T; i++)
            Ans[A[i].pos] = A[i + 1].V;
        Ans[A[T].pos] = A[1].V;
        printf("YES\n");
        for (int i = 1; i <= n; i++)
            printf("%d%c", Ans[i], i == n ? '\n' : ' ');
    }
}

D.The Pool

\(T\)次询问，每次询问给定\(n,m\)，问长宽为\(n,m\)的矩形顶点摆放在整点后，所有不同的摆放方案中，每个方案完全包含的\(1\times1\)的格子数量和是多少？

两种方案不同，当且仅当一个方案的矩形无法仅通过平移变换，得到另一个方案。

几何+数学，咕咕咕

给定\(n\)个互不相同的数字和一个初始为空的序列\(\{a\}\)，依次将其插入到序列的末尾，问至少经过几次相邻交换操作可以让序列符合三分特性（单峰）

咕咕咕

F.Candies

给定\(n,x\)，之后给定一个长为\(n\)的环形序列\(A\)，如果\(A_i=A_{i+1}\)或者\(A_i+A_{i+1}=x\)，则可以将它俩删去。问序列最多可以删除多少次？

考虑所有能消去的组合：\((a,a),(a,x-a),(x-a,a),(x-a,x-a)\)，可以发现，如果一个数\(a\)满足\(a>\frac{x}{2}\)且\(a<x\)，则可以将其变为\(x-a\)，并且这样对答案是没有影响的

然后我们用一个栈暴力删除相邻的相同数即可。由于是环形序列，因此最后要考虑栈顶和栈底

/*program from Wolfycz*/
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define UNUSED(x) (void)(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<typename T>inline T read(T x) {
    int f = 1; char ch = getchar();
    for (; ch < '0' || ch>'9'; ch = getchar())	if (ch == '-')	f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())	x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}
inline void print(int x) {
    if (x < 0)	putchar('-'), x = -x;
    if (x > 9)	print(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e5;
int stack[N + 10], top;
int main() {
    int n = read(0), limit = read(0);
    for (int i = 1; i <= n; i++) {
        int x = read(0);
        if (x > limit >> 1 && x < limit)
            x = limit - x;
        if (top && stack[top] == x) top--;
        else    stack[++top] = x;
    }
    int l = 1, r = top;
    while (r > l && stack[l] == stack[r])
        l++, r--;
    printf("%d\n", (n - (r - l + 1)) >> 1);
    return 0;
}

G.Regular Expression

给定串\(S\)，求其最短正则匹配式以及匹配种数？

匹配式可使用小写字母以及\(.?*+|()\)这七个字符，它们的规则如下：

  • \(|\) 表示或，\(a|b\) 能匹配\(a\)也能匹配\(b\)
  • \(?\) 表示前面的字符可有可无，\(a?b\) 能匹配\(ab\)也能匹配\(b\)
  • \(*\) 表示前面的字符重复任意次(包括零)
  • \(+\) 表示前面的字符重复正整数次
  • \(.\) 表示任意字符
  • \(()\) 改变优先顺序

显然，\(.*\)可以匹配任意长度的字符串，因此最大长度一定不超过2。我们分类讨论：

  • \(S\)长度为1，则可匹配\(\text{'a'，'.'}\)
  • \(S\)长度为2，且相同，则可匹配\(\text{'aa'，'a.'，'.a'，'..'，'.+'，'.*'，'a+'，'a*'}\)
  • \(S\)长度为2，且不同，则可匹配\(\text{'ab'，'a.'，'.b'，'..'，'.+'，'.*'}\)
  • \(S\)长度\(>2\)，且全部相同，则可匹配\(\text{'a+'，'a*'，'.+'，'.*'}\)
  • \(S\)长度\(>2\)，且不全相同，则可匹配\(\text{'.+'，'.*'}\)
/*program from Wolfycz*/
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define UNUSED(x) (void)(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<typename T>inline T read(T x) {
    int f = 1; char ch = getchar();
    for (; ch < '0' || ch>'9'; ch = getchar())	if (ch == '-')	f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())	x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}
inline void print(int x) {
    if (x < 0)	putchar('-'), x = -x;
    if (x > 9)	print(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e5;
char s[N + 10];
int main() {
    int T = read(0);
    while (T--) {
        scanf("%s", s);
        int len = strlen(s);
        if (len == 1) {
            printf("1 2\n");
            continue;
        }
        if (len == 2) {
            printf("2 %d\n", 6 + 2 * (s[0] == s[1]));
            continue;
        }
        if (len > 2) {
            int Flag = 1;
            for (int i = 0; i < len; i++)
                Flag &= s[i] == s[0];
            printf("2 %d\n", 2 + 2 * Flag);
            continue;
        }
    }
    return 0;
}

H.Grammy Sorting

给定一个无向连通图\(G\)，给定两个特殊点\(A,B\)，每个点上有权值\(p_i\)，并且\(p_{1\sim n}\)是一个排列

现在可以选择从\(A\)开始到任意点结束的一条路径，假定路径上经过的点为\(a_1,a_2,...,a_n\)，那么可以把这些点改为\(a_2,a_3,...,a_n,a_1\)(权值也跟着一块改变)

问至多10000次操作后，能否使得图\(G\)满足，对于任意一个点\(i\)，存在一条\(A\)到\(B\)的路径，使得路径经过\(i\)，并且路径上的点权值严格升序？

Bipolar Orientation(双极定向) + 构造，咕咕咕

I.Suffix Sort

定义一个串\(S\)的最小表示为，按出现某个字符第一次出现的顺序从小到大的排序，并依次编号为abc...z，如edcca的最小表示为abccd

给定串\(S\)，对其全部后缀进行最小表示的排序

后缀排序 + lcp优化，咕咕咕

J.Melborp Elcissalc

求长度为\(n\)，每个数字都在\([0,k)\)，使得区间连续和为\(k\)的倍数的子区间有\(t\)个的序列个数。\(n,k\leqslant 64,t\leqslant \frac{n(n-1)}{2}\)

考虑对于给定序列如何统计满足条件的子区间个数，可以用前缀和，记\(c_i\)为前缀和\(\% k\)意义下的值，则其子区间个数为\(\sum\limits_{i=0}^{k-1}\binom{c_i}{2}\)

考虑Dp，设\(F[i][j][l]\)表示考虑到数字\(i\)，填了\(j\)个位置，子区间个数为\(l\)的方案数，那么转移则有\(F[i][j][l]=\sum\limits_{k=0}^jF[i-1][j-k][l-\binom{k}{2}]\binom{n-j+k}{k}\)，最后输出\(F[k][n][t]\)即可

(注意数组啥都没填的时候为0，因此0的贡献会多一些)

/*program from Wolfycz*/
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define UNUSED(x) (void)(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<typename T>inline T read(T x) {
    int f = 1; char ch = getchar();
    for (; ch < '0' || ch>'9'; ch = getchar())	if (ch == '-')	f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())	x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}
inline void print(int x) {
    if (x < 0)	putchar('-'), x = -x;
    if (x > 9)	print(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e2, P = 998244353;
int F[N + 10][N + 10][N * N + 10], C[N + 10][N + 10];
int S(int x) { return x * (x - 1) / 2; }
int main() {
    int n = read(0), k = read(0), t = read(0);
    for (int i = 0; i <= n; i++)
        C[i][0] = C[i][i] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
    F[0][0][0] = 1;
    for (int i = 0; i < k; i++)
        for (int j = 0; j <= n; j++)
            for (int l = 0; l + j <= n; l++)
                for (int s = 0; s + S(l + (!i)) <= t; s++)
                    F[i + 1][j + l][s + S(l + (!i))] = (F[i + 1][j + l][s + S(l + (!i))] + 1ll * F[i][j][s] * C[n - j][l]) % P;
    printf("%d\n", F[k][n][t]);
    return 0;
}

K.Great Party

有\(n\)堆石子，每堆\(a_i\)个石子，两人轮流操作，每次可选取一堆取走任意多个，并且在取完后可以选择是否将该堆并入其他石子中

现有\(Q\)次询问，每次询问给定两个数\(L_i,R_i\)，问有多少个子区间\([l,r]\sub[L_i,R_i]\)，使得将子区间拎出来单独进行游戏，能保证先手必胜？

首先考虑如何必胜，当局面为偶数堆时，先手不能进行合并操作使其变成奇数堆(之后会提)，因此只能不断取石子，直至所有堆数均为1，此时先手必败。故偶数堆的情况下可以看成是一个\(a_i-1\)的Nim游戏

当局面为奇数堆时，先手必定能对最大的一堆操作，之后将其合并，使得剩余偶数堆变成\(a_i-1\)异或和为0的状态。

所以在奇数堆先手必胜，面对偶数堆时\(a_i-1\)异或和不为零先手必胜，否则必败

这样问题就变成了区间查询异或前缀和的出现位置(考虑奇偶性)，我们使用莫队即可

/*program from Wolfycz*/
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define UNUSED(x) (void)(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<typename T>inline T read(T x) {
    int f = 1; char ch = getchar();
    for (; ch < '0' || ch>'9'; ch = getchar())	if (ch == '-')	f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())	x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}
inline void print(int x) {
    if (x < 0)	putchar('-'), x = -x;
    if (x > 9)	print(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e5, V = 1 << 20;
int Pre[N + 10], Val[2][V + 10], Sz;
struct node {
    int l, r, ID;
    node(int _l = 0, int _r = 0, int _ID = 0) { l = _l, r = _r, ID = _ID; }
    bool operator <(const node& ots)const {
        if (l / Sz != ots.l / Sz)
            return (l / Sz) < (ots.l / Sz);
        return r < ots.r;
    }
}A[N + 10];
ll Ans[N + 10], Extra;
ll sum(int x) { return x <= 1 ? 0 : 1ll * x * (x - 1) / 2; }
void Add(int x) {
    Extra -= sum(Val[x & 1][Pre[x]]);
    Val[x & 1][Pre[x]]++;
    Extra += sum(Val[x & 1][Pre[x]]);
}
void Del(int x) {
    Extra -= sum(Val[x & 1][Pre[x]]);
    Val[x & 1][Pre[x]]--;
    Extra += sum(Val[x & 1][Pre[x]]);
}
int main() {
    int n = read(0), q = read(0); Sz = sqrt(n);
    for (int i = 1; i <= n; i++)
        Pre[i] = Pre[i - 1] ^ (read(0) - 1);
    for (int i = 1; i <= q; i++) {
        int l = read(0), r = read(0);
        A[i] = node(l - 1, r, i);
    }
    sort(A + 1, A + 1 + q);
    int l = 1, r = 0;
    for (int i = 1; i <= q; i++) {
        while (l > A[i].l)    Add(--l);
        while (r < A[i].r)    Add(++r);
        while (l < A[i].l)    Del(l++);
        while (r > A[i].r)    Del(r--);
        Ans[A[i].ID] = sum(A[i].r - A[i].l + 1) - Extra;
    }
    for (int i = 1; i <= q; i++)
        printf("%lld\n", Ans[i]);
    return 0;
}

L.Maximum Range

给定一个无向连通图\(G\)，要求找到一个简单环，使得环上最大边权和最小边权之差最小，要求输出方案。

对每一个边双，其中的最大权值与最小权值可以出现在一个环上。考虑输出方案，在这两条边中间各加一个点，建一个网络流的图(流量均为1)，跑完取有流量的边再跑一个欧拉回路即可

代码，咕咕咕

标签：10,ch,int,蔚来,多校,long,牛客,include,define
From： https://www.cnblogs.com/Wolfycz/p/16664948.html

相关文章

  • "蔚来杯"2022牛客暑期多校训练营9
    A CarShow题意：给定一个数组，请找到有多个区间[L,R]满足1到m的数都出现过。分析：直接双指针就好#include<bits/stdc++.h>usingnamespacestd;longlongn,m,s[......
  • Slayers Come (区间覆盖种类数(dp+线段树)+ st表+二分,或者线段树) (2022杭电多校2)
    题目;给你一个长度为n的数组，每个位置上有一个野怪，野怪的攻击力和血量已知，你有m个技能，每个技能有三个值，一是可以击败的怪物，且怪物死后会攻击与它相邻的怪对于左边的怪伤害......
  • Static Query on Tree (述链剖分+线段树)(2022杭电多校)
    题意:给定一棵树，nn 个结点。根为 11，所有的结点只能走向其父亲结点。有 qq 次询问，每次询问给出 33 个结点集合 A,B,CA,B,C。问树上有多少点满足如下条件：该点可以......
  • DOS Card (线段树)(hud杭电多校)
    题目:对序列 a，回答 q 次询问：给定长度至少为 4 的区间 [L,R]，在区间内选择 1对 (ai,aj)(L≤i<j≤R)可以获取分数 (ai+aj)(ai−aj) ，计算选择 2 对可以获取的最......
  • copy (倒叙离线+bitset+^特性) (hud 2022多校 2)
    题目:给定一个序列 a1,a2,…,an，共有 q 次操作，每次操作有两种类型：操作1(1,l,r) 表示复制区间 [l,r] 的内容，在区间 [l,r]的末尾处插入这段内容。操作2(2,x) 询问......
  • "蔚来杯"2022牛客暑期多校训练营7
    CConstructiveProblemsNeverDie题意：给你一个数组A,你需要构造一个排列P，使得P[i]≠A[i]分析：考虑构造不出来的情况如果所有A[i]都相同一定不成立先构造P[i]=i......
  • 牛客dfs专题 NC13594 选择困难症（dfs+剪枝）
    链接：https://ac.nowcoder.com/acm/problem/13594来源：牛客网题目描述有k类物品，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。小L想知道，有多......
  • 牛客dfs专题：轰炸区最优选取（二维前缀和）
    链接：https://ac.nowcoder.com/acm/problem/14505来源：牛客网题目描述现在给出一个正方形地图，其边长为n，地图上有的地方是空的，有的地方会有敌人。我们现在有一次轰炸敌人......
  • 牛客练习赛102
    A清楚姐姐的学术群intmain(){ intn=read(),m=read(),a=read(),b=read(); for(inti=1;i<=n;i++)people[i].push_back(0); for(inti=1;i<=......
  • 29. 牛客-一人行者
    本来不想为了这题写一篇博客的，但因为昨天被一组数据卡了一个小时，还是有必要来记录一下。牛客练习赛102D：一人行者题意是给一棵树，求断掉每一条边后得到的两棵树各自的联通......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99