widsnoy's blog

ZJCPC选拔 Round1

发表于 2024-03-06 分类于 ACM

三场选拔三个人，第一场我第四 :(

ll: “很多队员能拿金牌都不一定能参加省赛”

我有铁牌.jpg :L
最开始觉得每道题都有难度，但其实最后除了最后一题我都会做。
最开始摸鱼了 40 min，罚时太差，还是不能很快进入状态 :(
第三题挺遗憾的，寒假做过算这个最大子段平均值的题，我一眼看出字典树上每个节点维护一个单调栈。没注意到空间只有 64M，之后看题解说二分答案立马就懂了...难怪答案只保留整数:)

强连通计数

显然这是一个外向基环树森林。不是环的每个点贡献就是 $1-p_i$，是环的考虑这个环最终存不存在。

子集整除

刚开始觉得很神秘，做了第四题再看，这不就是个 dp, 状态记录一下余数

最大平均区间

:L
其实就是缝合了两个题，找 $p_i \oplus p_j\le k$ 我在牛客寒假集训营做过，找最大子段平均值是某场 abc F 题。但是那个 abc 答案是输出浮点数，二分精度误差太大。没仔细想为什么答案只保留整数，不然应该能想到二分的，代码还好写()

合法数对

阅读全文 »

BZOJ 3102 Sgu512 Friendly Points

发表于 2024-02-04 分类于 ACM

画图可以发现，对于每个点做右下顶点的时候，合法的另一个顶点是其右上方的一个下凸壳。
下凸壳可以用单调队列维护，但每次都建立一个单调队列肯定不行。按照 x 的值建立树状数组，用树状数组的区间划分一个后缀，对每个区间都维护其中的点的单调队列。合并两个单调队列，二分即可。

//能确定的事情只有啊，今天感觉有点寂寞啊
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;
int n;
pii a[N];
vector<pii> tr[N];
void insert(int x, int y) {
    for (int i = x; i; i -= i & -i) {
        while (!tr[i].empty() && tr[i].back().se >= x) tr[i].pop_back();
        tr[i].push_back({y, x});
    }
}
int qry(int x, int y) {
    int res = 0, lst = 2000000005;
    for (; x <= n; x += x & -x) {
        if (tr[x].empty()) continue;
        int l = 0, r = tr[x].size() - 1, pos = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (tr[x][mid].fi < lst) r = mid - 1, pos = mid;
            else l = mid + 1;
        }
        if (pos == -1) continue;
        res += tr[x].size() - pos;
        lst = tr[x].back().fi;
    }
    return res;
}

ll solve() {
    for (int i = 1; i <= n; i++) tr[i].clear();
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += qry(a[i].fi, a[i].se);
        insert(a[i].fi, a[i].se);
    }
    return ans;
}
void MAIN() {
    cin >> n;
    vector<int> vec;
    map<int, int> rx, ry;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se, vec.push_back(a[i].fi);
        rx[a[i].fi]++, ry[a[i].se]++;
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    auto cmp = [](pii x, pii y) {return x.se > y.se || (x.se == y.se && x.fi > y.fi);};
    for (int i = 1; i <= n; i++) a[i].fi = lower_bound(vec.begin(), vec.end(), a[i].fi) - vec.begin() + 1;
    sort(a + 1, a + n + 1, cmp);
    ll ans = solve();
    for (int i = 1; i <= n; i++) a[i].se = -a[i].se;
    sort(a + 1, a + n + 1, cmp);
    ans += solve();
    for (auto [x, r] : rx) ans -= r - 1;
    for (auto [x, r] : ry) ans -= r - 1;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}

2024牛客寒假D、J题解

发表于 2024-02-04 分类于 ACM

比赛链接：https://ac.nowcoder.com/acm/contest/67741/D

D. 数组成鸡

可以发现，最后的局面不可能所有数的绝对值都大于 $\exp{\ln{1e9}/n}$。直接枚举哪个数在这个范围。

//能确定的事情只有啊，今天感觉有点寂寞啊
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;

int a[N], n, q;

void MAIN() {
    cin >> n >> q;
    set<ll> ans, d;
    ans.insert(0);
    int k = exp(log(1e9) / (double)n) + 3;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = -k; j <= k; j++) d.insert(-a[i] + j);
    }
    for (int di : d) {
        ll r = 1;
        for (int i = 1; i <= n; i++) {
            r *= (di + a[i]);
            if (abs(r) > 1e9 || r == 0) break;
        }
        ans.insert(r);
    }
    while (q--) {
        ll m;
        cin >> m;
        cout << (ans.count(m) ? "Yes" : "No") << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}

J.又鸟之亦心

