Logo FiraCode 的博客

博客

标签
暂无

CF1902C

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-27 20:52:43

思路:

假如没有插入，那么我们发现最后所有的数字都是这个数组的最大值，考虑反证：

设这个数组的最大值为 $maxn$，假设最后为 $maxn+k(k>0)$ 为最优，那么 $maxn$ 要变成 $maxn+k$，那么 $x \mid k$，于是其他的数要先到 $maxn$ 然后再到 $maxn+k$，所以实际上它相比于变成 $maxn$ 增加了一些操作，所以变成 $maxn$ 比 $maxn+k$ 更优，与假设矛盾。

证毕。

那么一个数组最优的 $x$ 为 $\gcd(a_n-a_{n-1},a_{n-1}-a_{n-2},\dots,a_{2}-a_1)$。

然后考虑增加一个数字，那么这个数为 $maxn+xk$，若 $k>0$ 时每次都要 $n$ 的代价，而 $k<0$ 时，只需要找到最大的 $k$ 使得它没有在数组中出现过即可，而代价最多为 $n$，所以 $k<0$ 一定比 $k > 0$ 更优。

然后就计算每个数到最大值的操作次数再加上插入数字的操作次数即可。

复杂度 $O(Tn \log n)$。

Code:

#include <bits\/stdc++.h>

using namespace std;

#define int long long

int T;
int n;
int a[200010];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

signed main() {
	scanf("%lld", &T);
	while (T--) {
		map<int, int> ma;
		scanf("%lld", &n);
		int Gcd = 0;
		for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), ma[a[i]] = 1;
		if (n == 1) {
			puts("1");
			continue;
		}
		sort(a + 1, a + 1 + n);
		for (int i = 2; i <= n; ++i) Gcd = gcd(Gcd, a[i] - a[i - 1]);
		int k = -1;
		while (true) {
			if (!ma[a[n] + k * Gcd]) break;
			--k;
		}

		int ans = 0;
		for (int i = 1; i <= n; ++i) ans += (a[n] - a[i]) \/ Gcd;

		ans -= k;

		printf("%lld\n", ans);
	}
	return 0;
}

CF151B题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-10-24 08:14:30

这是一道模拟题。

先建立 $3$ 个数组：

int c[1210][3];\/\/存储第i每个号码三种的个数
char st[210], name[1210][25];\/\/名字

然后判断这个电话号码应该放在哪里

int type() {
	int i, lst = 0;
	bool f1, f2;
	f1 = f2 = true;
	for(i = 1; i < 8; i++) {
		if(i % 3 == 2)
			continue;
		if(st[i] != st[lst])\/\/号码不相等
			f1 = false;
		if(st[i] >= st[lst])\/\/号码不递减
			f2 = false;
		lst = i;
	}
	return f1 + 2 * f2;
}

然后处理读入：

m0 = m1 = m2 = 0;
for(i = 1; i <= n; ++i) {
    scanf("%d%s", &nm, name[i]);
    while(nm--) {
        scanf("%s", st);\/\/读入号码
        c[i][type()]++;\/\/把号码对应的类型+1
    }
}

然后对于 $c_{i,0},c_{i,1},c_{i,2}$ 取个最大值，然后对于每个数，若他等于对应的最大值，就输出他的名字。

完整代码：

#include <bits\/stdc++.h>
using namespace std;
int c[1145][3];
char st[114], name[1145][25];
int type() {
	int i, lst = 0;
	bool f1, f2;
	f1 = f2 = true;
	for(i = 1; i < 8; i++) {
		if(i % 3 == 2)
			continue;
		if(st[i] != st[lst])
			f1 = false;
		if(st[i] >= st[lst])
			f2 = false;
		lst = i;
	}
	return f1 + 2 * f2;
}
int main() {
	int n, nm, i, m0, m1, m2;
	bool first;
	scanf("%d", &n);
	m0 = m1 = m2 = 0;
	for(i = 1; i <= n; ++i) {
		scanf("%d%s", &nm, name[i]);
		while(nm--) {
			scanf("%s", st);
			c[i][type()]++;
		}
	}
	for(i = 1; i <= n; ++i)
		m0 = max(m0, c[i][0]);
	for(i = 1; i <= n; ++i)
		m1 = max(m1, c[i][1]);
	for(i = 1; i <= n; ++i)
		m2 = max(m2, c[i][2]);
	first = true;
	printf("If you want to call a taxi, you should call: ");
	for(i = 1; i <= n; ++i)
		if(c[i][1] == m1) {
			if(first)
				first = false;
			else
				printf(", ");
			printf("%s", name[i]);
		}
	printf(".\n");
	first = true;
	printf("If you want to order a pizza, you should call: ");
	for(i = 1; i <= n; ++i)
		if(c[i][2] == m2) {
			if(first)
				first = false;
			else
				printf(", ");
			printf("%s", name[i]);
		}
	printf(".\n");
	first = true;
	printf("If you want to go to a cafe with a wonderful girl, you should call: ");
	for(i = 1; i <= n; ++i)
		if(c[i][0] == m0) {
			if(first)
				first = false;
			else
				printf(", ");
			printf("%s", name[i]);
		}
	printf(".\n");
	return 0;
}

