5 ws_fqk

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

NOI2016滚粗记

Day-1由于飞机是明天一早,所以今天就要先去济南了。下午2:00出发,与之前不同的是这次是商务车直达。路上老师检查了一下笔试,似乎没什么问题。傍晚就到了,老师们请客一起吃饭,然而在机场旁太偏了并没什么好吃的东西。 晚上没什么事情,玩了玩手机,跟yzy说了一些linux相关的东西。老师贴心的送来了明天早晨的早餐:2包好吃点(一脸不可吃)+1灌八宝粥+1包香肠。就早睡了。 6:15起床,我就喝了半

2016-07-29 22:32:42

PKUSC2016酱油记

无聊报上了pkusc结果居然过了初审,于是滚粗狗就又续命几天。 据说今年thusc比pkusc容易过然而我thusc没过pkusc过了是smgDay -?退役了报了D,虽然希望渺茫,但还是在机房里等着。期间跟随yzy大爷报了pkusc。然后yzy要去胜利一中参加省队集训,听说有不少退役选手也要去于是我也去旅游了。在胜利一中感觉生活不错,晚上偶尔浪浪,被叫去打狼人结果打完了还没搞懂游戏规则,和省实验

2016-06-05 22:44:15

3716: [PA2014]Muzeum 计算几何+贪心+set

刷空PA2014的CA凉果然劲啊。。这题好难。。 第一步是用计算几何的知识进行坐标变换,然后是一个最大权闭合图的模型。 由于图的特殊性可以贪心来解决。 具体参考CA的题解#include<iostream>#include<cstdio>#include<set>#include<algorithm>using namespace std;const int N=400005;int

2016-05-22 15:28:52

3712: [PA2014]Fiolki LCA 思路题

非常神的一道题。。orzzzzz 做法: 我们用一个节点代表一个瓶子,合并的时候新建一个节点,代表合并出来的瓶子,并且向原来的两个点连边。可以发现,反应的话,其实就是两个瓶子代表节点的LCA。 然后按照LCA的深度以及时间戳排序,算答案就好了。#include<iostream>#include<cstdio>#include<algorithm>using namespace std;

2016-05-22 15:26:16

3718: [PA2014]Parking 树状数组

%CA凉 代码风格药丸#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=50005;int n,m;int tree[N],pos[N];inline int read(){ int a=0,f=1; char c=getcha

2016-05-22 15:22:16

2626: JZPFAR K-D tree

裸题,用堆维护一下。#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;const int N=100005;const int INF=1000000007;int n,D,root;int ls[N],rs[N];struct node{ int d

2016-05-21 23:45:13

4565: [Haoi2016]字符合并 区间DP

令fi,j,kf_{i,j,k}表示区间[i,j][i,j]合并成kk的最大收益,其中K=0/1K=0/1保证[i,j][i,j]可以合并成一个数。 转移的时候用gj,kg_{j,k}表示对于当前的ii,[i,j][i,j]合并成了kk,其中kk是一个二进制数。 然后转移一下就行了#include<iostream>#include<cstdio>#include<cstring>usin

2016-05-21 23:43:45

4566: [Haoi2016]找相同字符 广义后缀自动机

建立广义后缀自动机,维护两个串的sizesize 那么答案等于∑(leni−lenfai)×size0×size1\sum (len_i-len_{fa_i})\times size_0 \times size_1#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=200005;

2016-05-21 23:40:55

2893: 征服王 tarjan+最小流

首先tarjan缩点,然后裸的最小流。 好像是个挺麻烦的费用流。。然而我写的最小流居然跑到了rank1。。#include<iostream>#include<cstdio>#include<queue>#include<cstring>#include<vector>using namespace std;const int N=1100;const int M=50005;con

2016-05-21 23:35:12

3180: [Coci2012]ograda 贪心

可以发现答案只与拐点有关,所以贪心就行了,最后把中间的点放进去。#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N=300005;int n;int num[N],ss[N],ans[N];inline int read(){ int a=0,f=1; char

2016-05-21 23:29:25

3463: [COCI2012] Inspector 分块+凸壳

可以发现答案一定在下凸壳上,我们考虑分块,然后如果有修改操作在块上打标记,查询的时候暴力重构。 由于TT是单调的,所以维护一个队列,弹出队头元素直到到了TT所在的直线就好了。#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N=100005;c

