首页 > 其他分享 >闲话 22.10.17

闲话 22.10.17

时间:2022-10-17 19:22:21浏览次数:92  
标签:##_ frac 17 int 闲话 sum cin 22.10 节点

闲话

今天是伊蕾娜生日诶
听Muel说的
想找张伊蕾娜的图来着 然后第一时间想到了CYJian的luogu主页
图都可以在评论区发!谢谢你们(

一些认为应该被折叠的情绪化内容

关于 听不懂歌词就认为歌曲是劣质的 这件事
我的评价是[已编辑]
有很多想要说的
但是这些话不是很适合在任何公开场合出现
所以算了
总之一句话 有这种心理的人 他的心是劣质的
不做任何进一步说明。
心在颤抖
因为怒火?还是受到了侮辱?
不做任何进一步思考。

我认为我那时捏紧了拳。
但似乎都结束了。

所以有的时候发生了世界观或者价值观的冲突的时候,观察心理就变成了一件很有意思的事。
话说我会不自觉地在自己心理波动时开始对自己进行一个分析

但是思想的冲突不是一件好事,特别是其中一方没有认识到对方的这部分思想对对方的重要性的时候。这时最好(似乎是唯一?)的解决方案其实是好好交流一下,让双方理解意义。但是似乎最好的解决方案变成了最坏的方案。不知道为什么。

写摘要来着
写了:闲话 about 情绪
aaaaa我多久没听异世界情绪小姐的歌了aaaaa
好吧戒断反应又起了
但是情绪的歌真的好听 快去听!(


宇宙が ふたりきり食べたおにぎり

海苔とかなら良いのにね

杂题

所以今天上午在比赛所以题面数量比较少
大致的是找找AT和完结老题
那就开始!



ARC150B

给定 \(A,B\)。对于满足 \((A+x)\mid (B+y)\) 的 \(x,y\ge 0\) ,最小化 \(x+y\) 的值。

\(A,B\le 10^{14}\)。

数论题。

其实这题原来的数据范围不是很好看出来这是道根号复杂度的题 所以我就找了半个小时的性质最后发现这玩意不是常数复杂度 wssb

重写题面里的关系为 \((B + y) = k(A+x)\)。我们有 \(y = kA + kx - B\),\(x+y = kA + (k+1)x - B\)。
因此我们需要让 \(x\) 尽可能地小。

发现 \(x\) 最小时的取值为 \(\lfloor \frac {B-1} k\rfloor +1 - A\)。由于 \(x\ge 0\),因此 \(x = \max(0,\lfloor \frac {B-1} k\rfloor +1 - A)\)。
因此我们需要调整 \(k\) 的值,取得下式的最小值:

\[kA + (k+1)\times\max(0,\lfloor \frac {B-1} k\rfloor +1 - A) - B \]

发现这是个数论分块的形式。因此 \(O(\sqrt B)\) 地判断即可。
注意有些点需要特判,写一下就行。

code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e6 + 10;
int T, a, b, ans;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> a >> b;
        if (b <= a) {
            cout << a - b << '\n';
            continue;
        } 
        if (b % a == 0){
            cout << "0\n";
            continue;
        }
        ans = numeric_limits<decltype(ans)> :: max();
        for (int l = 1, r; l <= b - 1; l = r + 1) {
            r = (b - 1) / ((b - 1) / l);
            ans = min(ans, (l + 1) * max(0ll, (b - 1) / l + 1 - a) + l * a - b);
        } cout << ans << '\n';
    }
}



ARC150D

给定一棵 \(n\) 节点,根为 \(1\)。每个节点有黑白两种可能的颜色,初始时全为白色。 我们定义一个节点是好的,当且仅当其到根的路径上(含端点)节点颜色均为黑色。反之则为不好的节点。

现在需要重复执行以下操作直到所有节点均变为黑色:选择一个不好的节点,将其染成黑色。

你需要输出期望操作次数模 \(998,244,353\) 的值。注意每个节点不一定只被染一次

\(n\le 10^7\)。

期望题。有很好的trick。

这题本来出题人的做法是 \(O(n\log n)\),数据范围给到了 2e5。然后验题人给出了 \(O(n)\) 做法。本文中给出的代码是 \(O(n)\) 的实现,因此取数据范围为 1e7。

\(O(n\log n)\) 做法

这部分我是翻译的题解这题解5000诶

[1] 使用期望的线性性

