传送门 对于每个二进制位单独考虑贡献. 然后对于两种情况分别统计. 对于第二种要用类似数位dpdpdp的方法来计算贡献. 代码

传送门 考虑 n = 2 时的情况:假定两个人分别为(a, b),(c, d),则当且仅当min(a,d) ≤ min(b,c)时,把(a, b)放在前面更优,否则把(c, d)放在前面更优 然后把n = 2 的结论进行扩展.我们定义第 i 个小朋友比第 j 个小朋友小,当且仅当 min(ai,bj) <min(aj,bi),以这个规则进行排序,时间复杂度 O(nlogn). 这样得到的新队伍一定是满足题目要求的最优解之一,当然还可能存在其它最优解. 代码

传送门 sbsbsb签到题. 读题时间比写题时间长系列. 写一个checkcheckcheck函数来检验当前时间段第(i,j)(i,j)(i,j)号格子能否放入kkk就行了. 代码

传送门 对于每个点离线处理出向上走2i2^i2i班车到的最上面的点. 然后每个询问(u,v)(u,v)(u,v)先把(u,v)(u,v)(u,v)倍增到刚好走不到lcalcalca的情况(有一个点如果就是lcalcalca直接特判) 然后考虑最后把(u′,v′)(u',v')(u′,v′)连起来需要走一次还是两次. 这个就是一个二维数点问题了. 用dfsdfsdfs序求出每个点管辖的子树表示的区间. 然后对于询问(a,b)(a,b)(a,b)在dfs到aaa时统计bbb子树的答案. 把aaa子树

传送门 仔细读题会发现只要所有点点权之和等于0一定有解. 如何构造? 直接当做树来构造就行了,非树边都赋值成0就行. 代码

传送门 首先按照题意构造出转移矩阵. 然后可以矩阵快速幂求出答案. 但是直接做是O(n3qlogm)O(n^3qlogm)O(n3qlogm)的会TTT掉. 观察要求的东西发现我们只关系一行的答案. 于是倍增预处理出logloglog个矩阵每次变成O(n2)O(n^2)O(n2)转移. 代码

传送门 乱搞题. 我直接对权值分块+莫队水过了. 不过调了30min30min30min发现ststst表挂了是真的不想说什么233. 代码

传送门 考虑对于每次最后全部选完之后剩下的牌的集合都对应着一种构造方法. 一个更接地气的说法: 设消耗的牌数为ttt,如果使用的牌的lll值之和也为ttt,则对应着一种构造方式让这种情形成立. 于是做01背包就可以了. 代码

传送门 又TMTMTM考原题真是服. 考虑到两条路径相交一定满足某一条的lcalcalca在另外一条路径上面. 于是分开统计有多少个lcalcalca在当前路径上面以及有多少个路径经过了当前的lcalcalca,再扣去lcalcalca重复的情况就行了. 代码

传送门 正难则反. 考虑计算两人相遇的方案数. 先正反跑一遍最短路计数. 然后对于一条在最短路上的边(u,v)(u,v)(u,v),如果(dis(s,u)*2<total&&dis(v,t)*2<total)说明两人可以在这条边上面相遇. 如果对于一个点从起点到它的距离刚好是最短路的一半也可以在这个点相遇. 代码

传送门 直接建边跑差分约束就可以了. 代码

传送门 考虑直接推式子不用优化怎么做. 显然每一个二进制位分开计算贡献就行. 即记录fi,jf_{i,j}fi,j​表示距离iii这个点不超过jjj的点的每个二进制位的0/10/10/1个数. 但直接存是会爆炸的. 考虑到每个数只会被用一次,所以可以考虑主席树那种复用信息的思想来继承长链后代的信息,然后短链直接暴力统计贡献就行. 由于ldxldxldx蒟蒻是口胡选手只会暴力写法,因此正解差不多是照着标程写的233. 细节较多,用指针维护比较自然一些. 代码

传送门 显然如果AAA到BBB或者CCC到DDD走的不是最短路一定是有一段路径重合了,于是可以O(n2)bfsO(n^2)bfsO(n2)bfs出两点之间的最短距离然后枚举两个点作为重合的端点来更新答案. 然而考试的时候只枚举了最短路上的点没被卡成功踩标算? 如果数据强一点今天多半又垫底了233. 我果然还是太菜了啊! 代码

传送门 考试5分钟写完. 如果没这题今天多半爆零了(汗 直接二分出合法的转移范围. 然后用后面的状态更新前面的就可以了. 代码

传送门 分四个方向分别讨论. 每次枚举当前行iii,然后对于第二维jjj用斜率优化dpdpdp. f[i][j]=(j−k)2+mindisk2f[i][j]=(j-k)^2+mindis_k^2f[i][j]=(j−k)2+mindisk2​其中mindismindismindis表示离第iii行的最短距离. 这个显然可以斜率优化 代码

传送门 发现题目要求的就是从下到上的瓶颈路. 画个图出来发现跟去年noipnoipnoip提高组的奶酪差不多. 于是可以二分宽度+并查集检验,或者直接求瓶颈. 代码

传送门 考虑如果一个区间满足最小值等于最大公约数那么这个区间是合法的. 因此我们对于每一个点维护可以延展到的最左/右端点保证这一段区间的gcdgcdgcd等于这个点的值. 这个可以用之前同类的链表或者用单调栈维护. 代码

目录 2018.11.7 NOIP模拟 A 序列sequence(two pointers) B 锁lock(思路) C 正方形square(埃氏筛) 考试代码 B C 2018.11.7 NOIP模拟 时间:3.5h 期望得分:100+0+40 实际得分:100+0+40 A 序列sequence(two pointers) 其实我们只要处理每个数与哪些数相加,会产生进位就行了. 把数排序后,枚举一个数x,容易想到满足使x+y进位的y是单调的(要求y<=x).所以可以二分. 但是单调,好像只需

11.1 NOIP 模拟赛 期望得分:50:实际得分:50: 思路:暴力枚举 + 快速幂 #include <algorithm> #include <cstring> #include <cstdio> using namespace std; typedef long long LL; ; int n, m; LL ans; LL qpow(LL a, LL b) { LL res = ; while (b) { ) res = res * a % Mod; a =

*注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A 妹子 Problem B 旅程 Problem C 老大 因为业务水平下滑太严重,去和高一考NOIP模拟,sad... Problem A 妹子 题目大意 给定两个矩形,问一个能否将一个矩形放在另一个矩形里面. 先可以根据面积判断哪一个被放在里面,然后判断一下能不能直接放或者旋转90°放进去. 如果不行的话,接着考虑旋转.我们考虑这样↓放置小矩形. 连接$EG$,作$GI\perp AD$于点$I$,$FJ\perp