tshoigyr-CSDN博客

原创新的开始

一直想（bei）写（lao）博（shi）客（cui），可总因种（lan）种（ai）原（wan）因（qi）未能成文今天这篇，就算做开始吧……

2017-10-23 18:44:35 382 13

原创 NOIP2017爆炸记

Day0最后一天还要考试，差评！教练请所有学生吃了顿饭，想着有些同学就要退出oi了，还是有一点悲伤的。晚上想起了学长的忠告：考前千万不要打板！！！于是早早就睡了。Day1早早来到神大，被学长qizy强奶一口：“听wuvin说你遇到简单题就会爆炸。”emmmm……，心情复杂不想说话（最后果真炸了）。开题，T1，咦？什么玩意，不是一个最短路吗？（后来发现这真是一个奇葩的想法...

2018-02-21 21:29:21 590 1

原创 NOIP模拟（20171102）T3 回文子串

给定两个字符串s1,s2，按如下方式构造一个串s：每次从s1或s2的头部取一个字符放到s的末尾，求所有可能的s中最大的最长回文子串的长度（好吧题意有点绕）考虑dp，f[i][j][k][l]f[i][j][k][l]表示s的前半部分选了i−1i-1个来自s1的字符，j−1j-1个来自s2的字符，s的后半部分选了k−1k-1个来自s1的字符，l−1l-1个来自s2的字符，在中间结合处的回文串长度。

2017-11-08 16:48:46 261 1

原创 NOIP模拟（20171102）T2 最佳序列

给定一个序列aia_i，求区间长度在ll到rr之间的所有区间平均数的最大值二分答案，之后将序列中每一个数减去二分的平均数，原题转换为是否存在一个区间，长度在ll到rr之间，且区间和大于0 求新的序列的前缀和，记为bib_i 则对于每一个bib_i，我们要判断在bj(i−r≤j≤i−l)b_j(i-r\leq j \leq i-l) 中有没有小于等于bib_i 的那就是一个sliding w

2017-11-08 10:07:18 209 1

原创 NOIP模拟（20171102）T1 活动安排

给定n个区间，求最多取多少区间使这些区间无交集贪心：取能塞下区间中结束时间最早的即可证明什么的，算法导论上找#include<bits/stdc++.h>#define FE "arrange"using namespace std;inline int getint(){ int x=0,p=1; char c=getchar(); while(!isdigi

2017-11-08 09:16:59 247 1

原创 NOIP模拟（20171031）T3 纸带