2016-05-21 23:27:47

3181: [Coci2012]BROJ 找规律

我们根据PP的大小来分类,当PP比较大的时候,10910^9范围内PP的倍数会比较少,暴力枚举就可以。 PP比较小的时候,我们来找循环节。 令C=∏pi<=PpiC=\prod_{p_i<=P}p_i,假设ii合法,则i+Ci+C也合法。 证明: 若C+iC+i不合法, 则存在质因子p<Pp<P且p∣C+ip\mid C+i,因为p∣Cp\mid C,所以p∣ip\mid i,矛盾。 所以

2016-05-21 23:24:37

3176: [Coci 2012]Sort 树状数组

可以发现第一次reverse后,只会存在一些长度为2的递减序列,其实就是逆序对的数量了。#include<iostream>#include<cstdio>using namespace std;int n,a[100005],tree[100005];long long ans;inline int read(){ int a=0,f=1; char c=getchar();

2016-05-21 23:14:54

2275: [Coci2010]HRPA 打表/齐肯多夫定理

博弈什么的真是弱啊。。虽然这题根本用不到博弈的知识。。但看着这类问题就懵逼。 记得sxb是打表找规律过的。。 题解是一个叫做齐肯多夫定理的东西。。可以百度一下qwq#include<iostream>#include<cstdio>using namespace std;long long n;int cnt;long long f[100];int main(){ scanf

2016-05-21 23:11:43

3881: [Coci2015]Divljak fail树+树链的并

我们对SS集建立AC自动机,用TT集中的串算答案。 可以发现在AC自动机上运行串时,所经过的节点和沿这个节点的fail指针向上经过的所有节点代表的串都在TT中出现过。所以要求的就是一些树链的并集。 我们把这些点拿出来按照fail树的dfs序排序,用树状数组维护dfs序的前缀和,把每个点处+1,把两两lca处-1,询问就变成询问子树了。#include<iostream>#include<cst

2016-05-21 23:07:17

3188: [Coci 2011]Upit splay

splay,对于区间加等差数列的操作,我们可以发现等差数列的首项和公差是可以分开考虑并且可叠加的。那么就打标记就好了。#include<iostream>#include<cstdio>using namespace std;const int N=200005;int n,Q,t1,t2,tot,root;int fa[N],tree[N][2];long long size[N],su

2016-05-21 22:54:56

3743: [Coci2015]Kamp BFS

首先我们可以搞出这KK个点的一棵生成树,记这棵生成树的边权和为sumsum。 假设每次都要返回出发点xx,那么这里分两种情况讨论: 如果xx是KK个点中的某个点,那么答案为2×sum2\times sum 否则,答案为2×sum+mindis(x,tree)2\times sum+mindis(x,tree) 那么如果不需要返回的话,答案在以上基础上上要减去maxdis(x,i)(i bel

2016-05-21 22:52:19

3810: [Coci2015]Stanovi 记忆化搜索

首先观察性质:对于一个合法的方案,总能将矩形分成两部分。 否则总会有四面均不接触边界的矩形。 那么我们用fn,m,u,d,l,rf_{n,m,u,d,l,r}表示n×mn\times m的矩形,四个边界是否存在(0/1)(0/1)然后记忆化搜索#include<iostream>#include<cstdio>#include<cstring>using namespace std;con

2016-05-21 22:45:52

4571: [Scoi2016]美味 主席树+贪心

建立主席树,然后从高位到低位贪心就好了。#include<iostream>#include<cstdio>using namespace std;const int MAXN=100000;const int N=200005;const int M=5000005;int n,m,size;int root[N];int ls[M],rs[M],sum[M];inline int

2016-05-21 22:41:44

3727: PA2014 Final Zadanie 乱搞

很神的一道题。参考PoPoQQQ的题解: 首先转化为以11为根的有根树,sizeisize_i表示以ii为根的子树的aia_i的和。 那么有 b1=∑ai×disib_1=\sum a_i\times dis_i bi=bfai−sizei+(size1−sizei)b_i=b_{fa_i}-size_i+(size_1-size_i) 并且有ai=sizei−∑sizesonia_i=s

2016-05-21 22:36:32

查看更多

勋章 我的勋章
    暂无奖章