2019-07-21 20:34:56 |  0 Comments  |  KMP

Light OJ 1268 Unlucky Strings KMP DP矩阵快速幂优化

Description

Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.

One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.

So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 109). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only.

Output

For each case, print the case number and the total number of names that don't cont

 2019-07-21 20:14:23 |  0 Comments  |  KMP

Light OJ 1258 Making Huge Palindromes KMP构造回文串

Description

A string is said to be a palindrome if it remains same when read backwards. So, 'abba', 'madam' both are palindromes, but 'adam' is not.

Now you are given a non-empty string S, containing only lowercase English letters. The given string may or may not be palindrome. Your task is to make it a palindrome. But you are only allowed to add characters at the right side of the string. And of course you can add any character you want, but the resulting string has to be a palindrome, and the length of the palindrome should be as small as possible.

For example, the string is 'bababa'. You can make many palindromes including

bababababab

babababab

bababab

Since we want a palindrome with minimum length, the solution is 'bababab' cause its length is minimum.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a string S. You can assume that 1 ≤ length(S) ≤ 106.

Output

For each case, print the case number and the length of the shorte

 2019-07-20 21:56:59 |  0 Comments  |  KMP

HDU 3336 Count the string KMP(瞎搞)

题目大意

求给定的字符串所有前缀在字符串中出现次数的总和mod10007的值

题解

这题的结论是这样的:求出next数组,然后从后向前,依次累加……

算了我也说不明白,还是给个代码合适。。。。

for(int i = 1;i <= n;++i){
	a[i] = 1;
}
for(int i = n;i >= 1;--i)
    a[nxt[i]] += a[i];

就是这样的一个结论,然后O(n)就能求出所有我们要的结果。

其中ai代表以当前位置i为结尾的前缀字符串在原字符串中出现的次数。

为什么这样可以做?
我个人的想法是……KMP中的next数组,实际上表示的真正含义为到位置pos为止的前缀字符串中,最长的能够匹配的前缀和后缀的长度(这里的前缀和后缀值得是我们取出的前缀字符串的前缀和后缀,而且这里的前缀和后缀的长度不能和取出的这个前缀字符串的长度相等)。

于是我们想,如果我们取出一个前缀,结束位置为pos,他出现过x次,那么他对应的以next[pos]为结尾的前缀字符串一定也会随着这个前缀串出现x+1次。但是这其中还有一次是会不断算重复的,于是累加的时候就加x,把本身有的那一次放入初始化的时候,先对每个位置的值赋值1。

其实我也不是很明白这样正确性怎么证明,但是毕竟icpc吗,要大胆猜想……

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
const int maxn = 2e5+5;
int cas;
char s[maxn];
int a[maxn];
int nxt[maxn];
void KMP(){
	int j = 0;
	nxt[1] = 0;
	int len = strlen(s+1);
	for(int i = 2;i <= len;++i){
		while(j && s[i] != s[j+1])j = nxt[j];
		if(s[j+1] == s[i])j++;
		nxt[i] = j;
	}
	return;
}
int T;
const int mod = 10007;
int main(){
	scanf("
 2019-07-20 09:58:14 |  0 Comments  |  DP 贪心 回溯

Codeforces Round #2 The least round way DP+贪心

题目大意

现在给一个n*n的矩阵,你要从(1,1)走到(n,n),求一条路径,使得路径上所有数的乘积的尾部零的个数最少。

题解

我们先考虑尾部零怎么能够产生。

首先要产生尾部零,就一定要乘10或者0。

先来考虑0的情况,如果你走一条带有0的路径的话,那么最后乘积一定会是0,尾部零的数量为1个。

如果我们不走带有0的路径的话,那么要产生尾部0就一定要有因数10,而且有多少个因数10就有多少个尾部零。

而10这个数,很明显的,我们能够将其分解为2*5,由质因数分解的唯一性,我们只需要统计路径上2和5的个数,然后取其中的最少就是最终因数10的个数,也即尾部零的个数。

讨论完尾部0的产生,我们来看一下怎样选择路径。

我们可以先不考虑带0的路径,先来看带质因数2和5的路径。

我们可以用一个三位dp[x][y][0/1]代表走到点(x,y),质因数2/5总共有几个(0和1分别表示选2和选5),然后我们转移方程是很容易写出来的。不过要注意边界,请自行看参考代码。

最后我们得到的dp[n][n][0]和dp[n][n][1]中的最小值就是不考虑带0路径的答案。这里其实是一种贪心思想,由于非常简单十分好理解不再证明(贪心的证明一般都是反证)。

然后我们要看看有没有带0的路径,因为带0的路径尾部零只有1个,所以有可能使答案更小。

我们在DP过程中分别记录选2和选5个数最少的路径(记录从哪个方向来就行了),然后最后进行回溯输出即可。

代码

#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;
}
int n;
const int maxn = 1005;
int mp[maxn][maxn];
int c;
 2019-07-15 17:15:53 |  0 Comments  |  网络流

骑士共存问题 [网络流24题] 二分图最大独立集

题解

很明显能看出来同色的格子之间是不会相互攻击的。

于是我们就可以把这张图分成一张二分图了,然后建边跑最大流。

有攻击关系的点需要连一条流量为1的边。

不过值得注意的是,要优化建边方法,不然会超时。

既然是二分图,我们考虑黄色格子代表的点与S连边,红色格子代表的点与T连边,在考虑攻击关系的时候,只从黄色格子连向红色格子就可以了(因为互相攻击,所以是等价的,当然与上述方案完全反过来建边也可以)。

我们要求的是最多的共存骑士,所以是明显的二分图最大独立集的问题,求出的最大流相当于一个最小割,用总数n*n-m再减去这个最小割就是最大独立集的最后剩余的数目。

代码

#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<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 205;
struct edge{
    int to,next,cap;
}e[maxn*maxn * 16];
int cnt = 0;
int h[maxn*maxn];
void add(int u,int v,int c){
    e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];
    h[u] = cnt++;
    return;
}
int d[maxn*maxn];
const int INF = 1e9;
bool BFS(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = INF;
    }
    d[s] = 0;
    queue<int>q;
   
 2019-07-13 19:09:19 |  0 Comments  |  最短路 二分 离散化 网络流 最大流

