luoyuef-CSDN博客

原创 cf 词汇积累

因为自己的英语太渣了在做CF COCI POI 的时候都非常emmm…所以这是一个英语单词本。 1.corporation 公司n —–a big company, She works in a transnational corporation. 她工作在一个跨国公司。相关单词: company2.client 客户客户端 n She is a client of our co...

2018-04-18 20:32:12 400

原创各种模板

一些奇妙的模板。慢慢更新好啦。目录之外的windows对拍 while (T--) { system("rand > rand.in"); system("mthq < rand.in > mthq.out"); system("jvruo < rand.in > jvruo.out"); i...

2018-04-03 20:57:48 269

原创 Codeforces Round #476 (Div. 2) [Thanks, Telegram!] 题解

A. Paper Airplanes 简单数学模拟题。#include<bits/stdc++.h>using namespace std;typedef long long ll;ll k,n,s,p;int main(){ scanf("%I64d%I64d%I64d%I64d",&k,&n,&s,&p); ll...

2018-05-03 19:46:24 314

原创 P3608 [USACO17JAN]Balanced Photo平衡的照片

FJ正在安排他的N头奶牛站成一排来拍照。（1<=N<=100,000)序列中的第i头奶牛的高度是h[i]，且序列中所有的奶牛的身高都不同。就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。如果存在i满足max(Ri,Li)>2*min(Li,Ri) 那这个奶牛的就是不平衡的。请帮助FJ计算不平衡的奶牛数量。口胡一下题解。计算左边比他少的只要开权值线段树然后...

2018-04-27 08:03:46 299

原创 [POI2009]SLO-Elephants

对于一个 1−N1−N1-N 的排列(ai)，每次你可以交换两个数ax与ay(x<>y)，代价为W(ax)+W(ay) 若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。交换关系显然成一个有向环。若环是自环代价为 000 。若环不为自环。环内每个点都要被计算至少一次。(把他们移动到正确的位置) 若环中点数为 222 可以直接交换。 ...

2018-04-26 21:17:59 312

原创 [POI2010]PIL-Pilots

