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]) \\ \]exgcd
或excrt
合并计算即可。
#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