Rockdu's Blog

我是原题 题目等价于求最长下降子序列长度不超过2" role="presentation" style="position: relative;">222的排列个数，否则就不可能让冒泡排序在复杂度下限。 先想一个dp" role="presentation" style="position: relative;">dpdpdp做法：设f(i,j)" role="presentation" style="position: relative;">f(i,j)f(i,j)f(i,j)是放到了第i" role="presentation" style="position:

【题目描述】给出一个N个顶点、M条边的无向图，边(u,v)有权值w(u,v)，顶点i也有权值p(i)， 并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。 现在要将顶点i的权值减去z(i)，其中0≤z(i)≤p(i)。 修改后设顶点i的权值p'(i)=p(i)-z(i)，对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。 求sum{z(i)}的最小值和最大值。   【输入】第一行两个正整数n,m (n≤500,000, m≤3,000,000)。 第二行n个整数，依次表示p(1),p(2),...,p(n) (0≤p(i)≤10^6)。 下面m行，

【题目描述】IOI铁路是由N+2个站点构成的直线线路。这条线路的车站从某一端的车站开始顺次标号为0...N+1。 这条路线上行驶的电车分为上行电车和下行电车两种，上行电车沿编号增大方向行驶，下行电车沿编号减小方向行驶。乘坐这两种电车的话，移动1站的距离需要T秒。换句话说，乘坐上行电车从车站i走到车站i+1需要T秒，称作下行电车从车站i走到车站i-1也需要T秒。你不能在0号车站乘坐下行电车，或在N+1号车站乘坐上行电车。由于电车发车的频率非常高，你可以无视等待电车消耗的时间。 每个车站设有上行电车的站台和下行电车的站台，连接两个站台的道路上设有邮戳台。 现在，IOI铁路召开了邮戳拉力赛。在拉力赛

题目描述 给你一个质数p" role="presentation" style="position: relative;">ppp以及n" role="presentation" style="position: relative;">nnn组询问， 判定给定的r" role="presentation" style="position: relative;">rrr是否为p" role="presentation" style="position: relative;">ppp的原根。 输入输出格式 输入格式 题目有多组测试数据。 每组测试数据的第一行两

Description Fib数列为1,1,2,3,5,8... 求在Mod10^9+9的意义下，数字N在Fib数列中出现在哪个位置 无解输出-1 Input 一行，一个数字N，N < = 10^9+9 Output 如题 Sample Input 3 Sample Output 4 109+910^9+9明示55有二次剩余。 考虑FibFib的通项公式: fn=1√5((1+√52)n−(1−√52)n) f_n=\frac{1}{\sqrt 5}\left (\left (\frac{1+\sqrt 5}{2}\

类欧几里得是统计直线下整点贡献的一种套路，最常见的类欧几里得是求： &#x2211;i=0n&#x230A;ai+bc&#x230B;" role="presentation" style="position: relative;">∑i=0n⌊ai+bc⌋∑i=0n⌊ai+bc⌋ \sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor 也就是直线ax+bc" role="presentation" style="position: relative;">ax+bcax+bc\fr

题意： 给定a,b,c" role="presentation" style="position: relative;">a,b,ca,b,ca,b,c,求满足方程Ax+By&#x2264;C" role="presentation" style="position: relative;">Ax+By≤CAx+By≤CAx+By\le C的非负整数解 A,B&#x2264;109,C&#x2264;Min(A,B)&#x2217;109" role="presentation" style="position: relative;">A,B

传送魔法：biu~~~~~~~ 算是一道较有趣的dp" role="presentation" style="position: relative;">dpdpdp了。 首先有一个简单的做法，状压3" role="presentation" style="position: relative;">333进制。 第i" role="presentation" style="position: relative;">iii位是0" role="presentation" style="position: relative;">000表示ai" role="pres

题目描述给定一棵n个点的树，点带点权。 有m次操作，每次操作给定x,y，表示修改点x的权值为y。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 输入输出格式输入格式：   第一行，n,m，分别代表点数和操作数。 第二行，V1​,V2​,...,Vn​，代表nn个点的权值。 接下来n−1行，x,y，描述这棵树的n−1条边。 接下来m行，x,y，修改点x的权值为y。   输出格式：   对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。 保证答案在int范围内   输入输出样例输入样例#1： 复制10 10 -11 80

题目地址：嘤嘤嘤 听说是FMT" role="presentation" style="position: relative;">FMTFMTFMT裸题然而学了FMT" role="presentation" style="position: relative;">FMTFMTFMT还是不会啊QAQ" role="presentation" style="position: relative;">QAQQAQQAQ。 首先有一个比较显然的dp" role="presentation" style="position: relative;">dpdpdp。