HR# 5题解

T1 我傻了

前20个数暴力开桶记录，后面的每次暴力统计。

#include<bits/stdc++.h>

#define R register int

using namespace std;

namespace Luitaryi {

int n,ans;

int vis[40010];

int c[30];

inline void main() {

  cin>>n;

  while(n--) {

    R op,x; cin>>op>>x;

    if(op==1) {

      for(R i=1;i<=20;++i) if(x%i==0) ++c[i];

      ++vis[x];

    } else {

      if(x<=20) ans^=c[x];

      else {  R sum=0;

        for(R i=x;i<=40000;i+=x) sum+=vis[i];

        cerr<<sum<<endl;

        ans^=sum;

      }

    }

  } cout<<ans<<endl;

}

} signed main() {Luitaryi::main(); return 0;}

md 后来发现直接 \(\sqrt n\)

T2 我又傻了

一眼淀粉质搞他。。。然后搞了一会。。

#include<bits/stdc++.h>

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

  register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;

}

const int N=300010,Inf=1e+9;

int n,m,cnt,sum,rt,tot; bool vis[N];

int vr[N<<1],nxt[N<<1],fir[N],w[N<<1],d[N],mx[N],sz[N],buf[N],c[N];

ll cursum,cursz,totsz,totsum,ans;

unordered_map<int,ll> mmp,mem;

inline void add(int u,int v,int ww) {

  vr[++cnt]=v,nxt[cnt]=fir[u],w[cnt]=ww,fir[u]=cnt;

  vr[++cnt]=u,nxt[cnt]=fir[v],w[cnt]=ww,fir[v]=cnt;

}

inline void getsz(int u,int fa) {

  sz[u]=1,mx[u]=0; for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

    if(vis[v]||v==fa) continue;

    getsz(v,u); sz[u]+=sz[v];

    mx[u]=max(mx[u],sz[v]);

  } mx[u]=max(mx[u],sum-sz[u]);

  if(mx[u]<mx[rt]) rt=u;

}

inline void getdis(int u,int fa,int C) { cursum+=d[u],++cursz;// cout<<"de"<<' '<<u<<' '<<d[u]<<endl;

  for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

    if(vis[v]||v==fa||w[i]==C) continue;

    d[v]=d[u]+c[v]; getdis(v,u,w[i]);

  }

}

inline void solve(int u,int fa) { tot=0; //cout<<"begin"<<' '<<u<<endl;

  vis[u]=true; totsz=1,totsum=c[u];

  for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

    if(vis[v]||v==fa) continue;

    d[v]=c[v]; getdis(v,u,w[i]);

    //cout<<v<<' '<<cursum<<' '<<cursz<<' '<<totsum<<' '<<totsz<<endl;

    ans+=cursum*(totsz-mem[w[i]])+(totsum-mmp[w[i]])*cursz,

    totsum+=cursum+cursz*c[u],totsz+=cursz,mem[w[i]]+=cursz,mmp[w[i]]+=cursum+cursz*c[u];

    //cout<<ans<<' '<<v<<' '<<cursum<<' '<<cursz<<' '<<totsum<<' '<<totsz<<' '<<mmp[w[i]]<<' '<<mem[w[i]]<<endl;

    buf[++tot]=w[i]; cursum=0,cursz=0;

  } while(tot) mem[buf[tot]]=0,mmp[buf[tot]]=0,--tot;

  totsz=0,totsum=0;

  for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

    if(vis[v]||v==fa) continue;

    sum=sz[v]; rt=0,mx[rt]=Inf;

    getsz(v,u),getsz(rt,-1); solve(rt,u);

  }

}

inline void main() {

  n=g(); for(R i=1;i<=n;++i) c[i]=g();

  for(R i=1,u,v,w;i<n;++i) u=g(),v=g(),w=g(),add(u,v,w);

  sum=n,rt=0,mx[rt]=Inf;

  getsz(1,-1),getsz(rt,-1); solve(rt,-1);

  printf("%lld\n",ans);

}

} signed main() {Luitaryi::main(); return 0;}

然后就被 L队的记搜锤了。

T3 唯一没有掉智的题

设有效的行操作 (即两个相同的操作是无效的) 为 \(i\) , 有效的列操作为 \(j\) ;

有 \(i*m+j*n-2*i*j=s\) ，即 \(j=\frac{s-i*m}{n-2*i}\)

剩余次数为 \(r-i\) 和 \(c-j\) ,即我们可以把 \(\frac{r-i}{2}\) 和 \(\frac{c-j}{2}\) 对操作任意分配到每个行或列上。

所以是 \(C(n,i)*C(m,j)*C(n+(r-i)/2-1,(r-i)/2)*C(m+(c-j)/2-1,(c-j)/2)\)

欣喜的以为自己A了

结果一输样例，RE。。。出现了%0的算术错误（雾）

。。。

aaaa

\(n==2*i???\)

那那 \(s==i*m???\)

...

那那列操作系数是0???

???

枚举列???

awsl

#include<bits/stdc++.h>

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

inline ll g() { register ll x=0,f=1;

  register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;

} const int N=200000,M=1000000007;

int n,m,r,c,ans; ll s;

int Inv[N+10],fac[N+10],rfac[N+10];

inline int C(int n,int m) {

  return 1ll*fac[n]*rfac[m]%M*rfac[n-m]%M;

}

inline void main() {

  n=g(),m=g(),r=g(),c=g(),s=g(); Inv[1]=1;

  for(R i=2;i<=N;++i) Inv[i]=M-1ll*M/i*Inv[M%i]%M;

  fac[0]=fac[1]=1; for(R i=2,lim=max(n*2,m*2);i<=lim;++i) fac[i]=1ll*fac[i-1]*i%M;

  rfac[0]=rfac[1]=1; for(R i=2,lim=max(n*2,m*2);i<=lim;++i) rfac[i]=1ll*rfac[i-1]*Inv[i]%M;

  for(R i=r&1,lim=(ll)min(r,n);i<=lim;i+=2) if(n!=2*i) {

    if((s-1ll*i*m)%(n-2*i)) continue;

    R j=(s-1ll*i*m)/(n-2*i);

    if(j>c||(c-j)&1||j<0) continue;

    ans=(ans+1ll*C(n,i)*C(m,j)%M*C(n+(r-i)/2-1,(r-i)/2)%M*C(m+(c-j)/2-1,(c-j)/2)%M)%M;

  } else {

    if(1ll*i*m!=s) continue; register ll tot=0;

    for(R j=c&1,lim=min(r,c);j<=lim;j+=2) tot=(tot+1ll*C(m,j)*C(m+(c-j)/2-1,(c-j)/2)%M)%M;

    ans=(ans+1ll*C(n,i)*C(n+(r-i)/2-1,(r-i)/2)%M*tot%M)%M;

  } printf("%d\n",ans);

}

} signed main() {Luitaryi::main(); return 0;}

T4 我又双叒叕傻了

交互题少读了一行结果T爆

考后怒压行。。

#include<bits/stdc++.h>

#define R register int

using namespace std;

inline void g(int& x){x=0;char ch;while(!isdigit(ch=getchar()));do x=x*10+ch-48;while(isdigit(ch=getchar()));}

int main() {R x;while(1) puts("move_left"),fflush(stdout),g(x),puts("reach_dest"),fflush(stdout),g(x);}

巴特西

HR# 5题解

T1 我傻了

T2 我又傻了

T3 唯一没有掉智的题

T4 我又双叒叕傻了

海星，该拿的（除了T4）都拿了。。。还是要稳

最新文章

热门文章