2021.10.9考试总结[NOIP模拟72]
2024-09-22 06:00:25
T1出了个大阴间题
状压\(DP\)，记当前状态的代价和与方案数。状态\(\Theta(2^nn)\)，转移\(\Theta(n)\)。
发现每个状态的最大值只会是所选集合的\(max\)或加一。于是可以降维。（我太弱考场上没想到
\(code:\)
T1
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
auto read=[]()->int{
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
};
auto write=[](int x,int sp)->void{
char ch[20]; int len=0;
if(x<0){ x=~x+1; putchar('-'); }
do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);
for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
};
auto ckmax=[](int& x,int y)->void{ x=x<y?y:x; };
auto ckmin=[](int& x,int y)->void{ x=x<y?x:y; };
} using namespace IO;
const int p=1e9+7;
int n,U,k,tot,ans,mxa,a[20],b[20],num[50];
int f[1<<18][50],g[1<<18][50];
unordered_map<int,int>has;
auto id=[](int x)->int{
if(has[x]) return has[x];
has[x]=++tot; num[tot]=x;
return tot;
};
auto getnum=[](int x)->int{
int res=0;
for(;x;x>>=1) res+=x&1;
return res;
};
signed main(){
freopen("repair.in","r",stdin);
freopen("repair.out","w",stdout);
n=read(); k=read(); U=(1<<n)-1;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=(b[i-1]<<1)+1;
for(int i=1;i<=n;i++)
f[1<<i-1][id(a[i])]=0,g[1<<i-1][id(a[i])]=1;
for(int tmp,rd,u=1;u<(1<<n);u++){
rd=getnum(u)-1; tmp=tot;
for(int i=1;i<=tmp;i++) if(g[u][i]){
for(int j=1;j<=n;j++) if(!(u&(1<<j-1))){
int now=id((num[i]==a[j])?(a[j]+1):max(num[i],a[j]));
int st=u|(1<<j-1);
(f[st][now]+=f[u][i]+(k*num[now]%p+b[rd])*g[u][i]%p)%=p;
(g[st][now]+=g[u][i])%=p;
}
}
}
for(int i=1;i<=tot;i++) ckmax(mxa,num[i]);
for(int i=1;i<=tot;i++)
if(mxa==num[i]) (ans+=f[U][i])%=p;
write(mxa,' '); write(ans,'\n');
return 0;
}
T2最简单辣快来做
考场上过分相信\(\Theta(1)\)光速幂，只打了个暴力，跟快速幂一个分。。
考虑用\(x=x_i\)与\(y=y_i\)将平面分为若干小矩形，那么这些矩形节点位置的代价可以通过四个二分前缀和预处理实现。
找到询问的位置所在的矩形，分别对四个矩形顶点位置不同方向的前缀和乘上矩形内部的贡献即可。
\(code:\)
T2
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
auto read=[]()->int{
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
};
auto write=[](int x,int sp)->void{
char ch[20]; int len=0;
if(x<0){ x=~x+1; putchar('-'); }
do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);
for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
};
auto ckmax=[](int& x,int y)->void{ x=x<y?y:x; };
auto ckmin=[](int& x,int y)->void{ x=x<y?x:y; };
} using namespace IO;
const int NN=2010;
int n,q,w,d,p,a,b,res,h[NN],x[NN],y[NN];
int xx[NN],yy[NN],pre[NN][NN][5];
namespace flash_power{
const int MM=1e5;
int u,v,blo,pwa[MM],pwb[MM],pra[MM],prb[MM];
int A(int op){
u=op/blo; v=op%blo;
return pra[u]*pwa[v]%p;
}
int B(int op){
u=op/blo; v=op%blo;
return prb[u]*pwb[v]%p;
}
void init(){
pwa[0]=pwb[0]=pra[0]=prb[0]=1;
blo=ceil(sqrt(1.0*max(w,d)));
for(int i=1;i<=blo;i++){
pwa[i]=pwa[i-1]*a%p;
pwb[i]=pwb[i-1]*b%p;
}
for(int i=1;i<=blo;i++){
pra[i]=pra[i-1]*pwa[blo]%p;
prb[i]=prb[i-1]*pwb[blo]%p;
}
}
} using namespace flash_power;
void prework(){
sort(xx+1,xx+n+1); sort(yy+1,yy+n+1); xx[n+1]=xx[n]; yy[n+1]=yy[n];
for(int i=1;i<=n;i++){
int X=lower_bound(xx+1,xx+n+1,x[i])-xx;
int Y=lower_bound(yy+1,yy+n+1,y[i])-yy;
pre[X][Y][1]=pre[X][Y][2]=pre[X][Y][3]=pre[X][Y][4]=h[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) (pre[i][j][1]+=pre[i][j-1][1]*B(yy[j]-yy[j-1]))%=p;
for(int j=1;j<=n;j++) (pre[i][j][1]+=pre[i-1][j][1]*A(xx[i]-xx[i-1]))%=p;
for(int j=n;j;j--) (pre[i][j][2]+=pre[i][j+1][2]*B(yy[j+1]-yy[j]))%=p;
for(int j=n;j;j--) (pre[i][j][2]+=pre[i-1][j][2]*A(xx[i]-xx[i-1]))%=p;
}
for(int i=n;i;i--){
for(int j=1;j<=n;j++) (pre[i][j][3]+=pre[i][j-1][3]*B(yy[j]-yy[j-1]))%=p;
for(int j=1;j<=n;j++) (pre[i][j][3]+=pre[i+1][j][3]*A(xx[i+1]-xx[i]))%=p;
for(int j=n;j;j--) (pre[i][j][4]+=pre[i][j+1][4]*B(yy[j+1]-yy[j]))%=p;
for(int j=n;j;j--) (pre[i][j][4]+=pre[i+1][j][4]*A(xx[i+1]-xx[i]))%=p;
}
}
int query(int qx,int qy){
int dx=lower_bound(xx+1,xx+n+1,qx)-xx,ux=dx-1;
int dy=lower_bound(yy+1,yy+n+1,qy)-yy,uy=dy-1;
int res=0;
if(ux &&uy ) (res+=pre[ux][uy][1]*A(qx-xx[ux])%p*B(qy-yy[uy]))%=p;
if(ux &&dy<=n) (res+=pre[ux][dy][2]*A(qx-xx[ux])%p*B(yy[dy]-qy))%=p;
if(dx<=n&&uy ) (res+=pre[dx][uy][3]*A(xx[dx]-qx)%p*B(qy-yy[uy]))%=p;
if(dx<=n&&dy<=n) (res+=pre[dx][dy][4]*A(xx[dx]-qx)%p*B(yy[dy]-qy))%=p;
return res;
}
signed main(){
freopen("satellite.in","r",stdin);
freopen("satellite.out","w",stdout);
n=read(); q=read(); w=read(); d=read(); p=read(); a=read(); b=read();
for(int i=1;i<=n;i++)
h[i]=read(),xx[i]=x[i]=read(),yy[i]=y[i]=read();
init(); prework();
while(q--){
int qx=read(),qy=read();
write(query(qx,qy),'\n');
}
return 0;
}
/*
4 1 9 9 100000000 2 3
1 3 4
2 1 9
1 3 5
2 4 6
5 5
*/
T3是我的你不要抢
不会\(AC\)自动机加\(Trie\)的\(NB\)操作，整了个分块。
设块长为\(len\)，那么长度大于等于\(len\)的串只有\(\frac{sum}{len}\)，预处理即可。剩下的串哈希暴力跑。
最优串长为\(\frac{sum}{q}\)。复杂度\(\Theta(sum\sqrt q)\)，但很松，肯定跑不满。
\(code:\)
T3
#include<bits/stdc++.h>
using namespace std;
namespace IO{
auto read=[]()->int{
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
};
auto write=[](int x,int sp)->void{
char ch[20]; int len=0;
if(x<0){ x=~x+1; putchar('-'); }
do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);
for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
};
auto ckmax=[](int& x,int y)->void{ x=x<y?y:x; };
auto ckmin=[](int& x,int y)->void{ x=x<y?x:y; };
} using namespace IO;
const int NN=600010;
int n,q,res,sum,len[NN];
vector<int>vec;
map<pair<int,int>,int>mp;
char s[NN];
namespace Hash{
typedef unsigned long long ULL;
const ULL base=131;
ULL *has[NN],pw[NN];
ULL get(int id,int l,int r){ return has[id][r]-has[id][l-1]*pw[r-l+1]; }
void init(){
pw[0]=1;
for(int i=1;i<=n;i++){
scanf("%s",s+1);
len[i]=strlen(s+1);
has[i]=new ULL[len[i]+5];
sum+=len[i];
for(int j=1;j<=len[i];j++)
has[i][j]=has[i][j-1]*base+(ULL)s[j];
}
for(int i=1;i<=sum;i++) pw[i]=pw[i-1]*base;
}
} using namespace Hash;
namespace blocks{
int blo;
void prework(){
blo=1.0*sum/sqrt(1.0*q);
for(int i=1;i<=n;i++)
if(len[i]>=blo) vec.push_back(i);
for(auto a:vec) for(auto b:vec) if(a!=b){
int res=0;
for(int i=min(len[a],len[b]);i;i--)
if(get(a,len[a]-i+1,len[a])==get(b,1,i)){ res=i; break; }
mp[make_pair(a,b)]=res;
}
}
int query(int x,int y){
if(len[x]>=blo&&len[y]>=blo&&x!=y)
return mp[make_pair(x,y)];
for(int i=min(len[x],len[y]);i;i--)
if(get(x,len[x]-i+1,len[x])==get(y,1,i)) return i;
return 0;
}
} using namespace blocks;
signed main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
n=read(); q=read(); init(); prework();
while(q--){
int x=read(),y=read();
write(query(x,y),'\n');
}
return 0;
}
/*
3 6
wwq
eew
qwe
1 2
2 3
1 3
2 1
3 2
3 1
*/
T4显然也是我整的
\(NB\)题，看不大懂。%战神就完了。
最新文章
- Php compiler for .NET framework
- js-函数eval
- crossplatform---Nodejs in Visual Studio Code 07.学习Oracle
- iframe中子页面通过js计算高度（使得页面不会显示不全）
- iOS 发布流程
- BZOJ 1103: [POI2007]大都市meg（dfs序，树状数组）
- 设计模式二：MVC
- SQL Server Alwayson可用性副本会话期间的可能故障
- 关于移动端自动化测试-Appium的搭建
- java 学习之环境配置
- nginx功能扩展整理
- Python字符串操作之字符串分割与组合
- 校正PHP服务器时间不准的问题
- <Consistency><of HBase><CAP><ACID>
- Go编写一个比特币交易自动出价程序
- html 简单的预缓存
- 第七届蓝桥杯C-B-10-最大比例/gcd变形
- 18-拍卖叫价(hdu2149 巴什博弈)
- iOS 控制台打印unicode 转中文汉字 UTF8String
- vue学习第四天 ------ 临时笔记