\(\forall 0\le k< n\),我们令 \(X_k\) 为表示从存在 \(k\) 个黑色节点到第一次存在 \(k+1\) 个黑色节点所需要操作次数的随机变量。由于期望的线性性,答案即为 \(\sum_{i=0}^{n-1}E[X_k]\)。

当黑色节点数没有改变时,好节点的个数也不变。因此,当存在恰好 \(m\) 个黑点时,\(X_k\) 的(条件)期望值即为 \(\frac{1}{\frac{n-k}{n-m}} = \frac{n-m}{n-k}\)。因此,若 \(p_{k,m}\) 表示当第一次存在 \(k\) 个黑色节点时,存在 \(m\) 个好节点的概率,则可以知道

\[E[X_k] = \sum_{m=0}^n \frac{p_{k,m}(n-m)}{n-k} = \frac {n}{n-k} - \frac{1}{n-k}\sum_{m=0}^np_{k,m}m \]

因此,我们只需要计算 \(\sum_{m=0}^np_{k,m}m\),即,当第一次存在 \(k\) 个黑色节点时,好节点的期望个数。
若 \(q_{k,i}\)为第一次存在 \(k\) 个黑色节点时 \(i\) 为好节点的概率,则根据期望的线性性,好节点的期望个数即为 \(\sum_{i=1}^n q_{k,i}\)。

[2] 关注选择白色节点的操作

令 \(d_i\) 为 \(i\) 的祖先个数(包含其本身)。

现在需要求得 \(q_{k,i}\)。我们总是以相同的概率选择被染为黑色的白色节点。因此,我们所需要的概率就等于随机从 \(n\) 个球中选择 \(k\) 个,有特定 \(d_i\) 个球被选择的概率。当 \(d_i > k\) 时显然是 \(0\)。在其他情况下我们有

\[q_{k,i} = \frac{\binom{n-d_i}{k-d_i}}{\binom{n}{k}} = \frac{k!(n-d_i)!}{n!(k-d_i)!} \]

[3] 我们使用 NTT。

因此,只需为每个 \(k\) 找到

\[\frac{k!}{n!}\sum_{1\le i \le n, d_i\le k}\frac{(n-d_i)!}{(k-d_i)!} \]

令 \(c_i = \sum_{v=1}^n [d_v = i]\) 。

\[\frac{k!}{n!}\sum_{1\le i \le n, d_i\le k}\frac{(n-d_i)!}{(k-d_i)!} = \sum_{i=1}^k c_i \frac{(n-i)!}{(k-i)!} \]

构造 \(f_i = c_i(n-i)!\),\(g_i = \frac 1{i!}\)。我们可以使用多项式乘法快速得到答案,即 \(f\) 和 \(g\) 的卷积。

总时间复杂度 \(O(n\log n)\)。

\(O(n)\) 做法

考虑令 \(X_v\) 为节点 \(v\) 被选择的期望次数。根据期望的线性性,有总答案即为 \(E[X_v]\) 的和。现在考虑分别求出 \(E[X_v]\)。

当我们考虑 \(X_u\) 时,不在 \(1\to u\) 的路径上的点都是可以被忽略的。因此操作可以被改为如下形式:

  1. 只会选择 \(1\to v\) 上的不好的节点染成黑色。
  2. 当 \(1\to v\) 上所有节点被染成黑色时停止。

我们发现,自始至终 \(u\) 节点都是一个不好的节点。这启发我们允许操作过程中选择好的节点改为黑色,简化运算。在实际计入贡献时不统计这部分即可。

然后考虑从 \(n\) 个元素的箱子里随机有放回地抽取元素。我们的期望值等同与从取出第一个元素开始到取出所有元素至少一次时期望的抽取次数。由于期望的总轮数是 \(\sum_{i=1}^n \frac ni\),抽取出一个元素的期望次数即为 \(\sum_{i=1}^n \frac 1i\)。

通过预处理逆元前缀和,我们可以在 \(O(n)\) 的时间复杂度内得到结果。

code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 2e5 + 10, mod = 998244353;
int n, fa[N], dep[N], inv[N], ans;

void add(int &a, int b) { (a += b) >= mod ? a -= mod : 0;}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    dep[1] = 1; inv[0] = inv[1] = 1;
    rep(i,2,n) {
        cin >> fa[i];
        dep[i] = dep[fa[i]] + 1;
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    } inv[0] = 0;
    rep(i,1,n) {
        add(inv[i], inv[i-1]);
        add(ans, inv[dep[i]]);
    }
    cout << ans << endl;
}



P1667

