首页 > 其他分享 >牛客多校1

牛客多校1

时间:2023-07-23 17:56:15浏览次数:43  
标签:const int ll 多校 long 牛客 return rhs

A.Almost Correct

题意:

给出一个长度为\(n\)的\(01\)串\(s\),他一定是没有被排序的,构造不超过\(120\)对的操作序列,使得他不能对\(s\)排序,但可以对长度为\(n\)的其他\(01\)序列排序。

思路:

  • 设\(s\)中最左边的位置为\(p\),首先先让所有不在\(p\)位置的\(1\)与\(p\)操作,这样对原串没有影响,但在其他串\(t\)可能将这个位置替换为\(0\)。

  • 此时固定\(p\)排序,指在\(s\)中固定原串不动,使用如下方法

for(int i = n; i >= 1; i--) {
    for(int j = i - 1; j >= 1; j--) {
        if(j == p) continue;
        operate(j, i);
    }
}

这样使得\(1\)尽量靠后了。如果是从前到后冒泡,可能会出现停在\(p\)等等问题

  • 此时\(t\)只可能是排序好的,或者是\(p\)位置是\(1\)且除了\(p\)是排序好的。

如果\(t\)的\(1\)是多于\(s\)的,那么我们只需要把这个\(1\)最多交换到排好的\(1\)前面一个位置即可,否则,他一定能被第一点操作影响,从而\(p\)位置是\(0\),不会是这样的情况

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;

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

	freopen("out.txt", "w", stdout);

	int t;
	cin >> t;

	while(t--) {
		string s;
		int n;
		cin >> n >> s;

		vector<pair<int, int>> ans;

		s = " " + s;

		vector<int> one;
		for(int i = 1; i <= n; i++) {
			if(s[i] == '1') {
				one.emplace_back(i);
			}
		}

		for(int i = 1; i < one.size(); i++) {
			ans.emplace_back(one[0], one[i]);
		}

		for(int i = n; i >= 1; i--) {
			for(int j = i - 1; j >= 1; j--) {
				if(j == one[0]) continue;
				ans.emplace_back(j, i);
			}
		}

		int g = (int)one.size() - 1;
		for(int i = one[0]; i <= n - g - 2; i++) {
			ans.emplace_back(i, i + 1);
		}

		cout << ans.size() << "\n";
		assert(ans.size() <= 120);
		for(auto &[i, j] : ans) {
			cout << i << " " << j << "\n";
		}
	}

    return 0;
}

H.Matches

题意:

给出两个长度都为\(n\)的数组\(a,b\),设

\[d = \sum_{i = 1} ^ {n} |a_{i} - b_{i}| \]

现在允许交换任意一个数组里的任意一对数。问能操作到的最小的\(d\)是多少?

思路:

只需要考虑交换\(a\)数组里的某一对即可。

我们把一对\((a_{i},b_{i})\)看成数轴上的一条线段,\(d\)就是所有线段的长度之和。

一次操作影响两条线段的端点,且有

  • 一条线段有两种情况,正序\((a_{i} \leq b_{i})\),反序\((a_{i}\ge b_{i})\)

  • 两条线段有三种相交情况:不相交,包含,部分相交

枚举六种情况,发现只有当两条线段一条正序一条反序并且相交的时候才有最大损失,所以只需要找到两种类型不同的线段两两最大相交即可。

按左端点排序,记录之前的线段最大的右端点为\(mr\),枚举当前的线段\((l, r)\),由于按左端点排序,左端点一定包含在之前线段,只需要把\(r\)跟\(mr\)比较即可

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e6 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;

struct ele {
	int x, y, op;
	ele() = default;
	ele(int x, int y, int op) {
		this->x = x;
		this->y = y;
		this->op = op;
	}
};

int n, a[N], b[N];
vector<ele> vec;

int main() {
    std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	cin >> n;
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for(int i = 1; i <= n; i++) {
		cin >> b[i];
	}

	for(int i = 1; i <= n; i++) {
		ans += abs(a[i] - b[i]);
		vec.emplace_back(min(a[i], b[i]), max(a[i], b[i]), a[i] <= b[i]);
	}

	sort(vec.begin(), vec.end(), [&](auto x, auto y) {
		return x.x < y.x;
	});

	int maxr[2] = {-inf, -inf};

	int max1 = 0;
	for(auto &[x, y, op] : vec) {
		max1 = max(max1, min(y, maxr[op ^ 1]) - x);
		maxr[op] = max(maxr[op], y);
	}

	cout << ans - 2ll * max1 << endl;
    return 0;
}

J.Roulette

题意:

