POJ训练计划

3299:公式转换题,需要读题,不能只看样例

2159:判断同构,按频率排序

1083:区间加+单点最值

2739:预处理素数表+尺取法

2262:暴力

1503:高精度加法

3006:暴力

2255:dfs的过程中把两个序列中同一个子树给对应上就好了

3094:模拟


初期

基本算法

1753:暴力

2965:发现如果’+’位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一’+’位置的符号改变,其余都不会改变.

https://xuanwo.org/2014/07/23/POJ-2965-The-Pilots-Brothers-refrigerator/

1328:贪心策略依然是从左往右,尽量让每颗雷达覆盖最大岛屿数。

将每个海岛转化为能覆盖它的雷达坐标的区间

2109:http://blog.csdn.net/code_pang/article/details/8263971

3295:模拟 求值

1068:模拟

2632:模拟= = RE一时爽

1573:模拟

2993:模拟 不太好写= =

2996:翘了 似乎是模拟就好= =

图算法

1860:判有没有负环

3259:判负环 注意边是单向还是双向 好久没写多case的了= =这么生疏

1062:枚举地位建图跑最短路

2253:求最短路上的最大边最小

可以二分答案+并查集

POJ上边不知道为啥有时候G++交是WA而C++交是AC 然后有的时候还反过来= =

还可以改一改最短路= =

注意别把double的变量在传参之类的时候一不小心当int用了酿成惨案

1125:Floyd

2240:spfa找正环 或者直接Floyd看

多case的题调不出来的时候一定要想一想是不是哪里忘记初始化了

1789:prim

2485:prim

1258:prim

3026:prim 写起来挺麻烦的 坐标反的 = =

1094:处理字符别忘记了换行符 可以处理出来元素之间的大小关系 然后就很方便了

3041:把原图的点和边互换构图 然后之前是这样找尽量少的行列覆盖点

现在是找尽量少的点覆盖行列 就是最小点覆盖了 然后发现这个点只与一行一列相关 所以新图是一个二分图 二分图的最小点覆盖数值上等于二分图最大匹配 想了很久还是不是很懂匈牙利的实现里面的一处trick 于是写了dinic跑最大流= =

3020:把每个可以放置的点作为新点 如果两个点在原图相邻那么就可以放 所以连一条边 求的就是最小路径覆盖 拆点构图 得到的是二分图

3436:点有流量限制就拆点就好了

数据结构

1035:模拟就好了 很久没写题代码能力捉急= =

3080:后缀数组最长公共子串 注意要求的是字典序最小的 二分答案从前往后找就行了

调了好久发现对后缀数组的理解还是不到位= =

1936:判断s是否是t的子序列 遍历t 同时维护s的一个指针就行了

2388:排序后输出位于中间的就行了

2299:求逆序对 归并就行

3349:hash判重就行 把每个雪花的六个角排序一下= =

3274:给出牛的个数n和总共特征个数k,求最长的区间,使得区间内所有牛的k个特征相加之和都相等。
比如样例区间 每个牛内部差分再对序列求前缀和 问题就转化成在前缀和序列中找相等的两个元素

注意一定要先差分的才能将问题转化

sum[j][0] - sum[i][0] = sum[j][1] - sum[i][1] = …… = sum[j][k] - sum[i][k]
变成

1
2
3
4
sum[i][1] - sum[i][0] = sum[j][1] - sum[j][0]
sum[i][2] - sum[i][0] = sum[j][2] - sum[j][0]
……
sum[i][k] - sum[i][0] = sum[j][k] - sum[j][0]

2151:概率dp

dp[i][j][k]表示第i个队在前j道题中解出k道的概率

dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]); //这两种来源,第j道做出来或者没做出来+前j-1道做k-1或者k道题概率

s[i][k]表示第i队做出的题小于等于k的概率
s[i][k]=dp[i][M][0]+dp[i][M][1]+...+dp[i][M][k];

每个队至少做出一道题概率为P1=(1-s[1][0])*(1-s[2][0])*...(1-s[T][0]);

每个队做出的题数都在1~N-1的概率为P2=(s[1][N-1]-s[1][0])*(s[2][N-1]-s[2][0])*...(s[T][N-1]-s[T][0]);

最后的答案就是P1-P2,代表至少一个队作出n到以上(1 - 所有队作出0...n-1的概率)

