本文由 发布，转载请注明出处，如有问题请联系我们！ 发布时间: 2021-08-22noip模拟44[我想我以后会碰见计数题就溜走的]
加载中noip仿真模拟44 solutions
这一场抱零的也忒多了，因为我仅有45pts
听说好像是把几身题里边较难的整理出去使我们考试能够顺利通过
好激烈啊，此次的考試我仅有第一题骗了40pts，别的都抱零了
T1 Emotional Flutter
这一我立即用线段树维护保养解集，
那样的，你不能碰到每一个黑块，因此 每一个黑块都相匹配着一个不踩他的范畴
大家用线段树维护保养这种范畴的相交，由于函数值域有点儿大因此 炸了
40pts
#include<bits/stdc .h>
using namespace std;
#define re register int
#define ll long long
const int N=5e5 5;
ll T,s,k,n,cnt,a[N],pre[N];
struct XDS{
int mx[N*15],ls[N*15],rs[N*15],laz[N*15];
int seg,rt;
void clear(){seg=0;rt=0;mx[0]=mx[1]=0;}
int newnode(){ seg;ls[seg]=rs[seg]=mx[seg]=laz[seg]=0;return seg;}
void pushup(int x){
mx[x]=max(mx[ls[x]],mx[rs[x]]);
return ;
}
void pushdown(int x){
if(!laz[x])return ;
if(!ls[x])ls[x]=newnode();
if(!rs[x])rs[x]=newnode();
mx[ls[x]] =laz[x];
mx[rs[x]] =laz[x];
laz[ls[x]] =laz[x];
laz[rs[x]] =laz[x];
laz[x]=0;
return ;
}
void ins(int &x,int l,int r,int ql,int qr){
if(ql>r||qr<l||ql>qr)return ;
if(!x)x=newnode();
if(ql<=l&&r<=qr){
laz[x] ;mx[x] ;
return ;
}
pushdown(x);
int mid=l r>>1;
if(ql<=mid)ins(ls[x],l,mid,ql,qr);
if(qr>mid)ins(rs[x],mid 1,r,ql,qr);
pushup(x);return ;
}
}xds;
signed main(){
//cout<<(sizeof(xds.mx)*4 sizeof(a) sizeof(pre)>>20)<<endl;
//xds.mx[1]=10000;cout<<xds.mx[1]<<endl;
scanf("%lld",&T);
while(T--){cnt=0;
scanf("%lld%lld%lld",&s,&k,&n);
for(re i=1;i<=n;i ){
scanf("%lld",&a[i]),pre[i]=pre[i-1] a[i];
}
for(re i=0;i<=n;i ){
if(i&1)continue;cnt ;
ll tmp=pre[i]%k,l0=-1,r0=-1,l1=-1,r1=-1;
if(a[i 1] tmp s<=k){
l0=0,r0=k-a[i 1]-tmp-s;
xds.ins(xds.rt,0,k-1,l0,r0);
}
if(tmp){
l1=k-tmp,r1=min(l1 k-a[i 1]-s,k-1);
xds.ins(xds.rt,0,k-1,l1,r1);
}
}
if(xds.mx[xds.rt]>=cnt)printf("TAK\n");
else printf("NIE\n");
xds.clear();
}
}
实际上正确的答案也是有\(log\)的，只不过是他的放到了1e5上，可是我的放到了1e9*1e5上，而且室内空间仿佛都不太够
每一次只有超越k个格，那麼大家每一次碰到的点在%k实际意义下都是在一个点上
而且这一点不可以被一切一个黑块遮盖，因此 把全部黑块弄出来
排列，减掉不起作用的，随后去遮盖，假如能寻找缺口便是合理合法的
脚内长为s，立即对黑块的长的 s，
AC_code
#include<bits/stdc .h>
using namespace std;
#define re register int
#define ll long long
const int N=5e5 5;
ll T,s,k,n,a[N],fro;
struct node{
ll l,r;
node(){}
bool operator < (node x)const{
if(l==x.l)return r>x.r;
return l<x.l;
}
}sca[N];
int cnt,mnt;
signed main(){
scanf("%lld",&T);
while(T--){
cnt=0;mnt=0;fro=0;
scanf("%lld%lld%lld",&s,&k,&n);
//if(k<s){printf("NIE\n");continue;}
bool flag=false;
for(re i=1;i<=n;i ){
scanf("%lld",&a[i]);
if(a[i] s>k&&(i&1))flag=true;
}
if(flag||k<s){printf("NIE\n");continue;}
//cout<<"Sb"<<endl;
for(re i=1;i<=n;i ){
if((i^1)&1){fro =a[i];continue;}
a[i] =s;a[i 1]-=s;
ll pl=(fro 1)%k,pr=(fro a[i]-1)%k;
//cout<<i<<" "<<pl<<" "<<pr<<endl;
fro =a[i];
sca[ cnt].l=pl;
if(pr>=pl)sca[cnt].r=pr;
else {
sca[cnt].r=k-1;
sca[ cnt].l=0;
sca[cnt].r=pr;
}
//cout<<i<<" "<<sca[cnt].l<<" "<<sca[cnt].r<<endl;
}
sort(sca 1,sca cnt 1);mnt=1;
for(re i=2;i<=cnt;i ){
if(sca[i].l>=sca[mnt].l&&sca[i].r<=sca[mnt].r)continue;
sca[ mnt]=sca[i];
}
flag=false;
if(sca[1].l!=0||sca[mnt].r!=k-1)flag=true;
//cout<<flag<<endl;
for(re i=1;i<mnt;i ){
if(sca[i].r 1<sca[i 1].l){
//cout<<i<<endl;
flag=true;
}
if(flag)break;
}
//cout<<sca[1].l<<" "<<sca[mnt].r<<endl;
if(flag)printf("TAK\n");
else printf("NIE\n");
}
}
留意边界争端极为ex
T2 Medium Counting
正确的答案与我考试场上想的一样，便是运用后边的尺寸计划方案发布前边的计划方案数
可是我考试场上只有一个基本的构思，沒有实际的完成出去，因此 00000
假如当今字符串数组短得话，后边补0就可以了
随后大家针对当今这一位，大家枚举类型分界线，看什么时候 1
随后立即记忆化搜索就好了
dp二维数组含意：dp[i][j][l][r]表明i位，最少的是c，范畴是l-r，的计划方案数
假如当今这一位被评定为c，那麼前边的字符串数组就不可以依据当今这一位来分辨
只有用后边的标识符来差别她们的尺寸，这个时候就迁移到下一层
最终小小判一下界限就可以了
AC_code
#include<bits/stdc .h>
using namespace std;
#define re register int
#define ll long long
const ll mod=990804011;
ll n,dp[25][28][55][55];
char ch[55][25];
int a[55][25];
ll dfs(int p,int c,int l,int r){
if(dp[p][c][l][r]!=-1)return dp[p][c][l][r];
if(l>r)return dp[p][c][l][r]=1;
if(p>20)return dp[p][c][l][r]=(l==r);
if(c>26)return 0;
dp[p][c][l][r]=dfs(p,c 1,l,r);
//cout<<dp[p][c][l][r]<<endl;
for(re i=l;i<=r;i ){
if((a[i][p]!=c&&a[i][p]!=27)||(a[i][p]==27&&!c))break;
dp[p][c][l][r]=(dp[p][c][l][r] dfs(p 1,0,l,i)*dfs(p,c 1,i 1,r)%mod)%mod;
}
return dp[p][c][l][r];
}
signed main(){
memset(dp,-1,sizeof(dp));
scanf("%lld",&n);
for(re i=1;i<=n;i ){
scanf("%s",ch[i] 1);
for(re j=1;j<=strlen(ch[i] 1);j ){
if(ch[i][j]=='?')a[i][j]=27;
else a[i][j]=ch[i][j]-'a' 1;
}
}
printf("%lld",dfs(1,0,1,n));
}
T3 Huge Counting
这一也是一个更为恶心想吐的记数题，我确实不想说啥了
或是数位dp，害，气人了
她们都说挺显而易见的是可重集排序，吼吼吼，我TM看过大半天才看出去
每一次挑选一个数-1，因此 减的次序便是一个排序，由于许多同一位的加减法是同样的，因此 可多次
那么就立即套公式计算就可以了\(\huge\frac{(\sum{x_i})!}{\prod{x_i!}}\)
因此你只必须分辨奇偶性就可以了（殊不知我考试场上并沒有看到mod2）
用那一个經典公式计算\(sum_2(x!)=\frac{x}{2} \frac{x}{4} \frac{x}{8} .....\)
暴力行为求得话能够 取得40pts的优异成绩
40pts
#include<bits/stdc .h>
using namespace std;
#define re register int
#define ll long long
const int N=15;
const ll mod=990804011;
ll T,k,l[N],r[N],ans,ji[N];
void dfs(int x){
if(x==k 1){
ll tmp=0,sum=0,t=2;
for(re i=1;i<x;i )tmp =ji[i];
tmp/=2;while(tmp)sum =tmp,tmp/=2;
for(re i=1;i<x;i ){
ll now=ji[i]/2;
while(now)sum-=now,now/=2;
}
if(!sum)ans ;
//if(ji[1]!=0)cout<<ji[1]<<endl;
if(ans>mod)ans-=mod;
return ;
}
for(ll i=l[x];i<=r[x];i ){
ji[x]=i-1;dfs(x 1);
}
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&k);ans=0;
for(re i=1;i<=k;i )scanf("%lld%lld",&l[i],&r[i]);
dfs(1);
printf("%lld\n",ans);
}
}
随后你发觉左右两一部分，假如加和沒有进位得话，她们2个有的2的因素数量是同样的
因此 假如想让这种x对答案有奉献，就需要让这种x的二进制表明每一位上最多有一个1
因此 立即多位do，设dp[i][s]表明第i位，卡界限的状况为s，便是每一个x的
留意不必臆想去卡左右界限，由于二维数组开不出来，因此 要容斥，多步的
我是用dfs完成的容斥指数，还可以用1的个数的奇偶性来明确
立即迁移就可以了，我是看了题解编码才会的。。。。。。。
迁移的情况下，我们要先把每一个卡界限的0拿出来，
此刻全是0，计划方案行得通，
再去枚举类型每一个很有可能的1，假如卡界限就需要把界限卡上，
假如流畅，那么就或是原先的界限
AC_code
#include<bits/stdc .h>
using namespace std;
#define re register int
#define ll long long
const int N=15;
const ll mod=990804011;
ll T,k,l[N],r[N],ans,ji[N];
ll f[52][1<<10];
ll get_ans(){
memset(f,0,sizeof(f));
f[50][(1<<k)-1]=1;
for(re i=50;i>=1;i--){
for(re j=0;j<(1<<k);j ){
if(!f[i][j])continue;
ll tmp=0;
for(re l=1;l<=k;l )
if((j>>l-1)&1 && ((ji[l]>>i-1)^1)&1)
tmp|=(1<<l-1);
f[i-1][tmp]=(f[i-1][tmp] f[i][j])%mod;
for(re l=1;l<=k;l )
if(((j>>l-1)^1)&1)f[i-1][tmp]=(f[i-1][tmp] f[i][j])%mod;
else if((ji[l]>>i-1)&1)f[i-1][tmp|(1<<l-1)]=(f[i-1][tmp|(1<<l-1)] f[i][j])%mod;
}
}
ll ret=0;
for(re i=0;i<(1<<k);i )ret=(ret f[0][i])%mod;
return ret;
}
void dfs(int x,int fl){
if(x==k 1){
ans=(ans get_ans()*fl mod)%mod;
return ;
}
ji[x]=r[x];
dfs(x 1,fl);
if(l[x]-1>=0){
ji[x]=l[x]-1;
dfs(x 1,-fl);
}
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&k);ans=0;
for(re i=1;i<=k;i )scanf("%lld%lld",&l[i],&r[i]),l[i]--,r[i]--;
dfs(1,1);
printf("%lld\n",ans);
}
}
T4 标识符清除2
说实话，一开始我连题面都没看懂，
之后发觉是寻找一个和原字符串数组t结合同样的01串
那样的话，大家先寻找全部行得通的t
立即用KMP从n往前跳，全部蹦出来的数，用n减掉它，便是一个行得通的t
随后考虑到结构这一01串，我们要把KMP配对到的全部的长短记下来
假如下一个的长短\(\le\)当今的2倍，那么就立即拷贝以往就可以了
否则的话，我也把正中间的全干成0，随后再跑一边KMP，看一下还是否原先的配对
我是立即将以前的p表针记下来，随后立即跳回去，
要不是原先的配对了，就把最终一位换为1
AC_code
#include<bits/stdc .h>
using namespace std;
#define re register int
const int N=2e5 5;
char ch[N];
int T,n,fail[N],p,len[N],cnt;
int nxt[N],pri[N],tot;
void kmp(int l,int r){
for(re i=l;i<=r;i ){
while(pri[i]!=pri[p 1]&&p)p=nxt[p];
if(pri[i]==pri[p 1])p ;
nxt[i]=p;
}
}
signed main(){
scanf("%d",&T);
while(T--){
memset(fail,0,sizeof(fail));
memset(len,0,sizeof(len));
memset(nxt,0,sizeof(nxt));
memset(pri,0,sizeof(pri));
p=cnt=tot=0;
scanf("%s",ch 1);n=strlen(ch 1);
//cout<<"sb"<<endl;
for(re i=2,j=0;i<=n;i ){
while(ch[i]!=ch[j 1]&&j)j=fail[j];
if(ch[i]==ch[j 1])j ;
//cout<<i<<" "<<j<<endl;
fail[i]=j;
}
int now=n;while(now)len[ cnt]=now,now=fail[now];//cout<<now<<endl;
if(len[cnt]>1)pri[len[cnt]]=1;
kmp(2,len[cnt]);
//cout<<"sb"<<endl;
//cout<<p<<endl;
for(re i=cnt-1;i>=1;i--){
if(len[i]>len[i 1]*2){
kmp(len[i 1] 1,len[i]-len[i 1]-1);
int pi=p;
for(re j=1;j<=len[i 1];j )pri[len[i]-len[i 1] j]=pri[j];
kmp(len[i]-len[i 1],len[i]);
//for(re j=1;j<=len[i];j )cout<<pri[j];cout<<endl;
//cout<<nxt[len[i]]<<endl;
if(nxt[len[i]]!=len[i 1]){
p=pi;pri[len[i]-len[i 1]]=1;
kmp(len[i]-len[i 1],len[i]);
}
}
else {
for(re j=len[i 1] 1;j<=len[i];j )
pri[j]=pri[j-len[i] len[i 1]];
kmp(len[i 1] 1,len[i]);
}
}
for(re i=1;i<=n;i )printf("%d",pri[i]);
printf("\n");
}
}
