MX 炼石计划 NOIP 模拟赛 #20
T1 邻间的骰子之舞
二分答案，发现性质，签到，过。
记得开 __int128
没开，挂 30.
码：
CODE
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 100;
#ifdef linux
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
inline int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
template <typename T> void write(T x) {
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
ll n, x, y;
ll maxer;
inline bool check(__int128 mid) {
for (__int128 i = 0; i <= maxer; ++ i) {
if (i * x >= mid) break;
if (i == 0) {
if ((mid - i * x) / y + 1 > n) return true;
continue;
}
__int128 j = (mid - i * x) / y, val = 1, aver = j / (i + 1), last = j - aver * (i + 1);
for (ll k = 0; k <= i; ++ k) {
if (last > 0) {
val += (aver + 1) * val, last --;
} else val += aver * val;
if (val > n) return true;
}
}
return false;
}
signed main() {
freopen("dice.in", "r", stdin);
freopen("dice.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> x >> y;
__int128 l = 1, r = 1e19, ans = 0; maxer = log2(n);
while (l <= r) {
__int128 mid = ((__int128)(l + r) >> 1ll);
if (check(mid)) {
ans = mid, r = mid - 1;
} else l = mid + 1;
}
write(ans + x);
}
T2 星海浮沉录
签到2，拿 \(set\) 维护一下每种数位置以及两者之间距离，然后线段树上二分。
码：
CODE
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e5 + 100;
#ifdef linux
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
inline int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
template <typename T> void write(T x) {
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, q; int a[N];
int last[N];
multiset <int> num[N], dis[N];
#define lson (id << 1)
#define rson (id << 1 | 1)
#define mid ((l + r) >> 1)
int t[N << 2];
void updata(int id, int l, int r, int x, int c) {
if (l == r) return t[id] = c, void();
return ((x <= mid) ? updata(lson, l, mid, x, c) : updata(rson, mid + 1, r, x, c)), t[id] = max(t[lson], t[rson]), void();
}
int Query(int id, int l, int r, int k) {
if (l == r) return l;
if (t[lson] >= k) return Query(lson, l, mid, k);
else return Query(rson, mid + 1, r, k);
}
#undef mid
#define iter set <int>::iterator
inline void change(int x, int i, int j) {
iter it = num[x].lower_bound(i), it2 = ++ it; -- it;
if (it != num[x].begin()) {
int fir = *(-- it); ++ it;
dis[x].erase(dis[x].lower_bound(i - fir - 1)), dis[x].insert(j - fir - 1);
}
if (it2 != num[x].end()) {
int sec = *it2;
dis[x].erase(dis[x].lower_bound(sec - i - 1)), dis[x].insert(sec - j - 1);
}
num[x].erase(i), num[x].insert(j);
updata(1, 0, n + 1, x, *dis[x].rbegin());
}
signed main() {
freopen("star.in", "r", stdin);
freopen("star.out", "w", stdout);
n = read(), q = read();
for (int i = 0; i <= n; ++ i) num[i].insert(0);
for (int i = 1; i <= n; ++ i) {
a[i] = read(), num[a[i]].insert(i);
dis[a[i]].insert(i - last[a[i]] - 1);
last[a[i]] = i;
}
for (int i = 0; i <= n; ++ i) {
dis[i].insert(n - *num[i].rbegin()); num[i].insert(n + 1);
updata(1, 0, n + 1, i, *dis[i].rbegin());
}
int opt, x, tot = 0;
while (q --) {
opt = read(), x = read();
if (opt == 1) {
if (a[x] == a[x + 1]) continue;
change(a[x], x, x + 1);
change(a[x + 1], x + 1, x);
swap(a[x], a[x + 1]);
} else {
write(Query(1, 0, n + 1, x)), puts("");
}
}
}
注：byd梦熊还有什么逆天文件问题，甚至还只有一个测试点有文件问题？唐。
T3 勾指起誓
不会，咕了。
T4 _八交响曲
赛时没想出来。
考虑两个有序数组合并，只需要将镜像位置交换之后，发现其左右儿子区间保证左大于右或右大于左这么一个情况，遍历他儿子的时候就可以按位置交换了，非常优秀。
CODE
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 200;
int n; int m;
vector <pair <int, int> > v[N];
int pos[N][N], pos2[N];
void Solve2(int l, int r, int dep, int ac) {
if (l == r) return;
if (!pos[ac][dep]) pos[ac][dep] = ++ m;
int mid = (l + r) >> 1;
for (int i = l; i <= mid; ++ i) {
int now = mid + i - l + 1;
if (now <= r && now != i) v[pos[ac][dep]].push_back(make_pair(i, now));
}
Solve2(l, mid, dep + 1, ac), Solve2(mid + 1, r, dep + 1, ac);
}
void Solve(int l, int r, int dep) {
if (l == r) return;
int mid = (l + r) >> 1;
Solve(l, mid, dep + 1), Solve(mid + 1, r, dep + 1);
if (!pos2[dep]) pos2[dep] = ++ m;
for (int i = 1; i <= mid; ++ i)
if (l + i - 1 < r - i + 1)
v[pos2[dep]].push_back(make_pair(l + i - 1, r - i + 1));
Solve2(l, mid, dep + 1, dep), Solve2(mid + 1, r, dep + 1, dep);
}
signed main() {
freopen("symphony.in", "r", stdin);
freopen("symphony.out", "w", stdout);
cin >> n; int p = n;
n = pow(2, ceil(log2(n)));
Solve(1, n, 1);
cout << m << '\n';
for (int i = 1; i <= m; ++ i) {
for (auto j : v[i]) {
if (j.first <= p && j.second <= p)
printf("CMPSWP R%d R%d ", j.first, j.second);
} puts("");
}
}
总结
70(-30) + 100(-0) + 12(-0) + 10(-0)
中学生誓词
泌阳的我再不看数据规模瞎几把用龙龙并认为龙龙可以拯救一切我就踏马的玩原神吃鸡屎及防盗管被合一哟纸发现再回去玩宝宝巴士和迷奥迷奥看三国志！！！