NOIP2017提高组 模拟赛21(总结)
程序员文章站
2022-03-14 19:27:50
...
NOIP2017提高组 模拟赛21(总结)
第一题 纸牌游戏 (分解质因数,尺取法)
【题目描述】
【解题思路】
问题转化为有多少个【L,R】使得a[]的L~R这个区间乘起来是k的倍数。
枚举L,可以发现R具有单调性,也就是若【L,R】合法,那么【L,R+1】也合法。
用尺取法就可以解决。
时间复杂度:
【代码】
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,k;
const int N=1e5;
int d[N+100],kl,sl,ty[N+100],cnt;
ll f[N+100];
ll ans;
int pck(int x,int v)
{
for(int i=1;i<=cnt;i++)
{
for(;!(x%ty[i]);)
{
x/=ty[i];
f[i]+=v;
}
}
return x;
}
bool check()
{
if(sl<0) return 0;
for(int i=1;i<=cnt;i++)
if(f[i]<0) return 0;
return 1;
}
int main()
{
freopen("1979.in","r",stdin);
freopen("1979.out","w",stdout);
scanf("%d%d",&n,&k);
cnt=0; ans=0ll; kl=k;
for(int i=2;i*i<=k;i++)
{
if(!(k%i))
{
ty[++cnt]=i;
for(;!(kl%i);) kl/=i,f[cnt]--;
}
} sl=-1;
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
int la=0;
for(int i=1;i<=n;i++)
{
int yu;
while(!check() && la<n)
{
la++;
yu=pck(d[la],1);
if(!(yu%kl)) sl++;
}
if(check()) ans+=(n-la+1);
yu=pck(d[i],-1);
if(!(yu%kl)) sl--;
}
printf("%lld\n",ans);
return 0;
}
第二题 XOR (线段树)
【题目描述】
【解题思路】
异或有结合律,交换律。
但题目需要求和,加法不能跟异或同时做。
其实把每一个数字x,分解成
若【L,R】这一区间xor 2^k,则把线段树k中的【L,R】范围的1变成0,0变成1。(统计1的个数sum1就行,打反转标记。反转的话1的个数就等于R-L+1-sum1)
【代码】
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int kp=20;
int n;
int d[N];
struct data
{
int s,la;
} T[21][N<<2];
ll ans;
int gd(int x,int y)
{
return ((x&(1<<y))>0);
}
void build(int w,int ro,int L,int R)
{
if(L==R)
{
T[w][ro].s=gd(d[L],w);
return;
}
int Mid=(L+R)>>1;
build(w,ro<<1,L,Mid); build(w,ro<<1|1,Mid+1,R);
T[w][ro].s=T[w][ro<<1].s+T[w][ro<<1|1].s;
}
void down(int w,int ro,int L,int R)
{
if(T[w][ro].la)
{
int Mid=(L+R)>>1;
T[w][ro].la=0;
T[w][ro<<1].la^=1; T[w][ro<<1|1].la^=1;
T[w][ro<<1].s=(Mid-L+1)-T[w][ro<<1].s;
T[w][ro<<1|1].s=(R-Mid)-T[w][ro<<1|1].s;
}
}
void updata(int w,int ro,int L,int R,int li,int ri)
{
if(L>ri || R<li ) return;
if(li<=L && R<=ri)
{
T[w][ro].la^=1;
T[w][ro].s=(R-L+1)-T[w][ro].s;
return;
}
int Mid=(L+R)>>1;
down(w,ro,L,R);
updata(w,ro<<1,L,Mid,li,ri); updata(w,ro<<1|1,Mid+1,R,li,ri);
T[w][ro].s=T[w][ro<<1].s+T[w][ro<<1|1].s;
}
int query(int w,int ro,int L,int R,int li,int ri)
{
if(L>ri || R<li ) return 0;
if(li<=L && R<=ri) return T[w][ro].s;
int Mid=(L+R)>>1;
down(w,ro,L,R);
int x1=query(w,ro<<1,L,Mid,li,ri),x2=query(w,ro<<1|1,Mid+1,R,li,ri);
T[w][ro].s=T[w][ro<<1].s+T[w][ro<<1|1].s;
return x1+x2;
}
int main()
{
freopen("1980.in","r",stdin);
freopen("1980.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
for(int i=0;i<kp;i++) build(i,1,1,n);
int Q;
scanf("%d",&Q);
while(Q--)
{
int a,b,c,d;
scanf("%d",&c);
if(c==1)
{
scanf("%d%d",&a,&b);
ans=0ll;
for(int i=0;i<kp;i++)
{
int yu=query(i,1,1,n,a,b);
ans+=(ll)yu*(1<<i);
}
printf("%lld\n",ans);
} else
if(c==2)
{
scanf("%d%d%d",&a,&b,&d);
for(int i=0;i<kp;i++)
if(gd(d,i))
{
updata(i,1,1,n,a,b);
}
}
}
}
第三题 豆腐 (数位DP+AC自动机)
【题目描述】
【解题思路】
首先想到的就是数位DP(LR那么大,除此之外也没什么可以做的了)。
DP的状态:F[第i位][字符串的状态][当前的麻辣值][是否有前导零][是否达到上界]=方案数
但,如果把所有的字符串的状态直接记下来,是很难转移的,不可能再重新匹配。
所以想到建AC自动机来维护,字符串的状态也就是在AC自动机上的位置T(先预处理出字符串所对应的麻辣值)。枚举下一位的数字x(0~19),直接转移到T->c[x]的位置,再加上麻辣值,累计方案数。
最后统计所有位置,麻辣值不超过k的方案数的和。
【代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mods=1000000007;
const int Ln=505;
struct data { int fail,fa,r[21],s; } T[Ln];
int dl[210],dr[210],q[210];
int root,n,m,k,cnt;
int f[2][205][705][2][2];
void buildfail()
{
T[root].fail=root; T[root].fa=root; T[root].s=0;
int head=1,tail=1; q[1]=root;
while(head<=tail)
{
int fnow=q[head++];
for(int i=0;i<m;i++)
if(T[fnow].r[i])
{
int v=T[fnow].r[i];
int k=T[fnow].fail;
bool flag=(fnow!=root);
while(!T[k].r[i])
{
if(k==root) { flag=0; break; }
k=T[k].fail;
}
if(flag) T[v].fail=T[k].r[i]; else T[v].fail=root;
(T[v].s+=T[T[v].fail].s)%=mods;
q[++tail]=v;
} else T[fnow].r[i]=T[T[fnow].fail].r[i];
}
}
int getans(int A[])
{
memset(f,0,sizeof(f)); f[0][0][0][0][0]=1;
for(int i=0,w=0;i<A[0];i++,w^=1)
{
memset(f[w^1],0,sizeof(f[w^1]));
for(int j=0;j<=cnt;j++)
for(int h=0;h<=k;h++)
for(int p1=0;p1<2;p1++)
for(int p2=0;p2<2;p2++)
if(f[w][j][h][p1][p2])
{
for(int g=0;g<=((p2)?(m-1):(A[i+1]));g++)
{
int nex=((p1) || (g>0))?(T[j].r[g]):(0);
(f[w^1][nex][h+T[nex].s][p1|(g>0)][p2|(g<A[i+1])]+=f[w][j][h][p1][p2])%=mods;
}
}
}
int res=0;
for(int i=0;i<=cnt;i++)
for(int h=0;h<=k;h++)
for(int p1=0;p1<2;p1++)
for(int p2=0;p2<2;p2++)
(res+=f[(A[0]&1)][i][h][p1][p2])%=mods;
return res;
}
int main()
{
freopen("1981.in","r",stdin);
freopen("1981.out","w",stdout);
scanf("%d%d%d",&n,&m,&k); cnt=0; root=0;
scanf("%d",&dl[0]); for(int i=1;i<=dl[0];i++) scanf("%d",&dl[i]);
scanf("%d",&dr[0]); for(int i=1;i<=dr[0];i++) scanf("%d",&dr[i]);
dl[dl[0]]--;
for(int i=dl[0];i>=1;i--)
if(dl[i]<0) dl[i]+=m,dl[i-1]--; else break;
for(int i=1;i<=n;i++)
{
int a,cd;
scanf("%d",&a);
int now=root;
for(int i=1;i<=a;i++)
{
scanf("%d",&cd);
if(!T[now].r[cd]) { cnt++; T[cnt].fa=now; T[now].r[cd]=cnt; }
now=T[now].r[cd];
}
scanf("%d",&cd);
(T[now].s+=cd)%=mods;
}
buildfail();
printf("%d\n",((getans(dr)-getans(dl))%mods+mods)%mods);
return 0;
}
上一篇: Flink
下一篇: 买电竞显示器的理由我给你3个!