ohEPse

四中不教数论，只好用九中的进度来学习了 upd 11.18 终于开始教数论力！！！！1.数论基础2.质数2.1 质数的判定没什么好说的，幼儿园大班的知识。 什么？你说你不知道什么是质数？赶紧滚回去上幼儿园 kdw听了都要连夜跑过来打你 2.2 质数筛2.2.1 埃氏筛也不知道 $when how$ 老师 怎么教的，我一直以为这个叫欧拉筛。 原理：原理很简单，就是质数的倍数一定不是质数。所以我们就可以这样子求质数。 时间复杂度大概是 $O(nlog(log n))$。 123456789int isprime[maxn];memset(isprime,1,sizeof(isprime));//初始全为1，素数标记为0，合数标记为1isprime[2]=0;for(int i=2;i<=maxn;i++){ if(!isprime[i]){ for(int j=2;j*i<=maxn;j++) isprime[i*j]=1; }} 2.2.2 欧拉筛这才是正统欧拉筛 2.2.2.1 原理：跟埃氏筛原理相似。 ...

background在解决很多树形问题的时候会遇到多叉树，但是多叉树在很多时候解决起来很麻烦。根据数学家烧水的思想可以将多叉树转化为二叉树求解。同时该方法也可以将森林转化为一棵二叉树，非常实用。 solution把多叉树的第一个儿子放在左儿子，其他兄弟放在右儿子，称为“左兄弟右儿子”。 至于代码实现，输入一条边 $(u,v)$ ，表示 $v$ 是 $u$ 的孩子，如果 $u$ 的左儿子为空，就将 $v$ 放在左儿子，否则循环知道右儿子不为空放进去。12345678910111213for(int i=1;i<=n;i++){ cin>>v>>w; if(ch[v][0]==0) ch[v][0]=i; else { int temp=ch[v][0]; while(ch[temp][1]!=0) temp=ch[temp][1]; ch[temp][1]=i; } c[i]=w; in[ch[i][0]]++; in[ch[i][1]]+ ...

2.6~2.9 数据结构与 $dp$ 专练，每天4题，难度不小，深蓝到深紫之间的难度。 绝大部分题来自bzoj，洛谷上只收录了一小部分。 D1T1 与或 ：线段树维护二进制操作 D1T2 排队计划：推导性质+线段树维护 D1T3 Kinoman： 权值线段树 D1T4 Hotel：线段树+最长子序列 D2T1 [NOI2016]区间：双指针+线段树 D2T2 跳伞求生：贪心/线段树模拟费用流 D2T3 Cards：线段树合并 D2T4 [AHOI2014/JSOI2014]奇怪的计算器：线段树 D3T1 层流：树剖+树上染色 D3T2 Graph：树剖/dfs序+树状数组 D3T3 three：长链剖分维护 $dp$ D3T4 月下“毛景树”：树剖裸题 D4T1 [SDOI2014]旅行：树剖+主席树 D4T2 [NOI2011]嘉年华：单调队列优化 $dp$ D4T3 [BJWC2010]严格次小生成树：树剖+最小生成树 D4T4 路径的交：dfs序 Day1 线段树专题（确信D1T1 与或Description：对于一个长度为 $n$ 的序列，维护一下三个信息： 1 l r v ...

Description:Tim 正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数 —— 自然数包括0），计算机先读取第一个数字 $S1$ ，然后顺序向后读入 $S1$ 个数字。接着再读一个数字 $S2$ ，顺序向后读 入 $S2$ 个数字 …… 依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处理数据，否则计算机就会进行自毁性 操作！Tim 现在有一串输入序列。但可能不是合法的，也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改，加上一个数或者减去一个数，当然，仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。不过 Tim 还希望更改的总代价最小，所谓总代价，就是对序列中每一个数操作的参数的绝对值之和。写一个程序：从文件中读入原始的输入序列； 计算将输入序列改变为合法序列需要的最小代价；向输出文件打印结果。 Input输入文件包含两行，第一行一个正整数 $N$ ， $N<1e ...

1. 赛后感言（？）T1-T3 属于比较简单的一眼题，J组第一题难度 T4 T6 有思路，没写完 T4 二分 + $BFS$ T6 $Tarjan$求环+$Dijstra$最短路 T5 完全没思路,并查集的做法还是比较新奇 4个小时的题只写了不到三个小时，有点可惜 2.分析1. 猴子识数题意简化：给出一个数$X$，如果是回文数，输出是第几个回文数，否则输出“NO！”。 1<=$X$<1e5 思路： 简单枚举 代码：1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<cstdio>#include<string>using namespace std;int main() { int d[2000]; int i,j,n,sum,b; for(i=1;i<=9;i++) //一位 d[i]=i; i=10; for(j=1;j<=9;j++) ...

D2T2 跳伞求生传送门 Description：小Q最近沉迷于《跳伞求生》游戏。他组建了一支由 $n$ 名玩家（包括他自己）组成的战队，编号依次为$1,2,\dots,n$ 。这个游 戏中，每局游戏开始时，所有玩家都会从飞机上跳伞，选择一个目的地降落，跳伞和降落的时间有早有晚。在某局 游戏降落前，他们在空中观察发现地面上一共有 $m$ 间房子，编号依次为 $1$ 到 $m$ 。其中每间房子恰好有一名敌人早于他 们到达。小Q战队的第 $i$ 名玩家拥有 $a_i$发子弹，地面上第i间房子里的敌人拥有 $b_i$ 发子弹，消灭他可以获得 $c_i$ 点积 分。每名玩家必须且只能选择一间房子降落，然后去消灭里面的敌人。若第i名玩家选择了第j间房子，如果 $a_i>b_ j$ ，那么他就可以消灭该敌人，获得 $a_i-b_j+c_j$ 的团队奖励积分，否则他会被敌人消灭。为了防止团灭，小Q不允 许多名玩家选择同一间房子，因此如果某位玩家毫无利用价值，你可以选择让他退出游戏。因为房子之间的距离过长，你可以认为每名玩家在降落之后不能再去消灭其它房间里的敌人。作为小Q战队的指挥，请制定一套最 ...

D1T2 排队计划Description：对于一个序列 $h$，有 $m$ 次操作，每次操作 $j$ ，将 $p_j\le i\le n$中，小于等于第 $h_j$ 的元素取出并重排后插入。求每次操作后的逆序对的数量。 Solution：一开始以为是个三维偏序 首先考虑暴力解法。对于每次询问重新求逆序对即可，预计时间复杂度为 $O(mnlogn)$ ，而且常数巨大。 然后考虑优化。可以观察到这次询问的答案可以从上一次的答案更新。易得对于每个取出的数 $h_i$ ，减少的逆序对的数量就是 $h_i$ 后比它小的数的个数。因为每次操作后序列都趋向有序，所以逆序对的数量会减少，单点暴力修改的时间复杂度是有保证的。 Code:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 ...

总结难度不算特别大，但是我是傻逼 T1 一眼贪心 T2 无脑暴力 T3 毫无头绪 T4 写不出来 （没有押好韵） T1 地鼠游戏题意： 有 $n$ 个物品 $a_i$,在 $t_i$ 秒之内选中 $a_i$ 个物品会获得 $v_i$ 的权值，求最大权值。 一眼贪心，跟那道 智力大冲浪 完全是一回事。把每个物品以 $v_i$ 为关键字排一遍顺序，然后枚举每一个 $a_i$ 找到一个时间点放进去，然后累加就完了。 然后我就写错了，特此贴出来警示自己。还没开 freopen(寄 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;struct ele{ int t,v; double p;}a[100005];bool cmp(ele a,ele b){ if(a.t==b.t) return a.v>b.v; return a.t<b.t;}int n,Time[5005],ans=0,cnt ...

“这是一场难度约为 $CSP-J$ 的模拟赛”正确的，一针见血的。这么说我都不晓得当年怎么拿的2=（悲 T1 考场上想到了前缀和这么个鬼东西，也在考虑是不是该旋转矩阵，然后发现自己完全转不来，只能随手敲个 $O(n^2k)$ 的暴力前缀和，然后 $n \leq 400$ 的数据硬是越界了8个点。高低也算个黄题吧。 T2 只记得以前做过一道类似的，但是看到超级大的 $k$ 是在想不吃什么不超时的揭解法了，随手敲了个优先队列交上去准备骗点分。黄题水准罢。 T3 一眼线段树模板题，然后我用字符串操作写了30行的代码直接跑路，要不是那个数据太坑说不准还能骗点分。可能有个绿题。 T4 是真的没头绪，大概猜出来是个 $dp$ 但是完全不知道方程怎么推，然后完全没动（悲。绿到蓝吧。 T1 sum题意： 给定一个 $n * m$ 的矩阵，可以随意选一个点向上下左右走 $k$ 步，求取得的和的最大值。 solution：把矩阵旋转45度后利用前缀和求解。这个旋转的方法确实有点骚。 code1234567891011121314151617181920212223242526272829303132333 ...