2022牛客多校2补题
多校
多校
发布日期:   2022-08-23
更新日期:   2024-02-20
作者:   行码棋
文章字数:   2.6k
阅读时长:   14 分
阅读次数:  

2022牛客多校2补题

G Link with Monotonic Subsequence

max(lis(p),lds(p))max(lis(p), lds(p)) 的下界为 ⌈n⌉\lceil \sqrt n \rceil

如果 n=k2n = k^2 构造出 (n−k+1,n−k+2,...,n)(k+1,...,2×k)(1,2,3,...,k)(n-k+1,n-k+2,...,n)(k+1,...,2 \times k)(1,2,3,...,k)

规律也可以通过打表得到

打表程序主体

for(int i = 6; i <= 6; i++)
{
    vi a(i);
    iota(a.begin(), a.end(), 1);
    int ans = 1e9;
    vi t;
    do
    {
        vi dpd(i, 1), dpi(i, 1);
        for(int j = 0; j < i; j++)
            for(int k = 0; k < j; k++)
                if(a[j] < a[k])
                    dpd[j] = max(dpd[j], dpd[k] + 1);

        for(int j = 0; j < i; j++)
            for(int k = 0; k < j; k++)
                if(a[j] > a[k])
                    dpi[j] = max(dpi[j], dpi[k] + 1);
        int in = 0, de = 0;
        for(int j = 0; j < i; j++)
        {
            in = max(in, dpi[j]);
            de = max(de, dpd[j]);
        }
        if(max(in, de) < ans)
        {
            ans = max(in, de);
            t = a;
        }
    }while(next_permutation(a.begin(), a.end()));
    for(auto x : t)
        cout << x << " ";
    cout << "\n";
}
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;

