- 博客(153)
- 收藏
- 关注
RSS订阅
原创 bzoj1237: [SCOI2008]配对
发现排序后匹配的两个点距离不超过2，所以就分情况讨论就行了。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const ll inf=90000000000000000LL;int read(){ char
2018-01-04 16:38:40
285
原创 Codeforces Round #451 (Div. 2) D. Alarm Clock
题目大意删去最少的点使没有连续的长度m的一段有超过k个点。题解从前到后找，有一个时刻不符合条件就把当前点删掉，显然这样是最优的。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;int read(){ char ch=g
2017-12-16 22:45:05
248
原创 Codeforces Round #451 (Div. 2) E. Squares and not squares
题目大意每次给一个数加一或减一，问最小操作次数使一半是完全平方数一半不是。题解显然只需要将多的一部分变成少的一部分，贪心选需要操作次数最少的。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;int read(){ ch
2017-12-16 22:41:07
235
原创 Codeforces Round #451 (Div. 2) C. Phone Numbers
题目大意问有多少不同的人以及每个人有多少种不同号码，一个串是另一个后缀则算相同号码。题解先将相同的人的电话合并，然后暴力去重就行了。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f
2017-12-16 22:38:27
233
原创 Codeforces Round #451 (Div. 2) B. Proper Nutrition
题目大意求ax+by=c的一组非负整数解题解最开始没看数据范围就无脑exgcd发现有负数，然后才看到数据范围发现可以o(n)做…#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0
2017-12-16 22:34:42
186
原创 Codeforces Round #451 (Div. 2) A. Rounding
题目大意将数四舍五入…题解逗比题…#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0; while(ch<'0'||ch>'9') ch=getchar(); w
2017-12-16 22:32:38
168
原创 bzoj2209: [Jsoi2011]括号序列
还是个splay模板，写了一个晚上…太菜了#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0,x=1; while(ch<'0'||ch>'9'){if(ch=='-')
2017-12-12 22:54:10
198
原创 一些奇怪的东西
#if !defined(YCM) && 1#define _FORTIFY_SOURCE 0#pragma GCC optimize("Ofast,no-stack-protector")#pragma GCC target("avx")#include <stdio.h>#endif#include<iostream>#include<cstdio>#include<cstrin
2017-12-05 11:19:29
939
原创 BZOJ2659: [Beijing wc2012]算不出的算式
式子转化成求(1,1)-((p-1)/2,(q-1)/2)矩阵中有多少个整数点…#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0,x=1; while(ch<'0'||
2017-12-03 15:05:58
241
原创 bzoj4247: 挂饰
将挂钩数从大到小排序，然后f[ i ] [ j ]表示前i个装饰剩余j个钩子的最大价值，转移十分简单#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0,x=1; whil
2017-12-02 19:18:17
273
原创 bzoj4552: [Tjoi2016&Heoi2016]排序
二分答案，把大于二分值的变成1，否则变成0，线段树修改，最后查询问位置是1还是0。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0,x=1; while(ch<'0'|
2017-11-29 22:36:45
275
原创 bzoj3339: Rmq Problem
莫队。更新答案时加点暴力更新，删点后如果这个数出现次数为0且小于当前答案就更新。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;int read(){ char ch=getchar();int f=0,x=1;
2017-11-29 08:54:45
210
原创 bzoj1507: [NOI2003]Editor
平衡树裸题。光标位置直接修改就行，然后就区间插入删除，直接splay就行了。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0,x=1; while(ch<'0'||ch
2017-11-28 23:11:00
174
原创 Educational Codeforces Round 33 F. Subtree Minimum Query
题目大意一棵有根树，询问距离点x<=y且在x子树内的点的最小值。题解mmp,论线段树开两倍的危害… 一眼树套树裸题，就是子树内dep<=dep[x]+y的点的最小值。 搞遍dfs序，线段树套线段树就行了。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;
2017-11-24 16:28:21
600
1
原创 bzoj3991: [SDOI2015]寻宝游戏
刚刚学会虚树，有空补个详解。 显然按照dfs序走是最优解法，答案就是相邻两个点距离+第一个和最后一个距离。这玩意写平衡树怕不是写死…于是就用上了从学oi以来只用过一次的set。。。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<set>#define ll long longu
2017-11-23 22:31:13
213
原创 bzoj2648&&2716 kd-tree模板
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0,x=1; while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}
2017-11-22 10:47:16
350
原创 bzoj3714: [PA2014]Kuglarz
这题真是妙啊，只要知道所有所有[1,i]的和就能确定最后的值，当我们知道sum[i-1]，询问一次[i,j]，就知道了sum[j],这样我们可以用最小生成树来解决问题。对于[i,j],连一条从i-1到j的边。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;in
2017-11-18 17:05:37
193
原创 bzoj2132: 圈地计划
黑白染色，黑点s-(i,j)连a(i,j)的边，白色(i,j)-t连b(i,j)的边。 有关系的两点间连两点c之和的双向边。 最小割。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;queue<int> q;int rea
2017-11-15 09:58:40
199
原创 bzoj2216: [Poi2011]Lightning Conductor
这题挺妙的，hzwer#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<algorithm>#include<queue>using namespace std;int read(){ int x=0,f=1;char ch=getchar(
2017-11-14 22:19:01
266
原创 noip2017滚粗记
warning:这是一篇noi胸牌滚粗，noip预计不超过400的蒟蒻的游记…day -1喜闻乐见的颓废日前期…（明明就是颓废日好吗），然而我还是敲了几个模板233day 0喜闻乐见的颓废日…，望着一群会打红警的dalao，本蒟蒻瑟瑟发抖…有点虚，于是敲了敲模板…（alone_wolf:敲模板有用？），水了几道cf的…div2A…好似还有人与我讨论离散化和动态开点线段树那个快来着…day 1以为家里
2017-11-12 21:13:04
744
原创 给即将参加noip的自己和各位oier的一些提醒
这几天看了近几年的noip真题，并总结了一些做题经验，以后有新的感想还会总结/修改。 1.不要着急写题，先把题目读一遍，并想一想有没有思路。 2.如果T1很水的话不要着急，尽量一遍写对。并仔细检查一遍（比如手出几组数据），个人感觉T1的对拍成本很高，因为往往暴力比正解都难写。 3.其余的题必须写一个暴力，不要直接看正解的数据范围，如果没有思路先看部分分。 4.根据数据范围猜算法: 1.
2017-11-09 09:52:11
337
原创 bzoj5056: OI游戏
我们van♂游戏233。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;queue<int> q;int read(){ char ch=getchar();int f=0; while(ch<'0'||ch
2017-11-03 21:16:44
300
原创 bzoj3275: Number
1A了，最小割233，拆点，s向i1连a[i]的边，i2向t连a[i]的边，有限制的i1与j2,j1与i2连inf的边，答案就是sum-ans/2啦！#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;
2017-11-03 20:43:44
195
原创 bzoj1049: [HAOI2006]数字序列
我也贴一个233#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;int read(){ char ch=getchar();int f=0,x=1; while(ch<'0'||ch>'9'){if(
2017-10-30 19:54:43
157
原创 bzoj2252: [2010Beijing wc]矩阵距离
将1加入队列，然后随便搜…#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;queue<int> qx;queue<int> qy;int read(){ char ch=getchar();int f=0;
2017-10-23 11:02:54
394
原创 bzoj1054: [HAOI2008]移动玩具
就是把矩阵当成二进制数判断是否访问过，然后就能AC了。。。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;struct data{ int a[5][5]; int step; int num;};
2017-10-23 09:19:55
189
原创 bzoj3109: [cqoi2013]新数独
就是耿直的搜索然后就rank最后一名了…#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0; while(ch<'0'||ch>'9') ch=getchar();
2017-10-22 21:55:41
378
原创 bzoj3685: 普通van Emde Boas树
明明就是线段树模板题，就是插入时如果不存在就不插入…#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0; while(ch<'0'||ch>'9') ch=getchar
2017-10-21 13:05:03
295
原创 bzoj4390: [Usaco2015 dec]Max Flow
虽然知道差分能做，还是练了一波链剖模板。（其实是noip要到了QAQ）#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0; while(ch<'0'||ch>'9') c
2017-10-17 22:20:25
266
1
转载 【模板】后缀数组
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<ctime>using namespace std;#define N 2000006int sa1[N],sa2[N],rk1[N],rk2[N],v[N];int *sa,*SA,*rk,*RK;bool ac=0;cha
2017-10-16 16:15:42
212
原创 Codeforces Round #440 (Div. 1) B. Something with XOR Query
题目大意给一个排列p和每个数对应的位置b，你可以询问2n次，每次两个数i,j,返回p[i]^b[j],求最后如果询问n^2次都不能确定的排列个数。题解询问所有0,i和i,0,之后就能得知所有数的两两异或(a[i][j]=a[i][0] ^ a[0][j] ^a[0][0]),然后就枚举第一个数是什么，暴力计算即可。#include<iostream>#include<cstdio>#includ
2017-10-16 07:49:29
442
1
原创 Codeforces Round #440 (Div. 1) A. Maximum splitting
题目大意将一个数分解成若干合数的和，问最多分解成多少个。题解贪心用4,6,9来组合，%4=1需要一个9，%4=2需要一个6，%4=3需要一个6一个9，剩下都用4.#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=
2017-10-16 07:20:32
198
原创 bzoj1008: [HNOI2008]越狱
首先考虑由n-1转移到n，然后就会发现这是一道大水题，答案是m^n-(m-1)^(n-1)*m。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0; while(ch<'
2017-10-14 09:20:48
213
原创 bzoj4839: [Neerc2016]Abbreviation
细节写死我QAQ，全场最长。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0; while(ch<'0'||ch>'9')ch=getchar(); while
2017-10-09 16:06:34
291
原创 bzoj1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚
将时间视为一个点，相邻两点连长度0的边，将每个牛连u到v+1的边，spfa即可。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;queue<int> q;int read(){ char ch=getchar();i
2017-10-09 10:27:51
440
1
原创 bzoj1691: [Usaco2007 Dec]挑剔的美食家
按价格讲草和牛排序，维护一个以美味度为关键字的平衡树，不断枚举牧草，插入比牧草价值低的牛，之后用平衡树选择前驱并删除。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int read(){ char ch=getchar();int f=0;
2017-10-08 22:30:40
208
原创 bzoj2229: [Zjoi2011]最小割
听说只有n-1种最小割，于是可以计算一棵最小割树（并不知道怎么证QwQ）,不需要真的写出一棵树，只要 不断分治求最小割在ans数组更新答案即可。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;queue<int> q;int
2017-09-25 10:05:05
208
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人