P3007

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-04 19:31:40

题目链接

我们要判断一个变量恒为真/假/真假都可以。

方法一

我们可以强行设 $x_i$ 为假，若无解，那么 $x_i$ 一定为真或真假都行，或都不行。

要跑 $n$ 次，所以时间复杂度是 $O(nm)$。

方法二

若 $x_i$ 是指向 $\neg x_i$ 的话，我们就一定选 $x_i$ 为假。

若 $\neg x_i$ 是指向 $x_i$ 的话，我们就一定选 $\neg x_i$ 为假。

否则若 $\neg x_i$ 和 $x_i$ 没有可达关系，那么就是 ?。

那么这样的话，我们就可以判断两个点是否有可达关系就可以了，而判断可达关系的话就可以用 BFS 或 DFS。

时间复杂度为 $O(n^2)$。

CODE:

#include <bits\/stdc++.h>
using namespace std;
const int N = 2010;
int n, m;
bool ins[N], vis[N];
vector<int> e[N];
int dfn[N], low[N], idx, bel[N];
stack<int> stk;
int cnt;
char ans[N];
void taryan(int u) {\/\/联通分量
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);
	for (auto v: e[u]) {
		if (!dfn[v]) taryan(v);
		if (ins[v]) low[u] = min(low[u], low[v]);
	}
	if (dfn[u] == low[u]) {
		++cnt;
		while (true) {
			int v = stk.top();
			bel[v] = cnt;
			ins[v] = false;
			stk.pop();
			if (u == v) break;
		}
	}
}
void dfs2(int u) {\/\/dfs
	vis[u] = 1;
    for (auto v : e[u]) if (!vis[v])
        dfs2(v);
}
bool check(int s, int t) {
    memset(vis, false, sizeof(vis));
    dfs2(s);
    return vis[t];
}
int main() {
	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= m; ++i) {
		int u, v;
		char ty1[2], ty2[2];
		scanf("%d%s%d%s", &u, ty1, &v, ty2);
		--u, --v;
		u = (u * 2) + (*ty1 == 'Y');
		v = (v * 2) + (*ty2 == 'Y');
		e[u ^ 1].push_back(v);
		e[v ^ 1].push_back(u);
	}
	for (int i = 0; i < 2 * n; ++i) if (!dfn[i])
		taryan(i);
	for (int i = 0; i < n; ++i) {
		if (bel[i << 1] == bel[i << 1 | 1]) {
			puts("IMPOSSIBLE");\/\/无解
			return 0;
		}
	}
    for (int i = 0; i < n; ++i) {
        if (check(2 * i, 2 * i + 1)) ans[i] = 'Y';\/\/当i*2是2*i+1,则第i个恒为真
        else if (check(2 * i + 1, 2 * i)) ans[i] = 'N';\/\/另一种情况
        else ans[i] = '?';\/\/因为不会是无解，所以就是?
    }
    puts(ans);
    return 0;
}

P5355

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-18 16:11:23

--------------------------------------求积--------------------------------------

乘积的话就可以枚举因数，若他的两个因子都在区间里出现过，那么就输出 yuno 否则就输出 yumi。

--------------------------------------求差--------------------------------------

差值的话就是用一个二进制来表示区间的出现的数，那么差是否有 $x$，就是把这个二进制左移 $x$ 位，那么当他于以前的二进制的并还是有 $1$ 的话，就可以。

用 bitset 来维护的话就是 (s&(s << x)).any()。

