bzoj4943&洛谷3823&uoj315：[noi2017]蚯蚓排队——题解(代码片段)

关键词：

#include<cmath>
#include<stack>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+5;
const int K=50;
const int mod=998244353;
const int p=19260817;
const int B=13;
inline int read()
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))w|=ch==\'-\';ch=getchar();
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;

struct node
    int nxt,cnt;
    ll w;
e[21000000];
char s[10000005];
int n,m,cnt,head[p+5],t[10],a[N];
int nxt[N],pre[N];
ull f[K*2+5],base[K+5];
inline void add(ull w,int on)
    int u=w%p;
    for(int i=head[u];i;i=e[i].nxt)
    if(e[i].w==w)
        e[i].cnt+=on;return;
    
    
    e[++cnt].cnt=1;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;

inline int ask(ull w)
    int u=w%p;
    for(int i=head[u];i;i=e[i].nxt)
    if(e[i].w==w)return e[i].cnt;
    
    return 0;

void merge(int x,int y)
    int l=K+1,r=K;
    memset(f,0,sizeof(f));
    for(int i=x;i&&l>1;i=pre[i])f[--l]=a[i];
    for(int j=y;j&&r<2*K;j=nxt[j])f[++r]=a[j];
    for(int i=l;i<=r;i++)f[i]+=f[i-1]*B;
    for(int i=l;i<=K;i++)
    for(int j=K+1;j<=min(r,i+K-1);j++)
        add(f[j]-f[i-1]*base[j-i+1],1);
    
    
    nxt[x]=y;pre[y]=x;

void split(int x,int y)
    int l=K+1,r=K;
    memset(f,0,sizeof(f));
    for(int i=x;i&&l>1;i=pre[i])f[--l]=a[i];
    for(int j=y;j&&r<2*K;j=nxt[j])f[++r]=a[j];
    for(int i=l;i<=r;i++)f[i]+=f[i-1]*B;
    for(int i=l;i<=K;i++)
    for(int j=K+1;j<=min(r,i+K-1);j++)
        add(f[j]-f[i-1]*base[j-i+1],-1);
    
    
    nxt[x]=0;pre[y]=0;