BAPC18 I In Case of an Invasion,Please... 最短路+离散化+二分+最大流

题目大意

有n个居民点,m条双向有权路径,和s个避难所。每个居民点有pi个居民,每个避难所的容量为Ci。

现在求能够让所有人避难的最少的需要的时间。

题解

我们如果有一个时间,那么我们该如何判断在这个时间内能不能安置所有居民呢?

很简单就能想到,这是一个利用最大流判断是否存在可行流的问题。

建立从源点s到每个居民点的容量为pi的有向边,从每个居民点到每个避难所容量为+∞的有向边,从每个避难所到汇点t容量为ci的有向边。

然后建完图直接跑最大流,判断最大流的流量是否等于所有的居民人数总和即可。

那这个时间我们该如何去求?

答案是可以二分。

二分出一个答案时间,然后检验这个时间下能否将所有人安置好。当然在建立居民点到避难所的有向边的时候应当考虑该居民点到该避难所的时间会不会大于当前给出的答案时间,若是小于等于则加入此边,否则不加入此边。

至于离散化,是一个能够优化常数的做法。就是预处理所有避难所到所有居民点的距离,并且装入一个数组,并对数组从小到大排序。然后直接枚举数组下标获取答案时间。

这样做是正确的,因为最终答案一定是某个居民点到某个避难所的时间,而不会有多余(这是很显然的,请读者思考)。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
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;
}
int n,m;
const int maxn = 2e5+25;
const int max
 2019-07-09 00:21:56 |  0 Comments  |  模拟

CSP201903 T2 二十四点 论STL的正确应用

题解

这道题如果会C++ STL的话会方便许多,当然也可以手写,不过可能要麻烦一点点。

首先考虑运算符的运算顺序,肯定是x和/先进行运算了。

那么我们就先将+和-操作丢进双端队列里面,等待最后运算。

然后我们还要设置一个保存数字的双端队列,且要保证此队列任何时候都有数字。

这样当我们遇到x和/的时候,就把队尾元素取出和下一个数字进行运算,然后再压入队尾。