1840:判断方程是否有根 先枚举前两项可能的值再枚举后三个的值看看是否有和为0就行 hash姿势不对会mle 直接用map会tle = = 而且poj还没有unordered_map

2002:问平面上一堆点能组成多少个正方形,正方形的边允许不和坐标轴平行。方法是枚举一条边上的两个点,因为是正方形,此时就可以算出另外两个点,只需要二分一下看看是否存在就好了。注意每个正方形会被计算两次。

2503:应该是想要考哈希+二分,但是map一下就好了。值得一提的是gets会接受空行

3253:求哈夫曼树,priority_queue一波

2513:把字符串映射到点,再判断是否有欧拉通路。因为是无向图,只需要统计顶点度数为奇数的数和判断全图是否联通。至于如何映射字符串到点,用map会多个log超时,选用trie。好久没写并查集忘记了初始化竟然看了好久才发现。

简单搜索

2488:爆搜即可,注意字典序的要求,字母用来表示列,就是说要列优先最小,再行最小。具体体现在dx, dy数组的设置上。

1
2
const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};

3083:bfs很好写,难点在于如何按照左(右)手边靠墙走,核心仍然在于方向数组

1
2
3
4
5
6
7
8
9
10
const int dxl[] = {-1, 0, 1, 0};
const int dyl[] = {0, 1, 0, -1};
const int dxr[] = {-1, 0, 1, 0};
const int dyr[] = {0, -1, 0, 1};
// 然后dfs枚举方向的时候:
f(i, 0, 4) {
t = (i + op + 3) % 4;
nx = x + dx[t]; ny = y + dy[t];
}
// op用来表示方向

发现dxl实际上是从12点方向顺时针转,drl是逆时针转,从而刚好对应位置-1就是要找的方向,取模之后相当于是+3

3009:看起来很吓人但是实际上不难处理,把之前的dfs每次选一步走改成每次选一个方向走就好了。

1321:给一个不规则棋盘问放k个子的方案数,dfs枚举方案。值得注意的是允许当前位置不放子,所以还要记录横竖的vis数组。

2251:三维的地图,bfs或者dfs都可以

3278:bfs思路很好想,但是几年前简直是又wa又t一时爽。注意写法可能会忽略掉n==k的情况。用pair放到queue里写会很慢,不妨把时间戳放到外面开个数组单独记录。

1426:直接爆搜就过了 感觉会有更优美的写法

3126:实际上就是处理出来质数然后bfs就好了,然而筛法写错的我= =

3087:模拟就好了,写法是dfs而已

3414:著名的倒水问题,bfs。注意数组大小

2531:dfs把这堆东西分成两组

1416:找数字的分割方式使得各部分的和与x最近,好像应该dp不过dfs就过了。

2676:计算概论实验班选拔考试考了就懒得再写了= =

1129:给点染色的最小色数

动态规划

1837:dp[i][c[k] * d[i] + j] += dp[i - 1][j]; 第二维是两侧重量差(体积)。因为有负的所以平移一波。

1276:01背包和多重背包的混合。考虑每一个多重背包,如果num[i] * c[i]大于体积,那么可以对这个物体看作是完全背包,否则拆成log个,然后当成01背包来做

3267:给一堆词,问一个字符串最少删掉多少字符后可以由这些单词中的某几个(可重复)顺序连接而成。

dp[i] = min(dp[i + 1] + 1, dp[i + match] + (match - len[j])) 其中 match 表示从当前位置开始需要延伸 match 长度来包含 len[j] ,这样 match - len[j] 就是需要删掉的那部分了 dp[i]的含义是从第 i 个位置开始的答案

1836:给一个序列,问最少要删掉多少个,使得每一个元素都有一个性质:向左向右看不会有>=自己的元素。方法是求两个方向的 LIS,然后求前缀和后缀 max。最后 res = max(l[i] + r[i + 1]) 。注意从 discuss 拿到的这组数据: 8 3 4 5 1 2 5 4 3 答案是 2。换言之允许中间一段是相等的,解决办法可以对l[i]求前缀max,r[i]求后缀max,再去求res

1260:给出每种品质的价格和需求,每多买一种品质需要多加钱,低品质可以用高品质代替。问最少花多少钱。 dp[i] 表示 前 i 种品质最少要花多少钱,转移的时候要么自己买,要么枚举一段相邻的品质用当前品质的价格来买。为什么是连续的呢?因为保证了价格递增,如果不是连续的,那么分成两段可以更便宜。