首先二分将最优化问题变为判定性问题。
首先可以发现当某个任务结束过后一定有一个人在这个位置。
另一个人在更前面的某个位置。考虑下一个任务是继续排这个人还是换人。我们可以发现相当于将任务在时间轴上划分成一些线段。每个任务维护可能的上一个线段右端点。

//能确定的事情只有啊，今天感觉有点寂寞啊
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;

int n, x, y;
int a[N];

bool check(int mid, int x) {
    set<int> st;
    if (abs(a[1] - x) <= mid) st.insert(x);
    for (int i = 2; i <= n; i++) {
        if (st.empty()) return false;
        while (!st.empty() && abs(*st.begin() - a[i]) > mid) st.erase(*st.begin());
        while (!st.empty() && abs(*st.rbegin() - a[i]) > mid) st.erase(*st.rbegin());
        if (abs(a[i] - a[i - 1]) <= mid) st.insert(a[i - 1]);
    }
    return !st.empty();
}

void MAIN() {
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int l = abs(x - y), r = 1e9, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid, x) || check(mid, y)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}

BZOJ 3723: [PA2014Final] Gra w podwajanie 题解

发表于 2024-02-01 分类于 ACM

考虑倒着做，从起点开始扩展打印出可能的形状。比如从起点是 16, 向四周扩展一个格子，变为 8、8...可以发现最大填的数是 16，合法的形状不大于 9x9。
实际上预处理可行的形状是非常麻烦的，这里提供一个~~全网最~~简单的做法，反正我没看懂 Claris 大神的代码 qwq（
反正数据范围很小，我们直接用一个单调队列保存状态来搜索，判断重复可以重载一个比较结构体用 map 判重。保存形状可以用一个 __int128。

阅读全文 »

详细揭秘⚡🧊专业

发表于 2023-12-09 分类于编程

好吧，我是标题党x

请各位完成一份杭州电子科技大学院系逻辑结构，以树形结构描述出来，叶子结点为各专业，可去各分院官网搜索信息，作为本学期的思政作业。

我发现学校总是喜欢布置些奇怪的任务x
不过不会真有人手写吧（x
记录一下我是怎么做这个作业的（
这个应该算可以公开的信息吧（？

阅读全文 »

Sereja and Permutations

发表于 2022-09-18 更新于 2023-12-07 分类于题解

SEAPERM2.pdf

$O(n^5)$

因为总有一个排列是由删除$p_1$得来的，所以可以枚举之并还原每个$n-1$的排列。得到$n^2$个可能的 P。然后暴力验证每一个。

$O(n^4)$

验证的时候比对排列的哈希值，哈希不必担心碰撞问题，因为恰好不同排列的哈希值对应交换才会产生影响，这个几率应该很小.......
不知道用什么模数？

$O(n^3)$

可以发现，输入的$n-1$的排列的第一个数一定有$p_1-1$个$p_1-1$，$1$个$p_2$，$n-p_1$个$p_1$。所以我们是可以知道$p_1$的取值的。

$O(n^2\log n)$

如果使用可加减的哈希，那么可以$O(n\log n)$求出一个原排列操作后的$n$个$n-1$的排列的哈希值。

#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
const int mod = 233329, b = 17, inv = 54901;
const int N = 305;

int n, a[N][N], p[N], h0[mod + 5], h1[mod + 5], ba[N];

int t[N];

int lowbit(int x) { return x & -x; }
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) t[i] += k, t[i] %= mod;
}
int sum(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += t[i], ans %= mod;
    return ans;
}
int qry(int l, int r) { return l <= r ? ((sum(r) - sum(l - 1)) % mod + mod ) % mod : 0; }

int f[N], g[N], h[mod + 5];

bool check() {
    for (int i = 1; i <= n; i++) {
        h[i] = (h[i - 1] + ba[n - i] * 1ll * p[i] % mod) % mod;
    }
    memset(t, 0, sizeof t);
    for (int i = 1; i <= n; i++) {
        f[i] = qry(p[i] + 1, n);
        add(p[i], ba[n - i]);
    }
    memset(t, 0, sizeof t);
    for (int i = n; i >= 1; i--) {
        g[i] = qry(p[i] + 1, n);
        add(p[i], ba[n - i]);
    }
    auto dec = [](int a, int b) { return ((a - b) % mod + mod) % mod; };
    memcpy(h1, h0, sizeof h1);
    for (int i = 1; i <= n; i++) {
        static int res = 0;
        res = (1ll * dec(h[i - 1], f[i]) * inv % mod + dec(dec(h[n], h[i]), g[i])) % mod;
        if (!h1[res]) return 0;
        h1[res]--;
    }
    return 1;
}

bool gen(int p1) {
    for (int i = 1; i <= n; i++) {
        p[1] = p1;
        for (int j = 1; j < n; j++) p[j + 1] = a[i][j] + (a[i][j] >= p1);
        if (check()) return 1;
    }
    return 0;
}