给定nnn kkk和一个长度为nnn的序列，求最长的最大值最小值相差不超过kkk的序列第一行两个有空格隔开的整数kkk (0<=k<=2000,000,000)(0<=k<=2000,000,000)(0nnn (1<=n<=3000,000)(1<=n<=3000,000)(1kkk代表设定的最大值，nnn代表序列的长度。第二行为 nnn 个由...

2018-04-26 21:07:51 345

原创 cf963 A. Alternating Sum

给出 n,a,b,kn,a,b,kn,a,b,k. 输入 kkk 个数全是 111 或 −1−1-1 的序列 SSS. 求∑sian−ibi∑sian−ibi\sum sia^{n-i}b^i 对 1e9+91e9+91e9+9取模的结果。数据范围n,a,b<=109n,a,b<=109n,a,bk<=105k<=105k(b/a)(b/a)(b/a) 因为...

2018-04-25 19:56:04 859

原创 cf964 D. Destruction of a Tree

给一棵树每次可以选一个度数为偶数的点删掉。问能不能删完所有点。如果能输出任意方案。我们注意到给的树如果是偶数点就会有奇数条边。然而我们每个操作一定删掉偶数条边。所以一棵偶数点的树是不能被删完的。如果有奇数点的树。删掉任意一点后，他的子树就会变成森林。如果有偶数点的树是删不掉的。因此，对于一个点他的子树的sizesizesize是奇数的，那么可以先删掉父亲再删掉子树，否则先删掉子...

2018-04-25 15:12:07 182

原创 [CTSC2017]密钥

一个环有 2∗n+12∗n+12*n+1 个位置, 选择 nnn 个位置填上//nnn 个 AAA 或 nnn 个 BBB ….题目太长了自己查吧qwq有一点很容易想到就是把 AAA 和BBB 一个看成 111 一个看成−1−1-1 空位看成 BBB 然后枚举空位的位置为x 快速计算答案。我们发现对于 i>xi>xi>x : sum[i]>sum[x]su...

2018-04-25 14:13:52 254

原创 AtCoder Regular Contest 096 题解

C - Half and Half 题意：你需要买两种披萨AAA BBB 分别 AiAiAi BiBiBi 个。 AiAiAi BiBiBi 为整数有 333 种购买方式。买 111 个 AAA 买 111 个 BB B. 买 0.50.50.5 个 AAA 和 0.50.50.5 个 BBB 三种购买方式价格不相同，求最小花费。简单贪心即可。#include<b...

2018-04-25 12:51:48 259

原创 cf949C Data Center Maintenance

题意：某土豪公司建立了n个数据中心，把m份资料每份在其中的两个数据中心备份。每个数据中心在一天h个小时当中有一个小时需要维护，此时不提供资料下载服务。现在土豪公司想要将其中若干个数据中心的维护时间向后推迟一小时，并要求一天中任意时刻每份资料都可以被下载，问最少选取多少个数据中心维护。输入第一行n,m,h,见题目描述第二行n个整数，维护时间接下来m行，每行两个整数，存相同资料的一对...

2018-04-18 19:58:26 286

原创 [HNOI2012]永无乡

永无乡包含 nnn 座岛，编号从 111 到 nnn ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 nnn 座岛排名，名次用 111 到 nnn 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 aaa 出发经过若干座（含 000 座）桥可以到达岛 bbb ，则称岛 aaa 和岛 bbb 是连通的。现在有两种操作：BBB xxx yyy 表示在岛 xx...

2018-04-18 15:21:15 406

原创 [COCI2017-2018#2] Garaža

维护一个nnn个数的序列支持两个操作。 1. Change the value at positionXXX in the sequence to VVV 2. Determine the number of interesting contiguous subarrays contained in the interval [L,...

2018-04-18 11:52:26 360

原创 [SCOI2014]方伯伯的OJ

数据范围n<=108,m<=105n<=108,m<=105n222颗平衡树,一棵以编号中序遍历,一棵以排名中序遍历，每个节点开pairpairpair记录下这排名和编号。然后对于每个操作直接按照题意去修改就好了。把连续的区间缩成点用的时候再拆开。注意以编号中序遍历中 pairpairpair 的排名并不是真实排名而是相对排名,需要到另一棵树中再查找。 fi...

2018-04-17 15:53:08 318

原创 AtCoder Regular Contest 083 D

题意：有 nnn 个点的无向图。给你两两点对间最短路。最小化原图边权。若不存在原图输出−1−1-1. n<=300n<=300n−1−1-1.有 (n∗n−1)/2(n∗n−1)/2(n*n-1)/2 条边,每次判断最短路O(n2)O(n2)O(n^2)。复杂度O((n4−n3)/2)O((n4−n3)/2)O((n^4-n^3)/2)然而标算并不是这样的… 考虑...

2018-04-17 15:44:39 140

原创 BZOJ 2456 and 洛谷总统选举

给出 nnn 个数,其中有一个数出现过>0.5∗n+1>0.5∗n+1>0.5*n+1 次输出这个数。 n<=5∗105n<=5∗105n1MB1MB1MB 时限0.1s0.1s0.1s思考这个数的性质, 这样的数有且只有一个,其他数的总和加起来没有这个数多。设这个数为p 所以sump−sumother>0sump−sumother>0sum p...

2018-04-16 16:08:00 189

原创 [POI2014]FAR-FarmCraft

mhy住在一棵有 nnn 个点的树的 111 号结点上，每个结点上都有一个妹子。 mhy从自己家出发，去给每一个妹子都送一台电脑，每个妹子拿到电脑后就会开始安装zhx牌杀毒软件，第i个妹子安装时间为 CiCiCi 。树上的每条边 mhymhymhy 能且仅能走两次，每次耗费 111 单位时间。mhy送完所有电脑后会回自己家里然后开始装zhx牌杀毒软件。卸货和装电脑是不需要时间的。求所...

2018-04-13 07:58:34 253

原创 [POI2005]DWU-Double-row

题意：有长度为 nnn 的二元组 (ai,bi)(ai,bi)(ai,bi)。可交换 (ai,bi)(ai,bi)(ai,bi) 。使得任意ai!=ajai!=aj ai!=aj 且 bi!=bjbi!=bj bi!=bj 的最少交换次数。对于两个二元组如果他们有相同权值的元素那么会有两种关系： 1.1.1. 必须换其中任意 111 个。 2.2.2. 若交换两个必须都要换。...

2018-04-12 20:09:49 195

原创 Bird

有一棵 nnn 个点的树。iii 的父亲为 ⌊i/2⌋⌊i/2⌋ \lfloor{i/2\rfloor}。(i>=2)(i>=2)(i>=2) 每个点有一个承载上限，给出mmm个点的位置。输出前 iii个点 (1<=i<=m)(1<=i<=m)(1n,m<=3∗105n,m<=3∗105n,mSSS 连初始位置容量为初始点个数费用0，每个点连 ...

2018-04-12 16:44:20 217

原创 BZOJ3894:文理分科

https://blog.csdn.net/PoPoQQQ/article/details/43968017求最大收益->总收益-最小的丢失->最小割。对于直接选文理很简单，直接把点分别连 S,TS,TS,T容量分别是文理愉悦度就好了。然后如何解决相邻相同的问题呢。我们可以考虑抵消的思想。被割开的是不选的科。直接选文理的残量网络是什么样的？是选那科多出来的收益。如果这些...

2018-04-12 11:17:28 245 1

N people are waiting in line to enter a concert. People get bored waiting so they turn and look for someone familiar in the line. n个人排队等待进入音乐会。人们无聊地看看队伍里有没有自己熟悉的人。 Two persons A and B standing in li...

2018-04-12 08:54:49 286

原创 cf 337D - Book of Evil

给定一棵树和树上的一些点，求到任意的给定点的距离≤d的点有几个?一个显然的性质如果这个点到这些点里距离最长的两个点的距离都 <=d<=d

2018-04-11 20:19:55 287

原创 804D - Expected diameter of a tree

太久之前写的都快忘了= = 这题做起来还是挺简单的。当时很快就想出来写完了（调好久我会乱说嘛）题意即给你一个森林，每次询问给出u,v，从u所在连通块中随机选出一个点与v所在连通块中随机选出一个点相连，问你此时相连出的树的直径期望是多少？（如果本身就在同一个连通块内，则输出-1）仔细想一下就知道答案只有两种情况，大树的直径或两个树链接起来。求每个连通块直径后从两端点找到最长的...

2018-04-11 20:13:55 175

原创 cf 665E - Beautiful Subarrays

One day, ZS the Coder wrote down an array of integers a with elements a1, a2, …, an. A subarray of the array a is a sequence al, al + 1, …, ar for some integers (l, r) such that 1 ≤ l ≤ ...

2018-04-11 19:55:22 377

原创 cf 950C - Zebras

Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a zebra, if it starts with a bad day, ends with a bad day, and...

2018-04-11 19:44:07 201

原创 UVA 1619 Feel Good

一句话翻译题意：给定含有 nnn 个含有非负整数的数列 a1...ana1...ana1...an。最大化(∑ai)∗min(ai)(∑ai)∗min(ai)(\sum ai)*min(ai) (l<=i<=r)(l<=i<=r)(ll,r,suml,r,suml,r,sum。考虑每个点的贡献，如果他为乘的那个最小值的话，我们只要快速求出区间就好了，单调...

2018-04-11 16:59:35 164

原创 [USACO06NOV]糟糕的一天Bad Hair Day

一些农民约翰的N头牛（1≤N≤80,000）头发不好！由于每头母牛都对自己的发型很敏感，因此FJ想要计算能够看到其他母牛头顶的其他母牛的数量。每头牛都有一个特定的高度hi（1≤hi≤1,000,000,000），站在一排朝东的牛群中。因此，只要这些奶牛严格比奶牛矮，i就可以看到奶牛头顶上的奶牛（即母牛i + 1，i + 2等等）。考虑每个点对答案的贡献。设他右边比他高的第一个点为k，点...

2018-04-11 15:53:17 288

原创 [POI2008]PLA-Postering

题目简述：N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们。不能超出边界.emm 残缺的知识点。。长度显然没什么用。宽度考虑单调递增的情况，每多一个就加一个。如果新来一个矮的且高度在之前出现过，答案不变。如果再新来一个比刚加入的矮的高一些的且也出现过，答案还是要+1。这个过程可以用单调栈维护单调递增的序列，如果其中有那个元素答案不变，否则+1.#inclu...

2018-04-11 15:09:09 180

原创 [2018多省省队联测] Day 2 部分解题报告

T1劈配题目太长传送门第一问考虑动态加边网络流。按照志愿顺序加边，如果能够bfs成功就能成功增广。记录答案即可。难点在第二问，如何确定最少增长几名呢。二分是比较好想到的。。有一个妙妙的做法就是，在第一问时存下每一个状态的图，然而第二问二分到相应的图，上去增广。小技巧就是不需要的边及时删掉。这题还是比较妙的，动态加边加上存残图。// luogu-judger-enable-o2#...

2018-04-11 13:53:53 226

原创 [2018多省省队联测] Day 1 解题报告

T1 一双木棋chess n,m<=10 Alice想最大化差值，Bob想最小化差值。发现棋子呈阶梯状排布，总状态数阶梯状排布，阶乘复杂度。哈希记录状态后爆搜，记录当前是谁的回合，按照自身的决策去最大化/最小化价值。#include<bits/stdc++.h>using namespace std;typedef long long ll;const...

2018-04-10 15:50:02 276

原创 [BJOI2017]喷式水战改

= = 虽然这题并不太难调可我还是调了一年呀。。一个区间DP+平衡树维护。因为空间不太够，所以点合并起来（就像NOIP2017列队一样）。然后用的时候拆开，最多2e5个点。考虑状态f[l][r][i][j]f[l][r][i][j]f[l][r][i][j]为l-r区间内用了从i到j的方案的最大价值。转移显然。。然后就在平衡树上调就好了= =然后你要注意update时不要写反，拆点时...

2018-04-08 17:12:00 364

原创 HDU4609 3-idiots

给定n条线段，随机选3条，输出三条线段能组成三角形的概率。考虑暴力。枚举两条线段，第三条前缀和查询。O(n2)O(n2)O(n^2)在O(nlogn)O(nlogn)O(nlogn)时间内枚举两条线段不太好办。换种思路考虑。如果我们枚举最长边，去找2个短边之和＞最长边的数量。设f(x)f(x)f(x)为长度为x的线段数量。求f(x)f(x)f(x)的卷积g(x)g(x)g(x)。...

2018-04-08 17:01:48 138

原创 ORZMTHQ

#include<bits/stdc++.h>using namespace std;#define ll long longconst int MAXN=1e5+5;int n,k,l,r;ll a[MAXN],sum[MAXN],sump[MAXN];double check(ll a,double b){ double t=(double)a; r...

2018-04-04 17:10:34 245

原创多重背包

有N种物品和容量为V的背包，若第i种物品，容量为v[i]，价值为w[i]，共有n[i]件。怎样装才能使背包内的物品总价值最大？最暴力的方法：拆成∑n∑n\sum n 个物品复杂度O( c∑n )O( c∑n ) O(\ c\sum n \ )二进制拆分：用2k2k 2^{k} 次方且最大的那个不超过n 表示所有的数，可证明最多有logn+1个...

2018-04-03 19:09:17 142

原创 BZOJ4503 两个串

兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。给cjr的题解跪啦~我这种菜鸡根本想不到这题怎么做呀qwq如果没有通配符考虑两个串匹配的条件对于每个ai有ai==bi 即ai-bi=0 可转化为 sigma （ai-bi）²=0考虑通配符如果有通配符无论ai是否等于b...

2018-04-03 10:58:55 201

原创 [APIO2014]序列分割

你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k + 1 个非空的块。为了得到 k + 1 块，你需要重复下面的操作 k 次：选择一个有超过一个元素的块（初始时你只有一块，即整个序列）选择两个相邻元素把这个块从中间分开，得到两个非空的块。每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。满足n<=100000,k<=200.

2018-04-03 09:05:50 364

原创 [AH2017/HNOI2017]礼物

给定两个序列A={a1..an},B={b1..bn}; 支持对序列B进行两种操作 1 整体右移 bi变成bi+1 bn变成b1 2 整体加c 最小化sigma{ (ai-bi)²}如果只有整体加c操作。即为最小化sigma{ (ai-bi+c)²}的值。解得sigma xi + sigma yi - sigma 2xiyi +元素个数*c²+ 2(sigma ...

2018-04-02 16:33:37 286

原创 ZJOI 2014 力

将Fi代入Ei=qi可消去Fj中的qj。（i-j）²可看做g（i-j）求两个卷积。注意考虑翻转后对应的位置。#include<bits/stdc++.h>using namespace std;const double Pi=acos(-1);const int MAXN=4e5+5;double q1[MAXN],q2[MAXN];struct c...

2018-04-02 14:12:13 111

原创高精度乘法

#include<bits/stdc++.h>using namespace std;const double Pi=acos(-1);const int MAXN=150000;struct cp{ double x,y; cp (double xx=0,double yy=0){x=xx,y=yy;}}a[MAXN],b[MAXN];cp oper...

2018-04-02 10:50:53 115

原创 BZOJ 2194:

一万年没有更新过博客啦。。把之前做过的题都慢慢补上吧= =请计算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n ，并且有 n < = 10 ^ 5。 a,b中的元素均为小于等于100的非负整数。题意就是c i是a和b中距离差为定值k的元素的乘积。翻转b数组后变为卷积形式。。直接做就好了#include<bits/stdc++.h...

2018-04-02 10:47:56 139

空空如也

空空如也