POJ

Question POJ3667 Hotel 旅店有 \(n\) 间连续的房间，操作有两种 D 入住，查询数量为 \(D\) 的连续房间，并且要最靠左，若能找到，则返回这个区间的左端点并占用这些房间，找不到则返回 \(0\) X D 退房，从房间 \(X\) 开始，退出连续长度为 \(D\) 的房间 ......

Floyd判联通(传递闭包) Floyd传递闭包顾名思义就是把判最短路的代码替换成了判是否连通的代码，它可以用来判断图中两点是否连通。板子大概是这个样的： for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++ ......

Cut the Sequence Time Limit: 2000MS Memory Limit: 131072K Total Submissions: 15419 Accepted: 4735 Description Given an integer sequence { an } of leng ......

Islands and Bridges Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 15357 Accepted: 4098 Description Given a map of islands and bridges tha ......

炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 43084 Accepted: 16457 Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可 ......

Mondriaan's Dream Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 29096 Accepted: 15505 Description Squares and rectangles fascinated the f ......

Blocks Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 7889 Accepted: 3210 Description Some of you may have played a game called 'Blocks'. ......

SUBTRACT Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2677 Accepted: 1182 Special Judge Description We are given a sequence of N positiv ......

https://vjudge.csgrandeur.cn/problem/POJ-3040 /* 作为创纪录的牛奶产量的奖励，约翰决定每周给贝西一小笔零用钱。FJ拥有一组N（1 <= N <= 20）种不同面额的硬币， 其中每个面额的硬币均可整除较大面额的硬币（例如，1分硬币、5分硬币、10分硬币和 ......

Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there ......

#include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> #include <math.h> #include <map> #include <string.h> #define ll long long ......

Mr. Young's Picture Permutations Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5841 Accepted: 1860 Description Mr. Young wishes to take a ......

https://vjudge.net/problem/POJ-2393 奶牛们购买了一家酸奶厂，生产世界闻名的 "Yucky Yogurt "酸奶。在接下来的 N (1 <= N <= 10,000) 周里，牛奶和劳动力的价格每周都会波动， 因此在第 i 周生产一单位酸奶将花费公司 C_i (1 < ......

https://vjudge.net/problem/POJ-1328 假设海岸线是一条无限长的直线。陆地在海岸线的一边，海洋在另一边。每个小岛都是位于海边的一个点。 而位于海岸线上的任何雷达装置都只能覆盖 d 的距离，因此，如果两者之间的距离最多为 d，那么海中的一个小岛就可以被一个半径为 d 的 ......

https://vjudge.net/problem/POJ-2386 由于最近的降雨，水在农夫约翰的田地上聚集，在这片田地中，每个方块都被表示为一个 N x M（1 ≤ N ≤ 100；1 ≤ M ≤ 100）的矩形。 每个方块可以是水（'W'）或干地（'.'）。农夫约翰想弄清楚他的田地上形成了多 ......

https://vjudge.net/problem/POJ-3009 在 MM-21 星球上，今年的奥运会之后，冰壶运动开始流行起来。但规则与我们的有些不同。冰壶比赛是在一块冰板上进行的，冰板上标有方形网眼。 他们只使用一块石头。游戏的目的是用最少的步数将石头从起点引向终点。 图 1 显示了游戏棋 ......

题意：树的最小点覆盖，选择最少的点覆盖所有边。 分析： 状态：f[u][0/1] 表示不选/选编号u的点的最优解 转移： 不选u，则一定选u的儿子v，即 f[u][0] +=f[v][1] 选u，则可以选，也可以不选u的儿子v，即 f[u][1] += min(f[v][0], f[v][1]); ......

题意：某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀 ......

题意：给出一棵无向树，求树的直径，即树上两点之间的最长距离 分析：两种解法 解法1：先任取一个点，找到距离该点最远的点u，再找到距离u最远的点v，那么u和v之间的路径就是一条直径。 证明：只要找到了树的直径的一个端点，再从该点找到最远点就一定是直径的另一个端点。所以只需要证明第一次找到的最远点u就是 ......

不妨设 \(n, m\) 相等，常规的状压 DP 做法时间复杂度为 \(O(n * 2^n)\)，但是可以通过套用公式使复杂度变为 \(O(n^2)\)。 具体地，用 \(1*2\) 的小长方形覆盖 \(n*m\) 的棋盘的方案数为 \[\Large \prod\limits_{j = 1}^{\l ......

## [$POJ$ $1300$ $Door Man$](http://poj.org/problem?id=1300) ### 一、题目描述 你是一座大庄园的管家。庄园有很多房间，编号为$0、1、2、3$，…。你的主人是一个心不在焉的人，经常沿着走廊随意地把房间的门打开。多年来，你掌握了一个诀窍： ......

## [$POJ$ $1780$ $Code$(欧拉回路+模拟栈)](http://poj.org/problem?id=1780) ### 一、题目大意 - 1.提供密码的位数。 - 2.密码的输入可以一直保持，取后$n$位作为密码。如果密码正确则开锁。 - 3.设计一种方法使得在输入最少的情况下 ......

## [$POJ$ $1392$-$Ouroboros$ $Snake$](http://poj.org/problem?id=1392) // 这道题和上面那道题几乎一样, 算是变形题把, 这道题要求构造的01字符串就是必须是字典序最小的, // 在上面那道题的注意下建边的顺序即可. 因为是链式前 ......

## [$POJ$ $2513$ $Colored$ $Sticks$](http://poj.org/problem?id=2513) ### 一、题目描述 一堆木棍左右两端涂有颜色,相同颜色的可以连接在一起，问所有木棍能否都连上 ### 二、解题代码 ```cpp {.line-numbers} ......

## [$POJ$ $2230$ $Watchcow$](http://poj.org/problem?id=2230) ### 一、大致题意： 有一个人每晚要检查牛场，牛场内有m条路，他担心会有遗漏，就每条路检查两次，且每次的方向不同，要求你打印他行走的路径（必须从1开始），打印一条即可。 ![] ......

##[$POJ$ $2337$ $Catenyms$](http://poj.org/problem?id=2337) 给出$n$个单词，求出最小字典序的头尾连接方案。 **有向图欧拉路径** 板子题。 把每个单词当做边，头字母和尾字母当做节点，建完跑 **有向图欧拉路径** 即可。 ```cpp ......

## [$POJ$ $1041$ $John's$ $trip$](http://poj.org/problem?id=1041) ### 一、题目大意 多组数据，输入$x，y，z$，表示结点$x$和结点$y$之间有一条序号为$z$的边，如果这个 **无向图** 中存在欧拉回路，就 **输出字典序最 ......

##[$POJ$ $3020$ $Antenna$ $Placement$](http://poj.org/problem?id=3020) ### 一、题目描述 *--代表城市，o--代表空地 给城市安装无线网，一个无线网最多可以覆盖两座城市，问覆盖所有城市最少要用多少无线。 **公式：最小路径覆 ......

## [$POJ3216$ $Repairing$ $Company$](http://poj.org/problem?id=3216) ### 一、题目描述 有$n$个维修站，给出了一个邻接矩阵(对称阵)表示每个维修站到其他维修站的花费的时间，$-1$表示不可达，然后给出了$m$个任务，给出了每个 ......

# H - Collecting Bugs POJ-2096 期望 dp ## 题意 根据题意可以将原题意转换成： 有个 $n * s$ 的矩阵，每次会随机选取一个格子填上颜色，问每行每列都填上颜色的期望次数。 ## 思路 dp，显然是期望 dp，那么设 $dp_{i,j}$ 为已经有 $i$ 行 ......