6.11 NOI 模拟
2024-10-20 03:29:57
\(T1\)魔法师
\(f(x)\)是各个数位之积，当\(f(x)\ne 0\)，每一位只能是\(1\sim 9\)，考虑数位积的质因数分解只能是\(2,3,5,7\)的形式，考虑对所有的\((a,b,c,d)\)计算满足\(f(x)=2^a\times 3^b\times 5^c\times 7^d\)的\(x\)的数量
这个东西考虑用数位\(dp\)求
\(f[i][0/1][a][b][c][d]\)表示当前已经处理到从高到低第\(i\)为，前\(i\)位的拆分为\(2^a\times 3^b\times 5^c\times 7^d\)的方案数
我们现在得到了\(g[a][b][c][d]\)即满足小于等于\(n\)的所有拆分方案
我们做一个\(Min\)卷积，求一下方案数即可
\(h[a][b][c][d]=\sum g[x_1][x_2][x_3][x_4]\times g[y_1][y_2][y_3][y_4][\min(x_1,y_1)=a,\min(x_2,y_2)=b,\min(x_3,y_3)=c,\min(x_4,y_4)=d]\)
这个过程可以用四维后缀和优化
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int la=60,lb=38,lc=25,ld=25,mod=998244353;
int dp[22][2][64][43][28][28],f[16][65][43][28][28];
ll Ans,n,k;
int sola(int x)
{
if(x==2) return 1;
if(x==4) return 2;
if(x==6) return 1;
if(x==8) return 3;
return 0;
}
int solb(int x)
{
if(x==3) return 1;
if(x==6) return 1;
if(x==9) return 2;
return 0;
}
int solc(int x)
{
if(x==5) return 1;
return 0;
}
int sold(int x)
{
if(x==7) return 1;
return 0;
}
void Init(ll num)
{
int cnt=0,wei[50];
while(num)
{
wei[++cnt]=num%10;
num/=10;
}
reverse(wei+1,wei+1+cnt);
dp[0][1][0][0][0][0]=1;
for(int i=1;i<=cnt;i++)
{
dp[i][0][0][0][0][0]=1;
for(int j=1;j<=9;j++)
{
int ja=sola(j),jb=solb(j),jc=solc(j),jd=sold(j);
for(int a=0;a+ja<=la;a++)
for(int b=0;b+jb<=lb;b++)
for(int c=0;c+jc<=lc;c++)
for(int d=0;d+jd<=ld;d++)
dp[i][0][a+ja][b+jb][c+jc][d+jd]=(1ll*dp[i][0][a+ja][b+jb][c+jc][d+jd]+1ll*dp[i-1][0][a][b][c][d])%mod;
}
for(int j=1,opt=(j==wei[i]);j<=wei[i];j++,opt=(j==wei[i]))
{
int ja=sola(j),jb=solb(j),jc=solc(j),jd=sold(j);
for(int a=0;a+ja<=la;a++)
for(int b=0;b+jb<=lb;b++)
for(int c=0;c+jc<=lc;c++)
for(int d=0;d+jd<=ld;d++)
dp[i][opt][a+ja][b+jb][c+jc][d+jd]=(1ll*dp[i][opt][a+ja][b+jb][c+jc][d+jd]+1ll*dp[i-1][1][a][b][c][d])%mod;
}
}
for(int i=0;i<16;i++)
for(int a=0;a<=la;a++)
for(int b=0;b<=lb;b++)
for(int c=0;c<=lc;c++)
for(int d=0;d<=ld;d++)
{
f[i][a][b][c][d]=(1ll*dp[cnt][0][a][b][c][d]+1ll*dp[cnt][1][a][b][c][d])%mod;
}
for(int i=0;i<16;i++) f[i][0][0][0][0]--;
}
signed main()
{
scanf("%lld%lld",&n,&k);
Init(n);
for(int i=0;i<16;i++)
{
if(i&1)
for(int a=la;a>=0;a--)
for(int b=lb;b>=0;b--)
for(int c=lc;c>=0;c--)
for(int d=ld;d>=0;d--)
f[i][a][b][c][d]=(1ll*f[i][a][b][c][d]+1ll*f[i][a+1][b][c][d])%mod;
if(i&2)
for(int a=la;a>=0;a--)
for(int b=lb;b>=0;b--)
for(int c=lc;c>=0;c--)
for(int d=ld;d>=0;d--)
f[i][a][b][c][d]=(1ll*f[i][a][b][c][d]+1ll*f[i][a][b+1][c][d])%mod;
if(i&4)
for(int a=la;a>=0;a--)
for(int b=lb;b>=0;b--)
for(int c=lc;c>=0;c--)
for(int d=ld;d>=0;d--)
f[i][a][b][c][d]=(1ll*f[i][a][b][c][d]+1ll*f[i][a][b][c+1][d])%mod;
if(i&8)
for(int a=la;a>=0;a--)
for(int b=lb;b>=0;b--)
for(int c=lc;c>=0;c--)
for(int d=ld;d>=0;d--)
f[i][a][b][c][d]=(1ll*f[i][a][b][c][d]+1ll*f[i][a][b][c][d+1])%mod;
}
for(ll i2=0,now2=k;now2;i2++,now2/=2)
for(ll i3=0,now3=now2;now3;i3++,now3/=3)
for(ll i5=0,now5=now3;now5;i5++,now5/=5)
for(ll i7=0,now7=now5,res=0;now7;i7++,now7/=7)
{
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(((i^15)|(j^15))==15) Ans=(1ll*Ans+1ll*f[i][i2+(i&1)][i3+((i&2)!=0)][i5+((i&4)!=0)][i7+((i&8)!=0)]*f[j][i2+(j&1)][i3+((j&2)!=0)][i5+((j&4)!=0)][i7+((j&8)!=0)]%mod)%mod;
}
cout<<Ans<<"\n";
}
\(T2\ Warrior\)
首先当 \(l\) 确定的时候，\(r\) 越大字典序越小，考虑尺取法，每次移动时候判断有多少字典序小，每次查询\(O(n\log n)\)，总复杂度是\(O(n^2\log n)\)
考虑如何在线段树上查询，考虑完全包含进去的字典序必然大。
暴力尺取
#define Eternal_Battle ZXK
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
int w[MAXN],b[MAXN],tot,n,k;
map<int,int>mp;
namespace Seg
{
//支持动态插入值
//然后再这棵线段树上继续尺取找比他小的
#define ls (now<<1)
#define rs ((now<<1)|1)
struct Tr
{
int l,r,num;
bool del;
}tr[MAXN<<2];
void build(int now,int l,int r)
{
tr[now].l=l,tr[now].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void push_up(int now)
{
tr[now].del=(tr[ls].del|tr[rs].del);
}
void change(int now,int poz,int k)
{
if(poz==0) return ;
if(tr[now].l==poz&&tr[now].r==poz)
{
tr[now].num+=k;
if(tr[now].num) tr[now].del=true;
else tr[now].del=false;
return ;
}
int mid=(tr[now].l+tr[now].r)>>1;
if(poz<=mid)change(ls,poz,k);
else change(rs,poz,k);
push_up(now);
}
bool query(int now)
{
if(tr[now].l==tr[now].r)
{
if(tr[now].num>0) return true;
return false;
}
if(tr[ls].del) return query(ls);
return query(rs);
}
}
int Min_num(int l,int r)
{
int res=0,i,j;
//计算比他小的
// cout<<"Sit: "<<l<<" "<<r<<"\n";
for(i=1,j=0;i<=n;i++)
{
while(Seg::query(1)&&j<=n)
{
Seg::change(1,w[++j],-1);
}
res+=(n-j+1);
// if(l==5&&r==30)cout<<"sol: "<<i<<" "<<j<<"\n";
Seg::change(1,w[i],1);
}
for(int poi=i;poi<=j;poi++)
{
Seg::change(1,w[poi],1);
}
// cout<<"res: "<<res<<"\n";
return res;
}
int bc[MAXN];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
b[i]=w[i];
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
if(!mp[b[i]]) mp[b[i]]=++tot,bc[tot]=b[i];
}
Seg::build(1,1,tot);
for(int i=1;i<=n;i++) w[i]=mp[w[i]];
for(int l=1,r=0;l<=n;l++)
{
//尺取，往右走直到字典序小于k
while(r<n)
{
Seg::change(1,w[++r],1);
if(Min_num(l,r)<k)
{
Seg::change(1,w[r--],-1);
break;
}
else if(Min_num(l,r)==k) break;
}
if(Min_num(l,r)==k)
{
// cout<<l<<" "<<r<<"\n";
map<int,int>t;
for(int i=l;i<=r;i++)
{
t[bc[w[i]]]++;
}
for(map<int,int>::iterator it=t.begin();it!=t.end();it++)
{
for(int i=1;i<=it->second;i++)
{
cout<<it->first<<" ";
}
}
exit(0);
}
Seg::change(1,w[l],-1);
if(Min_num(l+1,r)==k)
{
map<int,int>t;
for(int i=l+1;i<=r;i++)
{
t[bc[w[i]]]++;
}
for(map<int,int>::iterator it=t.begin();it!=t.end();it++)
{
for(int i=1;i<=it->second;i++)
{
cout<<it->first<<" ";
}
}
exit(0);
}
}
}
考虑在这个基础上加一些随机化，考虑每次随机一个位置，然后如果小于\(k\)的话，就把小于\(k\)的删去，更新一下\(k\)，期望下\(O(\log n)\)只剩下一个，单次查询\(O(n\log n)\)，总复杂度\(O(n\log^2 n)\)
#include<bits/stdc++.h>
#define rint register int
#define mid ((l+r)>>1)
#define ll long long
#define M 131072
using namespace std;
int Rand(int l,int r)
{
return rand()*rand()%(r-l+1)+l;
}
int T=256,n,k,s[1000001],L[1000001],R[1000001],lim[1000001];
int tr[1000001],cntr[1000001];
void build()
{
for(int i=1;i<=n;++i)
{
if(cntr[i]>0) tr[i+M]=1;
if(cntr[i]<0) tr[i+M]=-1;
if(cntr[i]==0) tr[i+M]=0;
}
for(int i=M-1;i>=1;--i) tr[i]=tr[i<<1]?tr[i<<1]:tr[i<<1|1];
}
void change(int p,int v)
{
int now=p+M;
cntr[p]+=v;
if(cntr[p]>0) tr[now]=1;
if(cntr[p]<0) tr[now]=-1;
if(cntr[p]==0) tr[now]=0;
p=now;
p=(p>>1);
while(p) tr[p]=tr[p<<1]?tr[p<<1]:tr[p<<1|1],p=(p>>1);
}
signed main()
{
double t=clock();
srand(20050323);
scanf("%d %d",&n,&k);
for(rint i=1;i<=n;++i) scanf("%d",&s[i]);
for(rint i=1;i<=n;++i) L[i]=i,R[i]=n;
while(clock()-t<=1400000&&T--)
{
ll now=0;
for(rint i=1;i<=n;++i) now+=R[i]-L[i]+1;
now=Rand(0,now-1);
for(rint i=1;i<=n;++i) cntr[i]=0;
rint nowl,nowr;
for(rint i=1;i<=n;++i)
{
if(L[i]>R[i]) continue;
if(now>=R[i]-L[i]+1) now-=R[i]-L[i]+1;
else
{
nowl=i,nowr=L[i]+now;
break;
}
}
for(rint i=nowl;i<=nowr;++i) ++cntr[s[i]];
build();
ll tot=0;
for(rint l=1,r=0;l<=n;++l)
{
while(r<=n&&(r<l-1||tr[1]>=0))
{
if(++r<=n)
{
change(s[r],-1);
}
}
tot+=n-r+1;
lim[l]=r-1;
change(s[l],1);
}
if(tot<k) for(rint i=1;i<=n;++i) R[i]=min(R[i],lim[i]);
else for(rint i=1;i<=n;++i) L[i]=max(L[i],lim[i]+1);
}
vector<int> res;
for(int i=1;i<=n;++i)
if(L[i]<=R[i])
{
for(rint j=i;j<=L[i];++j) res.push_back(s[j]);
sort(res.begin(),res.end());
for(rint i=0;i<res.size();++i) printf("%d ",res[i]);
exit(0);
}
}
\(T3\)最佳观影
考虑分成两种情况
一种是没有放人的行，另一种是已经放人的行，首先放人的行左右两边可以分开维护
我们每次需要查询人数\(\times\)右端点最小的，考虑用线段树维护一下到边界的人数，在满足条件里选一个最小的就好了，考虑维护二元组\((r,r+d)\)，由于我们贡献是\(Mid-r+Mid-d\)
第一维建立线段树，第二维在叶子上维护一个堆，就是查区间最大了
#include<bits/stdc++.h>
using namespace std;
int n,k,x1;
struct node{
int x,y,z;
friend bool operator < (node a,node b)
{
if(a.z!=b.z) return a.z>b.z;
if(a.x!=b.x) return a.x>b.x;
return a.y>b.y;
}
}tr[600100];
priority_queue<node> q[150010];
void build(int x,int l,int r)
{
tr[x].x=0,tr[x].y=0,tr[x].z=1<<30;
if(l==r) return;
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
long long cal(int l,int r)
{
return 1ll*(l+r)*(r-l+1)>>1;
}
long long calc(node a,int b)
{
if((a.y<k&&a.y-b<0)||(a.y>k&&a.y+b>k+k))return 1ll<<60;
return 1ll*b*abs(a.x-k)+cal(abs(k-a.y),abs(k-a.y)+b-1);
}
long long calc(int a,int b)
{
if(!a||a==k+k)return 1ll<<60;
return 1ll*b*abs(a-k)+cal(1,b-1>>1)+cal(1,b>>1);
}
void ins(int x,int l,int r,int p,node v)
{
if(l==r)
{
q[l].push(v);
tr[x]=q[l].top();
return;
}
int mid=(l+r)>>1;
if(p<=mid) ins(x<<1,l,mid,p,v);
else ins(x<<1|1,mid+1,r,p,v);
tr[x]=max(tr[x<<1],tr[x<<1|1]);
}
void erase(int x,int l,int r,int pos)
{
if(l==r)
{
q[l].pop();
tr[x]=q[l].size()?q[l].top():(node){0,0,1<<30};
return;
}
int mid=(l+r)>>1;
if(pos<=mid) erase(x<<1,l,mid,pos);
else erase(x<<1|1,mid+1,r,pos);
tr[x]=max(tr[x<<1],tr[x<<1|1]);
}
node query(int x,int l,int r,int pos)
{
if(l>=pos)
{
return tr[x];
}
int mid=(l+r)>>1;
if(pos>mid) return query(x<<1|1,mid+1,r,pos);
return max(query(x<<1,l,mid,pos),query(x<<1|1,mid+1,r,pos));
}
void slo(int a,int b)
{
cout<<a<<" "<<k-(b>>1)<<" "<<k+(b-1>>1)<<"\n";
if((b>>1)+1<k)
{
ins(1,1,k,k-1-(b>>1),(node){a,k-1-(b>>1),abs(a-k)+1+(b>>1)});
}
if((b-1>>1)+1<k)
{
ins(1,1,k,k-1-(b-1>>1),(node){a,k+1+(b-1>>1),abs(a-k)+1+(b-1>>1)});
}
}
int main()
{
scanf("%d%d%d",&n,&k,&x1);
k=(k+1)>>1;
build(1,1,k);
slo(k,x1);
int L=k-1,R=k+1;
for(int i=2,x;i<=n;i++)
{
scanf("%d",&x);
node now=x<=k?query(1,1,k,x):(node){0,0,1<<30};
if(calc(L,x)<=min(calc(now,x),calc(R,x)))
{
if(!L) cout<<"-1\n";
else slo(L--,x);
}
else
{
if(calc(R,x)<calc(now,x))
{
slo(R++,x);
}
else
{
// cout<<1<<endl;
if(now.y<k)
{
erase(1,1,k,now.y);
cout<<now.x<<" "<<now.y-x+1<<" "<<now.y<<"\n";
now.y-=x,now.z+=x;
if(now.y) ins(1,1,k,now.y,now);
}
else
{
erase(1,1,k,k+k-now.y);
cout<<now.x<<" "<<now.y<<" "<<now.y+x-1<<"\n";
now.y+=x,now.z+=x;
if(now.y<k+k) ins(1,1,k,k+k-now.y,now);
}
}
}
}
}
最新文章
- 曝光最新WIN10系统32位，64位系统ghost版
- java 复制字串算法
- 利用 PortableBasemapServer 发布地图服务
- HowTo Perform the spatial selection 'Share a line segment with' using ArcObjects
- codeforces 489B. BerSU Ball 解题报告
- Photoshop: 机关单位公章
- 《你是我的小羊驼》游戏源码 v1.0
- HDU 1166 敌兵布阵 （线段树 单点更新）
- DevExpress GridView属性设置 z
- [简历] PHP 技能关键字列表
- [转载]使用兼容ie6 ie7 ie8 FF的text-overflow:ellips
- ISO14443协议中，卡片对RATS,PPS,IBLOCK的处理约定
- kafka消息中间件及java示例
- iOS通过代码关闭程序
- Java 线程基本知识
- WPF 窗口居中 & 变更触发机制
- 【安富莱】【RL-TCPnet网络教程】第10章 RL-TCPnet网络协议栈移植（FreeRTOS）
- Python中怎么读写文件
- tab页的使用方法
- js判断输入的字符是否是汉字