有一个人在玩游戏,一开始他会投入一块钱,如果输了什么都不会获得,如果赢了会获得投入的钱的两倍,输赢概率都是\(\frac{1}{2}\)。如果这一个人输了,他下一把会投入上一把投入的钱的两倍,直到玩不起为止。现在有一个人有\(n\)元,问赚到\(m\)元的概率是多少?

思路:

这个游戏有个特点:只要赢了,不但把之前投入的钱拿回,还倒赚一块,但每次他能玩的次数是有限的。

他要赚\(m\)元,则在\(m\)元前,每次到最后没钱之前一定要赢。比如现在有\(12\)块,最多只能支付起\(1+2+4\),他最多只能玩三局,并且最迟一定要在第三局赢。

假设现在有\(x\)元,能玩的局数即\(log_{2}(x + 1)\),每赚一元钱的概率即玩一场的概率+玩两场+...+玩\(log_{2}(x+1)\),即

\[(\frac{1}{2})^{1} + (\frac{1}{2})^{2} + ... + (\frac{1}{2})^{log_{2}(x + 1)} \]

直到下一个阶段都是这个概率,一阶段一阶段计算即可

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;

namespace ModInt {
	const int P = mod;
	using i64 = long long;
	int norm(int x) {
		if (x < 0) {
			x += P;
		}
		if (x >= P) {
			x -= P;
		}
		return x;
	}
	template<class T>
	T power(T a, int b) {
		T res = 1;
		for (; b; b /= 2, a *= a) {
			if (b % 2) {
				res *= a;
			}
		}
		return res;
	}
	struct Z {
		int x;
		Z(int x = 0) : x(norm(x)) {}
		int val() const {
			return x;
		}
		Z operator-() const {
			return Z(norm(P - x));
		}
		Z inv() const {
			assert(x != 0);
			return power(*this, P - 2);
		}
		Z &operator*=(const Z &rhs) {
			x = i64(x) * rhs.x % P;
			return *this;
		}
		Z &operator+=(const Z &rhs) {
			x = norm(x + rhs.x);
			return *this;
		}
		Z &operator-=(const Z &rhs) {
			x = norm(x - rhs.x);
			return *this;
		}
		Z &operator/=(const Z &rhs) {
			return *this *= rhs.inv();
		}
		friend Z operator*(const Z &lhs, const Z &rhs) {
			Z res = lhs;
			res *= rhs;
			return res;
		}
		friend Z operator+(const Z &lhs, const Z &rhs) {
			Z res = lhs;
			res += rhs;
			return res;
		}
		friend Z operator-(const Z &lhs, const Z &rhs) {
			Z res = lhs;
			res -= rhs;
			return res;
		}
		friend Z operator/(const Z &lhs, const Z &rhs) {
			Z res = lhs;
			res /= rhs;
			return res;
		}
		friend std::istream &operator>>(std::istream &is, Z &a) {
			i64 v;
			is >> v;
			v %= P;
			a = Z(v);
			return is;
		}
		friend std::ostream &operator<<(std::ostream &os, const Z &a) {
			return os << a.val();
		}
	};
}

using mint = ModInt::Z;

mint sum[N];

int main() {
    std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	mint now = mint(1) / 2;
	for(int i = 1; i <= 40; i++) {
		sum[i] = sum[i - 1] + now;
		now /= 2;
	}

	int tot = n + m;

	mint ans = 1;
	while(n < tot) {
		int can = __lg(n + 1);
		int r = min((1 << (can + 1)) - 1, tot);
		ans *= ModInt::power(sum[can], r - n);
		n = r;
	}

	cout << ans << endl;

    return 0;
}

K.Subdivision

题意:

给出一副\(n\)个点,\(m\)个边的图,可以在一条边上加上新点,即选择一条边\((u,v)\),删去他,并且加上\((u,w),(w,v)\),问如此操作,最后距离\(1\)不超过\(k\)的点最多有多少个?

思路:

既然要加点构造新边,还要考虑让距离最小,我们在bfs树上考虑。

构造bfs树后,我们应该尽量考虑在叶子结点加边,这样一定更好,因为不会增加子树这么多链的距离。

在树上加边时,是加在与父亲相连的边的。因为\(1\)无父亲,所以叶子加边需要特判掉\(1\)。

同时还需要考虑回边,回边对距离没影响,所以每个点有回边的话都应该在回边上添加。

在树上添加后回边不能添加,有回边的时候回边添加一定不会比树上更差,因为回边的数量是\(\geq1\)的,所以优先在回边上添加。

预处理每个点的深度,回边数量以及是否是叶子结点即可

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;