有一个纸带·，每次区间染色，同一个地方后染的颜色覆盖先染的，求最后纸带上颜色种类数。咦，这不是线段树吗？咦，倒过来做好像很方便啊？咦，离散化有坑？区间涂色，若该颜色所在区间均被染色，则该颜色按原顺序操作后会被后面的颜色覆盖注意离散化本来三个颜色3-8,2-5,7-9，最后6号点上颜色是1 离散化后为2-5,1-3,4-6，颜色1就被“吃”掉了怎么解决？自(kan)行(d

2017-11-08 09:11:31 220 1

原创 NOIP模拟（20171031）T2 朋友（BZOJ2143 飞飞侠）

题目链接 BZOJ2143 orz题解我们引入云端的概念建立一个包含n∗m∗(n+m−2)n*m*(n+m-2) 个点的分层图 G[1⋯n][1⋯m][1⋯n+m−2]G[1\cdots n][1\cdots m][1\cdots n+m-2] 其中G[n][m][0]G[n][m][0] 表示街区，G[n][m][h](h>0)G[n][m][h](h>0) 表示一个高为hh 的云

2017-11-02 16:23:41 268 1

原创 NOIP模拟（20171031）T1 机器清洁工

没什么好说的，矩阵前缀和裸题代码#include<bits/stdc++.h>using namespace std;inline int getint(){ int x=0,p=1; char c=getchar(); while(!isdigit(c)){ if(c=='-')p=-1; c=getchar(); }

2017-11-02 16:19:02 233 1

原创 NOIP模拟（20171030）T3 星星

题意：（说不清）一道证明复杂度题这样是O(mm−−√log2n)O(m\sqrt m log_2n) 的自己看吧~#include<bits/stdc++.h>#define LEN 300000using namespace std;inline int getint(){ int x=0,p=1; char c=getchar(); while(!isd

2017-11-01 08:48:13 249 1

原创 NOIP模拟（20171030）T2 游戏

nn个物品，每个物品权值为ai(1≤i≤n)a_i(1\leq i\leq n)，两人按给定顺序轮流拿物品，先手先拿11或22个物品。然后若上一个人拿了kk个物品，这一个人必须拿kk或k+1k+1个物品，若剩余物品不足k个，游戏结束。两个人都尽可能使自己拿的权值比别人大，游戏结束后，先手拿的权值比后手多多少（假设两个人都绝顶聪明）那还要我干嘛 n≤20000n\leq20000 考虑dp：d

2017-11-01 08:41:55 291 1

原创 NOIP模拟（20171030）T1 比赛

给定nn个人的能力值ai(1≤i≤n){a_i}{(1\leq i\leq n)}，每轮比赛任选两个人i,ji,j，若∣ai−aj∣>k\mid a_i-a_j\mid>k，则能力值大的人获胜，否则，两人均有可能获胜。每轮比赛完后，失败方淘汰。n−1n-1轮比赛完后，剩下的人获得总冠军。求一开始哪些人可能获得总冠军。题解：将ai(1≤i≤n){a_i}{(1\leq i\leq n)}从小到大排

2017-11-01 08:20:16 291 1

原创 NOIP模拟（20171026）T3 大逃杀

一棵带权树，第一次经过一个节点需ti时间，获得wi的武力值求T时间内获得的最大武力值 n,T≤300n,T\leq 300 树形dp神题（告诉了我什么叫转移顺序） dp[i][j][0/1/2]dp[i][j][0/1/2]表示路径的【起点终点都在i/起点（或终点）在i，另一点在i的子树内（因为路径是可逆的）/起点终点都在i的子树】内能得到的最大武力值转移即可（说的容易！！！）

2017-10-26 19:12:40 257 1

原创 NOIP模拟（20171026）T2 做运动

最小生成树+最短路裸题？二分+最短路裸题？还是归为卡常题吧别看了，没卡过去#include<bits/stdc++.h>#define LEN 2000000#define INF 1000000000000000000using namespace std;inline int getint(){ int x=0,p=1; char c=getchar();

2017-10-26 19:02:21 305 1

原创 NOIP模拟（20171026）T1 抄代码

题意——我不知道，我不知道，我不知道反正判判就行了怎么判？不知道不知道不知道……#include<bits/stdc++.h>using namespace std;inline int getint(){ int x=0,p=1; char c=getchar(); while(!isdigit(c)){ if(c=='-')p=-1;

2017-10-26 15:55:43 227 1

原创 NOIP模拟（20171024）T3 数学

求满足方程ax≡xa(mod2n)a^x\equiv x^a\pmod{2^n} 的解的个数 n≤30,a≤109n\leq 30,a\leq 10^9 询问组数T≤1000T\leq1000 引理一：若a,b均为奇数，且a2k+1≡b2k+1(mod2n)a^{2k+1}\equiv b^{2k+1}\pmod{2^n}，则a≡b(mod2n)a\equiv b\pmod{2^n} 证明

2017-10-25 07:43:55 207 3

原创 NOIP模拟（20171024）T2 乘积

求从1-n中选k个数，使得这k个数的乘积不含完全平方因子 70% n≤30\ \ \ n\leq30 100% n≤500\ \ \ n\leq50070%：状压dp，f[i][j][k]表示前i个数，选了j个，当前所选数之积分解质因数后的状态为k（k表示成二进制后，第一位表示有没有2，第二位表示有没有3……以此类推）令i+1分解质因数后状态为pos[i+1] f[i][j][

2017-10-24 19:57:47 261 1

原创 NOIP模拟（20171024）T1 Graph

poj3177弱化版双连通分量缩点，答案为（叶子节点+1）/2 （还不带重边，实在没什么好说的了）#include<bits/stdc++.h>#define LEN 1000006using namespace std;inline int getint(){ int x=0,p=1; char c=getchar(); while(!isdigit(c)){

2017-10-24 19:08:49 226 1

原创 NOIP模拟（20171023）T3 拆网线

求用最小数量的边使得树上至少k个点被这些边覆盖 2≤k≤n≤1052\leq k\leq n\leq 10^5 显然，一条边覆盖两个点最好。考虑最多能有多少边能覆盖两个点，用树形dp即可复杂度O(n)O(n)#include<bits/stdc++.h>#define LENusing namespace std;inline int getint(){ int x=0,p

2017-10-23 20:51:14 340 3

原创 NOIP模拟（20171023）T2 一样远

求树上离给定两点a，b一样远的点的个数点数n≤105n\leq10^5，询问数m≤105m\leq10^5 首先，如果a=b，那么n个点都是答案如果a≠\neqb，将从a到b的链提出来，易得链中点及其子树到a、b距离均相等显然，我们不能暴力跳树高找中点，考虑倍增注意当lca是链中点时lca的祖先节点及祖先节点的其他子树上的点也是答案复杂度O(nlog2n+mlog2n)O(nl

2017-10-23 20:05:00 335 2

原创 NOIP模拟（20171023）T1 fibonacci

求一个数是否为两个fibonacci数的乘积数据组数T≤100\leq100，n≤1000,000,000\leq1000,000,000 好吧小于等于1e9的fibonacci数只有45个，暴力即可#include<bits/stdc++.h>using namespace std;inline long long getint(){ int x=0,p=1; char

2017-10-23 19:35:06 272 4

tshoigyr的博客