11.26 模拟赛

写的分基本全挂了非常的菜

T1 password

题目大意：

$m$个模式串求长度为$n$的串中包含所有$m$个串的方案数

$mle4,lenle50$ $len=字符串总长度$

思路：

可以想到一个$n imes len imes 2^m$的dp

然后将状压部分转换成容斥使用矩阵加速矩阵i j 表示节点i - j的转移

（死于全集没写快速幂）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<vector>
  8 #include<queue>
  9 #include<map>
 10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
 11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
 12 #define ren for(register int i=fst[x];i;i=nxt[i])
 13 #define Fill(x,t) memset(x,t,sizeof(x))
 14 #define ll long long
 15 #define inf 2139062143
 16 #define MAXN 1400
 17 #define MOD 998244353
 18 using namespace std;
 19 inline int read()
 20 {
 21     int x=0,f=1;char ch=getchar();
 22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
 23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
 24     return x*f;
 25 }
 26 inline int add(ll a,ll b) {return a+b<MOD?a+b:a+b-MOD;}
 27 char s[5][60];
 28 int n,m,ch[MAXN][10],fail[MAXN],sz,ed[MAXN],cnt;
 29 ll tot;
 30 void ins(int x)
 31 {
 32     int len=strlen(s[x]),pos=0;
 33     rep(i,0,len-1) 
 34     {
 35         if(!ch[pos][s[x][i]-'0']) ch[pos][s[x][i]-'0']=++sz;
 36         pos=ch[pos][s[x][i]-'0'];
 37     }
 38     cnt++,ed[pos]|=(1<<cnt);
 39 }
 40 int q[MAXN],l=1,r,vis[MAXN];
 41 void build()
 42 {
 43     int x;
 44     rep(i,0,9) if(ch[0][i]) q[++r]=ch[0][i];
 45     while(l<=r)
 46     {
 47         x=q[l++];
 48         rep(i,0,9) if(ch[x][i]) fail[ch[x][i]]=ch[fail[x]][i],q[++r]=ch[x][i];
 49         else ch[x][i]=ch[fail[x]][i];
 50         ed[x]|=ed[fail[x]];
 51     }
 52 }
 53 struct Mat
 54 {
 55     ll num[55][55];
 56     Mat(){Fill(num,0);}
 57     Mat operator * (const Mat &a) const
 58     {
 59         Mat res;
 60         rep(i,0,sz) rep(j,0,sz) rep(k,0,sz)
 61             res.num[i][j]=add(res.num[i][j],(num[i][k]*a.num[k][j])%MOD);
 62         return res;
 63     }
 64 };
 65 Mat res;
 66 ll calc(int x)
 67 {
 68     vis[x]=1;ll ans=res.num[0][x];
 69     rep(i,0,9) if(!vis[ch[x][i]]&&!ed[ch[x][i]]) ans=add(ans,calc(ch[x][i]));
 70     return ans;
 71 }
 72 ll q_pow(Mat x,ll t)
 73 {
 74     Fill(res.num,0);rep(i,0,sz) res.num[i][i]=1;
 75     for(;t;t>>=1,x=x*x)
 76         if(t&1) res=x*res;
 77     //rep(i,0,sz) {rep(j,0,sz) cout<<res.num[i][j]<<" ";puts("");}
 78     return calc(0);
 79 }
 80 ll qaq(ll bas,ll t)
 81 {
 82     ll res=1;
 83     for(;t;t>>=1,(bas*=bas)%=MOD)
 84         if(t&1) (res*=bas)%=MOD;
 85     return res;
 86 }
 87 int main()
 88 {
 89     freopen("password.in","r",stdin);
 90     freopen("password.out","w",stdout);
 91     m=read(),n=read();int ms=(1<<m)-1;Mat tmp;
 92     rep(i,1,m) scanf("%s",s[i]);tot=1;
 93     tot=qaq(10LL,n);
 94     rep(t,1,ms)
 95     {
 96         Fill(fail,0);Fill(ch,0);Fill(vis,0);Fill(tmp.num,0);Fill(ed,0);sz=cnt=0;
 97         rep(i,1,m) if(1&(t>>(i-1))) ins(i);
 98         build();rep(i,0,sz) if(!ed[i]) rep(j,0,9) tmp.num[i][ch[i][j]]++;
 99         if(cnt&1) tot=(tot+MOD-q_pow(tmp,n))%MOD;else tot=add(tot,q_pow(tmp,n));
100     }
101     printf("%lld
",tot);
102 }

View Code

T2 paint

题目大意：

一个数列分成若干段每段长度属于$[l,r]$ 设该段和为x 每一段的价值为$a*x^2+b*x+c$ 求最终的最大价值

思路：

看上去像是一个斜优但是由于斜率和x坐标都不单调，还有长度的限制

考虑线段树分治每个点可以对之后的一段区间造成影响用线段树记录

对于每个点我们将包含它的线段树上的节点的凸包搞出来在每个凸包上二分出答案并在这$log_n$个答案中取最优

（中间有结果会爆long long 所以特判了一波）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren(x) for(register int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 1152921504606846976LL
16 #define maxi 2147483647
17 #define MAXN 600100
18 #define MOD 998244353
19 using namespace std;
20 inline ll read()
21 {
22     ll x=0,f=1;char ch=getchar();
23     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
24     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
25     return x*f;
26 }
27 ll a,b,c,sum[MAXN],dp[MAXN];
28 int n,fst[MAXN],to[MAXN<<4],nxt[MAXN<<4],cnt,l,r;
29 vector <int> vec[MAXN];
30 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
31 void mdf(int k,int l,int r,int a,int b,int w)
32 {
33     if(l==a&&r==b) {add(k,w);return ;}
34     int mid=l+r>>1;
35     if(b<=mid) mdf(k<<1,l,mid,a,b,w);
36     else if(a>mid) mdf(k<<1|1,mid+1,r,a,b,w);
37     else {mdf(k<<1,l,mid,a,mid,w);mdf(k<<1|1,mid+1,r,mid+1,b,w);}
38 }
39 int top,q[MAXN],tl;
40 struct Point
41 {
42     ll x,y,fi;int id;
43     Point operator - (const Point &a) const {return (Point){x-a.x,y-a.y,fi,id};}
44     bool operator < (const Point &a) const {return x<a.x;}
45     ll operator * (const Point &a) const {return (ll)x*a.y-y*a.x;}
46 }st[MAXN];
47 ll calc(int x,int y) {if(sum[y]-sum[x]>maxi&&a<0) return -inf;return dp[x]+a*(sum[y]-sum[x])*(sum[y]-sum[x])+c;}
48 void solve(int k,int l,int r)
49 {
50     top=tl=0;int mid;
51     ren(k) st[++top]=(Point){sum[to[i]],dp[to[i]]+a*sum[to[i]]*sum[to[i]]-b*sum[to[i]],dp[to[i]],to[i]};
52     if(top)
53     {
54         sort(st+1,st+top+1);q[++tl]=1;
55         rep(i,2,top)
56         {
57             if(st[i].fi<=-inf+100000000000000LL) continue;
58             while(tl>1&&(st[q[tl]]-st[q[tl-1]])*(st[i]-st[q[tl]])>=0LL) tl--;
59             q[++tl]=i;
60         }
61         rep(i,1,tl) vec[k].push_back(st[q[i]].id);
62     }
63     if(l==r)
64     {
65         int ml,mr,mid,res;
66         for(int t=k;t;t>>=1)
67         {
68             ml=0,res=mr=vec[t].size()-1;if(mr<0) continue;mr--; 
69             while(ml<=mr) {mid=ml+mr>>1;if(calc(vec[t][mid+1],l)<=calc(vec[t][mid],l)) mr=mid-1,res=mid;else ml=mid+1;}
70             dp[l]=max(calc(vec[t][res],l),dp[l]);
71         }
72         return ;
73     }
74     mid=l+r>>1;solve(k<<1,l,mid);solve(k<<1|1,mid+1,r);
75 }
76 int main()
77 {
78     freopen("paint.in","r",stdin);
79     freopen("paint.out","w",stdout);
80     n=read(),a=read(),b=read(),c=read(),l=read(),r=read();
81     rep(i,1,n) sum[i]=sum[i-1]+read(),dp[i]=-1LL<<60;
82     rep(i,0,n-l) mdf(1,0,n,i+l,min(i+r,n),i);
83     solve(1,0,n);printf("%lld
",dp[n]+b*sum[n]);
84 }

View Code

T3 route

题目大意：

一棵树一个路径的权值为这个路径上最小边的权值*权值和求一条路径上最大值与最小值之差<m的路径的权值最大值

思路：

首先可以知道一个结论：

还是线段树分治按边权排序后每条边对一个区间内边有影响

我们使用带撤销并查集维护这个图的直径每个点的答案即为当前图的直径$ imes$ 这个点的权值（由于从小到大加入边）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(register int i=fst[x];i;i=nxt[i])
13 #define ren0 for(register int i=fst0[k];i;i=nxt0[i])
14 #define Fill(x,t) memset(x,t,sizeof(x))
15 #define ll long long
16 #define inf 2139062143
17 #define MAXN 170100
18 using namespace std;
19 inline int read()
20 {
21     int x=0,f=1;char ch=getchar();
22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 int n,m,fa[MAXN],in[MAXN<<1],rnk[MAXN],l2[MAXN<<1];
27 int fst[MAXN],to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],cnt,tot;
28 int nxt0[MAXN*20],fst0[MAXN<<2],to0[MAXN*20],top;
29 struct Edge{int u,v,w;}e[MAXN];
30 struct Path{int x,y;}g[MAXN];
31 struct Cancel{int x,y,rnk;ll len;Path a;}st[MAXN];
32 bool operator < (const Edge &a,const Edge &b) {return a.w<b.w;}
33 ll ans,dis[MAXN],f[20][MAXN<<1],dmt;
34 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
35 void Add(int u,int v) {nxt0[++cnt]=fst0[u],fst0[u]=cnt,to0[cnt]=v;}
36 int find(int x) {return x==fa[x]?x:find(fa[x]);}
37 void dfs(int x,int fa)
38 {
39     in[x]=tot;
40     ren if(to[i]!=fa) {f[0][++tot]=dis[to[i]]=dis[x]+val[i];dfs(to[i],x);f[0][++tot]=dis[x];}
41 }
42 ll calc(int x,int y)
43 {
44     if(in[x]>in[y]) swap(x,y);int t=l2[in[y]-in[x]+1];
45     return dis[x]+dis[y]-(min(f[t][in[x]],f[t][in[y]-(1<<t)+1])<<1);
46 }
47 Path merge(int x,int y,int xx,int yy)
48 {
49     int ax=x,ay=y;
50     if(calc(x,xx)>calc(ax,ay)) ax=x,ay=xx;
51     if(calc(x,yy)>calc(ax,ay)) ax=x,ay=yy;
52     if(calc(y,xx)>calc(ax,ay)) ax=y,ay=xx;
53     if(calc(y,yy)>calc(ax,ay)) ax=y,ay=yy;
54     if(calc(xx,yy)>calc(ax,ay)) ax=xx,ay=yy;
55     return (Path){ax,ay};
56 }
57 void Merge(int x,int y)
58 {
59     int u=find(x),v=find(y);
60     if(rnk[u]<rnk[v]) swap(u,v);
61     fa[v]=u,st[++top]=(Cancel){u,v,rnk[u],dmt,g[u]},g[u]=merge(g[u].x,g[u].y,g[v].x,g[v].y);
62     if(rnk[u]==rnk[v]) rnk[u]++;
63     dmt=max(dmt,calc(g[u].x,g[u].y));
64 }
65 void dlt()
66 {
67     int x=st[top].x,y=st[top].y;
68     fa[y]=y,rnk[x]=st[top].rnk,g[x]=st[top].a,dmt=st[top--].len;
69 }
70 void mdf(int k,int l,int r,int a,int b,int w)
71 {
72     if(l==a&&r==b) {Add(k,w);return ;}
73     int mid=l+r>>1;
74     if(b<=mid) mdf(k<<1,l,mid,a,b,w);
75     else if(a>mid) mdf(k<<1|1,mid+1,r,a,b,w);
76     else {mdf(k<<1,l,mid,a,mid,w);mdf(k<<1|1,mid+1,r,mid+1,b,w);}
77 }
78 void solve(int k,int l,int r)
79 {
80     int pos=top,mid=l+r>>1;
81     ren0 Merge(e[to0[i]].u,e[to0[i]].v);
82     if(l==r) ans=max(ans,dmt*e[l].w);
83     else {solve(k<<1,l,mid);solve(k<<1|1,mid+1,r);}
84     while(top!=pos) dlt();
85 }
86 int main()
87 {
88     freopen("route.in","r",stdin);
89     freopen("route.out","w",stdout);
90     n=read(),m=read();int a,b,c;
91     rep(i,1,n-1) {a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);e[i]=(Edge){a,b,c};}
92     dfs(1,0);sort(e+1,e+n);rep(i,1,n) fa[i]=i,g[i]=(Path){i,i};
93     rep(i,2,tot) l2[i]=l2[i>>1]+1;cnt=0;
94     rep(j,1,19) rep(i,1,tot) {if(i+(1<<j)-1>tot) break;f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]);}
95     a=n-1;
96     dwn(i,n-1,1) {while(e[i].w-e[a].w<=m&&a) a--;mdf(1,1,n-1,a+1,i,i);}
97     solve(1,1,n-1);
98     printf("%lld
",ans);
99 }

View Code