泳池
Luogu
LOJ
UOJ
BZOJ
先用差分转成(le k)的概率减去(le k-1)的概率。
设(f_{i,j})表示总共有(i)列，默认(1,cdots,j)行一定全部安全，第(j+1)行存在至少一个危险的点，保证当前最大合法子矩形面积(le k)的概率。
转移方程为(f_{i,j}=(1-q)q^jsumlimits_{k=1}^i(sumlimits_{l>j}f_{k-1,l})(sumlimits_{l>j}f_{i-k,l}))，后缀和优化即可。
设(g_i)表示有(i)列，第(1)行第(i)列的点是危险的，保证当前最大合法子矩形面积(le k)的概率。
那么答案就是(frac{g_{n+1}}{1-q})。
转移方程为(g_0=1,g_i=sumlimits_{j=1}^{min(i,k)}g_{j-i}sumlimits_{kge1}f_{j,k})。
常系数齐次线性递推即可，可以暴力多项式取模。
#include<bits/stdc++.h>
#define LL unsgined long long
#define N 2048
#define P 998244353
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],*iS,*iT;
char Get() { return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++); }
int read(){int x=0;char ch=Get();while(ch>57||ch<48)ch=Get();while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return x;}
}
using namespace IO;
int inc(int a,int b){a+=b;return a>=P? a-P:a;}
int dec(int a,int b){a-=b;return a<0? a+P:a;}
int power(int a,int k){int r=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)r=1ll*r*a%P;return r;}
int n,x,y,p,q,dp[N][N],s[N],num[N],tmp[N],f[N],F[N],G[N],a[N];
int solve(int k)
{
int i,j,h,Pow,sum,ans=0;
for(i=0;i<=k+1;++i) dp[i][0]=1;
for(j=k;j;--j)
for(i=1;i*j<=k;++i)
{
for(sum=0,h=1;h<=i;++h) sum=inc(sum,1ll*dp[j+1][h-1]*dp[j][i-h]%P);
sum=1ll*sum*p%P*power(q,j)%P,dp[j][i]=inc(dp[j+1][i],sum);
}
for(++k,tmp[1]=p,i=1;i<=k-1;++i) tmp[i+1]=1ll*dp[1][i]*p%P;
for(s[0]=1,i=1;i<k;++i) for(j=0;j<i;++j) s[i]=inc(s[i],1ll*s[j]*tmp[i-j]%P);
for(i=1;i<=k;++i) f[k-i]=P-tmp[i]; f[k]=1,num[0]=1,a[1]=1,Pow=n+1;
while(Pow)
{
if(Pow&1)
{
for(i=0;i<=k;++i) F[i]=num[i],num[i]=0;
for(i=0;i<=k;++i) for(j=0;j<=k;++j) num[i+j]=inc(num[i+j],1ll*F[i]*a[j]%P);
for(i=2*k;i>=k;--i) for(j=0;j<=k;++j) num[i+j-k]=dec(num[i-k+j],1ll*num[i]*f[j]%P);
}
for(i=0;i<=k;++i) F[i]=G[i]=a[i],a[i]=0;
for(i=0;i<=k;++i) for(j=0;j<=k;++j)a[i+j]=inc(a[i+j],1ll*F[i]*G[j]%P);
for(i=2*k;i>=k;--i) for(j=0;j<=k;++j) a[i-k+j]=dec(a[i+j-k],1ll*a[i]*f[j]%P);
Pow>>=1;
}
for(i=0;i<k;++i) ans=inc(ans,1ll*s[i]*num[i]%P);
for(i=0;i<=k+1;++i) for(j=0;j<=k+1;++j) dp[i][j]=0;
for(i=0;i<=k;++i) s[i]=a[i]=num[i]=0;
return 1ll*ans*power(p,P-2)%P;
}
int main()
{
n=read();int k=read();x=read(),y=read(),q=1ll*x*power(y,P-2)%P,p=dec(1,q);
return !printf("%d",dec(solve(k),solve(k-1)));
}
游戏
Luogu
LOJ
UOJ
BZOJ
如果不存在(x)类型的地图，那么我们可以直接2-SAT。
对于一个(x)类型的地图，我们可以枚举它是(a)类型还是(b)类型，不难发现这样可以遍历所有可能的情况。
#include<stack>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<algorithm>
const int N=1000007;
int n,m,tot,dfn[N],bel[N],lim[N];std::vector<int>e[N];std::stack<int>stk;
struct limit{int x,ty1,y,ty2;}a[N];
int read(){int x;scanf("%d",&x);return x;}
int fetch(){char c=getchar();while(isspace(c))c=getchar();return c-'A';}
void add(int u,int v){e[u].push_back(v);}
void tarjan(int u)
{
static int tim,cnt,low[N],ins[N];
dfn[u]=low[u]=++tim,stk.push(u),ins[u]=1;
for(int v:e[u]) if(!dfn[v]) tarjan(v),low[u]=std::min(low[u],low[v]); else if(ins[v]) low[u]=std::min(low[u],dfn[v]);
if(dfn[u]==low[u]) for(++cnt;ins[u];) bel[stk.top()]=cnt,ins[stk.top()]=0,stk.pop();
}
void solve()
{
memset(dfn+1,0,4*tot);
while(!stk.empty()) stk.pop();
for(int i=1;i<=tot;++i) e[i].clear();
for(int i=1;i<=m;++i)
{
int u=a[i].x*2+a[i].ty1-(a[i].ty1>lim[a[i].x]),v=a[i].y*2+a[i].ty2-(a[i].ty2>lim[a[i].y]);
if(a[i].ty1==lim[a[i].x]) continue;
else if(a[i].ty2==lim[a[i].y]) add(u,u^1);
else add(u,v),add(v^1,u^1);
}
for(int i=2;i<=tot;++i) if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;++i) if(bel[2*i]==bel[2*i+1]) return ;
for(int i=1,x;i<=n;++i) x=bel[2*i]>bel[2*i+1],putchar(x+(x>=lim[i])+'A');
std::exit(0);
}
int main()
{
static char str[N];static int cnt,pos[8];
n=read(),read(),scanf("%s",str+1),m=read(),tot=n+n+1;
for(int i=1;i<=m;++i) a[i]={read(),fetch(),read(),fetch()};
for(int i=1;i<=n;++i) lim[i]=str[i]-'a';
for(int i=1;i<=n;++i) if(lim[i]>3) pos[cnt++]=i;
for(int i=0;i<1<<cnt;solve(),++i) for(int j=0;j<cnt;++j) lim[pos[j]]=i>>j&1;
puts("-1");
}
蔬菜
Luogu
LOJ
UOJ
BZOJ
我们一份一份地处理菜怎么卖。
显然，越贵的菜卖出来的越多越有利。
并且对于这个菜，在这个菜即将过期的时候卖显然是最优的。
所以我们每次取出最贵的菜，尽量把它安排在接近过期的时候。这里我们使用并查集来维护前一个可以买菜的日子。
这样安排下来就是时间长度为(mx)天时的卖菜计划，但是当时间更短时我们是不能这样来卖的。
但是我们考虑一下，对于(t)天的卖菜，我们把上面的最前面(t*m)份菜卖出去一定是最优的，并且一定是可行的（与(mx)天的计划相比，有一些菜不卖了，另外有一些提前卖了，这样一定不会不合法）。
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[21],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
void Put(char x){*oS++=x;if(oS==oT)Flush();}
int read(){int x=0;char ch=Get();while(ch>57||ch<48)ch=Get();while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return x;}
void write(LL x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put('
');}
}
using namespace IO;
int max(int a,int b){return a>b? a:b;}
int min(int a,int b){return a<b? a:b;}
const int N=1000007;
int a[N],s[N],c[N],x[N],fa[N],num[N],Q[N];LL ans[N];
priority_queue<P>q;
int Find(int x){return x==fa[x]? x:fa[x]=Find(fa[x]);}
int main()
{
int n=read(),m=read(),k=read(),mx=0,i,cnt=0,w,p,t;
for(i=1;i<=n;++i) a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read(),q.push(P(a[i]+s[i],i));
for(i=1;i<=k;++i) mx=max(mx,Q[i]=read());
for(i=1;i<=mx;++i) fa[i]=i,num[i]=m;
while(!q.empty())
{
w=q.top().fir,p=q.top().sec,q.pop();
if(!(t=Find(x[p]? min(mx,(c[p]-1)/x[p]+1):mx))) continue;
--c[p],--num[t],++cnt;
if(!num[t]) fa[t]=Find(t-1);
if(c[p]) q.push(P(a[p],p));
ans[cnt]=ans[cnt-1]+w;
}
for(i=1;i<=k;++i) write(ans[min(cnt,m*Q[i])]);
return Flush(),0;
}