mhy笔试题AK代码

第一题.分两种情况讨论一下即可，注意开long long

ll n,H;
ll x11,y11,h1,a1,b1;
ll x22,y22,h2,a2,b2;
void solve()
{
    cin >> n >> H;
    cin >> x11 >> y11 >> h1 >> a1 >> b1;
    cin >> x22 >> y22 >> h2 >> a2 >> b2;
    // 两种情况
    ll ttt = H;
    ll d1 = abs(x11 - 1) + abs(y11 - 1);
    ll d2 = abs(x22 - x11) + abs(y22 - y11);
    ll ans = -1;
    if(ttt >= h1 + 1ll * d1 / a1 * b1){
        ttt -= h1 + 1ll * d1 / a1 * b1;
        if(ttt >= h2 + 1ll * (d1 + d2 + 1) / a2 * b2){
            ttt -= h2 + 1ll * (d1 + d2 + 1) / a2 * b2;
            ans = max(ans,ttt);
        }
    } 

    d2 = abs(x22 - 1) + abs(y22 - 1);
    d1 = abs(x22 - x11) + abs(y22 - y11);
    ttt = H;
    if(ttt >= h2 + 1ll * d2 / a2 * b2){
        ttt -= h2 + d2 / a2 * b2;
        if(ttt >= h1 + 1ll * (d1 + d2 + 1) / a1 * b1){
            ttt -= h1 + 1ll * (d1 + d2 + 1) / a1 * b1;
            ans = max(ans,ttt);
        }
    }
    if(ans == -1){
        puts("yingyingying");
    }else{
        cout << ans << endl;
    }
}

第二题.思维题，动态维护左侧最小值，判断当前值是否大于最小值即可

const int N = 100010;
int a[N];
int n;
void solve()
{
  cin >> n;
  for(int i=1;i<=n;++i){
    cin >> a[i];
  }
  int b2 = n,b1 = 0;
  int leftmin = 0x3f3f3f3f;
  for(int i=1;i<=n;++i){
    if(leftmin < a[i]){
      b1 ++;
    }
    leftmin = min(leftmin,a[i]);  // 最小值
  }

  if(b1 != 0){
    int ttt = __gcd(b1,b2);
    b1 /= ttt,b2 /= ttt;
    printf("%d/%d",b1,b2);
  }else{
    printf("%d/%d",0,1);
  }
}

第三题：贡献法+换根dp

const int N = 100010;
string s;
int n;
vector<int> g[N];
ll f[N];
ll g1[N];
int tot;
ll ans;
void dfs(int u,int fa){
    f[u] = 1;
    for(auto& ne:g[u]){
        if(ne == fa) continue;
        dfs(ne,u);
        f[u] += f[ne];
    }
}
void dfs1(int u,int fa){
    ll s1 = 0,s2 = 0;
    for(auto& ne:g[u]){
        if(s[u] == 'h' && s[ne] == 'm'){
            s1 += ne == fa ? tot - f[u] : f[ne];
        }
        if(s[u] == 'h' && s[ne] == 'y'){
            s2 += ne == fa ? tot - f[u] : f[ne];;
        }
    }
    ans += s1 * s2;
    for(auto& ne:g[u]){
        if(ne == fa) continue;
        dfs1(ne,u);
    }
}
void solve()
{
    cin >> n;
    cin >> s;
    s = " " + s;
    for(int i=1;i<n;++i){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b),g[b].push_back(a);
    }
    dfs(1,0);
    tot = f[1];
    dfs1(1,0);

    cout << ans << endl;
}