Atcoder Beginner Contest 133

自己把题目翻译一遍就当，考研翻译训练了()

A T or T

题意

我们有$N$个人要去旅行，通过乘坐火车或者出租车进行出游，坐火车我们每个人要出$A$元(日元)，做出租车我们总共会花费$B$元。请问，我们的旅费最少是多少?

思路

直接计算两种出行方式的总花费，输出最小值

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


signed main()
{
    int n = read(), a = read(), b = read();
    cout << min(n * a, b) << endl;
    return 0;
}

B Good Distance

题意

在$D$维度空间中有$N$个点，第$i$个点的坐标为 $ \left (x_1, x_2,…,x_n \right ) $，问有多少对点对，两点之间的距离是整数

思路

两重for循环枚举就行

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


signed main()
{
    int n = read(), d = read();
    vector<vector<int>> a(n + 1, vector<int>(d + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= d; j++) a[i][j] = read();
    int cnt = 0;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = i + 1 ; j <= n ; ++j){
            int sum = 0;
            for(int k = 1 ; k <= d ; ++k)
                sum = sum + (a[i][k] - a[j][k]) * (a[i][k] - a[j][k]);
            if((int)sqrt(sum) * (int)sqrt(sum) == sum) ++cnt;
        }
    }
    cout << cnt << endl;
    return 0;
}

C Remainder Minimization 2019

题意

给你两个非负整数$L$和$R$，我们将会选择两个整数$i$ 和 $j$($L \le i < j \le R$)，遭到最小的$(i * j) % 2019$

思路

当区间范围超过$2019$时，则区间内必然有2019的倍数，所以必然有$(i * j) % 2019 = 0$

如果区间范围小于$2019$，直接枚举所有状况就行

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


signed main()
{
    int l = read(), r = read();
    if(l > r) swap(l, r);
    if(r - l + 1 >= 2019) cout << 0;
    else {
        int mn = 1e18;
        for(int i = l; i <= r; i++)
            for(int j = i + 1; j <= r; j++)
                mn = min(mn, i * j % 2019);
        cout << mn << endl;
    }
    return 0;
}

D Rain Flows into Dams

题意

有$N$座山围成一个圈，按照顺时针分别被称为 Mountain 1, Mountain 2, ……, Mountain N，$N$是奇数

在这些山之间有$N$个 Dams，$Dam_i$ 位于 $Mountain_i$ 和 $Mountain_{i + 1}$ 之间((MountainN+1 就是 Mountain 1).)

当山$i(1≤i≤N)$降雨量为$2x$升时，$dam_{i−1}$和 $dam_i$各积水$x$升。

有一天，每座山的降雨量都是非负的。

求每座山的降雨量。我们可以证明，在此问题的约束条件下，解是唯一的。

思路

$$
Dam_1 = \frac{a_1}{2} + \frac{a_2}{2}
Dam_2 = \frac{a_2}{2} + \frac{a_3}{2}
Dam_3 = \frac{a_1}{2} + \frac{a_2}{2}
$$

观察可以发现
$$
Dam_1 -Dam_2 + Dam_3 - Dam_4 + … - Dam_{n - 1} = \frac{a_1}{2} - \frac{a_n}{2}
$$

$$
Dam_n = \frac{a_1}{2}+\frac{a_n}{2}
$$

$$
\therefore Dam_1 -Dam_2 + Dam_3 - Dam_4 + … - Dam_{n - 1} + Dam_n = a_1
$$

在计算出$a_1$之后，往后递推就能求解出后面的答案

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


signed main()
{
    int n = read();
    vector<int> a(n), ans(n);
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        a[i] = read();
        if(i & 1) sum -= a[i];
        else sum += a[i];
    }
    ans[0] = sum;
    for(int i = 1; i < n; i++)
    {
        ans[i] = (a[i - 1] - ans[i - 1] / 2) * 2;
    }
    for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

E Virus Tree 2

题意

给你一棵树，它有$N$个顶点和$N-1$条边。顶点的编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

您有 $K$ 种颜色的着色材料。对于树中的每个顶点，你将从 $K$ 种颜色中选择一种来给它上色，这样就满足了下面的条件：

