首页 > 其他分享 >AtCoder Regular Contest 154 C Roller

AtCoder Regular Contest 154 C Roller

时间:2023-06-23 23:55:30浏览次数:58  
标签:AtCoder typedef 154 int long Regular maxn m2

洛谷传送门

AtCoder 传送门

被这题干爆了

考虑把环压缩成块。这样一次操作就是,选择两个相邻的块,把左边块长度减 \(1\),右边块长度加 \(1\)。

特判 \(a, b\) 所有块长都是 \(1\) 的情况,这种情况不能操作。

排除掉上面的情况,我们断言:有解的充要条件是,存在某一种 \(a\) 的顺序,使得 \(b\) 是它的子序列。

充分性:因为存在长度 \(> 1\) 的块,所以块的位置可以随意移动,只要保持相对位置不变即可。

必要性:考虑证明它的逆否命题。如果不是子序列,那 \(a\) 不可能凭空中间冒出一个块使得有解,因为只能扩充或压缩块。

然后这个东西朴素 \(O(n^2)\) 判定即可。

code
// Problem: C - Roller
// Contest: AtCoder - AtCoder Regular Contest 154
// URL: https://atcoder.jp/contests/arc154/tasks/arc154_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 5050;

int n, m1, m2, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];
bool vis[maxn];

inline bool check() {
	int j = 1;
	for (int i = 1; i <= m1; ++i) {
		if (j <= m2 && e[i] == d[j]) {
			++j;
		}
	}
	return j > m2;
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	m1 = m2 = 0;
	for (int i = 1, j = 1; i <= n; i = (++j)) {
		while (j < n && a[j + 1] == a[i]) {
			++j;
		}
		c[++m1] = a[i];
	}
	for (int i = 1, j = 1; i <= n; i = (++j)) {
		while (j < n && b[j + 1] == b[i]) {
			++j;
		}
		d[++m2] = b[i];
	}
	if (c[1] == c[m1] && m1 > 1) {
		--m1;
	}
	if (d[1] == d[m2] && m2 > 1) {
		--m2;
	}
	if (m1 == n && m2 == n) {
		for (int i = 1; i <= n; ++i) {
			if (a[i] != b[i]) {
				puts("No");
				return;
			}
		}
		puts("Yes");
		return;
	}
	for (int i = 1; i <= m1; ++i) {
		int t = 0;
		for (int j = i; j <= m1; ++j) {
			e[++t] = c[j];
		}
		for (int j = 1; j < i; ++j) {
			e[++t] = c[j];
		}
		if (check()) {
			puts("Yes");
			return;
		}
	}
	puts("No");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,154,int,long,Regular,maxn,m2
From: https://www.cnblogs.com/zltzlt-blog/p/17500520.html

相关文章

  • 【题解】AtCoder-ABC306G Return to 1
    这也太强了!容易想到的是用若干环拼出这个\(10^{10^{100}}\),也就是这些环的\(\gcd\mid10\)。之后就不会了。先正图反图两次DFS,只留下\(1\)所在强连通分量里的边,对正图跑DFS生成树,定义其深度从\(0\)开始,然后有一个结论是:对于任何正整数\(a\),图中存在一个包含\(1\)......
  • AtCoder Beginner Contest 229(F,G)
    AtCoderBeginnerContest229(F,G)F(二部图,dp)F这个题大致是给你\(n+1\)个点,为\(0\)到\(n\),然后\(n\)条边是点\(0\)到\(1...n\)这些点的\(n\)条边,后面还有\(n\)条边,连接点\(i\)和\(i+1\)(其中\(i\)为\(1\)到\(n\),其中\(n\)是和\(1\)连接的)前\(n\)条边的价值是\(a_i\),后......
  • AtCoder Beginner Contest(abc) 306
    A-Echo题目大意把一个字符串的每个字符输出两遍解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;typedefpair<int,int>PII;constintN=1e6+10;intn,m;signedmain(){cin>>n;string......
  • AtCoder Regular Contest 162 F Montage
    洛谷传送门AtCoder传送门题目限制可以被改写成,如果\(A_{a,b}=A_{c,d}=1\),那么\(A_{a,d}=A_{c,b}=1\)。考虑删去空白的行和列,那么对于每个\(A_{a,b}=A_{c,d}=1\),矩形\((a,b),(c,d)\)中一定都是\(1\)。发现每一行只可能存在一个极长\(1\)区间。并......
  • AtCoder Regular Contest 162 E Strange Constraints
    洛谷传送门AtCoder传送门完全没有思路。但是其实不难的。设\(d_i\)为\(i\)在\(B\)中的出现次数,题目要求:\(\foralli\in[1,n],d_i\leA_i\);对于位置\(i\),\(d_j\leA_i\)的数\(j\)可以被放到\(B_i\)。考虑按照\(d_i\)从大到小dp。设\(f_{i,j,k}\)......
  • AtCoder Beginner Contest(abc) 304
    A-FirstPlayer题目大意顺时针给定一个序列,序列的元素由一个字符串和一个数字组成;我们需要从有最小数字的元素开始,顺时针遍历整个序列,并输出字符串;解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;ty......
  • CMU15445 (Fall 2020) 数据库系统 Project#4 - Concurrency Control 详解
    前言一个合格的事务处理系统,应该具备四个性质:原子性(atomicity)、一致性(consistency)、隔离性(isolation)和持久性(durability)。隔离性保证了一个活跃的事务(还没提交或者回滚)对数据库所做的系统对于其他的活跃事务是不可见的,看起来就像某一时刻就只有一个事务在操作数据库。然而完美的......
  • AtCoder Beginner Contest(abc) 300
    A-N-choicequestion题目大意从n个数里面找出a+b的结果解题思路签到题不多嗦了神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;typedefpair<int,int>PII;constintN=310;intn;signedmain(){inta,b;cin>>n......
  • SNN-RAT: Robustness-enhanced Spiking Neural Network through Regularized Adversar
    郑重声明:原文参见标题,如有侵权,请联系作者,将会撤销发布!同大组工作 Abstract ......
  • AtCoder Regular Contest 162
    A答案即后缀最小值个数。时间复杂度\(\mathcal{O}(n)\)。提交记录:Submission#42717665-AtCoderRegularContest162B发现操作不改变逆序对个数奇偶性。逆序对个数为奇数则无解;为偶数则可以直接模拟。时间复杂度\(\mathcal{O}(n^2)\)。提交记录:Submission#42718848......