bool vis[N], leaf[N];
int be[N];
int n, m, k, depth[N], dis[N];
long long ans;
vector<int> g[N];

void dfs(int u, int fa) {
	depth[u] = depth[fa] + 1;
	vis[u] = true;
	if(depth[u] > k + 1) {
		return;
	}
	leaf[u] = true;
	for(int v : g[u]) {
		if(v == fa) {
			continue;
		}
		if(vis[v]) {
			be[u]++;
			be[v]++;
		} else if(dis[v] == dis[u] + 1) {
			dfs(v, u);
			leaf[u] = false;
		}
	}
}

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

	cin >> n >> m >> k;
	while(m--) {
		int u, v;
		cin >> u >> v;

		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}

	queue<int> q;
	q.emplace(1);
	dis[1] = 1;

	while(!q.empty()) {
		int u = q.front();
		q.pop();

		for(int v : g[u]) {
			if(dis[v] == 0) {
				dis[v] = dis[u] + 1;
				q.emplace(v);
			}
		}
	}

	dfs(1, 0);
	for(int i = 1; i <= n; i++) {
        if(depth[i] && depth[i] - 1 <= k) {
            ans++;
            if(be[i]) {
                ans += 1ll * be[i] * (k - (depth[i] - 1));
            } else if(leaf[i] && i > 1) {
                ans += k - (depth[i] - 1);
            }
        }
	}

	cout << ans << endl;
    return 0;
}

L.Three Permutations

题意:

给出了三个长度为\(n\)的排列\(a,b,c\),现在有三个数\((x,y,z)\)为\((1,1,1)\),下一个时刻他们会变成\((a_{y},b_{z},c_{x})\)。

给出\((x',y',z')\),问\((1,1,1)\)至少过多久才能变为\((x',y',z')\),不可能的话输出\(-1\)

思路:

如果将他们置换下去,即:

\((x,y,z)\rightarrow(a_{y},b_{z},c_{x})\rightarrow(a_{b_{z}},b_{c_{x}},c_{a_{y}})\rightarrow(a_{b_{c_{x}}},b_{c_{a_{y}}},c_{a_{b_{z}}})\)

会发现每过三个时刻,就是原数的一个置换,这样,枚举开始时刻\(t=0,1,2\),走到数\(k\)的时间可以求出,并且是线性的。

设\(f(x) = a_{b_{c_{x}}},g(x)=b_{c_{a_{x}}},h(x)=c_{a_{b_{x}}}\)

tf[0/1/2][k]为过了\(0/1/2\)时刻后,通过\(f(x)\)置换走到\(k\)的最短时间,tg[0/1/2][k], th[0/1/2][k]同理。

lenf[0/1/2]为过了\(0/1/2\)时刻后,\(f(x)\)置换环的长度,leng[0/1/2], th[0/1/2]同理。

那么我们只需要枚举开始时间\(t=0,1,2\),满足下列同余方程组的解就是最短时间

\[x \equiv t+tf[t][x']\ (mod\ lenf[t]) \\ x \equiv t+tg[t][y']\ (mod\ leng[t]) \\ x \equiv t+th[t][z']\ (mod\ lenh[t]) \\ \]

exgcdexcrt合并计算即可。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;

int n, pa[N], pb[N], pc[N];

using tp = tuple<int, int, int>;

tp f(int x, int y, int z) {
	return {pa[y], pb[z], pc[x]};
}

void solve(int *t, int now, int &len, const function<int(int)>& f) {
	len = 0;
	while(t[now] == -1) {
		t[now] = len;
		len += 3;
		now = f(now);
	}
}

int lenf[3], leng[3], lenh[3];
int tf[3][N], tg[3][N], th[3][N];

void exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b, x, y);
	ll temp = x;
	x = y;
	y = temp - a / b * y;
}

ll sf(ll a, ll b, ll c) {
	if (a < 0) {
		a = -a;
		c = -c;
	}
	ll x, y, base = gcd(a, b);
	if(c % base) {
		return INF;
	}
	exgcd(a, b, x, y);
	x *= c / base;
	ll p = b / base;
	x = (x % p + p) % p;
	if (x < 0) x += abs(p);
	return x;
}

ll excrt(vector<ll> r, vector<ll> p) {
	for(int i = 1; i < 3; i++) {
		ll tmp = sf(-p[i], p[i - 1], r[i] - r[i - 1]);
		if(tmp == INF) {
			return INF;
		}
		r[i] = r[i] + tmp * p[i];
		p[i] = lcm(p[i - 1], p[i]);
	}
	return sf(1ll, p[2], r[2]);
}

