50/50

update:16.07.08

3713: [PA2014]Iloczyn

双指针查找

3715: [PA2014]Lustra

每个维排序找出所有点的范围

3721: PA2014 Final Bazarek

分类讨论，先取所有正数然后若和为偶数则用正奇数换负偶数或正偶数换负奇数

4292: [PA2015]Równanie

枚举 $f(n)$ 看 n 是否符合条件

4589: Hard Nim

FWT 裸题

1106: [POI2007]立方体大作战tet

直接从下到上扫一遍模拟交换即可

1131: [POI2008]Sta

找重心

1123: [POI2008]BLO

找割点，求出和割点相邻的联通块的个数

1116: [POI2008]CLO

联通块是树的话就不可以

1121: [POI2008]激光发射器SZK

水题

1112: [POI2008]砖块Klo

不断移动区间，然后维护主席树

1529: [POI2005]ska Piggy banks

缩点完看入度为 0 的点的数量

3524: [Poi2014]Couriers

主席树

1115: [POI2009]石子游戏Kam

阶梯 Nim，可知阶梯最低的是 $K_n-K_{n-1}$，只能减不能加

1098: [POI2007]办公楼biu

求反图联通块

我们可以先把全部没被确定的数扔到堆 A，每次调一个出来新建联通块并扔进堆 B，每次从 B 找出一个点通过边打标记，然后查找 A 里面的数是否有连边，有的话加入 B，用完就扔掉

2096: [Poi2010]Pilots

两个单调栈维护区间最小最大值

1113: [Poi2008]海报PLA

每次选用最小高度的海报，全部覆盖，然后分成多段递归处理（或者直接扫一遍用单调栈求

1101: [POI2007]Zap

随便莫比乌斯反演

2084: [Poi2010]Antisymmetry

回文树

2088: [Poi2010]Teleportation

所有点按和S或T相连分成两类，设为 A,B，再从剩余的点按和A或B相连的分成两类，最后分类讨论

2093: [Poi2010]Frog

首先用游标求出每个点下一次跳跃的点，然后倍增

3427: Poi2013 Bytecomputer

设 $f(x,o)$ 表示前 x 个格子以 o 结尾的最小代价

2089: [Poi2010]Monotonicity & 2090: [Poi2010]Monotonicity 2

两个单调栈

3523: [Poi2014]Bricks

每次优先用个数多的，有多个则结尾的优先，然后加一堆特判

1133: [POI2009]Kon

DP，计算漏掉了多少

4378: [POI2015]Logistyka

对于一段区间，求出大于等于s的个数，这些是能每次都选上的，剩余的选择则交给正数但是小于s的格子，用修改主席树维护即可

2085: [Poi2010]Hamsters

倍增大法好，求出从某个串到另一个串的最小代价

2072: [POI2004]MOS

两种运输方式：(Min+Max,Min)(Min+SeMin,Min,Max+SeMax,SeMin)，接着 dp

2797: [Poi2012]Squarks

弄个集合维护已知数的两两乘积，先从最小的推出 a1，删掉集合新增的 a1*a1，从最小推出 a2，删掉集合新增的……以此类推求出所有数

1524: [POI2006]Pal

★搞个 Trie 然后遍历一边，每个点维护其最近且为结束结点的祖先，然后 Hash 暴力判断是否回文

3521: [Poi2014]Salad Bar

★我们考虑前缀和，很容易观察出 $[l,r]$ 满足题中的条件当且仅当 $a[l-1]$ 是 $Min(a[l...r])$，而 $a[r]$ 是 $Max(a[l...r])$

然后用单调栈求出 $l[i],r[i]$，分别表示 $a[i]$ 作为最大值最远拓展到 $l[i]$，作为最小值最远拓展到$r[i]$

然后枚举区间左端点，查询 $i-r[i]$ 之间 $l[x]<=i$ 的，就线段树

1526: [POI2005]ban- Bankomat

对于每种移动顺序弄序列自动机，枚举可能的情况，判断对于当前移动顺序合不合法

3829: [Poi2014]FarmCraft

统计每个子树最少需要额外时间

2790: [Poi2012]Distance

枚举约数更新，对于每个数维护最小值和次小值（因为要求 i!=j

2073: [POI2004]PRZ

状压

2081: [Poi2010]Beads

枚举 k 然后 Hash 判断，由调和级数可得复杂度为 $O(nlogn)$

2796: [Poi2012]Fibonacci Representation

搜索+部分记忆化

3060: [Poi2012]Tour de Byteotia

先连大于 K 的边，无论成不成环；然后剩余的能连多少连多少，只要连完不成环

2213: [Poi2011]Difference

枚举出现次数最多的字母，扫一遍，对于非当前字母则维护前缀和&其最小值，对于当前字母则统计答案

注意：一段区间内出现次数最低的字母必须出现，所以 min 的维护要延迟更新，于是多开个数组

3834: [Poi2014]Solar Panels

考虑枚举 gcd，那么 $[a,b]$ 和 $[c,d]$ 两个区间内存在 $n$ 的倍数当且仅当 $floor(b/n)>floor((a-1)/n)$ 且 $floor(d/n)>floor((c-1)/n)$，然后枚举商就可以了

3831: [Poi2014]Little Bird

从后往前考虑，用单调栈来维护，相同代价的取高度较小的

2276: [Poi2011]Temperature

单调队列

2789: [Poi2012]Letters

一一对应后求逆序对

1510: [POI2006]Kra-The Disks

每个位置求序列自动机

1537: [POI2005]Aut- The Bus

二维偏序

2795: [Poi2012]A Horrible Poem

对于每个询问，枚举长度的约数然后 Hash 判定

（剪枝：求各个字母出现次数的 gcd 后再枚举约数

2083: [Poi2010]Intelligence test

怎么又是序列自动机

2086: [Poi2010]Blocks

全部减 k 完变成找总和非负的最长区间，顺序扫一遍得到单调栈然后枚举右端点扫一遍

1122: [POI2008]账本BBB

枚举最终的序列以哪个点开始，那么从这个点往后的最小前缀和可以用单调队列预处理出来，但是这样最后总数不一定满足要求，为此还要将最左的-1改成+1，或者将最右的+1改成-1，可以 $O(n)$ 求得