问能找出些许的S的(a一,T1.壹元2次方程

题意:
给八个串S,T,问能找出有个别的S的(a一,b一)(a2,b二)..(ak,bk),使Sa一—Sb1,…Sak—Sbk都饱含子串T,当中k>=1,且(a一,b1)…(ak,bk)互不相交。

T壹.一元一遍方程

诸如S =
“abacaba”,T=”aba”,
当k=壹时,(0,陆)满足,还有任何只含有一个aba串的也满意,k-二时,(0,二)(三,六)满意,(0,二)(四,陆)也满意,(0,三)(肆,陆)也满意,所以总共有12种。

付给一个形如a*x^3+b*x^2+c*x+d=0的一元一回方程的全面a,b,c,d,保障有四个不一样的实根,输出并保存两位小数。

解法:dp.先用kmp找出具有匹配点。

鉴于解的限量相比小,-100到100,果断用枚举,因为保存两位小数,所以能够推广【放大法??大致的吗】。。然后既能够直接从-一千0到10000实行枚举,判断是还是不是是解的时候,就裁减拾0倍,判断和零的差是还是不是丰盛小即可。

定义dp[i] =
bn为 i 的点子数(底部为 i )。

理所当然那是因为数量范围。假如把解的限量放大到-一千0到一千0的话,放大法的功用就不突显那么高。所以能够动用二分。由于两根之差的相对化值>=壹,所以可以枚举长度为壹的距离,然后对于这一个距离中的数举办二分求解。(分明,判断根所在的间距就和数学里判断零点所在是1模一样的)

则转移方程:  
要是 i 是某卓越的尾字母时,

 

图片 1左边意味着取的区间数K>一的景况,第一个循环枚举ak,第二个循环枚举b(k-一),
右侧表示取得区间数为1,即就取二个间距的诀要数(为从左边取起,取到此时匹配串的首先个假名字截至)

T二.数的分开

否则         
dp[i] = dp[i-1]

给出n,要把它分成k个数的和。求方案数。

于是,大家可以保险 
图片 2,
再维护图片 3

一开始致的原因为数量小,唯有陆层,就打了个暴力dfs。。。当然也是能过的,只是200,陆的数额跑了0.7s…

那么sum[i] =
sum[i-1]+ans[i],    ans[i] = ans[i-1]+dp[i];

接下来因为打完后时间还多,就起来想优化。。觉得那一个景况能够变一下,直接这样是优化不到何地去的。。

(谢谢God
yue 提供思路)

下一场就改了,用f(remain,maxn,cnt)作为气象,表示剩余remain的数要分成cnt个数的和,且剩下的数最大不超越maxn。。。这样的话,就能够用一下回忆化搜索。还有两个递推方程。。。

代码:

f(remain,maxn,cnt)=f(remain-maxn,maxn,cnt-1)+f(remain,maxn-1,cnt)

图片 4图片 5

那样的话,功能就高很多了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
#define lll __int64
using namespace std;
#define N 100007

char S[N],T[N];
int next[N],flag[N],n,m;

void getnext(char* b) {
    int i = 0,j = next[0] = -1;
    while(i < m) {
        if(j == -1 || b[i] == b[j]) next[++i] = ++j;
        else                        j = next[j];
    }
}

void kmp(char* a,char *b){
    memset(flag,0,sizeof(flag));
    int i = -1,j = -1;
    while(i < n && j < m) {
        if(j == -1 || a[i] == b[j]) i++,j++;
        else                        j = next[j];
        if(j == m) {
            flag[i] = 1;
            j = next[j];
        }
    }
}

lll dp[N],ans[N],sum[N];

int main()
{
    int i,j;
    scanf("%s%s",S,T);
    n = strlen(S), m = strlen(T);
    getnext(T);
    kmp(S,T);
    dp[0] = ans[0] = sum[0] = 0;
    for(i=1;i<=n;i++)
    {
        if(!flag[i]) dp[i] = dp[i-1];
        else         dp[i] = (sum[i-m]+i-m+1)%Mod;
        ans[i] = (ans[i-1] + dp[i])%Mod;
        sum[i] = (sum[i-1] + ans[i])%Mod;
    }
    cout<<ans[n]<<endl;
    return 0;
}

然后老师说这几个处境其实依然足以优化的。。。

View Code

下一场也确确实实是那般。。。大家得以设想3个境况f[i][k]表示将大小为i的数分成k份的方案数,然后能够发现,划分的最小数为一时是f[i-1][k-1],然后不为一时,可以视为f[i-k][k]的全数数+一组合的方案数,所以f[i][k]=f[i-1][k-1]+(i>k)*f[i-k][k]正是dp方程。这样就不难的多了。

 

 

T3.计算单词个数

交给p行(每行2十个)字母组成的字符串(一整个),要分开成k段,使得每段包蕴的单词数之和最大。。(单词种类不超过多少个,输入给出)

1初步考虑也是相比像dp的,所以只要解决每段里的单词数应该就没难题了。

从而难题即是单词了吗。。。由于标题中说,各类字母只可以起初二个单词,这些倒是个突破口。。。由于我们要硬着头皮升高空间利用率,就足以把每位字母开始的单词的矮小长度used[]总计出来。(那个嘛,不正是枚举吗。。。)然后能够枚举区间i,j,总计区间内的单词个数num[i][j].只要用2个动点p枚举区间中的每一种字母,看看p+used[p]-壹是还是不是在区间范围内,显著是或不是总括就好了。

接下来能够借助那些预处理来dp。。用f[i][k]表示将[1,i]那一个间隔分成k段的最大单词总数,显著有是枚举断点p,取f[i][k]=max{f[p][k-1]+num[p+1][i]}就好了。

 

 

T四.Car的远足路线

(个人觉得处理图的时候卓殊烦)

给出s个城市,各类城市有八个机场,呈矩形顶点分布。每一个城市内部有轻轨路线连接每七个飞机场,单位里程运费Ti。每种城市的航空站有航空线通往各样分歧城市的各样飞机场,单位运费是T。未来Car要从城市A到城池B,求最小开支。

由于标题输出相比较懵,只给了多少个极点,所以还要协调算第多少个。。。还要先判断给出的直角在哪儿。。。【于是恶狠狠地打了个向量数量积为零(滑稽.jpg)】

下一场本身是先处理了每一个城市内部的直通开销(顶点从一到四*n编号,每八个为1座城市),然后处理城市间的交通花费。(那是个精光图啊小编去。。。)

然后。。。然后枚举A城的七个飞机场,做了八回SPFA,每一遍从B城的多少个飞机场里取三个一点都不大距离。。。然后。。就没了。。。

写的时候脑残了那么一下下,预处理距离的时候,存的是邻接矩阵,然后。。。只存了半边。。忘记还要七个下标反一下了。。。就WA了3个点。(无奈.jpg)

相关文章