重新写了一下去年的题来看看自己到底是有多傻逼。

小凯的疑惑

• 打表。

时间复杂度

• 搞了一大坨题面，但是真正有用的信息只有几个：

• 判断他给你的复杂度是多少。

• 判断当前循环进不进的去。

• 判断当前循环产生的贡献。

• 判断当前的变量冲突和匹配。

• \(1\)傻逼，\(2,3\)就是分四种情况讨论一下就可以了，为了做\(2\)我们要开一个栈来记录之前所有的循环。

• 然后为了做\(2\)而开的栈，恰好就把\(4\)顺便做掉了。

• 所以代码巨短。

  //100
  #include
  #define R register int
  using namespace std;
  const int N=100001;
  int t,n,Std,ans,now,ban,ERR;
  int tp,Zm[N],Mark[N],ues[N],vis[30];
  string S,Fir,Sec;char f,I;
  void work(){
  cin>>f;
  if(f=='F'){
  cin>>I;R II=I-'a';
  if(vis[II])ERR=1;
  vis[II]=1,cin>>Fir>>Sec,Zm[++tp]=II;
  if(Fir=="n"&&Sec=="n"){
  if(!ban)ans=max(ans,now);
  Mark[tp]=0,ues[tp]=0;
  }
  else if(Fir=="n"&&Sec!="n")
  ban++,Mark[tp]=1,ues[tp]=0;
  else if(Fir!="n"&&Sec=="n"){
  now++,Mark[tp]=0,ues[tp]=1;
  if(!ban)ans=max(ans,now);
  }
  else {
  R fir=0,sec=0;
  for(R j=0,l=Fir.length();j10+Fir[j]-'0'; for(R j=0,l=Sec.length();j10+Sec[j]-'0'; if(fir<=sec){ if(!ban)ans=max(ans,now); Mark[tp]=0,ues[tp]=0; } else ban++,Mark[tp]=1,ues[tp]=0; } } else vis[Zm[tp]]=0,ban-=Mark[tp],now-=ues[tp],tp--; } void sol(){ cin>>n,Std=ans=ERR=tp=now=ban=0,cin>>S;
  memset(vis,0,sizeof(vis));
  if(S!="O(1)")
  for(R j=4,l=S.length();j>t;while(t--)sol();
  return 0;
  }

逛公园

• \(K\leq 50\)，就是让你\(dp\)的。

• 设\(f_{i,j}\)表示当前在\(i\)点，额外走过的路恰好为\(j\)的方案数。

• 这个正反\(dij\)之后就很好转移了。

• 如果不存在\(0\)环，那么转移就一定满足拓扑关系（最短路性质）。

• 但是存在\(0\)环就不满足拓扑关系了。

• 所以利用这一点来判断\(0\)环即可，如果当前\(dp\)状态已经存在于\(dfs\)栈中，则不合法。

• 至于为什么\(dp\)到的\(0\)环一定走的到？

• 因为\(dp\)的状态一定是和终点状态相通的。

  //100
  #include
  #define R register int
  #define ll long long
  using namespace std;
  const int N=100001;
  const int M=400001;
  int t,n,m,K,mod,u,v,x,ans;
  int vis[N][51],f[N][51];
  struct ip{int vl,id;};
  int operator < (ip x,ip y){return x.vl>y.vl;}
  priority_queueQ;
  void add(R &x,R y){x=(x+y>=mod?x+y-mod:x+y);}
  int gi(){
  R x=0,k=1;char c=getchar();
  while((c<'0'||c>'9')&&c!='-')c=getchar();
  if(c=='-')k=-1,c=getchar();
  while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x*k; } struct Gra{ int cnt,hd[N],to[M],w[M],nt[M]; int Dis[N],vis[N]; void link(R f,R t,R d){nt[++cnt]=hd[f],to[cnt]=t,w[cnt]=d,hd[f]=cnt;} void init(){ memset(hd,0,sizeof(hd)),cnt=ans=0; memset(vis,0,sizeof(vis)); memset(Dis,0x7f,sizeof(Dis)); } void dij(R s){ Dis[s]=0,Q.push((ip){0,s}); while(!Q.empty()){ R i=Q.top().id;Q.pop(); if(vis[i])continue;vis[i]=1; for(R k=hd[i];k;k=nt[k]) if(Dis[to[k]]>Dis[i]+w[k]){
  Dis[to[k]]=Dis[i]+w[k];
  Q.push((ip){Dis[to[k]],to[k]});
  }
  }
  }
  }Z,F;
  int Dfs(R i,R j){
  if(vis[i][j])return -1;
  if(f[i][j]!=-1)return f[i][j];
  f[i][j]=(i==1&&j==0),vis[i][j]=1;
  for(R k=F.hd[i];k;k=F.nt[k]){
  R v=F.to[k],p=j-(F.Dis[i]+F.w[k]-F.Dis[v]);
  if(p>=0){
  R g=Dfs(v,p);
  if(g==-1)return -1;
  add(f[i][j],g);
  }
  }
  vis[i][j]=0;return f[i][j];
  }
  void sol(){
  Z.init(),F.init();
  n=gi(),m=gi(),K=gi(),mod=gi();
  for(R i=1;i<=m;++i){
  u=gi(),v=gi(),x=gi();
  Z.link(u,v,x),F.link(v,u,x);
  }
  Z.dij(1),F.dij(n);
  memset(f,-1,sizeof(f));
  memset(vis,0,sizeof(vis));
  for(R i=0;i<=K;++i){
  f[n][i]=Dfs(n,i);
  if(f[n][i]==-1){puts("-1");return ;}
  else add(ans,f[n][i]);
  }
  printf("%d\n",ans);
  }
  int main(){
  t=gi();while(t--)sol();
  return 0;
  }

奶酪

• 连通性，并查集。

• 暴力连边即可。

• 防止爆\(longlong\)的方法，判断这个$$x2+y2\leq4*r2-z2$$

• 就可以了，效果很好。

  //100
  #include
  #define R register int
  #define ll long long
  using namespace std;
  const int N=5101;
  int t,n,fa[N];ll h,r;
  struct Qs{ll x,y,z;}Q[N];
  int gi(){
  R x=0,k=1;char c=getchar();
  while((c<'0'||c>'9')&&c!='-')c=getchar();
  if(c=='-')k=-1,c=getchar();
  while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return xk; } int find(R x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];} ll sqr(ll x){return xx;} int Dis(R i,R j){ return (sqr(Q[i].x-Q[j].x)+sqr(Q[i].y-Q[j].y)<=4ll*sqr(r)-sqr(Q[i].z-Q[j].z)); } void sol(){ n=gi(),h=gi(),r=gi(); for(R i=1;i<=n;++i) Q[i].x=gi(),Q[i].y=gi(),Q[i].z=gi(),fa[i]=i; for(R i=1;i<=n;++i) for(R j=i+1;j<=n;++j) if(Dis(i,j)){ R fu=find(i),fv=find(j); fa[fu]=fv; } fa[n+1]=n+1,fa[n+2]=n+2; for(R i=1;i<=n;++i) if(Q[i].z+r>=h){
  R fu=find(i),fv=find(n+1);
  fa[fu]=fv;
  }
  for(R i=1;i<=n;++i)
  if(Q[i].z-r<=0){
  R fu=find(i),fv=find(n+2);
  fa[fu]=fv;
  }
  puts(find(n+1)==find(n+2)?"Yes":"No");
  }
  int main(){
  t=gi();while(t--)sol();
  return 0;
  }

宝藏

• 以前落实这个题目的时候打了个假算法。

• 网上的\(dp\)大多都不正确，正解是子集\(dp\)。

• 先暴搜，然后套个\(A*\)，发现跑得比较快。

• 然后\(hash\)当前集合状态和到根节点距离，存下来。

• 然后就可以\(1000ms\)内通过所有测试点。

• 可以过网上我看到的所有\(hack\)数据。

  //100
  #include
  #define ull unsigned long long
  #define R register int
  using namespace std;
  const int N=600005;
  const int M=13;
  const int bas=257;
  int n,m,Mp[M][M];
  int ans,Dis[N];
  mapG;
  int gi(){
  R x=0,k=1;char c=getchar();
  while((c<'0'||c>'9')&&c!='-')c=getchar();
  if(c=='-')k=-1,c=getchar();
  while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return xk; } int check(R S){ R res=0; for(R j=1;j<=n;++j) if(((1<<(j-1))&S)==0){ R Mn=1e9; for(R k=1;k<=n;++k) Mn=min(Mn,Mp[j][k]); res+=Mn; } return res; } ull Hash(R S){ ull res1=0,res2=0; for(R j=1;j<=n;++j) res1=res1bas+j,res2=res2*bas+Dis[j]; return res1^res2; } void Dfs(R S,R now){ if(S==(1<=ans-now)return ;

  ull has=Hash(S);
  if(G.find(has)!=G.end())
      if(G[has]<=now)return ;
  G[has]=now;
  
  for(R k=1;k<=n;++k)
      if(((1<<(k-1))&S)==0){
          R T=((1<<(k-1))|S);
          for(R j=1;j<=n;++j)
              if(((1<<(j-1))&S)&&Mp[j][k]!=Mp[0][0]){
                  Dis[k]=Dis[j]+1;
                  Dfs(T,now+Dis[j]*Mp[j][k]);
                  Dis[k]=0;
              }
      }

  }
  int main(){
  freopen("testdata(2).in","r",stdin);
  n=gi(),m=gi(),ans=2e9;
  memset(Mp,0x7f,sizeof(Mp));
  for(R i=1;i<=m;++i){
  R u=gi(),v=gi(),x=gi();
  Mp[u][v]=min(Mp[u][v],x);
  Mp[v][u]=Mp[u][v];
  }
  for(R i=1;i<=n;++i){
  memset(Dis,0,sizeof(Dis));
  Dis[i]=1,Dfs(1<<(i-1),0);
  }
  cout<<ans<<endl;
  return 0;
  }

列队

• 这个真的是套路题，数据结构做多了就没什么意思了。

• \(O(q^2)\)的做法是每次考虑之前的询问对当前询问的影响。

• 比如说你这次询问\((i,j)\)是谁，上一次询问的是\((i,j−1)\)

• 那么你就知道了这一次在\((i,j)\)的人实际上就是上一次在\((i,j+1)\)的人。

• 这样依次推到最开始就可以了。

• \(80\)分只有一条链，在上面线段树二分即可。

• \(100\)分就是开很多个线段树。

• 网上\(100\)分代码一大堆，这里给出\(70\)分部分分代码。

  //70
  #include
  #define R register int
  #define ll long long
  using namespace std;
  const int N=600005;
  int n,m,q;
  int gi(){
  R x=0,k=1;char c=getchar();
  while((c<'0'||c>'9')&&c!='-')c=getchar();
  if(c=='-')k=-1,c=getchar();
  while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return xk; } namespace cpp1{ const int N=601; struct Qs{int x,y;}Q[N]; ll Idx(R x,R y){return 1ll(x-1)m+y;} void Main(){ for(R i=1;i<=q;++i)Q[i].x=gi(),Q[i].y=gi(); for(R i=1;i<=q;++i){ R x=Q[i].x,y=Q[i].y; for(R j=i-1;j>=1;--j){ if(Q[j].x==x&&Q[j].y<=y&&y4]; vectorG;
  int query(R le,R ri,R lim,R i){
  if(le==ri)return le;
  R mid=(le+ri)>>1,ls=(i<<1),rs=(ls|1),F=mid-le+1-vl[ls]; if(F>1,ls=(i<<1),rs=(ls|1);
  if(pos<=mid)mdf(le,mid,pos,ls);else mdf(mid+1,ri,pos,rs);
  vl[i]=vl[ls]+vl[rs];
  }
  void Main(){
  len=m+q;
  for(R i=1;i<=q;++i){
  gi();R x=gi();
  R ans=query(1,len,x,1);
  if(ans<=m)printf("%d\n",ans),G.push_back(ans);
  else printf("%d\n",G[ans-m-1]),G.push_back(G[ans-m-1]);
  mdf(1,len,ans,1);
  }
  }
  }
  int main(){
  n=gi(),m=gi(),q=gi();
  if(q<=500)cpp1::Main();
  if(n==1)cpp2::Main();
  return 0;
  }