Dispwnl

Crazy Up

[JSOI2008]火星人

题目题目描述火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，火星人定义了一个函数$LCQ(x,y)$，表示：该字符串中第$x$个字符开始的字串，与该字符串中第$y$个字符开始...

Posted by Dispwnl on May 7, 2018

[NOI2012]魔幻棋盘

题目题目描述将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 N行M列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 X 行第 Y列（行与列均从 1 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：（a）询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。（b）修改：他会随意挑选棋盘...

Posted by Dispwnl on April 19, 2018

[NOI2007]货币兑换

题目题目描述小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A 券和 B 券的价值分别为$A_K$和$B_K$（元/单位金券...

Posted by Dispwnl on April 19, 2018

[Violet 3]天使玩偶

题目题目描述 Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 (x,y) ，那么她离近的天使玩偶可能埋下的地方有多远。...

Posted by Dispwnl on April 17, 2018

[LUOGU1263]宫廷守卫

题目题目描述从前有一个王国，这个王国的城堡是一个矩形，被分为M×N个方格。一些方格是墙，而另一些是空地。这个王国的国王在城堡里设了一些陷阱，每个陷阱占据一块空地。一天，国王决定在城堡里布置守卫，他希望安排尽量多的守卫。守卫们都是经过严格训练的，所以一旦他们发现同行或同列中有人的话，他们立即向那人射击。因此，国王希望能够合理地布置守卫，使他们互相之间不能看见，这样他们就不可能互相射击了...

Posted by Dispwnl on April 14, 2018

[NOI2012]美食节

题目题目描述 CZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发...

Posted by Dispwnl on April 14, 2018

[JSOI2010]冷冻波

题目题目描述 WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖，每个巫妖释放Froze...

Posted by Dispwnl on April 12, 2018

2018SD省选题解

Day1 一双木棋由于$n,m\le 10$，可以考虑状态压缩又因为某个点能放的前提是左边和上边都有棋子所以表示轮廓线 $0$表示横边界，$1$表示竖边界那么$3\times 3$棋盘（其他一样）初始状态就是$000111$，边界条件是$111000$ 这样就可以每次根据轮廓线走，有拐角的时候就可以放棋子设$w$表示轮廓线，从$0\rightarrow n+m-2$用$...

Posted by "Dispwnl" on April 9, 2018

省选滚粗记

省选了啊啊啊滚粗了啊啊啊 AFO了啊啊啊慢着这不是喜闻乐见吗 $Day-1$ 明天就省选了……我竟然没什么压力大概是因为什么都不会学长们说高一进队几率接近于$0$ 进队是不可能的，这辈子都不可能的上午啥也看不进去，下午A了几道水题像我这样的只能看开点了整个机房弥漫着一股颓气……似乎大家都准备好赴死了结果发现似乎就我去赴死想当初我们刚来到这里的时...

Posted by Dispwnl on April 4, 2018

静态主席树略解

感谢$Refun$大爷的耐心讲解Orz 首先主席树维护的是什么东西呢？我们在每个节点都建一棵线段树，$i$节点的线段树维护的是$1$到$i$这段区间的值域里的每个数的出现次数（有点像前缀和的样子）既然要搞值域，我们把给定的序列离散化一下举个栗子：给定序列：1 5 4 7 2 3 3 排序后去重就是：1 2 3 4 5 7 重新编号：1 2 3 4 5 6 首先是节...

Posted by Dispwnl on April 3, 2018