20240413 美团笔试

第三题

解法：树形dfs，用1表示B，2表示R，对树自下而上取或，那么节点为3表示子树同时有1和2。也可用集合，从下往上更新集合，找集合中有1和2的，但集合常数比位运算大，推荐使用位运算。

C++和Python代码见截图，Python需要加sys.setrecursionlimit(100000)，防止递归深度过大。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int>a(n);
    for(int i=0;i<n;i++){
        if(s[i]=='B')a[i]=1;
        else a[i]=2;
    }
    auto dfs = [&](auto self, int u, int p) -> void {
        for (auto v: adj[u]) {
            if (v != p) {
                self(self, v, u);
                a[u]|=a[v];
            }
        }
    };
    dfs(dfs, 0, -1);
    int ans=0;
    for(auto i:a) ans+=(i==3);
    cout<<ans;
    return 0;
}

import sys
sys.setrecursionlimit(100000)

def dfs(adj, a, u, p):
    for v in adj[u]:
        if v != p:
            dfs(adj, a, v, u)
            a[u] |= a[v]

def main():
    n = int(input())
    s = input().strip()
    
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
    
    a = [0] * n
    for i in range(n):
        if s[i] == 'B':
            a[i] = 1
        else:
            a[i] = 2
    
    dfs(adj, a, 0, -1)
    
    ans = sum(1 for i in a if i == 3)
    print(ans)

if __name__ == "__main__":
    main()

第四题

解法：按因子数量前缀和，cdef分别表示对应位置a[i]的2，3，5，7的因子数量，pc，pd，pe，pf为c,d,e,f乘以数量b[i]之后的前缀和，之后再对b做前缀和。

，对每个查询l,r，设区间内的因子2，3，5，7分别为c0,d0,e0,f0，那么答案就是(c0+1)*(d0+1)*(e0+1)*(f0+1)。

找到对应位置x，y，若x=y，直接找x位置的因子数，否则，用前缀和找[x+1,y)区间的因子数加上x位置和y位置的因字数即可。

from bisect import *
mod=10**9+7
n,m=list(map(int, input().split()))
a=[0]*m
b=[0]*m
c=[0]*m
d=[0]*m
e=[0]*m
f=[0]*m
for i in range(m):
    a[i],b[i]=list(map(int, input().split()))
    while a[i]%2==0:
        a[i]//=2
        c[i]+=1
    while a[i]%3==0:
        a[i]//=3
        d[i]+=1
    while a[i]%5==0:
        a[i]//=5
        e[i]+=1
    while a[i]%7==0:
        a[i]//=7
        f[i]+=1
pc=c[:]
pd=d[:]
pe=e[:]
pf=f[:]
for i in range(m):
    pc[i]*=b[i]
    pd[i]*=b[i]
    pe[i]*=b[i]
    pf[i]*=b[i]
for i in range(1,m):
    b[i]+=b[i-1]
    pc[i]+=pc[i-1]
    pd[i]+=pd[i-1]
    pe[i]+=pe[i-1]
    pf[i]+=pf[i-1]
q=int(input())
for _ in range(q):
    l,r=list(map(int, input().split()))
    x=bisect_left(b,l)
    y=bisect_right(b,r)
    if x==y:
        ans=(c[x]*(r-l+1)+1)*(d[x]*(r-l+1)+1)*(e[x]*(r-l+1)+1)*(f[x]*(r-l+1)+1)
        print(ans%mod)
        continue
    #[x+1,y)
    c0=pc[y-1]-pc[x]+c[x]*(b[x]-l+1)
    d0=pd[y-1]-pd[x]+d[x]*(b[x]-l+1)
    e0=pe[y-1]-pe[x]+e[x]*(b[x]-l+1)
    f0=pf[y-1]-pf[x]+f[x]*(b[x]-l+1)
    if y<len(b):
        c0+=c[y]*(r-b[y-1])
        d0+=d[y]*(r-b[y-1])
        e0+=e[y]*(r-b[y-1])
        f0+=f[y]*(r-b[y-1])
    print((c0+1)*(d0+1)*(e0+1)*(f0+1)%mod)