1 黑夜和白天

尚未进行身份认证

我要认证

Szu 菜鸡冲冲,码农生来只为前进

等级
TA的排名 9w+

Codeforces Round #672 (Div. 2)D. Rescue Nibel![扫描线解决区间问题]

题目链接题目大意:就是给你n个区间,从中选出k个区间,这k个区间共同覆盖了同一个点,问有多少种选法?结果mod 998244353解题思路:1.首先我们可以这么想:我们把区间左端点赋值为1,右端点赋值为-1,那么我们就可以像扫描线一样那么将左右端点分开存储,先按照第一关键排序然后如果第一关键字相同,那么就入度的点先进来。2.当有一个点进来那么就从前面还存在的区间里面挑出k-1,一个点和它匹配那么不断的跟新答案就可以了代码:#include <iostream>#include

2020-09-25 18:54:12

Codeforces Round #672 (Div. 2):C2. Pokémon Army (hard version)[差分的思想]

题目链接题目大意:就算给你一序列,按照顺序出若干个数组成一个的序列,然后对这个序列定义一个权值就算奇数位置的和减去偶数位置的和,问你能的到的最大的权值是多少?**a1 - a2 + a3 - a4 + a5 … **解题思路:1.就是我们观擦一下:就任意多个ai - aj的组合;最后的就是an - 0;2.我们可以用差分的思想:ai就是差分数组前i位的前缀和,那么ai-aj就是差分数组的区间和,就是贪心挑出任意多个差分大于0的区间求他们的和3.我们发现如果这个区间内部有出现+配-配+但是总的s

2020-09-25 18:39:33

博弈论入门1

博弈论1.是二人或多人在平等的对局中各自利用对方策略变换自己的对抗策略,达到取胜目标的理论。2.博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系,从而确定自己在博弈中3.的优势,因此有不少博弈理论,可以帮助对弈者分析局势,从而采取相应策略,最终达到取胜开胃菜-抢糖果1.桌子上放着5块糖,Alice和Bob轮流拿,Alice先手2.没人最少可以拿1块最多拿3块3.拿最后一块糖的人获胜我们推导一下:1.假如说桌子上只有1~3块糖果时候,拿糖果得人可以一次拿走这就是先手必胜态

2020-09-21 20:04:10

min25模板链接

https://www.cnblogs.com/GreenDuck/p/10695376.html

2020-09-21 09:39:57

[hdu-6608] Fansblog 威尔逊定理 质数的密度分布 快速乘优化快速幂防止中间爆longlong