void solve() {
    scanf("%d", &n);
    memset(h0, 0, sizeof h0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < n; j++) scanf("%d", &a[i][j]);
        int res = 0;
        for (int j = 1; j < n; j++) res = (res * 1ll * b % mod  + a[i][j]) % mod;
        h0[res]++;
    }
    static bool pd[N];
    memset(pd, 0, sizeof pd);
    for (int i = 1; i <= n; i++) if (!pd[a[i][1]]) {
        pd[a[i][1]] = 1;
        if (gen(a[i][1])) {
            for (int i = 1; i <= n; i++) printf("%d ", p[i]);
            return printf("\n"), void(0);
        }
    }
    if (gen(n)) {
        for (int i = 1; i <= n; i++) printf("%d ", p[i]);
        return printf("\n"), void(0);
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ba[0] = 1;
    for (int i = 1; i < N; i++) ba[i] = ba[i - 1] * b % mod;
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

阅读全文 »

高考题面背后的故事

发表于 2021-12-25 更新于 2023-12-07 分类于数学

做到过这样一道题其实是2021年新高考Ⅱ卷数学 21题好像高考考概率压轴题还是挺少见的，不过其实这更像导数题。今天我要说的当然不是这道题的解法，而是第 $2$ 问中的已知条件的由来。

即$p$为什么是方程$p-0+p-1x+p-2x^2+p-3x^3=x$的根。我们将该生物群体的每一个个体编号。首先如果以$0$为祖先的群体灭绝，那么相当于所有$0$的下一代为祖先的群体都灭绝。题设每一代繁殖独立且分布列相同。于是$0$为祖先的群体灭绝的概率和每个孩子们($1$,$2$,$3$)为祖先的群体灭绝概率是相等的，因为后代无穷多，一代的差别可以忽略不计。于是我们只用分类讨论$0$的孩子个数，如以 $3$ 个孩子的情况为例：每一个后代所代表的子群体灭绝的概率都是$P$，于是$p=p-3*p^3$。其他两种情况类似，于是结论是显然的。

本人学艺不精，语言难免不清晰，尽情谅解。

Hello World

发表于 2021-11-03 更新于 2022-09-18

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

阅读全文 »

C、D题解解析

发表于 2020-11-12 更新于 2023-12-07 分类于测试

首先本人并不会做这两道题，以下只是对题解的理解

猪国杀

题目描述

《猪国杀》是一款热门的桌上游戏，该游戏以身份、势力或阵营等为线索，以卡牌为形式，合纵连横，经过一轮一轮的谋略和动作获得最终的胜利。《猪国杀》集合历史、文学、美术等元素于一身，在OI界广受欢迎。

在《猪国杀》游戏中，牌堆中牌的数量是无穷大的，并且每一张牌的点数都是在$[1,A]$内均匀随机的正整数。

游戏中有多种武将，每个武将有其独特的技能，其中一个技能描述如下：

称猪：每当你受到一次伤害后，你可以亮出牌堆顶的$n$张牌。然后获得其中任意数量点数之和不大于$m$的牌，将其余的牌置入弃牌堆。

现在询问如果“称猪”时总是获得尽量多的牌，那么单次发动“称猪”期望能获得几张牌。

输入格式

一行三个整数$n,m,A$。

阅读全文 »

「NOIP2017」列队数据结构

发表于 2020-11-11 更新于 2023-12-07 分类于题解

「NOIP2017」列队

这题做法比较多，感觉平衡树的写法应该比较简单。

虽然常数会比较大。

我们分别维护每一行和最后一列的元素。

对于每次操作的二元组$(x,y)$

如果$y=m$，就把元素移到列末尾。
否则，行内删除该元素，把最后一列第$x$个元素移到行末尾并删除，之后把$(x,y)$移动到列末尾。

查询很简单，查一下第$k$大的编号就是了。

但是有一个问题，这样开的点会非常多，空间根本开不下。

所以要向方伯伯的OJ那题那样，把连续的编号压缩一下，用到的时候再拆开。

和珂朵莉树思想应该是一样的。

阅读全文 »

widsnoy's blog

ZJCPC选拔 Round1

强连通计数

子集整除

最大平均区间

合法数对

BZOJ 3102 Sgu512 Friendly Points

2024牛客寒假D、J题解

D. 数组成鸡

J.又鸟之亦心

BZOJ 3723: [PA2014Final] Gra w podwajanie 题解

详细揭秘⚡🧊专业

Sereja and Permutations

\(O(n^5)\)

\(O(n^4)\)

\(O(n^3)\)

\(O(n^2\log n)\)

高考题面背后的故事

Hello World

Quick Start

Create a new post

Run server

Generate static files

C、D题解解析

猪国杀

题目描述

输入格式

「NOIP2017」列队数据结构