2022牛客多校第二场解题报告

D.Link with Game Glitch

思路:对所有物品建图,二分w,边权是log(w*c/a).然后判负环,一直到没有负环为止

技巧:1.乘积->加减法(log) 2.图上二分答案 3.spfa在整个图不连通情况下判负环

代码:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
// namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 4010, M = 1e6 + 10;
const long double eps = 1e-10;
int n, m;
int h[N], v[M], to[M], tot;
int a[N], b[N], c[N], d[N];
bool vis[N];
long double w[M], dis[N];
int cnt[N]; //cnt[x]表示从1到x的最短路径包含的边数,若cnt[x]>=n,则由抽屉原理判定为有负环
void add(int a, int b, long double c) {
	w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
}
bool check(long double x) {
	for (int i = 0; i <= 1500; ++i) dis[i] = 0, vis[i] = 0, h[i] = 0, cnt[i] = 0;
    tot = 0;
	for (int i = 1; i <= m; ++i) {
		long double ww = log(a[i]) - log(c[i]) - log(x);
		add(b[i], d[i], ww);
	}
	queue<int> q;
	for (int i = 1; i <= n; ++i) q.emplace(i);
	while (q.size()) {
		int x = q.front(); q.pop();
		vis[x] = 0;
		for (int i = h[x]; i; i = to[i]) {
			int y = v[i];
			long double z = w[i];
			if (dis[y] > dis[x] + z) {
				dis[y] = dis[x] + z;
				cnt[y] = cnt[x] + 1;
				if (cnt[y] >= n) return false;
				if (!vis[y]) q.emplace(y), vis[y] = 1;
			}
		}
	}
	return true;
}
signed main() {
	IOS;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) cin >> a[i] >> b[i] >> c[i] >> d[i];
	long double l = 0, r = 1;
	for (int i = 1; i <= 100; ++i) {
		long double mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	cout << fixed << setprecision(20);
	cout << l << '\n';
}

E.Falfa with Substring

思路:先考虑至少有k个bit的情况,假设为,有,然后设为恰好有k个bit的情况,那么有,由二项式反演可得,然后变化一些卷积即可.(不会卷qwq)

这里我详细讲一下,f(k)的求法.

 

技巧:"恰好"->容斥, 求固定有k个的方法.

G.Link with Monotonic Subsequence

思路:构造即可

代码:

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
    int x = 0, y = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    return x *= y;
}
inline void wt(int x) {
    if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    do sta[top++] = x % 10, x /= 10; while (x);
    while (top) putchar(sta[--top] + '0');
}
void solve() {
	int n = rd(), block = ceil(sqrt(n));
	for (int i = 1; i * block <= n; ++i)
		for (int j = i * block; j >= (i - 1) * block + 1; --j) wtt(j);
	int k = n / block;
	for (int i = n; i >= k * block + 1; --i) wtt(i);
	puts("");
}
signed main() {
	// IOS;
	// cin >> T;
	T = rd();
	for (int i = 1; i <= T; ++i) { solve();}
}

J.Link with Arithmetic Progression

思路:线性回归,注意精度

代码:

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
    int x = 0, y = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    return x *= y;
}
inline void wt(int x) {
    if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    do sta[top++] = x % 10, x /= 10; while (x);
    while (top) putchar(sta[--top] + '0');
}
const int N = 1e6 + 10;
int n;
long double x[N], y[N], xy[N], d[N], dd[N], s[N];
void solve() {
	long double b, a, avrx = 0, avry = 0, sumx = 0, sumy = 0;
// 	n = rd();
    cin >> n;
	for (int i = 1; i <= n; ++i) cin >> y[i], sumx += i, sumy += y[i];
	avrx = sumx / n, avry = sumy / n;
	long double sumxy = 0, sumxx = 0;
	for (int i = 1; i <= n; ++i) sumxy += i * y[i], sumxx += i * i;
	b = (sumxy - n * avrx * avry) / (sumxx - n * avrx * avrx);
	a = avry - b * avrx;
	long double ans = 0;
	for (int i = 1; i <= n; ++i) {
		long double x = b * i + a - y[i];
		ans += x * x;
	}
    cout << fixed << setprecision(20);
	cout << ans << endl;
}
signed main() {
	IOS;
	cin >> T;
	for (int i = 1; i <= T; ++i) { solve();}
}

K.Link with Bracket Sequence I

思路:f[i][j][k]表示前i个b字符串匹配了前j个a字符串,还剩下k个左括号没匹配的情况
f[i][j][k] -> f[i+1][j+(s[j+1]=='(')][k+1]
f[i][j][k] -> f[i+1][j+(s[j+1]==')')][k-1]
技巧:两个序列->lcs

代码:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e6 + 10, MOD = 1e9 + 7;
char s[N];
int n, m, f[210][210][210];
//f[i][j][k]表示前i个b字符串匹配了前j个a字符串,还剩下k个左括号没匹配的情况
//f[i][j][k] -> f[i+1][j+(s[j+1]=='(')][k+1]
//f[i][j][k] -> f[i+1][j+(s[j+1]==')')][k-1]
//
void solve() {
	qio >> n >> m >> s + 1;
	for (int i = 0; i <= m; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= m; ++k) f[i][j][k] = 0;
	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) {
				(f[i + 1][j + (s[j + 1] == '(')][k + 1] += f[i][j][k]) %= MOD;
				if (k) (f[i + 1][j + (s[j + 1] == ')')][k - 1] += f[i][j][k]) %= MOD;
			}
	qio << f[m][n][0] << "\n";
}
signed main() {
	int T;
	qio >> T;
	while (T--) solve();
}

L.Link with Level Editor I

思路:建图(i, u) -> (i + 1, v), 然后dp, f[i][j]表示到达第i个世界第j个点最大的世界是多少

代码:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e4 + 10, M = 2e3 + 10;
//f[i][j]表示到达第i个世界的第j个点编号最大的世界
int n, m;
signed main() {
	qio >> n >> m;
	vector<int> f(m + 1, -1);
	int ans = INF;
	for (int i = 1; i <= n; ++i) {
		int l;
		qio >> l;
		auto nf = f;
		f[1] = i;
		while (l--) {
			int u, v;
			qio >> u >> v;
			nf[v] = max(nf[v], f[u]);
			if (v == m && nf[v] != -1) ans = min(ans, i - nf[v] + 1);
		}
		f.swap(nf);
	}
	qio << (ans >= INF / 2 ? -1 : ans) << '\n';
}