• 如果两个不同顶点$x$和$y$之间的距离小于或等于 2，则$x$和$y$有不同的颜色。

这棵树有几种涂色方法？求模数 $1\ 000\ 000\ 007$。

什么是树？树是图的一种。详情请参见维基百科 “树（图论）”

什么是距离？两个顶点$x$和$y$之间的距离是从$x$到$y$所需经过的最少边数。

思路

一开始想树形dp，求$ \sum_{i=1}^{k} dp_{1,i} $ 作为答案，但是根据数据范围发现，内存会爆

然后考虑特殊性质

根节点有$K$种选择，根节点的孩子有$K-1$种选择，其余节点最多有$K-2$种选择

对于一个已经确定颜色的节点来说，他的有$x$个子节点，如果则它的子节点的情况有$\frac{n!}{(n-x)!} $种

然后遍历子节点，结果乘上子节点确定颜色可能的情况

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int mod = 1e9 + 7;

signed main()
{
    int n = read(), k = read();
    vector<vector<int>> g(n + 1);
    for(int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    function<int(int, int)> dfs = [&](int u, int fa) -> int
    {
        int use;
        if(fa == 0) {
            use = k - 1;
        } else {
            use = k - 2;
        }
        if(k < g[u].size()) return 0;
        int res = 1;
        for(auto x : g[u])
        {
            if(x == fa) continue;
            res *= use--;
            res %= mod;
        }
        for(auto x : g[u])
        {
            if(x == fa) continue;
            res *= dfs(x, u);
            res %= mod;
        }
        return res;
    };
    cout << k * dfs(1, 0) % mod << endl;
    return 0;
}

F Colorful Tree

题意

有一棵树，其顶点为 $N$，编号为 $1$至 $N$。这棵树的第$i$条边连接顶点$a_i$和顶点$b_i$，这条边的颜色和长度分别是$c_i$和$d_i$。在这里，每条边的颜色由一个介于 $1$和 $N-1$（含）之间的整数表示。相同的整数对应相同的颜色，不同的整数对应不同的颜色。

请回答下列 $Q$ 个问题：

• 查询题$j$（$1 \leq j \leq Q$）：假设颜色为$x_j$的每条边的长度都改为$y_j$，求顶点$u_j$与顶点$v_j$之间的距离（边长的改变不影响后面的查询）。

思路

也不算思路了，这题我没写出来，树剖+线段树这点是没问题的，对与边进行树剖，这种题也做过也没问题，计算距离就是考虑LCA，$d(u)+d(v)−2×d(LCA(u,v))$，路径的长度就用线段树维护，但是每次查询的按颜色修改都是暴力修改的，时间复杂度非常糟糕，在写了40min之后不出意料的TLE了，最后投降，看了一下题解是用可持久化数据做的，也有离线处理做优化的，看了半天，好像懂了()

code

这是一份霓虹的代码

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct HLDecomposition {
  Int n,pos;
  vector<vector<Int> > G;
  vector<Int> vid, head, sub, par, dep, inv, type;

  HLDecomposition(){}
  HLDecomposition(Int n):
    n(n),pos(0),G(n),vid(n,-1),head(n),sub(n,1),
    par(n,-1),dep(n,0),inv(n),type(n){}

  void add_edge(Int u, Int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void build(vector<Int> rs={0}) {
    Int c=0;
    for(Int r:rs){
      dfs_sz(r);
      head[r]=r;
      dfs_hld(r,c++);
    }
  }

  void dfs_sz(Int v) {
    for(Int &u:G[v]){
      if(u==par[v]) continue;
      par[u]=v;
      dep[u]=dep[v]+1;
      dfs_sz(u);
      sub[v]+=sub[u];
      if(sub[u]>sub[G[v][0]]) swap(u,G[v][0]);
    }
  }

  void dfs_hld(Int v,Int c) {
    vid[v]=pos++;
    inv[vid[v]]=v;
    type[v]=c;
    for(Int u:G[v]){
      if(u==par[v]) continue;
      head[u]=(u==G[v][0]?head[v]:u);
      dfs_hld(u,c);
    }
  }

  // for_each(vertex)
  // [l,r] <- attention!!
  template<typename F>
  void for_each(Int u, Int v, const F& f) {
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      f(max(vid[head[v]],vid[u]),vid[v]);
      if(head[u]!=head[v]) v=par[head[v]];
      else break;
    }
  }

  template<typename T,typename Q,typename F>
  T for_each(Int u,Int v,T ti,const Q &q,const F &f){
    T l=ti,r=ti;
    while(1){
      if(vid[u]>vid[v]){
        swap(u,v);
        swap(l,r);
      }
      l=f(l,q(max(vid[head[v]],vid[u]),vid[v]));
      if(head[u]!=head[v]) v=par[head[v]];
      else break;
    }
    return f(l,r);
  }

  // for_each(edge)
  // [l,r] <- attention!!
  template<typename F>
  void for_each_edge(Int u, Int v,const F& f) {
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]!=head[v]){
        f(vid[head[v]],vid[v]);
        v=par[head[v]];
      }else{
        if(u!=v) f(vid[u]+1,vid[v]);
        break;
      }
    }
  }

  Int lca(Int u,Int v){
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]==head[v]) return u;
      v=par[head[v]];
    }
  }

  Int distance(Int u,Int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
  }
};


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  Int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(Int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(Int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  template<typename C>
  Int find(Int st,C &check,T &acc,Int k,Int l,Int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    Int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    Int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }
  template<typename C>
  Int find(Int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,q;
  cin>>n>>q;
  vector<Int> as(n),bs(n),cs(n),ds(n);
  vector<Int> xs(q),ys(q),us(q),vs(q);

  vector< vector<Int> > C(n),D(n);
  HLDecomposition hld(n);
  for(Int i=1;i<n;i++){
    cin>>as[i]>>bs[i]>>cs[i]>>ds[i];
    as[i]--;bs[i]--;
    hld.add_edge(as[i],bs[i]);
    C[cs[i]].emplace_back(i);
  }
  hld.build();

  for(Int i=0;i<q;i++){
    cin>>xs[i]>>ys[i]>>us[i]>>vs[i];
    us[i]--;vs[i]--;
    D[xs[i]].emplace_back(i);
  }

  auto f=[&](Int a,Int b){return a+b;};
  Int ti=0;
  SegmentTree<Int> cnt(f,ti);
  SegmentTree<Int> sum(f,ti);
  cnt.build(vector<Int>(n,0));
  sum.build(vector<Int>(n,0));

  for(Int i=1;i<n;i++){
    Int ch=hld.dep[as[i]]>hld.dep[bs[i]]?as[i]:bs[i];
    sum.set_val(hld.vid[ch],ds[i]);
  }

  vector<Int> ans(q,0);
  for(Int i=0;i<q;i++){
    Int res=0;
    auto qry=[&](Int l,Int r){res+=sum.query(l,r+1);};
    hld.for_each_edge(us[i],vs[i],qry);
    ans[i]+=res;
  }
  sum.build(vector<Int>(n,0));

  for(Int t=1;t<n;t++){
    for(Int i:C[t]){
      Int ch=hld.dep[as[i]]>hld.dep[bs[i]]?as[i]:bs[i];
      cnt.set_val(hld.vid[ch],1);
      sum.set_val(hld.vid[ch],ds[i]);
    }

    for(Int i:D[t]){
      Int res=0,num=0;
      auto qry=[&](Int l,Int r){
                 num+=cnt.query(l,r+1);
                 res+=sum.query(l,r+1);
               };
      hld.for_each_edge(us[i],vs[i],qry);
      ans[i]+=num*ys[i];
      ans[i]-=res;
    }

    for(Int i:C[t]){
      Int ch=hld.dep[as[i]]>hld.dep[bs[i]]?as[i]:bs[i];
      cnt.set_val(hld.vid[ch],0);
      sum.set_val(hld.vid[ch],0);
    }
  }

  for(Int i=0;i<q;i++) cout<<ans[i]<<"\n";
  cout<<flush;
  return 0;
}