int main() {
    std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> pa[i];
		for(int j = 0; j <= 2; j++) {
			tf[j][i] = -1;
		}
	}
	for(int i = 1; i <= n; i++) {
		cin >> pb[i];
		for(int j = 0; j <= 2; j++) {
			tg[j][i] = -1;
		}
	}
	for(int i = 1; i <= n; i++) {
		cin >> pc[i];
		for(int j = 0; j <= 2; j++) {
			th[j][i] = -1;
		}
	}

	int x = 1, y = 1, z = 1;
	for(int i = 0; i <= 2; i++) {
		solve(tf[i], x, lenf[i], [&](int x) { return pa[pb[pc[x]]]; });
		solve(tg[i], y, leng[i], [&](int x) { return pb[pc[pa[x]]]; });
		solve(th[i], z, lenh[i], [&](int x) { return pc[pa[pb[x]]]; });
		tie(x, y, z) = f(x, y, z);
	}

	int q;
	cin >> q;

	while(q--) {
		int xx, yy, zz;
		cin >> xx >> yy >> zz;

		ll ans = INF;
		for(int i = 0; i <= 2; i++) {
			if(tf[i][xx] == -1 || tg[i][yy] == -1 || th[i][zz] == -1) {
				continue;
			}

			ans = min(ans, excrt({i + tf[i][xx], i + tg[i][yy], i + th[i][zz]}, {lenf[i], leng[i], lenh[i]}));
		}

		if(ans == INF) ans = -1;
		cout << ans << endl;
	}

	return 0;
}

M.Water

题意:

有两个杯子,容量分别为\(A,B\),有以下四种操作:

  • 装满这个杯子
  • 倒空这个杯子
  • 喝掉这个杯子里的水
  • 把某个杯子的水倒到另一个杯子里去,如果另一个杯子不够装了,保留在当前杯子

问最少需要几步才能喝到恰好\(x\)的水?

思路:

喝掉的水能够被表示为\(uA+vB\)的形式,所以是否可行可以考虑不定方程

\[uA+vB=x \]

只需要他有解,即

\[gcd(A, B) | x \]

在此情况下,讨论\(uA+vB=x\)的解情况,此时方程的含义为喝/倒了\(u\)杯\(A\),喝/倒了\(v\)杯\(B\)

  • 如果\(u >0, v > 0\)

    那么此时代表的操作就是倒了一个杯子直接喝这个杯子,操作次数即\(2(u+v)\)

  • 如果\(u > 0, v < 0\)

    此时\(B\)杯是倒掉的,我们不考虑喝\(B\)杯,考虑的操作应该是喝\(A\)杯和喝一直从\(A\)杯倒给\(B\)杯后倒满剩下的。

    假设我们喝的\(u\)杯\(A\)里有\(k\)杯是直接喝的,剩下\(u-k\)杯是经过与\(B\)操作后喝的。

    再设我们与\(B\)操作的\(u-k\)杯里有\(t\)杯是需要倒掉的,剩下\(u-k-t\)是不需要倒的。

    按顺序地:

    • \(k\)杯经过倒\(A\),直接喝
    • \(t\)杯经过倒\(A\),分给\(B\),喝\(A\)剩下的,清空\(B\)。最后一次本操作可以不清空,这是为什么\(-1\)的原因
    • \(u-k-t\)杯,倒给\(A\),分给\(B\)

    其中\(t=-v\),那么总次数为

    \[2k + 4t + 2(u-k-t) - 1 = 2(u + t) - 1 = 2(u - v) - 1 \]

  • 如果如果\(u < 0, v > 0\)

    同第二种一样分析,总次数为\(2(v-u) - 1\)

假设\(A\leq B\),那么应尽量让一次倒的或者喝的水多,即尽可能让\(|u|\)小

因此exgcd求的最小的非负\(u\)解,然后考虑两个比他小的解即可,这两个解一定包括\(|u|\)尽可能小的情况了

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;

void exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b, x, y);
	ll temp = x;
	x = y;
	y = temp - a / b * y;
}

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

	int t;
	cin >> t;

	while(t--) {
		ll a, b, x;
		cin >> a >> b >> x;

		if(a > b) {
			swap(a, b);
		}

		ll g = gcd(a, b);

		if(x % g) {
			cout << -1 << "\n";
			continue;
		}

		ll u, v;
		exgcd(a, b, u, v);

		u *= x / g;
		ll du = b / g;
		u = (u % du + du) % du;

		ll ans = INF;
		for(int i = 1; i <= 3; i++) {
			v = (x - a * u) / b;
			ans = min(ans, 2 * (abs(u) + abs(v)) - (u * v < 0));
			u -= du;
		}

		cout << ans << "\n";
	}
    return 0;
}

