1.今天呢,我考了一套题目。

分数100/300。

很无奈。

sequence[模拟]

题面就是给你个序列,然后让你找出max{a[i]-a[j]}(i<j)

只要线性找最大值然后拿当前值减即可。

心态爆炸。只有50/100分。mod爆了。

#include<cstdio>

long long sa,sb,sc,sd,n,mode;
long long a[5000010];

inline long long v_in(){
    char ch=getchar();
    long long sum=0,f=1;
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        sum=(sum<<3)+(sum<<1)+(ch^48);
        ch=getchar();
    }
    return sum*f;
}

inline long long f(long long x){
    long long res=sa;
    res=((res*x)%mode+sb)%mode;
    res=((res*x)%mode+sc)%mode;
    res=((res*x)%mode+sd)%mode;
    return res;
}

inline void prework(){
    for (register long long i=2;i<=n;i++)
        a[i]=(f(a[i-1])+f(a[i-2]))%mode;
}

int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=v_in();
    sa=v_in();
    sb=v_in();
    sc=v_in();
    sd=v_in();
    a[0]=0;
    a[1]=v_in();
    mode=v_in();
    prework();
    long long maxn=a[1],ans=0;
    for (long long i=2;i<=n;i++){
        if (maxn<a[i]) maxn=a[i];
        if (ans<maxn-a[i]) ans=maxn-a[i];
    }
    if (ans&1) ans++;
    printf("%lld\n",ans>>1);
    return 0;
}

travel[并查集]

0/100分。

并没有做这道题。

如果强行暴力的话可以60分。

然而正解是并查集。

我们只需要按照权值将询问和边从小到大排序

然后按顺序每次询问将权值小于该询问权值的边连起来合并即可。

#include<cstdio>
#include<algorithm>

using namespace std;

struct edge{
    int u,v,w;
    bool operator < (const edge &k)const{
        return w<k.w;
    }
}e[200010];
struct query{
    int x,w,id;
    bool operator < (const query &k)const{
        return w<k.w;
    }
}qu[100010];
int fa[100010],size[100010],ans[100010];
int n,m,q;

inline int v_in(){
    char ch=getchar();
    int sum=0,f=1;
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        sum=(sum<<3)+(sum<<1)+(ch^48);
        ch=getchar();
    }
    return sum*f;
}

inline int getf(int x){
    if (fa[x]==x) return x;
    return fa[x]=getf(fa[x]);
}

inline void chain(int u,int v){
    int f1=getf(u),f2=getf(v);
    if (f1!=f2){
        fa[f2]=f1;
        size[f1]+=size[f2];
    }
}

int main(){
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    n=v_in();
    m=v_in();
    q=v_in();
    for (int i=1;i<=n;i++){
        fa[i]=i;
        size[i]=1;
    }
    for (int i=1;i<=m;i++){
        int u=v_in(),v=v_in(),w=v_in();
        e[i].u=u;
        e[i].v=v;
        e[i].w=w;
    }
    sort(e+1,e+m+1);
    for (int i=1;i<=q;i++){
        int x=v_in(),w=v_in();
        qu[i].x=x;
        qu[i].w=w;
        qu[i].id=i;
    }
    sort(qu+1,qu+q+1);
    int pos=1;
    for (int i=1;i<=q;i++){
        while (e[pos].w<=qu[i].w&&pos<=m){
            chain(e[pos].u,e[pos].v);
            pos++;
        }
        ans[qu[i].id]=size[getf(qu[i].x)];
    }
    for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}

string[KMP]

这个题因为不会看毛片所以不会做。

然后就暴力了50/100分。

其实这题是很裸的一道KMP

求出匹配数=x

#include<cstdio>
#include<cstring>

int k,n,ans,next[5010];
char s[5010];

void kmp(int pos){
    for (int i=1;i<=n;i++) next[i]=pos-1;
    for (int i=pos+1;i<=n;i++){
        int j=next[i-1];
        while (j!=pos-1&&s[j+1]!=s[i]) j=next[j];
        if (s[j+1]==s[i]) j++;
        next[i]=j;
    }
    int j=next[pos];
    for (int i=pos+1;i<=n;i++){
        while (j!=pos-1&&s[j+1]!=s[i]) j=next[j];
        if (s[j+1]==s[i]) j++;
        while ((j-pos+1)*2>=i-pos+1) j=next[j];
        if (j-pos+1>=k) ans++;
    }
}

int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    scanf("%s",s+1);
    scanf("%d",&k);
    n=strlen(s+1);
    for (int i=1;i<=n;i++) kmp(i);
    printf("%d\n",ans);
    return 0;
}

ans+=x*(x+1)/2

所以说呢,我其实基本功还是不过关的。

如果说最优状态的话,我估计可以拿到260分左右。

第二题暴力骗60,其他裸题,不出差错就有260分。

最终只有一百分。我好菜啊。

2.kmp真是玄学啊

我今天重新复习了一边kmp,看了一个写的很好的博客

然后就觉得kmp这种算法真的是优化了很多,节约了很多时间

比起暴力o(nm),kmp只需要o(n+m)

在这里贴个链接

3.还有需要弄的内容

(1) 白书4.1~4.5(一个星期弄完)

(2) kmp复习

(3) 计算几何(扫描线&&凸包)