AtCoder 题目集2

终于迈入了一个新的阶段，接下来希望质量能高一点吧。

现在我主要刷的是1600左右的题，毕竟实力太拉，只能按照 ”分上200“ 的策略。

(我觉得类型标个 “思维” 貌似没啥意义，毕竟AT几乎全是思维啊...)

NO.1 ABC201E

有关 \(XOR\) 的题目很多都考察了按位解决的思想...确实，很常见的一种解决办法。

所以对于这道题，只要能发现按位解决就OK了。

最后复杂度(我写的) 是 \(O(60n)\) 左右...但是慢的一比...不知道为啥...

const int N=200010,mod=1e9+7;

int n,cnt,head[N];
struct Edge{
  int to,nxt; ll val;
}edge[N<<1];
void Add(int fo,int to,ll val){
  edge[++cnt]={to,head[fo],val};
  head[fo]=cnt;
}

ll f[N][60],ans,sz[N];

void dfs(int pos,int fa,ll dis){
  sz[pos]=1;
  for(int i=0;i<60;++i) f[pos][i]=!!(dis&(1ll<<i));
  for(int i=head[pos];i;i=edge[i].nxt){
    int &to=edge[i].to;
    if(to^fa){
      dfs(to,pos,dis^edge[i].val);
      for(int i=0;i<60;++i)
        f[pos][i]+=f[to][i];
      sz[pos]+=sz[to];
    }
  }
}

void solve(int pos,int fa,int wei,bool tag){
  if(tag) ans=(ans+(sz[1]-f[1][wei])*((1ll<<wei)%mod)%mod)%mod;
  else ans=(ans+f[1][wei]*((1ll<<wei)%mod)%mod)%mod;
  for(int i=head[pos];i;i=edge[i].nxt){
    int &to=edge[i].to;
    if(to^fa){
      if(edge[i].val&(1ll<<wei))
        solve(to,pos,wei,tag^1);
      else solve(to,pos,wei,tag);
    }
  }
}

void check(int wei){
  solve(1,1,wei,0);
}

signed main(){
  // freopen("gen.txt","r",stdin);
  // freopen("");
  IOS
  //int T;

  cin>>n;
  for(int i=1;i<n;++i){
    int fo,to; ll val;
    cin>>fo>>to>>val;
    Add(fo,to,val);
    Add(to,fo,val);
  }

  dfs(1,1,0);
  for(int i=0;i<60;++i)
    check(i);
  cout<<ans*q_Pow(2,mod-2,mod)%mod<<'\n';
  
  return 0;
}

NO.2 ABC243E

看到 \(n\leqslant 300\) 就知道先来个 \(Floyd\) 。然后对于一条边，如果可以丢掉它，那当且仅当我们任何一条最短路都不会经过它，更进一步地说，就是存在另一条路，使得路径长度不长与这条边。思路就是这样。开始我想了求最短路的时候维护一下每条边是否会使用，但是没法排除等长的情况，会少统计...

const int N=305;

int n,m;
ll dis[N][N];
struct Edge{int fo,to,val;}edge[N*N];

signed main(){
  // freopen("gen.txt","r",stdin);
  // freopen("a.txt","w",stdout);
  IOS
  //int T;
  cin>>n>>m; memset(dis,0x3f3f,sizeof(dis));
  for(int i=1,fo,to,val;i<=m;++i){
    cin>>fo>>to>>val;
    edge[i]={fo,to,val};
    dis[fo][to]=dis[to][fo]=val;
  }

  F(1,i,1,n) F(1,j,1,n) F(1,k,1,n)
    dis[j][k]=Min(dis[j][k],dis[j][i]+dis[i][k]);

  int ans=0;
  F(1,i,1,m){
    int fo=edge[i].fo,to=edge[i].to,val=edge[i].val;
    for(int j=1;j<=n;++j)
      if(j!=fo&&j!=to&&dis[fo][to]>=dis[fo][j]+dis[j][to]){
        ++ans;
        break;
      }
  }
  cout<<ans<<'\n';

  return 0;
}

NO.3 ABC083D

这题真的很烧我的脑(