题目链接题目大意:就是给你一个质数P∈[2,1e14]P\in[2,1e14]P∈[2,1e14]求一个质数Q<PQ<PQ<P解出Q!modPQ!modPQ!modP解题思路:1.素数阶乘:我们可以使用威尔逊定理,(P−1)!mod(−1)≡P(P-1)!mod(-1)\equiv P(P−1)!mod(−1)≡P2.那么Q!=(P−1)!(Q+1)∗(Q+2)...∗(P−1)Q!={(P-1)!\over (Q +1)*(Q+2)...*(P-1)}Q!=(Q+1)∗(Q+

2020-09-14 08:51:58

B. Power Sequence[Codeforces Round #666 (Div. 2)][暴力]

B. Power Sequence有 n 个数,现在要求将这个数列变成一个等比数列的形式你可以将这 n 个数随意排列或者将任意一个数加一或者减一操作,每次此类操作都要花费 1,问最少花费是多少这题神坑:把快速幂卡了,边界处理不好,快速幂中途爆了long long,可以用pow代替剩下的暴力枚举就可以了#include <iostream>#include <cstdio>#include <stack>#include <sstream&gt

2020-09-12 10:31:54

D. Colored Rectangles[思维dp]

题意:3种颜色木棍,每次从两种颜色木棍各选一对组成矩形。求最后所有矩形面积和最大值。#include <cstdio>#include <cstring>#include <vector>#include <algorithm>#include <map>using namespace std;typedef long long ll;const int maxn = 205;int R[maxn],G[maxn],B

2020-08-29 23:10:04

可删除任意位置数据的堆

struct heap {//手写实现删除任意位置数值的堆 priority_queue<int> A , B; void push(int x) { A.push(x); } void erase(int x) { B.push(x); } void pop() { while(B.size() && A.top() == B.top()) A.pop(), B.

2020-08-28 21:10:54

Codeforces 1400E Clear the Multiset(贪心 + 分治)

E Clear the Multiset#include <iostream>#include <cstdio>#include <stack>#include <sstream>#include <limits.h>#include <vector>#include <map>#include <cstring>#include <deque>#include <cm

2020-08-28 19:54:41

B. RPG Protagonist[Educational Codeforces Round 94 (Rated for Div. 2)]数学枚举

B. RPG Protagonist题目大意:就是你有两个人,每个人都有一个最大的体力值p和f,这两个人要去搬运剑和盾牌,剑的数量是cnts,盾的数量是cntw,每个剑的重量是是s,每个盾的重量是w,问你最多可以搬运多少武器解题思路:一眼就是一个贪心题但是如何贪心确是一个问题?很显然剑和盾哪个轻就拿哪个为了直观一点,我们可以设出这些自变量了****#include <iostream>#include <cstdio>#include <stack>

2020-08-28 19:42:16

D. Zigzags[ Educational Codeforces Round 94 (Rated for Div. 2)]思维枚举优化4重循环

D. Zigzags题目大意:就是给你i<j<k<l并且aj=al&&ai=aki<j<k<l并且a_j=a_l \&\& a_i=a_ki<j<k<l并且aj​=al​&&ai​=ak​,求满足(i,j,k,l)的四元组有多少对解题思路:1.很明显我们最暴力的做法是O(n4)O(n^4)O(n4)去枚举,因为题目的数据只有3000,可以预估的复杂度在O(n2)O(n^2)O(n2)左右,那么实际上

2020-08-28 17:21:22

矩阵树定理2020HDU多校第6场j-Expectation[位运算+期望]

矩阵树定理用于求解图上面生成树的个数,生成树的个数等于基尔霍夫矩阵的任何一个N-1阶主子式的行列式的绝对值矩阵树模板struct Matrix_Tree{ ll a[N][N]; Matrix_Tree () {ms(a,0);} void init_cnt(ll val) { memset(a,0,sizeof(a)); for(int i = 1; i <= m; i ++) {

2020-08-17 21:28:41

[Ahoi2013]差异[后缀数组+单调栈]

链接解题思路:很明显前面∑1<=i<j<=nlen(Ti)+len(Tj)\sum_{1<=i<j<=n}len(T_i)+len(T_j)∑1<=i<j<=n​len(Ti​)+len(Tj​)是定值len∗(len+1)∗(len−1)/2len*(len+1)*(len-1)/2len∗(len+1)∗(len−1)/2那么题目就是变成了求任意两个后缀的lcp求和根据后缀数组的求法lcp(suf(i),suf(j))=min(Heigh

2020-08-17 18:43:44

存一个讲ac自动机比较好博客

链接

2020-08-14 22:03:03

codeforces432D[kmp的next数组的运用]

解题思路:1.就是nxt数组不断嵌套递归下去就好了2.如何统计子串出现的个数我们从后往前遍历:根据那个图大的子串会包含小的子串,所以我们就处理前缀和将大的个数加到小的里面去#include <cstdio>#include <cstring> const int N = 1e5+5; int n, jump[N], c, r[N], dp[N];char str[N]; void getJump() { int k = 0; n = ..

2020-08-14 21:40:16

exkmp解读

题解 P5410 【【模板】扩展 KMP】 posted on 2019-05-20 13:51:22 | under 题解 | 55 一、引言一个算是冷门的算法(在竞赛上),不过其算法思想值得深究。二、前置知识kmp 的算法思想,具体可以参考这篇日报。trie 树(字典树)。三、...

2020-08-14 20:16:24

[Scoi2016]背单词[字典树+dfs重构树[类似虚树]]

解题思路:很明显第一个条件是可以避免的,第二个条件是第三个条件的特殊情况,所以有用的只有第三个条件,现在我们就是想将这些单词重排使得每个单词后缀都在这个单词的前面并且代价最小我们举个例子:6acaeagdahdaifb很明显我们发现很多点是没有用的我们为了计算其实可以直接提出红色的点我们可以举几个例子,发现先跑子树小的明显最优#include <iostream>#include <cstdio>#include <stack>...

2020-08-14 17:16:22

Codechef REBXOR[dp+字典树]

解题思路:1.区间异或和可以搞前缀[or后缀]异或,xori=lra=pre[l]⊕pre[r]xor_{i=l}^{r}a=pre[l]\oplus pre[r]xori=lr​a=pre[l]⊕pre[r]2.那么题目就变成了pre[l]⊕pre[r]+suf[l1]⊕suf[r1],pre是前缀异或和,suf是后缀异或和pre[l]\oplus pre[r] +suf[l_1]\oplus suf[r_1],pre是前缀异或和,suf是后缀异或和pre[l]⊕pre[r]+suf[l1​]⊕s...

2020-08-14 10:23:49

bzoj异或之[查询异或和的第k小]

题目大意:给你n个数,两两互相异或出n∗(n−1)/2n*(n-1)/2n∗(n−1)/2个数,求前k小的数第一次知道trie树可以查询异或值得第k小解题思路有点像这道题:题目门我们可以用优先队列维护每次先整出每个数异或的第二小值,因为第一小是自己异或自己,再继续把第二小踢掉类推下去找第三小#include <iostream>#include <cstdio>#include <stack>#include <sstream>#inc.

2020-08-13 22:55:41

Balkan2007]Toponyms[链式前向星建字典树+getchar()读入优化]

思路容易想,卡空间和时间就吐了用链式前向星压缩空间,用getchar()一位一位读加快读入#include <iostream>#include <cstdio>#include <stack>#include <sstream>#include <limits.h>#include <vector>#include <map>#include <cstring>#include <.

2020-08-13 17:32:07

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv3
    阅读者勋章Lv3
    授予在CSDN APP累计阅读博文达到30天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。