AtCoder Regular Contest 151补题
AtCoder Regular Contest 151
简单题，注意下答案需要字典序最小即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define ll long long
signed main()
{
int n;
string a, b;
cin >> n >> a >> b;
int cnt(0);
rep(i, 0, n - 1) if (a[i] != b[i]) cnt++;
if (cnt % 2) cout << -1 << endl;
else
{
string ans(a);
int s1 = 0, s2 = 0; cnt /= 2;
rep(i, 0, n - 1)
{
if (a[i] != b[i])
{
if (a[i] == '0')
{
if (s1 < cnt) s1++;
else
{
ans[i] = b[i];
s2++;
}
}
else
{
if (s2 < cnt)
{
s2++;
ans[i] = b[i];
}
else s1++;
}
}
else ans[i] = '0';
}
cout << ans << endl;
}
}知识点：计数，连通块
复杂度：\(O(n)\)
一开始被题目吓住了，以为要上带权并查集，后来发现只需要维护连通块的个数即可
枚举 \(A\) 中第一个满足 \(A_i<A_{P_i}\) 的位置
那么对所有的 \(1\) 到 \(i-1\) 都要满足 \(A_i=A_{P_i}\)
我们将之前的 \(j\) 和 \(p_j\) 使用并查集合并
那么此时符合题意的数列个数为 \(C_m^2×m^{cnt-2}\)
\(cnt\) 为连通块个数
注意 \(i\) 和 \(p_i\) 可能一开始就连通，所以要用并查集维护
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
const int mod = 998244353;
const int N = 2e5 + 5;
int f[N];
void init(int n) { iota(f, f + n + 1, 0); }
int find(int u)
{
if (f[u] == u) return u;
return f[u] = find(f[u]);
}
bool link(int u, int v)
{
int fu = find(u), fv = find(v);
if (fu == fv) return false;
f[fu] = fv;
return true;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
ll n, m;
cin >> n >> m;
init(n);
vc<ll> p(n + 1), pow_m(n + 1);
pow_m[0] = 1;
rep(i, 1, n)
{
cin >> p[i];
pow_m[i] = pow_m[i - 1] * m % mod;
}
ll cm2 = m * (m - 1) / 2 % mod;
int cnt = n;
ll ans = 0;
for (int t = 1; t <= n; t++) if (link(t, p[t]))
{
ans = (ans + cm2 * pow_m[cnt - 2]) % mod;
cnt--;
}
cout << ans << endl;
}显然每一段连续的空位是互相独立的
我们先推导一个结论
对于左右均有 \(0/1\) 的连续空位，
- 0__1 可以填偶数次数
- 0__0 1__1 可以填奇数次数
从边界开始判断
0_0
0_1
空格长度
可填次数
可填次数
1
1
0
2
1
2
3
1/3
2
…
…
…
那么对于一个 0_1 段来说
如果我在中间插入一个 0[1]，那么我们会得到一对更短的 0_0 串和 0_1 串
总操作次数为： 奇数 + 偶数 + 1 = 偶数
对于一个 0_0 段来说
如果我在中间插入一个 0，那么我们会得到一对更短的 0_0 串
总操作次数为： 奇数 + 奇数 + 1 = 奇数
如果我在中间插入一个 1，那么我们会得到一对更短的 0_1 串
总操作次数为： 偶数 + 偶数 + 1 = 奇数
由数学归纳法可证明上述结论
此时中间一段操作次数的奇偶是固定的，
我们只需要考虑两侧可能存在的 __0 和 1__ 串，
由于是博弈题，我们先考虑更加对称的情况，
PS：下述情况中，左右端空格数均大于1，其他情况十分容易推导，就不再赘述
显然，如果左右端空格数相同，无论是 __0…1__ 还是 __0…0__ 串都会增加偶数次操作[2]，
此时答案只与中间操作次数的奇偶有关
自然而然的，我们就考虑先手修正到对称状态的情况
如果，左右端空格数相差超过1，
那么无论中间操作次数的奇偶性如何，先手都可以修正到偶数次操作次数，并且左右端空格数相同
如果，左右端空格数相差等于1
此时如果中间操作次数为偶数，那么先手必然可以修正到左右端空格数相同，因为 01 可以相邻
如果中间操作次数为奇数
假设左端空格有 x + 1 个，右端空格有 x 个
那么如果先手要在 这两段空格中填数，就只能填在左边第 x 个空上，并且只能填与 x+2 位置上相反的数
否则都会转化成上述中的先手必胜态
则情况转化成谁第一个填到最左端或最右端的空谁赢
显然 x 为奇数，先手必败
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
void pr(bool fi_win)
{
cout << (fi_win ? "Takahashi" : "Aoki") << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
ll n, m; cin >> n >> m;
vc<pll> x(m + 1);
rep(i, 1, m) cin >> x[i].fi >> x[i].se;
int ans = 0;
rep(i, 2, m) if (x[i].se == x[i - 1].se) ans ^= 1;
if (m == 0) pr(n % 2);
else if ((x[1].fi == 1 || x[1].fi == 2) && (x[m].fi == n || x[m].fi == n - 1))
{
if (x[1].fi == 2) ans ^= 1;
if (x[m].fi == n - 1) ans ^= 1;
pr(ans);
}
else if (x[1].fi == 1 || x[1].fi == 2 || x[m].fi == n || x[m].fi == n - 1) pr(1);
else if (!ans && abs(n - x[m].fi + 1 - x[1].fi) == 0) pr(0);
else if (ans && abs(n - x[m].fi + 1 - x[1].fi) == 1)
pr(min(x[1].fi, n - x[m].fi + 1) % 2 == 0);
else pr(1);
}知识点：高维前缀和的可互换性
复杂度：\(O(n*2^n)\)
完全不会，被学长教会的
我们可以视原题有一个 n 维的数组，
那么对于操作 \(X_i\) \(Y_i\)，我们可以认为是在第 \(X_i\) 维上做前缀和(\(Y_i=0\))或后缀和(\(Y_i=1\))
那么对于不同的 \(X_i\) 来说，操作的顺序是可以互换的
对于相同的 \(X_i\)，我们可以用两个二维的单位向量来模拟第 \(X_i\) 维上的操作结果
所以我们开一个桶分类所有的操作，分别对于不同的 \(X_i\) 模拟操作即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
#define db(x) cout<<#x<<'='<<x<<' '
#define deb(x) cout<<#x<<'='<<x<<endl
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
const int mod = 998244353; //1e9 + 7;
const int N = 1e5 + 5;
int n, q;
ll a[1 << 18];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
rep(i, 0, (1 << n) - 1) cin >> a[i];
vc<int> p[20];
rep(i, 1, q)
{
int x, y; cin >> x >> y;
p[x].push_back(y);
}
rep(i, 0, n - 1)
{
pii x = { 1,0 }, y = { 0,1 };
for (auto t : p[i])
{
if (t) x.fi = (x.fi + y.fi) % mod, x.se = (x.se + y.se) % mod;
else y.fi = (y.fi + x.fi) % mod, y.se = (y.se + x.se) % mod;
}
rep(j, 0, (1 << n) - 1)
{
if (j & (1 << i))
{
int mi = j ^ (1 << i), ma = j;
ll a0 = a[mi] * x.fi + a[ma] * x.se;
ll a1 = a[mi] * y.fi + a[ma] * y.se;
a[mi] = a0 % mod;
a[ma] = a1 % mod;
}
}
}
rep(i, 0, (1 << n) - 1) cout << a[i] << " \n"[i == _i];
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章