给定一个 \(n\) 长度的数列 \(A\) ,我们称一个数列是完美的,当且仅当对于其任意连续子序列的和都是正的。定义操作如下:选择一个区间 \([l,r]\) 满足 \(\sum\limits_{i = l}^r A_i < 0\) ,其中 \(1 < l \le r < n\)。令 \(S = \sum\limits_{i = l}^r A_i\) ,对于 \(A_{l - 1}\) 和 \(A_{r + 1}\) 分别加上 \(S\),\(A_l\) 和 \(A_r\) 分别减去 \(S\)(如果 \(l = r\) 就减两次)。

问最少几次这样的操作使得最终数列是完美的。

\(1 \le N \le 10^5\) ; \(1 \le |A_i| < 2^{31}\)

观察题。

考虑设 \(A\) 的前缀和序列为 \(P\)。令 \(P_0 = 0\)。

\(\text{Key Observation 1}\)

完美序列充要于 \(P\) 单增。

证明

连续子序列 \([l,r]\) 的和可以被表示为 \(P_r - P_{l-1}\) 。由于完美序列,因此 \(P_r - P_{l-1} > 0\)。
因此有充分性。

必要性类似,不再赘述。

\(\text{Key Observation 2}\)

对 \([l,r]\) 的操作等价于交换 \(P_{l-1},P_r\)。

证明

题设中 \(S = P_r - P_{l-1}\)。
则 \([1,l-2]\) 段前缀和不变,\(P_{l-1}' = P_{l-1} + S = P_{l-1} + P_r - P_{l-1} = P_r\),\([l,r-1]\) 段前缀和不变,\(P_{r}' = P_{r} - S = P_r - P_r + P_{l-1} = P_{l-1}\),\([r+1,n]\) 段前缀和不变。

因此有证明。

然后我们直接取一个前缀和,判掉无解后找到最小的使得单增的交换次数即可。

首先将前缀和离散化,然后这就是一个在集合 \(N^+ \cap [1,n]\) 上的置换了。我们只需要找到上面的所有环,计数长度减一就是答案。

code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, a[N], s[N], lsh[N], mx, cnt, ans;
int vis[N];

void reportNoSolution() {
    puts("-1");
    exit(0);
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n; 
    rep(i,1,n) {
        cin >> a[i], s[i] = s[i-1] + a[i];
        if (s[i] < 0) reportNoSolution();
        lsh[i] = s[i];
        mx = max(mx, s[i]);
    }
    if (s[n] != mx) reportNoSolution();
    sort(lsh+1, lsh+1+n); cnt = unique(lsh+1, lsh+1+n) - lsh - 1;
    if (cnt < n) reportNoSolution();
    rep(i,1,n) s[i] = lower_bound(lsh+1, lsh+1+cnt, s[i]) - lsh;
    rep(i,1,n) {
        if (vis[i]) continue;
        int ptr = i, cnt = 0;
        while (!vis[ptr]) {
            vis[ptr] = 1; cnt++;
            ptr = s[ptr];
        } ans += cnt - 1;
    }  cout << ans << endl;
}



CF914F

给你一个字符串 \(s\),共有 \(q\) 次操作,每个都是下面两种形式的一种。

1 i c:将字符串 \(s\) 的第 \(i\) 项变为字符 \(c\)。
2 l r y:求字符串 \(y\) 在字符串 \(s\) 中以第 \(l\) 项为起点,以第 \(r\) 项为终点的子串(第 \(l\) 和第 \(r\) 项)中作为子串出现的次数。

\(1\leq |s|\leq 10^5\),\(1\leq q\leq 10^5\),\(\sum |y| \leq 10^5\)。时间 \(6s\)。