--------------------------------------求和--------------------------------------

那么加的话就是看把前 $x$ 位翻转之后，原来的第 $i$ 位和现在的第 $i$ 位是不是都是 $1$。

但是翻转我们怎么做呢？

我们就可以设另一个 bitset，比如叫 $T$，那么 $T$ 就是当 $x$ 位为 $1$ 的时候，我们把 $n - x$ 设成 $1$，其中 $n$ 是 bitset 的长度。

那么翻转的结果就是 $T$ 的后 $x$ 个。

那么判断的话就是 (s << (n - x))) & T。

那么时间复杂度就变成了 $O(\frac{n}{w})$。

但是我们怎么求某一段的二进制的值呢？

我们可以用莫队来做。

然后就可用 bitset + 莫队 来稿。

----------------------------------------CODE----------------------------------------

#include <bits\/stdc++.h>

using namespace std;

#define I return
#define AK 0
#define IOI ;

typedef long long ll;

const int N = 100010, B = 500, M = 100000;
int ans[N];
int n, m, a[N], cnt[N];
bitset<N> s, t; \/\/正着和反着的bitset
array<int, 5> q[N];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for (int i = 0; i < m; ++i) { \/\/读入查询
		int opt, l, r, x;
		scanf("%d%d%d%d", &opt, &l, &r, &x);
		q[i] = {opt, l, r, x, i};
	}

	sort(q, q + m, [&](array<int, 5> a, array<int, 5> b) {
		int c = a[1] \/ B;
		if (c != b[1] \/ B) return c < b[1] \/ B;
		return c % 2 ? a[2] > b[2] : a[2] < b[2]; \/\/莫队玄学优化 
	});

	int l = 1, r = 0;
	auto add = [&](int x) {
		cnt[a[x]] ++;
		if(cnt[a[x]] == 1) {\/\/从没有变成有
			s[a[x]] = 1;\/\/第一次有，都设成1
			t[M - a[x]] = 1;
		}
	};
	auto del = [&](int x) {\/\/删除
		cnt[a[x]] --;
		if (cnt[a[x]] == 0) {\/\/从有变成没有
			s[a[x]] = 0;\/\/没有了，都设成0
			t[M - a[x]] = 0;
		}
	};

	for (int i = 0; i < m; ++i) {
		while(r < q[i][2]) ++r, add(r);
		while(l > q[i][1]) --l, add(l);
		while(r > q[i][2]) del(r), --r;
		while(l < q[i][1]) del(l), ++l;
		int opt = q[i][0], id = q[i][4], x = q[i][3];
		if (opt == 1) {\/\/减法
			ans[id] = (s & (s << x)).any();
		} else if (opt == 2) {\/\/加法
			ans[id] = (t & (s << (M - x))).any();
		} else {\/\/乘法
			for (int y = 1; y <= x \/ y; ++y) {
				if (x % y == 0) {
					ans[id] |= s[y] & s[x \/ y];
				}
			}
		}
	}
	for (int i = 0; i < m; ++i)
		puts(ans[i] ? "yuno" : "yumi");
	I AK IOI
}

CF1354D

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-28 19:27:20

题解思路：

这个题有两个操作，先看第二个，就是加数操作。

那么我们就建一棵值域树状数组，然后就直接在 $x$ 的位置加一就可以了。

那么删除的话就可以二分，就是二分第一个满足值 $\le mid$ 的个数是否 $= \left | x \right |$ 就可以了。

这个的时间复杂度是 $O(n \log^2 n)$ 的时间复杂度，需要卡卡常数才可以过。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
const int N = 1000010;
int &read(int &r){\/\/快读
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
int n, q;
template<class T>\/\/线段树模板
struct BIT {
	int c[N];
	void modify(int x, int d) {
		if (x <= 0) return;
		for (; x <= n; x += (x & -x))
			c[x] += d;
	}
	T query(int x) {
		T res = 0;
		for (; x; x -= (x & -x))
			res += c[x];
		return res;
	}
};
BIT<int> c;
int main() {
	read(n), read(q);
	for (int i = 1; i <= n; ++i) {
		int a = read(a);
		c.modify(a, 1);\/\/读入这个序列
	}
	for (int i = 1; i <= q; ++i) {
		int x = read(x);
		if (x > 0) c.modify(x, 1);\/\/把这个x位置+1
		else {
			x = -x;\/\/把x变成|x|
			x = (x < 0 ? -x : x);
			int l = 1, r = n, res = 0;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (c.query(mid) >= x) {\/\/若当前的值<=mid的数的个数是>=x，那么就可以更新答案了。
					res = mid;
					r = mid - 1;
				}else l = mid + 1;
			}
			c.modify(res, -1);\/\/把这个减去
		}
	}
	int l = 1, r = n, res = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (c.query(mid) >= 1) {\/\/就是求最小的那一个。
			res = mid;
			r = mid - 1;
		}else l = mid + 1;
	}
	printf("%d\n", res);
	return 0;
}