最后处理+和-操作就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
deque<int>x;
deque<char>y;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> s;
        while(!x.empty())x.pop_back();
        while(!y.empty())y.pop_back();
        x.push_back(s[0] - '0');
        for(int j = 1;j < 7;j += 2){
            if(s[j] == 'x' || s[j] == '/'){
                int now = x.back();
                x.pop_back();
                if(s[j] == 'x'){
                    now *= (s[j+1] - '0');
                    x.push_back(now);
                }
                else{
                    now /= (s[j+1] - '0');
                    x.push_back(now);
                }
            }
            else{
                y.push_back(s[j]);
 
 2019-07-08 23:31:04 |  0 Comments  |  文本处理

URL映射 CSP201803 T3

问题描述
  URL 映射是诸如 Django、Ruby on Rails 等网页框架 (web frameworks) 的一个重要组件。对于从浏览器发来的 HTTP 请求,URL 映射模块会解析请求中的 URL 地址,并将其分派给相应的处理代码。现在,请你来实现一个简单的 URL 映射功能。
  本题中 URL 映射功能的配置由若干条 URL 映射规则组成。当一个请求到达时,URL 映射功能会将请求中的 URL 地址按照配置的先后顺序逐一与这些规则进行匹配。当遇到第一条完全匹配的规则时,匹配成功,得到匹配的规则以及匹配的参数。若不能匹配任何一条规则,则匹配失败。
  本题输入的 URL 地址是以斜杠 / 作为分隔符的路径,保证以斜杠开头。其他合法字符还包括大小写英文字母、阿拉伯数字、减号 -、下划线 _ 和小数点 .。例如,/person/123/ 是一个合法的 URL 地址,而 /person/123? 则不合法(存在不合法的字符问号 ?)。另外,英文字母区分大小写,因此 /case/ 和 /CAse/ 是不同的 URL 地址。
  对于 URL 映射规则,同样是以斜杠开始。除了可以是正常的 URL 地址外,还可以包含参数,有以下 3 种:
  字符串 <str>:用于匹配一段字符串,注意字符串里不能包含斜杠。例如,abcde0123。
  整数 <int>:用于匹配一个不带符号的整数,全部由阿拉伯数字组成。例如,01234。
  路径 <path>:用于匹配一段字符串,字符串可以包含斜杠。例如,abcd/0123/。
  以上 3 种参数都必须匹配非空的字符串。简便起见,题目规定规则中 <str> 和 <int> 前面一定是斜杠,后面要么是斜杠,要么是规则的结束(也就是该参数是规则的最后一部分)。而 <path> 的前面一定是斜杠,后面一定是规则的结束。无论是 URL 地址还是规则,都不会出现连续的斜杠。
输入格式
  输入第一行是两个正整数 nm,分别表示 URL 映射的规则条数和待处理的 URL 地址个数,中间用一个空格字符分隔。
  第 2 行至第 n+1 行按匹配的先后顺序描述 URL 映射规则的配置信息。第 i+1 行包含两个字符串 piri,其中 pi 表示 URL 匹配的规则,ri 表示这条 URL 匹配的名字。两个字符串都非空,且不包含空
 2019-07-07 21:56:00 |  0 Comments  |  topsort DP

洛谷P1137 旅行计划

题解

别问我为什么写这么水的题解,问就是为了那门水的不行的专业选修课。

很简单,这个图肯定是个DAG(请不要问为什么,自己看一下题目描述。。。)

然后我们在这个DAG上按拓扑序来进行DP就可以了,因为入度为0的点一定最多游览一个,然后不断类似SPFA最长路一样的进行DP,就可以求出到某个城市最多可以游览的城市数目了。

代码

#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<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int n,m;
int x,y;
const int maxn = 1e5+5;
vector<int>g[maxn];
int f[maxn],d[maxn];
int inq[maxn];
int main(){
    memset(d,0,sizeof(d));
    n = get_num();
    m = get_num();
    for(int i = 1;i <= m;++i){
        x = get_num();
        y = get_num();
        g[x].push_back(y);
        d[y]++;
    }
    queue<int>q;
    for(int i = 1;i <= n;++i){
        if(!d[i])
            q.push(i),inq[i] = 1;
        f[i] = 1;
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
 2019-07-07 11:37:58 |  0 Comments  |  DP

BZOJ 3156 防御准备 决策单调性斜率优化DP

数据范围

1 ≤ n  106,1 ai 10

题解

这大概是第一道我自己做(手推)出来的斜率优化DP?

不多说,直接上推导的过程:

 来保存决策点的队列一直利用斜率维护一个下凸壳就完事了。

代码

#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<<1) + (num<<3) + c - '0';
    return (flag ? -1 : 1) * num;
}
typedef long long ll;
const int maxn = 1e6+5;
ll a[maxn],f[maxn],sum[maxn];
int q[maxn];
double slop(int k,int j){
    return double(f[j] - f[k] + sum[j] - sum[k]) / double(j-k);
}
int n,l,r;
int main(){
    n = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
        sum[i] = sum[i-1] + i;
    }
    for(int i = 1;i <= n;++i){
        while(l < r && slop(q[l],q[l+1]) < i)++l;
        int t = q[l];
        f[i] = f[t] + a[i] + ll(i-t-1)*i - sum[i-1] + sum[t];
        while(l < r && slop(q[r-1],q[r]) > slop(q[r],i))r--;
       
Title - Artist
0:00