int query(int k)
    ll ans=1;ull val=0;int len=strlen(s+1);
    if(k==1)
    for(int i=1;i<=len;i++)
        ans=ans*t[s[i]-\'0\']%mod;
    else
    for(int i=1;i<=len;i++)
        val=val*B+s[i]-\'0\';
        if(i>k)val-=base[k]*(s[i-k]-\'0\');
        if(i>=k)ans=ans*ask(val)%mod;
    
    
    return ans;

int main()
    n=read(),m=read();
    base[0]=1;
    for(int i=1;i<=K;i++)base[i]=base[i-1]*B;
    for(int i=1;i<=n;i++)
    a[i]=read();t[a[i]]++;
    
    for(int i=1;i<=m;i++)
    int op=read();
    if(op==1)
        int x=read(),y=read();
        merge(x,y);
    
    if(op==2)
        int x=read();
        split(x,nxt[x]);
    
    if(op==3)
        scanf("%s",s+1);
        int k=read();
        printf("%d\\n",query(k));
    
    
    return 0;

bzoj1229&洛谷2917：[usaco2008nov]toy玩具&洛谷4480：[bjwc2018]餐巾计划问题——题解(代码片段)

标题很长emmm……[USACO2008NOV]toy玩具https://www.luogu.org/problemnew/show/P2917https://www.lydsy.com/JudgeOnline/problem.php?id=1229[BJWC2018]餐巾计划问题https://www.luogu.org/problemnew/show/P4480其中 查看详情

bzoj1084&&洛谷2331[scoi2005]最大子矩阵

题解：分类讨论当m=1的时候，很简单的dp，这里就不再复述了当m=2的时候，设dp[i][j][k]表示有k个子矩阵，第一列有i个，第二列有j个然后枚举一下当前子矩阵，状态转移代码：#include<bits/stdc++.h>usingnamespacestd;constintN=105,M=15;intdp... 查看详情

bzoj3240&&洛谷p1397矩阵游戏[noi2013]（矩阵乘法+卡常）(代码片段)

　　题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3240　　这道题其实有普通快速幂+费马小定理的解法……然而我太弱了，一开始只想到了矩阵乘法的方法。　　首先定义两个矩阵：　　$A_1=\beginbmatrixa&b\\0&1\endb... 查看详情

bzoj3262：陌上花开&洛谷3810：三维偏序——题解

两者题一样，方便没有bzoj权限的朋友。http://www.lydsy.com/JudgeOnline/problem.php?id=3262https://www.luogu.org/problemnew/show/3810Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级... 查看详情

bzoj4009&洛谷3242&loj2113：[hnoi2015]接水果——题解(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=4009https://www.luogu.org/problemnew/show/P3242https://loj.ac/problem/2113风见幽香非常喜欢玩一个叫做osu!的游戏，其中她最喜欢玩的模式就是接水果。由于她已经DTFC了Thebigblack,她觉得这个游戏太简单了，于... 查看详情

bzoj3343&洛谷2801：教主的魔法——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=3343https://www.luogu.org/problemnew/show/2801题目描述教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一... 查看详情

bzoj2654&洛谷2619：tree——题解(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=2654https://www.luogu.org/problemnew/show/P2619给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。在APIO重学了二分……cljls的可... 查看详情

bzoj3435&洛谷3920&uoj55：[wc2014]紫荆花之恋(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=3435https://www.luogu.org/problemnew/show/P3920http://uoj.ac/problem/55强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见... 查看详情

bzoj1101&洛谷3455：[poi2007]zap——题解

https://www.luogu.org/problemnew/show/3455#subhttp://www.lydsy.com/JudgeOnline/problem.php?id=1101Description　　FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的... 查看详情

bzoj2830&洛谷3830：[shoi2012]随机树——题解(代码片段)

https://www.luogu.org/problemnew/show/P3830#sub  <-题面看这里~https://www.lydsy.com/JudgeOnline/problem.php?id=2830感觉智商被压制了的一题……后面放吐槽。参考：https://www.cnblogs.com/GuessYCB/p/846249 查看详情

bzoj3196&洛谷3380：二逼平衡树——题解(代码片段)

.../problem.php?id=3196https://www.luogu.org/problemnew/show/P3380（题面用洛谷的）您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：查询k在区间内的排名查询区间内排名为k的值修改某一位值上的数值... 查看详情

bzoj2938&洛谷2444：[poi2000]病毒——题解(代码片段)

http://www.lydsy.com/JudgeOnline/problem.php?id=2938https://www.luogu.org/problemnew/show/P2444二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安... 查看详情

[bzoj]3263陌上花开洛谷p3810三维偏序||cdq分治&&cdq分治讲解

原题定义一个点比另一个点大为当且仅当这个点的三个值分别大于等于另一个点的三个值。每比一个点大就为加一等级，求每个等级的点的数量。显然的三维偏序问题，CDQ的板子题。CDQ分治：CDQ分治是一种特殊的分治方法，在OI... 查看详情

bzoj4698&洛谷2463：[sdoi2008]sandy的卡片——题解(代码片段)

http://www.lydsy.com/JudgeOnline/problem.php?id=4698https://www.luogu.org/problemnew/show/P2463#subSandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都... 查看详情

bzoj4889&洛谷3759：[tjoi2017]不勤劳的图书管理员——题解(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=4889https://www.luogu.org/problemnew/show/P3759加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产... 查看详情

hdu3823primefriend

这题就是一道暴力但是我还有一些不明白的#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintMAXN=20000005;inlineintread() intx=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘)if(ch==‘-‘)f=-1;ch=getchar();... 查看详情

hdu3062&&hdu1824&&poj3578&&bzoj19972-sat

一条边<u,v>表示u选那么v一定被选。1#include<iostream>2#include<cstring>3#include<cstdio>4#include<algorithm>5usingnamespacestd;6constintMaxm=21000;7constintMaxn=2010;8structEDGE{intto, 查看详情

[bzoj2733]永无乡&&[bzoj3545]peaks

并不敢说完全会了线段树合并，只是至少知道原理写法了。。。还是太菜了，每天被大佬吊锤qwq我看到的几道线段树合并都是权值线段树的合并。这个算法适用范围应该只是01线段树的。这两道算入门题了吧。。。发现粘题面没... 查看详情