CF961E

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-28 20:40:56

题意

给你一个数组，求 $i,j$ 满足：

  • $1 \le x < y \le n$
  • $y \le a_x$
  • $x \le a_y$

题解思路

读入的时候，因为 $j \le n$ 所以当 $a_i > n$ 时，我们把 $a_i$ 变成 $n$ 就可以了。

然后我们可以用一个 vector 来维护 $(1)$ 和 $(3)$ 的最大可能值。

那么我们设 $v_i$ 表示最大可能为 $i$ 的数的下标是多少。

那么最大可能值就是 $i - 1$ 与 $a_i$ 取个最小值就行了。

因为 $x \le a_y$ 所以一种最大的可能就是 $x=a_y$，另一种就是 $i - 1$，因为 $x < y$ 所以 $x$ 的最大值就是 $y - 1$。

然后就枚举 $i$，然后对于每个 $i$ 枚举对应的 $v_i$，然后答案就加上 $i - \sum_{a_i < v_j}$。

AC CODE:

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int &read(int &r){\/\/快读
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
int n;
int a[N];
vector<int> v[N];\/\/表示i最大的x是多少
template<class T>
struct BIT {\/\/树状数组模板
	T c[N];
	void modify(int x, T d) {
		if (x <= 0) return;
		for (; x <= n; x += (x & -x))
			c[x] += d;
	}
	T query(int x) {
		T res = 0;
		for (; x; x -= (x & -x))
			res += c[x];
		return res;
	}
};
BIT<ll> c;
int main() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
		a[i] = min(a[i], n);
		v[min(i - 1, a[i])].push_back(i);
		\/\/因为要满足i>j那么i最大就是j-1,且i<=a[j]，所以还要与a[j]取个最小值
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		c.modify(a[i], 1);
		for (auto t : v[i]) {
			ans += i - c.query(t - 1);\/\/答案加上总数- x<a[x]的数的个数
		}
	}
	printf("%lld\n", ans);
	return 0;
}

CF1149Etj

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-02 21:17:20

题解思路

首先，先对原图进行拓扑排序。

我们求出每个点的 SG 值。

那么 $u$ 点的 SG 值，即：$SG(u) = \operatorname{mex}_{v\in son_u}(SG(v))$。

然后求出 $sum_x = \operatorname{xor}_{SG(u) = x} a_u$

那么先手必赢当且仅当存在 $sum_x$ 非零。

那么我们就找到最大的 $i$ 使得 $sum_x$ 非零。

然后对于 $i$，当有一个 $u$ 满足，$SG_u=i$ 且 $w_u \oplus sum_i < w_u$，就是存在一个满足条件的 $u$。

那么就修改 $w_i$，然后输出就可以了。

AC CODE

#include <bits\/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
int w[N];\/\/读入的数组
int d[N];\/\/度数，topsort时要用的度数
int SG[N], sum[N];\/\/这个分别就是SG函数，和SG(x)=i的w_i之和
vector<int> e[N], p;\/\/存边的，p是topsort的顺序
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		d[v] ++;
		e[u].push_back(v);
	}
	\/\/================topsort================
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		if (!d[i])
			q.push(i);
	while (q.size()) {
		int t = q.front();
		q.pop();
		p.push_back(t);
		for (auto v : e[t])
			if (!--d[v])
				q.push(v);
	}
	\/\/================topsort end================
	for (int i = p.size() - 1; i >= 0; --i) {\/\/计算SG函数
		set<int> mex;
		for (auto v : e[p[i]])
			mex.insert(SG[v]);
		for (int j = 0; ; ++j) {
			if (!mex.count(j)) {
				SG[p[i]] = j;
				break;
			}
		}
	}
	for (int i = n; i; --i)
		sum[SG[i]] ^= w[i];\/\/计算SG值为SG(i)的w[i]的异或和
	for (int i = n - 1; i >= 0; --i) {
		if (sum[i]) {\/\/这个值不是0
			puts("WIN");\/\/一定能赢。
			for (int u = 1; u <= n; ++u) {
				if (SG[u] == i && (w[u] ^ sum[i]) < w[u]) {
					w[u] ^= sum[i];
					for (auto v : e[u]) {
						w[v] ^= sum[SG[v]];
						sum[SG[v]] = 0;\/\/只有一次修改，所以修改完了要初始化成0。
					}
					for (int j = 1; j <= n; ++j) printf("%d ", w[j]);
					return 0;
				}
			}
		}
	}
	puts("LOSE");
	return 0;
}