标签:const,int,ll,多校,long,牛客,return,rhs
From: https://www.cnblogs.com/yawnsheep/p/17575324.html

相关文章

  • 牛客多校第二场补题
    牛客多校2I.LinkwithGomoku题意:两个人下五子棋,给出棋盘大小,构造一种方案,使得平局。思路:考虑这样构造xxxxooxxxxxxxxooooox以五一个为一个循环,多出来的部分也以这种方式构造,唯一的问题就是当有奇数行时会导致先手的棋子太多,因此当n为奇数时,让最后一行这样填充xoxoxox.......
  • 牛客第一场补题
    牛客多校1D.Chocolate题意:A、B轮流吃巧克力,当一个人选择一个点吃的时候,会把这个点及其左下的所有全部吃完,谁先吃完谁就输了,给出巧克力的大小,问谁会赢。思路:考虑当一个人吃完只剩一行或一列时,那么下一个吃的人就可以控制把最后一块留给这个人,因此当一个人吃完剩一行和一列的......
  • 杭电多校第一场补题
    杭电多校第一场1001Hide-And-SeekGame题意:给出一棵树,每次询问第一个人从Sa-Sb之间来回走,第二个人在Ta-Tb之间来回走,最早相遇的节点,如果无法相遇就输出-1做法:由于数据量是1e3级别,因此对于每一条路径都可以使用暴力找祖先的方法求出路径,然后对于路径上的每一个节点,其出现的时间......
  • 2023牛客暑期多校训练营2 补题
    D.TheGameofEating题意:有n个人和m道菜,每个人对每个菜的都有一个喜好度a[i][j],所有人都知道其他人的喜好度,现在需要上k道菜,从1,2...,n,1,2.....的顺序来选,如果每个人都只考虑自己的喜好,问最后哪些菜会被端上来Solution我们考虑到所有人都知道其他人的喜好度,也就是说,假设当前要选......
  • 牛客多校2
    D.TheGameofEating题意:有\(n\)个人,\(m\)种菜,从\(1\)开始轮流点菜,一共点\(k\)道,\(n\)点完轮到\(1\),直到点完,点过的菜其他人不能再点。第\(i\)个人对第\(j\)道菜有\(A_{i,j}\)的喜好度,每个人都想让自己对所有已选的菜的喜好度总和最大,他们能彼此看到对菜的喜好度,问最后点了的......
  • 暑假牛客多校第二场 2023-7-21
    未补完E.Square算法:二分做法:我们依据x来枚举k,得到\(x*10^k\),用二分在[0,1e9]查找mid的平方值,且这个值是第一个大于等于\(x*10^k\)的值。得到这个值后我们再判断这个值在除\(10^k\)后是否与\(x\)相等即可。code#include<iostream>#include<cstring>#incl......
  • 2023牛客多校7.21补题
    D-TheGameofEating题意:一共有m道菜,n个人轮流点一道菜,一共点k道。第i个人对第j道菜的喜爱程度\(A_{i,j}\)对所有人公开,一个人点了菜所有人都可以吃到。每个人都希望最大化自己的喜爱程度之和,求最终的点菜集合。分析:很容易想到每个人点菜时都点当前剩下的菜中自己最喜爱的,但是......
  • 牛客暑假多校 2023 第二场
    写在前面比赛地址:https://ac.nowcoder.com/acm/contest/57356。我是MINUS-FIFTEEN级超级战犯。澄清一下,我不是声优厨,我不是声优厨,我不是声优厨。同样是题目选补,我是飞舞。以下个人向难度排序。I签到。随便手玩一下就行。D虽然每个人都倾向于吃到自己最喜欢的菜,但给在......
  • 2023 牛客暑期多校
    7.17我正开,Dgjk倒开,AHJKLMA-AlmostCorrect设\(s\)中\(0\)的下标集合为\(S_{0}\),\(1\)的为\(S_{1}\),最右边的\(0\)的下标\(r\),最左边\(1\)的下标\(l\)。\(s\)没有排好序所以\(l\le|S_{1}|<r\)\(\foralli\inS_{0},(i,r)\)\(\foralli\inS_{1},(l......
  • 2023牛客多校2
    H.0and1inBIT题意给一串操作字符串,其中包含操作\(A,B\):\(A\)代表将二进制每一位反转。\(B\)代表将二进制加\(1\)。且当二进制为全\(1\)时,二进制变为全\(0\)现在包含多次询问,每次询问给定一个区间(区间需要计算得到),给定一个初始二进制\(x\),问你二进制在经过操作字符串对......