void solve()
{
	int n;
	cin >> n;
	int len = sqrt(n);
	if(len * len != n) len ++;

	int val = 0;

	if(n % len)
	{
		val += n % len;
		for(int i = 1; i <= n % len; i++)
			cout << val-- << " ";
		val += n % len + len;
	}
	else val += len;

	for(int i = 1; i <= n / len; i++)
	{
		for(int j = 1; j <= len; j++)
			cout << val-- << " ";
		val += len * 2;
	}
	cout << "\n";

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

D Link with Game Glitch

n种物品，m种交换，每 aia_i 个 bib_i 类物品可以换 w⋅ciw \cdot c_i 个 did_i 类物品。求最大的 w 使不存在一种无限交换的方式。

从 bib_i 向 did_i 连一条 w⋅ci/aiw \cdot c_i / a_i 的边。

二分 ww ，如果图中出现边乘积大于 1 的环，即存在无限转换的方式，否则不存在。

因为边乘积较大，需要转换为 loglog 进行处理。

log(w1⋅w2⋅...⋅wn)=logw1+logw2+...+logwnlog(w_1 \cdot w_2 \cdot ... \cdot w_n) = logw_1 + logw_2 + ... + logw_n

边权乘积转化为边权log和。

即为存在边权和大于等于0的环即是无限转换，我们把边权取符号，即存在小于等于0的环即为无线转换。所以转换为判断是否存在负环。

判断负环使用SPFA，建立一个超级源点，使其可以到达所有点。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using tu = tuple<int, int, db>;
using vi = vector<int>;
using vl = vector<ll>;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 1e3 + 5, M = 3 * N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

int n, m;
int e[M], h[N], ne[M], idx;
db w[M], dis[N];

void add(int a, int b, db c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void solve()
{
	cin >> n >> m;

	memset(h, -1, sizeof h);
	for(int i = 1; i <= n; i++)
		add(0, i, 0);
	for(int i = 1; i <= m; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		add(b, d, log(a) - log(c));
	}

	auto check = [&](db x) -> bool
	{
		for(int i = 1; i <= n; i++)
			dis[i] = 1e9;
		vector<db> W(idx);
		for(int i = 0; i < idx; i++)
		{
			if(i < n) W[i] = w[i];
			else W[i] = w[i] - log(x);
		}

		vector<bool> vis(n + 1);
		vi cnt(n + 1);
		queue<int> q;
		q.push(0);
		dis[0] = 0;
		vis[0] = true;
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			vis[u] = false;

			for(int i = h[u]; ~i; i = ne[i])
			{
				int v = e[i];
				db ww = W[i];
				if(dis[u] + ww < dis[v])
				{
					dis[v] = dis[u] + ww;
					cnt[v]++;
					if(cnt[v] >= n) return false;
					if(!vis[v])
					{
						vis[v] = true;
						q.push(v);
					}

				}
			}
		}
		return true;
	};

	db l = 0, r = 1;
	while(r - l > eps)
	{
		db mid = (l + r) / 2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	cout << fixed << setprecision(10) << l << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

J Link with Arithmetic Progression

给定数列 a1,a2,...,ana_1,a_2, ..., a_n ，求一个等差数列 b1,b2,...,bnb_1, b_2, ...,b_n 使 ∑i=1n(bi−ai)2\sum \limits_{i=1}^n(b_i-a_i)^2 最小，输出最小值。

线性回归，求出一条拟合直线 y=kx+by = kx + b 可以保证题目中最小值。

k=∑i=1nxiyi−nx‾y‾∑i=1nxi2−nx‾2b=y‾−kx‾k = \frac{\sum \limits_{i=1}^n x_iy_i - n \overline x \overline y}{\sum \limits_{i=1}^nx_i^2 - n \overline x^2}\\ b = \overline y - k \overline x 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

void solve()
{
	int n;
	cin >> n;
	vl y(n + 1);
	ll sy = 0, sx = 0, a = 0, b = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> y[i];
		sx += i, sy += y[i];
		a += 1ll * i * y[i];
		b += 1ll * i * i;
	}
	ld ax = (ld)sx / n, ay = (ld)sy / n;
	ld k = (a - n * ax * ay) / (b - n * ax * ax);
	ld c = ay - k * ax;

	ld ans = 0;
	for(int i = 1; i <= n; i++)
	{
		ld x = (k * i + c - y[i]) * (k * i + c - y[i]);
		ans += x;
	}
	cout << fixed << setprecision(12) << ans << "\n";


}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

K Link with Bracket Sequence I

长度为n的括号序列a是长度为m的合法括号序列的子序列，给定a，求b的数量。

f[i][j][k]f[i][j][k] : b串有 ii 个字符，a串中前 jj 个字符是b串的子序列，还有k个左括号未匹配的数量。

转移：

i+1i+1 位置放 (，且有 j=nj=n 或 sj+1≠s_{j+1}\neq ( ，那么有转移 fi,j,k→fi+1,j,k+1f_{i,j,k}\rightarrow f_{i+1,j,k+1}。

i+1i+1 位置放 )，且有 j=nj=n 或 sj+1≠s_{j+1}\neq ) ，且 k>0k>0，那么有转移 fi,j,k→fi+1,j,k−1f_{i,j,k}\rightarrow f_{i+1,j,k-1}。

i+1i+1 位置放 (，且有 j<n,sj+1=j<n,s_{j+1}=( ，那么有转移 fi,j,k→fi+1,j+1,k+1f_{i,j,k}\rightarrow f_{i+1,j+1,k+1}。

i+1i+1 位置放 )，且有 j<n,sj+1=j<n,s_{j+1}= ) ，且k>0k>0，那么有转移 fi,j,k→fi+1,j+1,k−1f_{i,j,k}\rightarrow f_{i+1,j+1,k-1}

#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 205, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

int f[N][N][N];

void add(int &x, int y)
{
	if((x += y) >= mod)
		x -= mod;
}
void solve()
{
	memset(f, 0, sizeof f);
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	s = " " + s;
	f[0][0][0] = 1;

	for(int i = 0; i < m; i++)
		for(int j = 0; j <= min(i, n); j++)
			for(int k = 0; k <= i; k++)
				if(f[i][j][k])
				{
					if(k < m && (j == n || s[j + 1] != '('))
						add(f[i + 1][j][k + 1], f[i][j][k]);
					if(k && (j == n || s[j + 1] != ')'))
						add(f[i + 1][j][k - 1], f[i][j][k]);
					if(j < n)
					{
						if(k < m && s[j + 1] == '(')
							add(f[i + 1][j + 1][k + 1], f[i][j][k]);
						if(k && s[j + 1] == ')')
							add(f[i + 1][j + 1][k - 1], f[i][j][k]);
					}
				}

	cout << f[m][n][0] << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

L Link with Level Editor I

nn 个世界， 每个世界有一个 mm 个点的无向图，从第一个世界的编号为 11 的点出发，每个世界可以不动或可以走一条边到达下一个点 uu ，然后跳到下一个世界的点 uu ，如果跳到点 mm 则胜利。求一个最短的子段，使得其可胜利。

(i,u)(i, u) 到 (i+1,v)(i + 1, v) 有关系，可以考虑进行状态转移。

设置 f[i][j]f[i][j] : 表示到达第 ii 个世界中的 jj 号点最少需要经过多少世界

初始时： f[i][1]=1,f[i][j]=∞f[i][1] = 1, f[i][j] = \infty

两种转移方式：

  • 在当前世界原地不动，之后到下一个世界。 f[i][j]+1→f[i+1][j](i<n)f[i][j] + 1 \rightarrow f[i+1][j] (i < n)
  • 在当前世界走一条边，之后到下一个世界。f[i][u]+1→f[i+1][v](i<n),(u,v)f[i][u]+1 \rightarrow f[i+1][v] (i < n),(u, v) 属于第 ii 个世界的一条边。

第一维可以进行压缩，进行空间优化。

注意：转移的时候，是先进行走边，然后再到下一个世界。

当到达第 ii 个世界时， 先对上一层状态 f[]f[] 数组不为无穷的加一，代表进入当前世界。然后进行状态转移，转移时候利用的是转移到当前世界的数组（即下面代码的f[]f[] 数组）进行更新。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

void solve()
{
	int n, m;
	cin >> n >> m;

	vi f(m + 1, 1e9), nf;
	f[1] = 1;
	for(int i = 1; i <= n; i++)
	{
		int c;
		cin >> c;

		for(int j = 1; j <= m; j++)
			if(j != 1 && j != m && f[j] != 1e9)
				f[j]++;// 走到第 i 个世界,世界数加一
		nf = f;
		while(c--)
		{
			int u, v;
			cin >> u >> v;
			nf[v] = min(f[u], nf[v]); // 在第i个世界中进行状态转移，f[]为老的状态，新的状态存在nf[]数组中
		}
		f = nf;
	}
	cout << (f[m] == 1e9 ? -1 : f[m]) << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}
赏

   转载规则


《2022牛客多校2补题》 由 行码棋 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
AtCoder Beginner Contest 266 A-G AtCoder Beginner Contest 266 A-G
AtCoder Beginner Contest 266 A-G A 直接输出字符串中间字符即可。 #include<bits/stdc++.h> using namespace std; using ll = long l
2022-08-30 2024-02-20
Atcoder
Atcoder
下一篇 
2022牛客多校1补题 2022牛客多校1补题
2022牛客多校1补题 题解有A C D G I J六题。 题解纯属自己玩，更多详细解释还请看官方题解。 G 题意 给定 nnn ，将 1,2,...,n1,2,. . . , n1,2,...,n 视为不含前导零的字符串 求这些字符
2022-08-21 2024-02-20
多校
多校
  目录