CF1772C

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-20 19:56:03

思路

可以想到，用贪心的方法，每次相隔 $1,2,3...$。

那么当当前这个数增加了间隔的数之后，剩余的数字加上以前的数字不足 $k$ 的话，就只能把剩下的间隔都变成 $1$。

例如 $n=4,k=3$

  1. 第一个数是 1。
  2. 第二个数，与前一个间隔 $1$,是 2。
  3. 第三个数，因为 2+2=4，所以这个数间隔完之后，就没有数字了（因为要 $\le n$，且要严格递增），所以就变成间隔一个，是 3。

CODE:

#include <bits\/stdc++.h>
using namespace std;
int T;
int k, n;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &k, &n);
		printf("%d ", 1);
		bool flag = false;
		int tempk = k;
		--k;
		int id = 1, last = 1, t = 0;
		for (int i = 1; i < tempk; ++i) {
			int temp = last + id;
			if (flag) {\/\/间隔都是1
				printf("%d ", ++t);
				continue;
			}
			if (temp > n) {\/\/超过了值域
				flag = true;
				t = last + 1;
				printf("%d ", t);
				continue;
			}
			if (n - temp + 1 < k) {\/\/即使其他的间隔只有一也不足k个数，即剩下的所有的都是前一个+1，都还是会在第k个数时超过值域，那么从这个开始，以后就是间隔是1
				flag = true;
				t = last + 1;
				printf("%d ", t);
				continue;
			}
			printf("%d ", temp);\/\/否则输出这个数
			--k;\/\/剩余的数字个数减一
			last = temp;
			id++;\/\/间隔加一
		}
		puts("");
	}
	return 0;
}

CF356C

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-21 12:09:02

思路

$p_i$ 表示i的出现次数。

当 $\sum a_i < 3$ 或 $\sum a_i = 5$ 就是 -1。

当 $p_1 \ge p_2$

答案加上 $p_2$。

答案再加上 $\frac{p_1}{3} \times 2$，因为三个合并成一个，要合并两次，所以要再乘 $2$。

当 $p_1 = 1$

当 $p_3 \not = 0$

答案加一，把这个 $1$ 放到一个三里面。

否则答案加二，因为要把两个 $4$ 每个拿出一个 $1$ 给他，所以有两次。

当 $p_1=2$

答案加上 $2$，因为要么是把他两个合并，一次在把一个 $4$ 里拿出一个 $1$，或者把他们分别合成在一个三里，所以都是需要两次。

然后当 $p_1 < p_2$ 类似的搞一搞就好了。

CODE:

#include <bits\/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
int a[N], p[N];\/\/p[i]表示i的出现次数
int main() {
    scanf("%d", &n);
    int sum = 0;\/\/总和最多是4*10^6
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
        p[a[i]]++;
    }
    if (sum == 1 || sum == 2 || sum == 5) {\/\/sum不够3个，或分不成3个和4个
        puts("-1");
        return 0;
    }
    int ans = 0;
    if (p[1] >= p[2]) {
        ans += p[2];
        p[1] -= p[2];\/\/把p[2]个2和p[2]个1构成三个
        ans += p[1] \/ 3 * 2;\/\/要把p[1]里三个合成一个，因为要说服另外两个，所以再乘2
        p[3] += p[1] \/ 3;\/\/3的个数加上它里面有多少个。
        p[1] %= 3;
        if (p[1] == 1) {
            if (p[3] >= 1)
                ans++;\/\/表示有一个3，可以直接说服，然后把他放到某个有三个人的房间里。
            else
                ans += 2;\/\/否则就要把两个4每一个都说服一个来。
        }else if (p[1] == 2)
            ans += 2;\/\/因为不管是把两个一合并到一个，再从四里拿过来一个，还是
    }else {\/\/同1的处理方法
        ans += p[1];
        p[2] -= p[1];
        ans += p[2] \/ 3 * 2;
        p[3] += p[2] \/ 3;
        p[2] %= 3;
        if (p[2] == 1) {
            if (p[4] >= 1)
                ans += 1;
            else
                ans += 2;
        }
        else if (p[2] == 2)
            ans += 2;
    }
    printf("%d\n", ans);
    return 0;
}

