poj - IMMEDIATE DECODABILITY Trie树模板
题解
本题为Trie（字典树）的模板题。
我们先来说一下Trie的基本构造：
Trie树，又名字典树，故名思义，将字符串各个字符以类似字典的方式构造成一棵树，以便检索。
Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。
字典树的根节点是我们检索字符串的起始，我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符，就顺延着当前这个字符所代表的边走向下一个节点。
有些节点会打一个flag标记，这代表着Trie树中一个单词的结束。
以上是Trie树的基本构造。
对于这个题目，它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。
所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。
所以题意在我们的思路中，就变为了：
在建Trie树的过程中，如果当前访问的节点打上了flag标记（一个单词的结尾）并且访问次数大于了1，则说明出现一个单词为其它单词的前缀。就输出not immediately decodable，如果建完Trie都不存在这样的单词，就输出immediately decodable。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
int cnt;
bool flag;
int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
memset(pool,0,sizeof(pool));
num = 0;
root = pool[0];
pp = false;
return;
}
int sum = 0;
int main(){
init();
while(cin >> s){
int len = s.size();
if
不解释，就是KMP模板题……给出个人常用KMP模板QAQ
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s1;
string s2;
int n;
int cnt = 0;
const int maxn = 10005;
int nxt[maxn];
void KMP_pre(){
int j = -1;
nxt[0] = -1;
for(int i = 1;i < s1.size();++i){
while(j != -1 && s1[j+1] != s1[i])
j = nxt[j];
if(s1[j+1] == s1[i]){
j++;
nxt[i] = j;
}
else nxt[i] = -1;
}
return;
}
void KMP(){
int j = -1;
cnt = 0;
for(int i = 0;i < s2.size();++i){
while(j != -1 && s1[j+1] != s2[i])
j = nxt[j];
if(s1[j+1] == s2[i])j++;
if(j == s1.size()-1){
cnt++;
j = nxt[j];
}
}
return;
}
int main(){
cin >> n;
while(n--){
cin >> s1;
cin >> s2;
KMP_pre();
KMP();
cout << cnt << endl;
}
return 0;
}
UvaLive-6437 Power Plant（变种Kruskal）
题外话
还是vjudge不错233，可以不用注册新帐号了。
这是本人第一篇关于Uva题目的题解。
题目链接放上面大家自己去点，因为PDF格式真的是粘不过来。
题目大意
现在有n个城市，城市之间有m个预期修筑电缆的方案线，其中有k个城市有发电站。
现在要求建设电线，使得每个城市都能有供电。由于每条线路有一定的花费，所以现在要求满足题目的最小花费。
题解
其实题目里已经简化成一个图了，剩下的就是自己想该怎么解决了。
其实思考一下，这好像跟用最小代价选边使得图连通的问题非常接近，第一感觉就是个最小生成树啊，直接kruskal或者Prim就行了啊。
但是回过头来想想，好像有那么一点不对劲的地方。
你看那个样例演示图，明明是不连通的啊。
这是因为本身就有发电站的城市不一定要跟外部连通。所以这题就不是一个纯粹的最小生成树了。但是还是很像，所以我们选择对kruskal进行一下修改。
记录一个cnt，表示当前供上电城市的数量，并查集跟普通kruskal一样的路径压缩写法，不过要加上一个siz数组来记录这一个并查集里有多少城市。
排序也和正常的kruskal一样。
关键点来了。
如何合并并查集啊？以及cnt怎么更新啊？
由于本身就有发电站的城市不一定要和外部连通，所以我们这样：
定义当前边的两个端点的父亲（并查集find后）为x，y，分以下三种情况：
1.x，y都不是有发电站的城市：直接合并并查集，f[y] = x;siz[x] += siz[y]；ans（总花费） += dis。
2.x，y都是有发电站的城市：直接跳过，不需要这条边，也不计入答案。
3.x为有发电站的城市，y则是没有发电站的城市：将y所在的并查集合入x所在的并查集内，维持x在并查集的根节点的位置，并更新当前已经有供电的城市数cnt。
f[y] = x;siz[x] += siz[y];ans += dis;cnt += siz[y];
cnt的初值就是赋为k，表示一开始共有k个城市有供电。
这样这个问题就很轻松的解决了。
为什么不选择Prim？因为Prim没有像Kruskal这样顺手的并查集啊QAQ。（好吧实际上是我Kruskal打习惯了）
参考代码
#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = f
题目大意
给出矩形的左下端点和右上端点的坐标，求所有的矩形的面积的并。
题解
求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。
扫描线，顾名思义，就是一条上下扫描或者左右扫描的虚拟的自主创造的线。
在扫描线扫描到一条线段的时候，就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。
在矩形面积的并这一个问题中，我们可以这样去把要计算的总的面积分为这样几个部分来看：
（图来自于别人的博客，实在是不想自己画图了QAQ）
我们可以看到，这个图就是按照扫描线来分区计算面积的。
我们每一次找到一条扫描线，就要维护当前在这条扫描线上（当然这里扫描线是向上扫的）所有的线段的覆盖总长（覆盖部分不再重复计算）。
然后我们用两条扫描线的高度差去乘前一条扫面先上的所有线段的覆盖总长，就是这两条扫描线与矩形围成的面积并。
对于扫描线的顺序，只需要把矩形的上下边去离散化排序以下就可以了。
于是我们剩下的任务就是维护当前扫描线上的线段覆盖总长。
由于x坐标可能会很大，我们一样要对x进行离散化，并且记录离散化后的元素对应的离散化前的元素。
然后我们可以类比前缀和的方式：
对于每一个矩形的下边，我们设这里的标记为+1，对于每一个矩形的上边，我们设这里的标记为-1
这里的标记就可以使用线段树来维护了（但是这里的标记并不需要下放，也不需要向上更新，这里的标记是用于记录这段区间线段是否被覆盖的）。
于是我们在线段树中维护两个变量，一个表示这段区间表示的线段是否被完全覆盖，另一个表示这段区间被覆盖的线段的总长。
在求被覆盖线段总长时，要分两种情况进行讨论：
1.当前区间表示的线段被完全覆盖：区间被覆盖的线段总长即为这段区间表示的线段总长。
2.当前区间表示的线段未被完全覆盖：当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。
我们是一边更新一边统计答案，统计答案只需要每次答案加上总区间被覆盖的线段总长×两条扫描线之间的高度差。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
double x1, x2, y1, y2; int id;
node(double X1 = 0, double Y1 = 0, double X2 = 0, do
题解
经典的单调队列维护。
单调队列可以在O(n)的时间内完成当前查找区间的最大值最小值的维护。
具体实现：
使用双端队列方便元素进出。元素保存的不是数而是数的位置，因为此题涉及到不在区间内的元素的删除，所以我们应该保存书的位置。
两个单调队列都要在遍历时，都要弹出当前不在查找区间内的元素。我们可以保证，如果要弹出，那么这个元素一定在队列的最开头。
第一个单调队列维护区间最小值，如果当前位置上的数比单调队列中的最后一个元素位置上的数大，则删除单调队列末尾位置的元素，一直到队列为空或者队列末尾元素位置的数比当前位置的数小，然后将当前位置编号加入队列。
第二个单调队列维护区间最大值，类比第一个单调队列。
记得循环的时候就保存答案。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e6+5;
int n,k;
int a[maxn];
dequeq1;
dequeq2;
int ans1[maxn];
int ans2[maxn];
int main(){
n = get_num();
k = get_num();
for(int i = 1;i <= n;++i){
a[i] = get_num();
}
for(int i = 1;i
题目背景
汉东省政法大学附属中学所在的光明区最近实施了名为“智慧光明”的智慧城市项目。具体到交通领域，通过“智慧光明”终端，可以看到光明区所有红绿灯此时此刻的状态。小明的学校也安装了“智慧光明”终端，小明想利用这个终端给出的信息，估算自己放学回到家的时间。
问题描述
一次放学的时候，小明已经规划好了自己回家的路线，并且能够预测经过各个路段的时间。同时，小明通过学校里安装的“智慧光明”终端，看到了出发时刻路上经过的所有红绿灯的指示状态。请帮忙计算小明此次回家所需要的时间。
输入格式
输入的第一行包含空格分隔的三个正整数 r、y、g，表示红绿灯的设置。这三个数均不超过 10^6。
输入的第二行包含一个正整数 n，表示小明总共经过的道路段数和路过的红绿灯数目。
接下来的 n 行，每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路，将会耗时 t 秒，此处 t 不超过 10^6；k=1、2、3 时，分别表示出发时刻，此处的红绿灯状态是红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 t，此处 t 分别不会超过 r、y、g。
输出格式
输出一个数字，表示此次小明放学回家所用的时间。
样例输入
30 3 30 8 0 10 1 5 0 11 2 2 0 6 0 3 3 10 0 3
样例输出
46
样例说明
小明先经过第一段路，用时 10 秒。第一盏红绿灯出发时是红灯，还剩 5 秒；小明到达路口时，这个红绿灯已经变为绿灯，不用等待直接通过。接下来经过第二段路，用时 11 秒。第二盏红绿灯出发时是黄灯，还剩两秒；小明到达路口时，这个红绿灯已经变为红灯，还剩 11 秒。接下来经过第三、第四段路，用时 9 秒。第三盏红绿灯出发时是绿灯，还剩 10 秒；小明到达路口时，这个红绿灯已经变为红灯，还剩两秒。接下来经过最后一段路，用时 3 秒。共计 10+11+11+9+2+3 = 46 秒。
评测用例规模与约定
前 6 个测试点保证 n ≤ 10^3。
所有测试点保证 n ≤ 10^5。
题解
这就是个水题……只要注意倒计时和从当前颜色灯开始亮起过的时间的区别就行了，剩下的就是一个一个的简单处理。
至于为什么写这道题……
因为我去年CSP的时候就是因为这道题崩了才没过……想想当时自己真的sb
注意开long long
代码
#include <bits/stdc++.h> using names
BZOJ 1537 POI2005 AUT-The Bus 二维偏序问题
由于格式问题，这道题的题面就不往这里放了，给一个洛谷的链接吧：
题解
这道题有中文题意，没有BZOJ权限号的可以去洛谷上搜到这道题。
首先会想到DP，但是一看这个数据范围也太大了，离散化后也没法做二维DP。
但是离散化也是要的，不然10的9次方的数据谁顶得住啊。
考虑这是一个二维偏序问题。一般的二维偏序都是找比当前物品的两个值都小的问题，而这道题并不是，这道题要做的是维护最大前缀和。
首先按照y排序并且离散化每个车站的y坐标，然后再按照x排序，使用树状数组维护最大前缀和即可（当然线段树应该也是可以的，只不过会比树状数组麻烦一点）。注意这里的树状数组不是维护的前缀和，而是维护前缀和的最大值。所以update操作和query操作里并不是求和，而是取最大值。
代码
#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
struct point{
int x,y,k;
}p[maxn];
bool cmp1(point a,point b){
return a.y < b.y;
}
bool cmp2(point a,point b){
if(a.x == b.x)return a.y < b.y;
return a.x < b.x;
}
int lowbit(int x){
return x & (-x);
}
int c[maxn];
int n,m,k,cnt;
void update(int x,int d){
while(x <=
Descrpition
Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are n cities and m bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he can rest at every city. Jack can only stand staying on the bus for a limited time and will go berserk after that. Assuming you know the time it takes to go from one city to another and that the time Jack can stand staying on a bus is x minutes, how many pairs of city (a,b) are there that Jack can travel from city a to b without going berserk?
Input
The first line contains one integer T,T≤5 , which represents the number of test case.
For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000 . The Undirected Kingdom has n cities and m bidirectional roads, and there are q queries.
Each of the following m lines consists of three integers a,b and d where a,b∈{1,...,n} and d≤100000 . It takes Jack d minutes to trav
HDU - 5876 Sparse Graph 补图最短路（使用两个set的做法）
题目大意
给出图G，求图G的补图H对于源点S的单源最短路
题解
这道题目就是稍微考虑一下就可以了。同样是一个BFS的写法，只不过这次的BFS要求不能使用图中给出的边，我们要求的是补图的最短路，就要用非原图的所有边。
这样我们可以使用两个set，其中过一个记录当前会被更新的点，另一个记录还没有被更新过的点。具体实现看代码，不好解释。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
sets1;
sets2;
const int maxn = 2e5+5;
struct edge{
int to,next;
}e[maxn];
int h[maxn];
int dis[maxn];
int T,n,m,S,u,v,cnt;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (((num<<2)+num)<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
void init(){
for(int i = 1;i <= n;++i){
h[i] = -1;
dis[i] = -1;
}
cnt = 0;
}
void add(int u,int v){
e[cnt].to = v;
e[cnt].next = h[u];h[u] = cnt++;
return;
}
void BFS(int s){
for(int i = 1;i <=
Description
Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.
He wants develop this kingdom from one city to one city.
Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.
He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.
Input
There are multiple test cases, terminated by a line "0".
For each test case, the first line contains an integer n (1<=n<=500).
The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.
Cities are labelled from 1.
Output
If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.