bitmask(

这题的正解是根号分治+根号平衡,得到一个复杂度 \(O(n\sqrt n)\) 的做法,\(n\) 和题面里的值同阶。
但是

\[\large\text{Bitset works MUCH better than sqrt} \]

然后就有了 bitset 维护字符串匹配。
实际上是暴力。但是能除以一个字长,所以在 \(10^5\) 的小数据下跑的很快。

具体地,我们对字符集内的每个元素开一个文本串长的 bitset 维护文本串内该元素的出现位置。修改可以 \(O(1)\)。
考虑对于整个串的查询。我们开一个初始为全 \(1\) 的 bitset,然后顺序扫模式串里的每个元素。若当前元素为第 \(i\) 位,就让当前元素对应 bitset 右移 \(i\) 位,再和现在的 bitset 与起来,就实现了全串的一次匹配。总共需要做模式串长次。最后现在的 bitset 里 \(1\) 的数量就是模式串的出现次数。
对于区间的查询可以右移后差分得到结果。

总时间复杂度为 \(O(\frac{\text{2操作次数}\times \text{模式串总长度}}{w})\)。由于 CF 是64位机子,而且 bitset 常数小到离谱,因此这玩意也就跑个 \(2.0s\)。具体可以在看。

当然啊,P4173那题过不去。具体可以在

code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, q, typ, l, r, len; 
char str[N], y[N], ch;
bitset<N> occ[26], msk;

signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> str + 1 >> q;
    n = strlen(str + 1);
    rep(i,1,n) occ[str[i] - 'a'].set(i, 1);
    while (q --) {
        cin >> typ;
        if (typ == 1) {
            cin >> l >> ch;
            occ[str[l] - 'a'].set(l, 0);
            str[l] = ch;
            occ[str[l] - 'a'].set(l, 1);
        } else {
            cin >> l >> r >> y + 1;
            msk.set(); len = strlen(y + 1);
            if (l > r - len + 2) { cout << "0\n"; continue; }
            rep(i,1,len) {
                msk &= (occ[y[i] - 'a'] >> (i - 1));
            } 
            int lv = (msk >> l).count(), rv = (msk >> (r - len + 2)).count();
            cout << (lv - rv < 0 ? 0 : lv - rv) << '\n';
        }
    }
}

标签:##_,frac,17,int,闲话,sum,cin,22.10,节点
From: https://www.cnblogs.com/joke3579/p/chitchat221017.html

相关文章

  • 20221017笔记
    这两天学了c语言的循环语句,有点烧脑,但是感觉的确能提高生产力。一定要自己敲代码,不然很多问题学不会,比如分号、括号的位置,是大括号还是花括号,还有语句的表达式。重要的事情......
  • AcCoders 10692:【2022NOIP联测10 10月17日】交换(swap) 题解
    考虑把一次交换产生的贡献记录在交换的两个数字中较小的那个数字上。则构造一个好的序列的过程可以看成是:按照从小到大的顺序枚举每个数,每次选择将这个数放在序列的左边或......
  • 10.17
    今日内容1.异常常见类型2.异常处理语法结构3.异常处理补充4.异常处理实战应用5.生成器对象6.yield冷门用法7.生成器表达式1.异常常见类型SyntaxErrorNameError......
  • 工作总结反思2022年10月17日
    2022年10月17日晴,今天是比较冷的一天,今天迟到了,明天不能迟到了,最近的工作都是别人推送的,解决之前先得问同事,然后进行解决,主要的解决方法,自己不会,要多问,多学,看日志,别的......
  • 【LeetCode】面试题 16.17. 连续数列(C++)
    面试题16.17.连续数列​​1题目描述​​​​2示例描述​​​​3解题思路​​​​4源码详解(C++)​​1题目描述给定一个整数数组,找出总和最大的连续数列,并返回总和。2......
  • 做题记录整理数据结构/线段树3 P3822 [NOI2017] 整数(2022/10/17)
    P3822[NOI2017]整数为什么这玩意是双tag呢因为他按理来说正解是用线段树来做的,但是有很多题解都是直接上set搞的,所以就两个tag都打上了首先我们可以想到用bitset来表......
  • 循环控制~17 斐波那契数列
    题目描述:K=1,1,2,3,5,8,13,21...输入:输入一行,包含一个正整数k。(1<=k<=46)输出:输出一行,包含一个正整数,表示菲波那契数列中第k个数的大小1#include<stdio.h>2intmai......
  • 自选股 2022年10月17日
    1.002559亚威股份2.603011合锻智能3.300260新莱应材4.002371北方华创5.603100川仪股份6.002737葵花药业7.002489浙江永强8.300789唐源电气9.603969银龙股份10.002......
  • CF1736C1 Good Subarrays (Easy Version)
    题目传送门思路给出一种不需要脑子的做法。首先我们把每个\(a_i\)都减去\(i\),这样原问题就转化为对于每一个左端点\(i\),寻找一段连续的区间,使得这段区间的最小值加......
  • LFM Oversea 每周策略晨报 2022-10-17
    盘面数据 国庆后上证指数下穿3000 点,随后迎来连续上涨,上周上证指数上涨1.57%,深证成指上涨3.18%,创业板指数上涨6.35%。上周A 股日均成交额6982亿元,较上周环比+......