abc268C

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-04-09 15:22:12

abc268

题意:

有 $N$ 个人从 $0$ 开始编号， 按逆时针顺序间隔均匀地坐在转盘周围。 在开始时， 第 $p_{i}$ 盘菜在第 $i$ 个人的前面。

现在， 你可以进行以下操作 $0$ 次或多次。

  • 将转盘逆时针旋转 $\frac{1}{N}$ 圈。也就是说， 旋转前在第 $i$ 号人面前的盘子现在在 $(i+1)\bmod N$ 号人面前了。

当你结束操作后，如果第 $i$ 盘菜在第 $(i-1)\bmod N$ 个人、第 $i$ 个人或第 $(i+1)\bmod N$ 个人面前，第 $i$ 个人就会感到高兴。

请求出你最多能使多少人感到高兴。

思路:

因为让第$i$个人开心开心要把第$i$盘菜转到$i-1$,$i$,$i+1$。 那么我们就记$f_i$表示转$i$次开心的人数。 那么我们记第$i$盘菜转到$i-1$,$i$,$i+1$的步数分别记为$cnt1$,$cnt2$,$cnt3$，那么$cnt_{cnt1}+1, cnt_{cnt2}+1, cnt_{cnt_3}+1$，因为转$cnt1$,$cnt2$,$cnt3$次都可以让$i$开心。 最后我们枚举转多少次（因为转$n$次就转回来了，所以枚举到$n$就足够了），然后对$cnt$求个最大值就可以了。

注意：取模会有负数要特判一下($i-1$)

$\texttt{My Code:}$

#include <bits\/stdc++.h>
using namespace std;
int n;
int a[200010], cnt[200010];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; ++i) {
		cnt[(a[i] - 1 - i - 1 + n) % n]++;\/\/转到i-1
		cnt[(a[i] - 1 - i + n) % n]++;\/\/转到i
		cnt[(a[i] - i + n) % n]++;\/\/转到i+1
	}
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans = max(ans, cnt[i]);
	printf("%d\n", ans);
	return 0;
}

$\texttt{S08577}$ $\texttt{Code}$:

这个$cnt_i$表示转$i$次，正好转到面前的个数。 那么最后统计答案的就要在少转或多转一次（因为若和他想等的菜在$i+1$或$i-1$，那么在少/多转一次就能转到）

#include<iostream>
#include<cstring>
using namespace std;
int a[200010],b[200010],c[200010];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        int t=a[i]-i;
        if(t>=0) b[i]=t;
        else b[i]=t+n;
        c[b[i]]++;
    }
    int maxn=0;
    for(int i=1;i<n;i++){
        maxn=max(maxn,c[i-1]+c[i]+c[i+1]);
    }
    maxn=max(maxn,c[0]+c[1]+c[n-1]);
    maxn=max(maxn,c[n-1]+c[n-2]+c[0]);
    cout<<maxn;
    return 0;
}

$\texttt{addnine}$ $\texttt{Code}$

这里用max_element求得最大值。

#include <bits\/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
using ll = long long;
using ld = long double;

int main() {
    int N;
    cin >> N;
    vector<int> p(N), q(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    vector<int> cnt(N, 0);
    for (int i = 0; i < N; i++) {
        int x = (p[i] + N - i) % N;
        cnt[(x-1+N) % N]++;
        cnt[x]++;
        cnt[(x+1) % N]++;
    }
    cout << *max_element(all(cnt)) << endl;
    return 0;
}
共 105 篇博客
中文 English

鲁ICP备2025150228号

服务器时间: 2026-01-29 06:40:43 | 开源项目