Kininged's Blog

NEERC2017 链接：https://codeforces.com/gym/101630/attachments A - Archery Tournament 题意 执行以下操作的两种： 1、在点(x,y)(x,y)(x,y)建立一个圆形靶子，靶子与x轴相切。 2、在点(x,y(x,y(x,y进行射击，如果射中靶子，输出靶子编号，并将靶子移除；否则输出−1-1−1。 思路 将坐标离散化后，在坐标轴建立线段树。结点使用set维护靶子信息。 更新信息每次都是找到最底层，不需要up和down。 注意删除靶子信息时不能找到后原地删除，因为这个靶子的信息不只存于当前要找的区间。 注意共有2n个点，线段树大小应为8n。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 ...

欧拉定理、矩阵快速幂 欧拉定理 若a,na,na,n互质，则有aϕ(n)≡1(modn)a^{\phi (n)} \equiv 1\pmod{n}aϕ(n)≡1(modn). 扩展欧拉定理 ABmod(C)=ABmod(ϕ(C))modCA^Bmod(C) = A^{Bmod(\phi(C))}mod CABmod(C)=ABmod(ϕ(C))modC,B<ϕ(C)B<\phi(C)B<ϕ(C); ABmod(C)=ABmod(ϕ(C))+ϕ(C)modCA^Bmod(C) = A^{Bmod(\phi(C)) + \phi(C)}mod CABmod(C)=ABmod(ϕ(C))+ϕ(C)modC,B>=ϕ(C)B>=\phi(C)B>=ϕ(C)。 矩阵快速幂 与普通快速幂同理。 矩阵模板 1234567891011121314151617181920212223242526272829303132333435363738394041424344struct mat { ll a[N][N]; inline mat()
...

SDUT 2021 summer team contest 8th Half Nice Years 题目大意： 有n个区间[L,R],找出每个区间满足下列条件的最大的数： 将该数平分成两部分，如果该数的位数是奇数则让右侧部分比左侧部分多一位，如123456分成123和456两部分，12345分成12和345两部分，我们把这两部分分别叫pre和past。 使得这两部分的最大公约数大于1. 思路： 按是否为素数分情况讨论 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788/* Kininged_7*/#include <algorithm>#include <cmath>#include <cstdio>#include <cstring>#inclu ...

数列分块 区间加法，区间内小于x的个数 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <vector>#define int long longusing namespace std;int n;const int N = 1e5 + 7;int add[N], a[N], pos[N], L[N], R[N], b[N];vector<int > ...

SDUT 2021 summer team contest 11th https://vjudge.net/contest/454997#problem/B B 12345678910111213141516171819202122232425262728#include <iostream>#include <algorithm>#include <cstring>#include <map>#include <vector>using namespace std;#define int long long typedef long long ll;int n;const int N = 5e3 + 7;int a[N];int dp[N][N];signed main() { scanf("%lld",&n); for ( int i = 1; i <= n; i ++) scanf("%lld", a + i); sort(a + 1,a ...

以下部分摘自《算法竞赛进阶指南》 最小生成树 常用算法 kruskal KruskalKruskalKruskal总是维护无向图的最小生成森林。 KruskalKruskalKruskal从剩余的边中选出一条权值最小的边，并且这条边的两端分属于不同的集合（即生成森林中不同的两棵树）；把这条边加入生成森林中。使用并查集来维护结点的连通情况。 实现步骤 1、建立并查集，最初时每个点各自为一个集合。 2、把所有边按照权值从小到大排序。 3、扫描每条边 如果这条边连接两个不同的树，合并这两个点，并将边权加入答案。 否则忽略这一条边。 时间复杂度 O(mlogm)O(mlogm)O(mlogm) 常用情况 基本都用。有的题使用KruskalKruskalKruskal做起来很方便，而用primprimprim很困难。 代码实现 1234567891011121314151617181920212223242526272829303132const int M = 5e4 + 8,N = 2e3 + 8;int fa[N],n,m,ans;struct rec{ int x,y ...

fhq treap 结构 12345678910struct node{ int l,r; int val, key; int Size; #define l(u) fhq[u].l #define r(u) fhq[u].r #define Size(u) fhq[u].Size #define v(u) fhq[u].val #define key(u) fhq[u].key}fhq[N]; 储存左右儿子，值，索引（用于平衡），树的大小。 基本操作 新建 123456int newnode(int val) { fhq[++cnt].val = val; fhq[cnt].key = rnd(); fhq[cnt].Size = 1; return cnt;} 更新 123void update(int u) { Size(u) = Size(l(u)) + Size(r(u)) + 1;} 分裂 按值分裂，把树拆成两棵，一棵全部小于等于给定值， ...

B:Boxes 题目链接：https://ac.nowcoder.com/acm/contest/11256/B 题意： 有nnn个盒子，每个盒子中要么是黑球，要么是白球。在盒子未打开之前不知道盒子内球的颜色，打开盒子需要花费wiw_iwi​。求出得知所有盒子中球是什么颜色所花费的期望。你可以选择花费价值ccc来获得一个提示，告诉你剩下的未打开的盒子中有多少个黑球。 思路： 提示只需要获取一次即可。因为在最开始时获取提示后可以全局有效。 第一种打开方式为将权值排序后，从小到大计算能取到当前位置的概率。能取到第iii个位置说明取了第i−1i-1i−1个位置上的还不是一个确定局面。确定局面为后面的一段全为同色。所以i−ni-ni−n肯定不为同色。同色的情况有两种，全为黑色或者全为白色。则第iii个位置上能取的概率为1−22n−i+11-\cfrac{2}{ 2^{n-i+1} }1−2n−i+12​，即p(i)=1−12n−ip(i)=1-\cfrac{1}{ 2^{n-i} }p(i)=1−2n−i1​。期望E=∑i=1np(i)∗w(i)E=\displaystyle\sum_{i=1 ...

尺取法 尺取法通常指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点直到得出答案的方法。 尺取法的实现方式是双指针。 当该区间满足一定性质时，就尝试移动左端点（起点）；如果不满足性质，就移动右端点（终点）。 模板 1234567//ed为尾指针，st为头指针，sum为当前状态while (1){ while (ed < n && sum不满足性质 ) sum更新 if (sum不满足性质) break; ans = min(ans, ed -st); sum -= a[st++]; } 时间复杂度：O（n） 例题1：POJ 3061 题目链接：http://poj.org/problem?id=3061 题意： 给出一个序列，求一个最小区间长度，该区间需满足区间内数的和大于等于所给值。 思路： 一种可行的做法是预处理出前缀和，然后二分，时间复杂度为O(nlogn)O(nlogn)O(nlogn)。 使用尺取法枚举所有区间，只需 ...

离散考前预习 我想及格啊╥﹏╥ 一、命题逻辑 1-1 命题逻辑及其表示法 只有确定真值的陈述句才是命题。 1-2 联结词 真值的确定方法： 合取：∧\land∧ ，同真则真。 析取：∨\lor∨ ，同假则假。 条件：→\rarr→，前真后假则假。 双条件：↔\leftrightarrow↔，同真异假。 1-3 命题公式与翻译 略 1-4 真值表与等价公式 枚举所有情况，通过运算，即可得到所需式子的真值。 命题定律： 满足结合律，交换律，吸收率。 德摩根率：¬(P∨Q)  ⟺  ¬P∧¬Q\neg(P \lor Q)\iff \neg P \land \neg Q¬(P∨Q)⟺¬P∧¬Q ¬(P∧Q)  ⟺  ¬P∨¬Q\neg (P \land Q) \iff \neg P \lor \neg Q¬(P∧Q)⟺¬P∨¬Q 1-5 重言式与蕴含式 重言式：永真式。 矛盾式：永假式。 定理 A  ⟺  BA\iff BA⟺B 当且仅当A↔BA \leftrightarrow BA↔B为重言式。 当且仅当P→QP\to QP→Q是一个永真式时，我们称PPP蕴含QQQ，记作P⇒QP\Ra ...