2018.10.16 NOIP模拟赛
时间：2h(实际)
期望得分：100+100+20
实际得分：100+100+100
T3：数据较水+时限较大+常数小+std也就是个暴力!!! = 暴力AC = 休闲半上午 = 辣鸡题目
A 购物shop
直接nth_element。
因为\(m\leq100\)，堆也是可以的。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod 1000000000
typedef long long LL;
const int N=1e7+3;
int A[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
int n=read(),m=read();
for(register int i=1,x=read(),y=read(); i<=n; ++i)
A[i]=(1ll*A[i-1]*y+x)%mod;//, printf("A[%d]=%d\n",i,A[i]);
std::nth_element(A+1,A+m,A+1+n);
LL ans=0;
for(int i=1; i<=m; ++i) ans+=A[i];
printf("%I64d\n",ans);
return 0;
}
B 期望exp(DP 期望 按位计算)
对每位分别DP计算概率，乘上它的贡献就ok了。
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define BIT 30
typedef long long LL;
const int N=1e5+5;
int n,opt[N],A[N];
double P[N],P2[N];//p:exist p2:disappear
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline double readdb()
{
double x=0,y=0.1;register char c=gc();
for(; !isdigit(c)&&c!='.'; c=gc());
for(; isdigit(c); x=x*10+c-'0',c=gc());
for(c=='.'&&(c=gc()); isdigit(c); x+=(c-'0')*y,y*=0.1,c=gc());
return x;
}
namespace Subtask1
{
double Ans=0;
void DFS(int x,int val,double p)
{
if(x>n) {Ans+=p*val; return;}
DFS(x+1,opt[x]?(opt[x]==1?val|A[x]:val^A[x]):val&A[x],p*P[x]),
DFS(x+1,val,p*P2[x]);
}
void Main()
{
DFS(1,0,1), printf("%.1lf\n",Ans);
}
}
double Solve(int x)
{//p:exist p2:disappear
static double f[N][2];
f[0][0]=1, f[0][1]=0;
for(int i=1; i<=n; ++i)//,printf("f[%d][0]=%.7lf f[%d][1]=%.7lf\n",i-1,f[i-1][0],i-1,f[i-1][1]))
if(!opt[i])//&
if(A[i]>>x&1) f[i][0]=f[i-1][0], f[i][1]=f[i-1][1];
else f[i][0]=f[i-1][0]+f[i-1][1]*P[i], f[i][1]=f[i-1][1]*P2[i];
else if(opt[i]==1)//|
if(A[i]>>x&1) f[i][0]=f[i-1][0]*P2[i], f[i][1]=f[i-1][0]*P[i]+f[i-1][1];
else f[i][0]=f[i-1][0], f[i][1]=f[i-1][1];
else//^
if(A[i]>>x&1) f[i][0]=f[i-1][0]*P2[i]+f[i-1][1]*P[i], f[i][1]=f[i-1][0]*P[i]+f[i-1][1]*P2[i];
else f[i][0]=f[i-1][0], f[i][1]=f[i-1][1];
// printf("bit:%d p:%.7lf\n",x,f[n][1]);
return f[n][1];
}
int main()
{
freopen("exp.in","r",stdin);
freopen("exp.out","w",stdout);
n=read();
for(int i=1; i<=n; ++i) opt[i]=read();
for(int i=1; i<=n; ++i) A[i]=read();
for(int i=1; i<=n; ++i) P2[i]=readdb(),P[i]=1-P2[i];
// if(n<=22) return Subtask1::Main(),0;
double ans=0;
for(int i=0,pw2=1; i<=BIT; ++i) ans+=Solve(i)*pw2, pw2<<=1;
printf("%.1lf\n",ans);
return 0;
}
C 魔法迷宫maze(状压 暴力)
因为边权只有\(2\)种，考虑预处理一次往上\(t\)步，那每个点的状态只有\(2^t\)种。
我们需要算\(f[s][k][rest]\)，表示当前点\(x\)上面\(t\)条边的状态为\(s\)，询问的\(K_i=k\)，到\(x\)时剩余可走距离为\(rest\)。
记两种边权分别为\(mn,mx\)，预处理复杂度\(O(2^t(t\times mx)^2)\)。令\(t=6\)好了。
这样当\(K_i\leq6mx\)时，一次至多走\(6\)步，可以直接这么\(6\)步\(6\)步往上跳。距离不足\(6\)时暴力跳。
\(K_i>6mx\)时，用上面预处理的每个点跳\(6\)步的位置及花费，不断每次跳\(6\)步。跳不了\(6\)步时，我们再预处理每个剩余可走距离为\(rest\in[1,6mx)\)时最远能到哪。
通过大量预处理，每次跳\(6\)步，就把暴力\(O(n^2)\)优化到了\(O(\frac{n^2}{6})\)啦，这就是std的做法啦。（mdzz）
\(u\to v\)的路径可以拆成\(u\to w\)和\(v\to w\)，最后直接在\(w\)处合并一下就好了（就是两条路径剩余距离\(r_1+r_2\)除以\(k\)。因为如果能拼出\(k\)步自然可以取代\(k\)步，拼不出来的话那有剩余距离也没啥用）（其实还是感觉有点迷...）。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=50005;
int n,Enum,mx=0,mn=233,H[N],nxt[N<<1],to[N<<1],len[N<<1],fa[N],dep[N],dis[N],sz[N],son[N],top[N];
int pos[N][230],sta[N],p6[N],d6[N],f[(1<<6)+2][230][230],g[(1<<6)+2][230][230];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AE(int w,int v,int u)
{
mx=std::max(mx,w), mn=std::min(mn,w);
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
inline int LCA(int u,int v)
{
while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
return dep[u]>dep[v]?v:u;
}
void DFS1(int x)
{
int mx=0; sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x])
{
fa[v]=x, dep[v]=dep[x]+1, dis[v]=len[i], DFS1(v), sz[x]+=sz[v];
if(sz[v]>mx) mx=sz[v], son[x]=v;
}
}
void DFS2(int x,int tp)
{
top[x]=tp;
if(son[x])
{
DFS2(son[x],tp);
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);
}
}
void Init()
{
for(int i=1; i<=n; ++i)
if(dep[i]>=6)
{
int p=i,cost=0,s=0;
for(int j=0; j<6; ++j)
{
if(dis[p]==mx) s|=1<<j;
cost+=dis[p], p=fa[p];
}
sta[i]=s, p6[i]=p, d6[i]=cost;//p6:向上走6步能到哪
}
dis[1]=2e9;
for(int i=1; i<=n; ++i)
for(int t=0,res=0,p=i,lim=d6[i]; t<lim; ++t)
{
if(res>=dis[p]) res-=dis[p], p=fa[p];
++res, pos[i][t]=p;//pos:走剩余不足6mx的距离res能到哪
}
for(int s=0,lim=1<<6,l2=6*mx; s<lim; ++s)//上面6条边状态为s，k[i]=k，剩余rest，向上走6步到达的花费及剩下步数
for(int k=mx; k<=l2; ++k)
for(int rest=0; rest<=k; ++rest)
{
int res=rest,used=0;
for(int j=0,cost; j<6; ++j)
{
cost=s>>j&1?mx:mn;
if(res<cost) res=k, ++used;
res-=cost;
}
f[s][k][rest]=used, g[s][k][rest]=res;
}
}
void Solve(int x,int ed,int k,int &ans,int &res)
{
ans=0, res=0;
if(k<6*mx)
while(dep[x]-dep[ed]>5)
{
ans+=f[sta[x]][k][res], res=g[sta[x]][k][res];
x=p6[x];
}
else
while(dep[x]-dep[ed]>5)
{
if(res>=d6[x]) res-=d6[x], x=p6[x];
else x=pos[x][res], res=k, ++ans;
}
while(x!=ed)
{
if(res<dis[x]) res=k, ++ans;
res-=dis[x], x=fa[x];
}
}
int main()
{
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
n=read();
for(int i=1; i<n; ++i) AE(read(),read(),read());
DFS1(1), DFS2(1,1), Init();
int Q=read();
for(int i=1,u,v,w,k,ans1,ans2,res1,res2; i<=Q; ++i)
{
u=read(),v=read(),w=LCA(u,v),k=read();
Solve(u,w,k,ans1,res1), Solve(v,w,k,ans2,res2);
printf("%d\n",ans1+ans2-(res1+res2)/k);
}
return 0;
}
考试代码
C
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=50005;
int n,Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],fa[N],dis[N],dep[N],sz[N],son[N],top[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AE(int w,int v,int u)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
inline int LCA(int u,int v)
{
while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
return dep[u]>dep[v]?v:u;
}
void DFS1(int x)
{
int mx=0; sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x])
{
fa[v]=x, dep[v]=dep[x]+1, dis[v]=len[i], DFS1(v), sz[x]+=sz[v];
if(sz[v]>mx) mx=sz[v], son[x]=v;
}
}
void DFS2(int x,int tp)
{
top[x]=tp;
if(son[x])
{
DFS2(son[x],tp);
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);
}
}
namespace Subtask1//辣鸡题目
{
int Solve(int k,int u,int v)
{
static int A[N];
int w=LCA(u,v),ans=1,rest=k;
// printf("%d,%d,%d k:%d\n",u,v,w,k);
while(u!=w)
{
if(dis[u]>rest) ++ans,rest=k;
rest-=dis[u], u=fa[u];
}
int t=0; for(int p=v; p!=w; p=fa[p]) A[++t]=p;
while(t)
{
if(dis[A[t]]>rest) ++ans,rest=k;
rest-=dis[A[t--]];
}
return ans;
}
void Main()
{
int Q=read();
for(int i=1; i<=Q; ++i) printf("%d\n",Solve(read(),read(),read()));
}
}
int main()
{
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
n=read();
for(int i=1; i<n; ++i) AE(read(),read(),read());
DFS1(1), DFS2(1,1);
if(n<=7000||1) return Subtask1::Main(),0;
return 0;
}