首页 > 其他分享 >ARC154

ARC154

时间:2023-07-17 23:24:52浏览次数:45  
标签:cout int cin tot ARC154 -- tie

[ARC154A] Swap Digit

和一定差小积大,竟可能的使两个数差大即可。

复杂度 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int n;
string s, t;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s >> t;
	s = "." + s; t = "." + t;
	for (int i = 1; i <= n; ++i) {
		if (s[i] < t[i]) swap(s[i], t[i]);
	}
	ll x = 0, y = 0;
	for (int i = 1; i <= n; ++i) {
		x = x * 10 % mod + s[i] - '0';
		x %= mod;
		y = y * 10 % mod + t[i] - '0';
		y %= mod;
	}
	cout << x * y % mod << endl;
	return 0;
}

[ARC154B] New Place

贪心。

我们找到 \(t\) 最长的后缀,满足其为 \(s\) 子序列,然后答案就是 \(n\) 减去其长度。

复杂度 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
int n, cnts[N], cntt[N];
string s, t;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s >> t;
	s = "." + s; t = "." + t;
	for (int i = 1; i <= n; ++i) {
		++cnts[s[i] - 'a'];
		++cntt[t[i] - 'a'];
	}
	for (int i = 0; i < 26; ++i) {
		if (cnts[i] != cntt[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	int cur = n;
	for (int i = n; i >= 1; --i) {
		if (s[cur] == t[i]) --cur;
	}
	cout << cur << endl;
	return 0;
}

[ARC154C] Roller

和上一题挺像的。

我们先把 \(B\) 序列同色块合并,\(A\) 序列倍长。

然后枚举 \(A\) 长为 \(n\) 的子段,看 \(B\) 是否为其子序列即可。

至于证明,感性理解。

复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
int T, n, a[N], b[N], c[N], tot, cur;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n; tot = 0;
		for (int i = 1; i <= n; ++i) cin >> a[i], a[i + n] = a[i];
		for (int i = 1; i <= n; ++i) {cin >> b[i]; if (b[i] != b[i - 1]) c[++tot] = b[i];}
		if (tot > 1 && c[tot] == c[1]) --tot;
		int ans = 0;
		if (tot == n) {
			ans = 1;
			for (int i = 1; i <= n; ++i) ans &= (c[i] == a[i]);
		} else {
			for (int i = 1; i <= n; ++i) {
				cur = 1;
				for (int j = i; j <= i + n - 1; ++j) {
					if (a[j] == c[cur]) ++cur;
				}
				ans |= cur > tot;
			}
		}
		if (ans) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

[ARC154D] A + B > C ?

交互题。

定义 \(\operatorname{cmp}(x,y)\) 为 \(a_x+a_{fir}>a_y\),其中 \(fir\) 为 \(1\) 的位置。

我们先跑一边,找到 \(1\) 的位置。

然后将 \(\operatorname{cmp}(x,y)\) 作为比较函数跑 stable_sort 排序。

不用 sort 是放置比较次数过多被卡。

最后输出答案即可。

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

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;
int a[N], ans[N], fir, n;
bool cmp(int i, int j) {
	cout << "? " << i << " " << fir << " " << j << endl;
	fflush(stdout);
	string s; cin >> s;
	if (s == "Yes") return true;
	return false; 
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fir = 1;
	for (int i = 2; i <= n; ++i) {
		if (cmp(fir, i)) {
			fir = i;
		}
	}
	for (int i = 1; i <= n; ++i) a[i] = i;
	swap(a[1], a[fir]);
	stable_sort(a + 1, a + n + 1, cmp);
	for (int i = n; i >= 1; --i) ans[a[i]] = n - i + 1;
	cout << "!" << " ";
	for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
	cout <<endl;
	fflush(stdout);
	return 0;
}

标签:cout,int,cin,tot,ARC154,--,tie
From: https://www.cnblogs.com/HQJ2007/p/17561588.html

相关文章

  • 「解题报告」ARC154F Dice Game
    看起来就多项式,跟概率有关就上概率生成函数吧。考虑类似于FlipCells的套路,设\(F(x)\)为翻出所有的生成函数,\(G(x)\)为第一次翻出所有的生成函数,\(H(x)\)是翻出后任......
  • [数学记录]arc154F Dice Game
    看这篇看懂的,感觉比洛谷题解的两篇具体不少。来写一下翻译。看懂后觉得官方题解更简练的,但显然我还是新手。思维走过的道路是无可替代的。题意:\(n\)面的骰子每次随......
  • ARC154E Reverse and Inversion(*)
    ARC154EReverseandInversionACrecord......
  • Solution to ARC154F Dice Game -- Generating functions and polynomials
    Linktothequestion:Luogu,AtCoderPrefaceTheveryfirstgeneratingfunctionandpolynomialproblemsolvedinmylife!Thisblogisadetailedexplanationa......
  • 「ARC154F」Dice Game
    题目点这里看题目。你有一个\(n\)个面的骰子。每次抛骰子的时候,每个面出现的概率相等。现在开始抛骰子。设\(X\)为每个面都被扔出至少一次时的抛骰子次数,你需要对......
  • ARC154 解题报告【A-D】
    AtcoderRegularContest154ContestlinkMyresult声明:代码只包含核心代码,交上去会CE!A-SwapDigit设\(a,b\)的第\(i\)位分别为\(a_i,b_i\)。由于\(a_i\)与......
  • 题解 ARC154D【A + B > C ?】
    显然\(1+1>x\)对任意大于\(1\)的正整数\(x\)都不成立。利用这一点,我们可以在\(n-1\)次询问内问出\(1\)的位置。具体地,首先假设\(p_1\)为\(1\),记我们假设的为......