POJ
poj2750(线段树+复杂区间合并)
Potted Flower POJ - 2750 思路:我们将题目简单化,假设我们要求的是序列的最大连续子段和,且可以包括所有数。 我们的线段树需要维护这段区间的最大前缀和pre,最大后缀和suf,区间和sum,区间连续最大和mx。 那么难点就在于如何由子节点更新父节点。 我们可以知道,tr[p]. ......
kuangbin专题一 简单搜索 洗牌(POJ-3087)
#Shuffle'm Up Time Limit: 1000MS Memory Limit: 65536K ####Description A common pastime for poker players at a poker table is to shuffle stacks of chip ......
kuangbin专题一 简单搜索 质数路径(POJ-3126)
#Prime Path Time Limit: 1000MS Memory Limit: 65536K ####Description The ministers of the cabinet were quite upset by the message from the Chief of Sec ......
kuangbin专题一 简单搜索 找倍数(POJ-1426)
#Find The Multiple Time Limit: 1000MS Memory Limit: 10000K ####Description Given a positive integer n, write a program to find out a nonzero multiple ......
poj2777(线段树)
Count Color POJ - 2777 思路:暴力能过,线段树维护这个区间的颜色,如果是混色则置为1,如果是单一颜色则设为这个颜色,修改就是正常的区间修改,区间查询就要变一下。还有题解是用二进制做得,可以学一下。 #define _CRT_SECURE_NO_WARNINGS 1 #inclu ......
kuangbin专题一 简单搜索 翻转(POJ-3279)
#Fliptile Time Limit: 2000MS Memory Limit: 65536K ####Description Farmer John knows that an intellectually satisfied cow is a happy cow who will give ......
poj 2182
Lost Cows POJ - 2182 与这题一样Buy Tickets - POJ 2828 - Virtual Judge (csgrandeur.cn) 题意:有1~N N个数字,这N个数字的顺序是打乱的,从第二个数字开始给你它的前面有多少个数字比他小 思路: 输入的数字都要加一,然后我们从 ......
kuangbin专题一 简单搜索 抓住那头牛(POJ-3278)
#Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 210291 Accepted: 63838 ####Description Farmer John has been informed of the ......
kuangbin专题一 简单搜索 地牢大师(POJ-2251)
#Dungeon Master Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 92499 Accepted: 31990 ####Description You are trapped in a 3D dungeon and n ......
kuangbin专题一 简单搜索 棋盘问题(POJ-1321)
#棋盘问题 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 125427 Accepted: 56304 ####Description 在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋 ......
poj 3090 Visible Lattice Points
#include<iostream> #include<algorithm> using namespace std; const int M=1e6; int vis[M+4],P[M+4],cnt; int fi[M+4]; void shai(int top){ cnt=0; fi[1]=1; ......
Mondriaan's Dream 【POJ2411】 题解
Mondriaan's Dream 【POJ2411】 题解 ——By Zy 注:原题中的 $h,w$ 在本文中使用 $n, m$ 代替。 一. 题意分析: 题目要求给定一个一定大小的 矩形 棋盘,求出使用 $1\times 2$ 大小的木条填充一共有多少种方案。 读题,发现数据范围 $(1\le ......
poj-3367(线段树+区间合并)
Hotel POJ - 3667 思路:与hdu-1540(线段树+区间合并) - 魏老6 - 博客园 (cnblogs.com)类似,只不过是区间修改,多维护一个最大连续区间sum。 #define _CRT_SECURE_NO_WARNINGS 1 #include<algorithm> #in ......
The Suspects POJ - 1611 (并查集)
题意:n个学生分属m个团体,一个学生可以属于多个团体。一个学生疑似患病则它所属的整个团体都疑似患病。已知0号学生疑似患病,以及每个团体都由哪些学生构成,求一共多少个学生疑似患病。 分析:维护一个并查集,查询与0在同一集合的元素数量。 #include <iostream> #include<cstd ......
Jungle Roads POJ - 1251 (最小生成树)
题意:有一个旅游区,旅游区有很多的景点,景点间需要开通缆车,使得任意两个景点可以互相到达。现在给出一些点间的缆车线路制造成本,两个景点之间可能有多重制造方式。问最少的花费是多少。 分析:连通+最少的花费 = 最小生成树。 Prim算法适用于稠密图, Kruskal适用于稀疏图 好家伙,两个 runt ......
Networking POJ - 1287 (最小生成树)
题意:存在许多点和点与点之间的路径,路径长度不一,点到点之间可能存在多条路径。挑选部分路径使得所有点连通且总路径长度最小。 分析:连通+路径长度最小 = 最小生成树。 Prim算法适用于稠密图, Kruskal适用于稀疏图 #include <algorithm> #include <cstdio> ......
Agri-Net POJ - 1258 (最小生成树)
题意:有n个农场,已知这n个农场都互相相通,有一定的距离,现在每个农场需要装光纤,问怎么安装光纤能将所有农场都连通起来,并且要使光纤距离最小,输出安装光纤的总距离。任意两个村庄之间的距离小于 100,000. 分析:连通+距离最小 = 最小生成树 Prim算法适用于稠密图, Kruskal适用于稀疏 ......
POJ--3187 Backward Digit Sums(暴搜/减枝)
记录 5:30 2023-3-25 http://poj.org/problem?id=3178 reference:《挑战程序设计竞赛(第2版)》第二章练习题索引 p135 Description FJ and his cows enjoy playing a mental game. They ......
POJ3415 Common Substrings 后缀数组 + 单调栈
传送门 题目大意: ** 给出两个字符串S和T,求出两个字符串之间有多少长度大于K的公共子区间。** ** 由于每一个子串都是包含在某一个后缀的前缀里面,求出sa和height了之后,我们可以将height进行分组,height < k为分割线,这样一来每个组内都是height >= k的后缀。我们 ......