[USACO5.3]校园网Network of Schools

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A 也不一定在 B 学校的列表中。

你要写一个程序计算,根据协议,为了让网络中所有的学校都用上新软件,必须接受新软件副本的最少学校数目(子任务 A)。更进一步,我们想要确定通过给任意一个学校发送新软件,这个软件就会分发到网络中的所有学校。为了完成这个任务,我们可能必须扩展接收学校列表,使其加入新成员。计算最少需要增加几个扩展,使得不论我们给哪个学校发送新软件,它都会到达其余所有的学校(子任务 B)。一个扩展就是在一个学校的接收学校列表...

【SPOJ1811】Longest Common Substring(后缀自动机模板题)

题目大意:给定两个字符串,求出两个字符串的最长公共子串,保证字符串长度不超过250000且均为小写字母。

附上一个详细讲解的 http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html

CODE:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=500000+10;
int len[maxn]...

【HNOI模拟】K小数查询 分块模板

题目大意

有n个数,两种操作 
1:将x~y的数增加z
2:求x~y中的第k小数 

区间修改就是将中间块加标记,边角暴力加上。查询就是二分第k小数的大小,因为块中是有序数,所以也能二分,同理边角暴力查询。因为n<=80000,块大小取300就差不多了

附上code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn...

求动态区间连续最大和

(目前写的只能求值,求坐标的那个贼恶心)

思路 线段树

最主要的是求:最大连续和 最大前缀和 最大后缀和

附上创伤的code


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=500001;
int n,m;
int zuo[maxn],you[maxn],a[maxn],doe[maxn*2],s[maxn*2],l[maxn*2],r[maxn*2],...

BSGS算法 (模板:POJ - 2417 Discrete Logging)

就是求 A^x=B(mod C)  x的最小值,但前提是C为质数

主要讲一下变换过程

设x=i*m-j,其中m=ceil(sqrt(C)),(ceil是向上取整)

代入后为 A^(i*m-j)=B(mod C)

经变换得 A^j×B=A^(m*i) (mod C)

先对j进行预处理,再枚举i

范围:(0<=j<=m)  (1<=i<=m)

反正因为用map 查询,原题5000ms 程序4750ms卡过去了

听说用哈希表超快,但是我作为蒻苟并不能看懂

附上code:


#include...

HDU 2222 Keywords Search

可以说是ac自动机的模板题

(开始题目意思一直没弄懂,感觉像英文双关,后来才发现是多少种而不是多少个,但是要算上重复的模板串)

附上code(c++,丑但成功):

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

char a[1000001],b[1000001];
int ch[1010001][26],v[1000001],f[1000001],last[1000001]...

© 双重 | Powered by LOFTER