除了I题以外的题的题解

A.鼠鼠打洞 https://ac.nowcoder.com/acm/contest/71344/A

观察题目条件后用哈希表记录洞出现的次数，累加到答案。

void solve() {
    string s;
    cin >> s;
    map<char, int> m;
    m['A'] = m['D'] = m['O'] = m['P'] = m['Q'] = m['R'] = 1;
    m['B'] = 2;
    m['a'] = m['b'] = m['d'] = m['e'] = m['g'] = m['o'] = m['p'] = m['q'] = 1;
    m['0'] = m['4'] = m['6'] = m['9'] = 1;
    m['8'] = 2;
    int ans = 0;
    for (char c : s) ans += m[c];
    cout << ans << endl;
}

B.scx，做规划 https://ac.nowcoder.com/acm/contest/71344/B

容易发现题目数据保证 1 <= L <= R <= 60，也就是说可以对每个 L <= D <= R，暴力统计任务为第 D 天且出现在以 x 节点为根节点的子树内的节点数量，这里使用DFS序与区间查询总和单点修改的数据结构维护。

对于 L, R 没啥限制的情况，可以使用比较恶心人的树套树来维护。


struct HLD {
    int n;
    std::vector<int> siz, top, dep, parent, in, out, seq;
    std::vector<std::vector<int>> adj;
    int cur;
     
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
        }
         
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                std::swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
     
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
     
    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }
         
        int d = dep[u] - k;
         
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
         
        return seq[in[u] - dep[u] + d];
    }
     
    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
     
    int rootedParent(int u, int v) {
        std::swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
     
    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
     
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    HLD hld(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        hld.addEdge(u, v);
    }
    hld.work(1);
    vector<vector<int>> bit(61, vector<int>(n + 1));
    auto update = [&](vector<int> &b, int x, int v) -> void {
        x++;
        while (x <= n) {
            b[x] += v;
            x += lowbit(x);
        }
    };
    auto query = [&](vector<int> &b, int x) -> int {
        x++;
        int r = 0;
        while (x) {
            r += b[x];
            x -= lowbit(x);
        }
        return r;
    };
    for (int i = 1; i <= n; i++) {
        update(bit[a[i]], hld.in[i], 1);
    }
    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            update(bit[a[x]], hld.in[x], -1);
            a[x] = y;
            update(bit[a[x]], hld.in[x], 1);
        } else {
            int x, l, r;
            cin >> x >> l >> r;
            int ans = 0;
            for (int i = l; i <= r; i++) {
                ans += query(bit[i], hld.out[x] - 1) - query(bit[i], hld.in[x] - 1);
            }
            cout << ans << endl;
        }
    }
}

C.广告位招商中 https://ac.nowcoder.com/acm/contest/71344/C

对获得的广告费累加求和之后判定是否大于等于 M + 50

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll s = 0;
    for (int i =  1; i <= n; i++) s += a[i];
    if (s >= m + 50) {
        cout << "KFC" << endl;
    } else {
        cout << "QAQ" << endl;
    }
}

D.最惨烈的代价 https://ac.nowcoder.com/acm/contest/71344/D

对下标进行稳定的排序(对于相等的元素保持它们的相对顺序)，然后使用前 (N + 1) / 2 个，有点卡常，sort好像过不去，得手写排序。


namespace Fast_IO{ 
    const int MAXL((1 << 18) + 1);int iof, iotp;
    char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55];
    char Getchar(){
        if (ioiS == ioiT){
            ioiS=ioif;ioiT=ioiS+fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++);
        }else return (*ioiS++);
    }
    void Write(){fwrite(ioof,1,iooS-ioof,stdout);iooS=ioof;}
    void Putchar(char x){*iooS++ = x;if (iooS == iooT)Write();}
    inline int read(){
        int x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    inline long long read_ll(){
        long long x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    void Getstr(char *s, int &l){
        for(ioc=Getchar();ioc==' '||ioc=='\n'||ioc=='\t';)ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(l=0;!(ioc==' '||ioc=='\n'||ioc=='\t'||ioc==EOF);ioc=Getchar())s[l++]=ioc;s[l] = 0;
    }
    template <class Int>void Print(Int x, char ch = '\0'){
        if(!x)Putchar('0');if(x<0)Putchar('-'),x=-x;while(x)iost[++iotp]=x%10+'0',x/=10;
        while(iotp)Putchar(iost[iotp--]);if (ch)Putchar(ch);
    }
    void Putstr(const char *s){for(int i=0,n=strlen(s);i<n;++i)Putchar(s[i]);}
} // namespace Fast_IO
using namespace Fast_IO;

int a[int(5e6 + 1)], p[int(5e6 + 1)], t[int(5e6 + 1)];

void mergesort(int l, int r) {
    if (l == r) return;
    int mid = l + (r - l) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    int i = l, j = mid + 1, pos = l;
    while (i <= mid && j <= r) {
        if (a[p[i]] <= a[p[j]]) {
            t[pos++] = p[i++];
        } else {
            t[pos++] = p[j++];
        }
    }
    while (i <= mid) {
        t[pos++] = p[i++];
    }
    while (j <= r) {
        t[pos++] = p[j++];
    }
    for (int i = l; i <= r; i++) {
        p[i] = t[i];
    }
}

void solve() {
    int n;
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        p[i] = i;
    }
    mergesort(1, n);
    ll ans = 0;
    for (int i = 1; i <= (n + 1) / 2; i++) {
        ans += a[p[i]];
        a[p[i]] = -1;
    }
    Print(ans, '\n');
    
    for (int i = 1; i <= n; i++) {
        if (a[i] == -1) Print(i, ' ');
    }
    Write();
}

E.递交申请 https://ac.nowcoder.com/acm/contest/71344/E

对每个点进行记忆化搜索，注意判定有环的情况。


void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> x(n + 1), t(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> t[i];
    }
    vector<ll> dis(n + 1, -1);
    dis[0] = 0;
    function<ll(int)> dfs = [&](int u) -> ll {
        if (dis[u] != -1) return dis[u];
        dis[u] = inf; //方便判环，环内节点距离设置成极大值
        dis[u] = dfs(x[u]) + t[u];
        dis[u] = min(dis[u], inf);
        return dis[u];
    };
    for (int i = 1; i <= q; i++) {
        int d, x;
        cin >> d >> x;
        if (dfs(x) <= d) {
            cout << "Holiday" << endl;
        } else {
            cout << "Stay" << endl; 
        }
    }
}

F.信念中心 https://ac.nowcoder.com/acm/contest/71344/F

真正意义上的缝合题。

求最小圆覆盖后除一下凸包面积。


struct vec
{
	double x, y;
	vec (const double& x0 = 0, const double& y0 = 0) : x(x0), y(y0) {}
	vec operator + (const vec& t) const {return vec(x+t.x, y+t.y);}
	vec operator - (const vec& t) const {return vec(x-t.x, y-t.y);}
	vec operator * (const double& t) const {return vec(x*t, y*t);}
	vec operator / (const double& t) const {return vec(x/t, y/t);}
	const double len2 () const {return x*x + y*y;}
	const double len () const {return sqrt(len2());}
	vec norm() const {return *this/len();}
	vec rotate_90_c () {return vec(y, -x);}
};

double dot(const vec& a, const vec& b) {return a.x*b.x + a.y*b.y;}
double crs(const vec& a, const vec& b) {return a.x*b.y - a.y*b.x;}

vec lin_lin_int(const vec& p0, const vec& v0, const vec& p1, const vec& v1)
{
	double t = crs(p1-p0, v1) / crs(v0, v1);
	return p0 + v0 * t;
}

vec circle(const vec& a, const vec& b, const vec& c)
{
	return lin_lin_int((a+b)/2, (b-a).rotate_90_c(), (a+c)/2, (c-a).rotate_90_c());
}

int n;
vec pot[500005];

#define unllong unsigned long long 
#define unint unsigned int
#define printline  printf( "\n" ) 
typedef long long llong ;
//const double PI = 2.0 * acos( 0.0 ) ;
#define zero(x) (((x)>0?(x):-(x))<eps)

const int Base=1000000000;//高精度
const int Capacity=1000;//高精度
const double eps = 1e-16 ;
const int INF = 1000000 ;

const int siz = 500100 ;

struct POINT
{
    double x ;
    double y ;
    double k ;
};
struct POINT point[siz] ;

int stak[siz] ; 
int top = 2 ;

int inn ;
double outarea ;

double fdist( double x1, double y1, double x2, double y2 )
{
    return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
}

void input()
{
    int leftdown = 0 ;
    for( int i=0; i<inn; i++ ) {
        //if( miny>point[i].y || miny==point[i].y&&minx>point[i].x )
        if( point[leftdown].y>point[i].y||zero(point[leftdown].y-point[i].y)&&point[leftdown].x>point[i].x )
            leftdown = i ;//找到最左下的点
    }
    double temp ;
    temp = point[0].x ; point[0].x = point[leftdown].x ; point[leftdown].x = temp ;
    temp = point[0].y ; point[0].y = point[leftdown].y ; point[leftdown].y = temp ;
    for( int i=1; i<inn; i++ ) {
        point[i].k = atan2( point[i].y-point[0].y, point[i].x-point[0].x ) ;
    }//以点(minx, miny)计算极角
}

double xmult( POINT &p1, POINT &p2, POINT &p0 )
{//计算叉乘--线段旋转方向和对应的四边形的面积--返回(p1-p0)*(p2-p0)叉积
    //if叉积为正--p0p1在p0p2的顺时针方向; if(x==0)共线

    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y) ;
}

int gramcmp1( const void *a, const void *b )
{
    struct POINT *c = (struct POINT *)a ;
    struct POINT *d = (struct POINT *)b ;

    if( c->k - d->k > eps )    return 1 ;
    else if( c->k - d->k < -1*eps ) return -1 ;
    else//斜率相等距离远的点在先
        return c->x - d->x > 0 ? 1 : -1 ;
}

int gramcmp( const void *a, const void *b )
{
    struct POINT *c = (struct POINT *)a ;
    struct POINT *d = (struct POINT *)b ;

    double xmult_val = xmult( *c, *d, point[0] ) ;
    if( xmult_val > eps )    return -1 ;
    else if( xmult_val < -1*eps ) return 1 ;
    else return c->x - d->x > 0 ? 1 : -1 ;
    //else 
    //return fdist( c->x,c->y,point[0].x,point[0].y )>fdist(d->x,d->y,point[0].x,point[0].y)? -1:1 ;
}

void gramham()
{//凸包的点存在于stack[]中
    qsort( point+1, inn-1, sizeof(point[1]), gramcmp ) ;//极坐标排序--注意只有(n-1)个点

    //int stack[size] ; int top = 2 ;
    stak[0] = 0 ; stak[1] = 1 ; stak[2] = 2 ; top  = 2 ;

    for( int i=3; i<inn; i++ )
    {
        while( top>=1&&xmult( point[i], point[stak[top]], point[stak[top-1]] )>=-1*eps ) 
            top-- ;//顺时针方向--删除栈顶元素
        stak[++top] = i ;//新元素入栈
    }
    /*
    for( int i=0; i<=top; i++ )
    {
    //printf( "%lf===%lf\n",point[stack[i]].x, point[stack[i]].y ) ;
    cout << point[stack[i]].x << "====" << point[stack[i]].y << endl ;
    }
    */
}

double flen_poly()
{//计算凸包的周长
    double len = 0.0 ; double x1, x2, y1, y2 ;
    for( int i=0; i<top; i++ ) {
        x1 = point[stak[i+1]].x ; x2 = point[stak[i]].x ;
        y1 = point[stak[i+1]].y ; y2 = point[stak[i]].y ;
        len += fdist( x1, y1, x2, y2 ) ;
    }
    x1 = point[stak[0]].x ; x2 = point[stak[top]].x ;
    y1 = point[stak[0]].y ; y2 = point[stak[top]].y ;
    len += fdist( x1, y1, x2, y2 ) ;

    return len ;
}

double farea_poly( int n, POINT poly[] )
{
    double area = 0.0 ; double s1 = 0.0 , s2 = 0.0 ;
    for( int i=0; i<n; i++ )
    {
        s1 += poly[stak[(i+1)%n]].y * poly[stak[i%n]].x ;
        s2 += poly[stak[(i+1)%n]].y * poly[stak[(i+2)%n]].x ;
    }

    return fabs( s1 - s2 ) / 2 ;
}

void process()
{
    gramham() ;//保存好凸包的点在stack[]中

    outarea = farea_poly( top+1, point ) ;
}

double ans;
void output()
{
    printf("%.4lf\n", outarea / ans) ;
}

void solve() {
    srand(time(0));
    int n;
    scanf("%d", &n);
    inn = n;
	for(int i=1; i<=n; i++) {
        scanf("%lf%lf", &pot[i].x, &pot[i].y);
        point[i - 1].x = pot[i].x;
        point[i - 1].y = pot[i].y;
    }
	random_shuffle(pot+1, pot+n+1);
	vec o;
	double r2 = 0;
	for(int i=1; i<=n; i++)
	{
		if((pot[i]-o).len2() > r2)
		{
			o = pot[i], r2 = 0;
			for(int j=1; j<i; j++)
			{
				if((pot[j]-o).len2() > r2)
				{
					o = (pot[i]+pot[j])/2, r2 = (pot[j]-o).len2();
					for(int k=1; k<j; k++)
					{
						if((pot[k]-o).len2() > r2)
						{
							o = circle(pot[i], pot[j], pot[k]), r2 = (pot[k]-o).len2();
						}
					}
				}
			}
		}
	}
    ans = r2 * M_PI;
    printf("%.4lf %.4lf\n", o.x, o.y);
    input();
    process();
    output();
    puts("Humanity will prevail, and the civilization of Earth will endure!");
}

G.scx的记忆碎片 https://ac.nowcoder.com/acm/contest/71344/G

写出状态转移方程后使用矩阵快速幂加速状态转移。


using mat = array<array<int, 101>, 101>;
const int mod = 998244353;

mat multiply(mat a, mat b) {
    mat r = {0};
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            for (int k = 0; k <= 100; k++) {
                r[i][k] = (r[i][k] + 1LL * a[i][j] * b[j][k]) % mod;
            }
        }
    }
    return r;
}

void solve() {
    ll m;
    cin >> m;
    int k;
    cin >> k;
    mat ans = {0};
    for (int i = 0; i <= 100; i++) ans[i][i] = 1;
    mat cur = {0};
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 9 && i - j >= 0; j++) {
            cur[i][i - j] = 1;
        }
    }
    while (m) {
        if (m % 2) ans = multiply(ans, cur);
        cur = multiply(cur, cur);
        m /= 2;
    }
    if (k == 1) {
        ans[k][0]++;
        ans[k][0] %= mod;
    }
    cout << ans[k][0] << endl;
}

H. 别卷了，总力战！https://ac.nowcoder.com/acm/contest/71344/H

先计算出一天的答案，然后直接乘天数（期望的可加性）。


void solve() {
    int k, t;
    cin >> k >> t;
    long double p;
    cin >> p;
    long double ans = 0, pre = 1;
    for (int i = 1; i <= t; i++) {
        ans += pre * p;
        pre *= (1 - p);
    }
    ans *= k;
    cout << fixed << setprecision(4) << ans << endl;
}

J.阶乘之乘 https://ac.nowcoder.com/acm/contest/71344/J

发现去掉所有末尾零也就是同时去掉一对 2 和 5 因子，直到不存在 2 因子或者不存在 5 因子为止，同时保留 K 位也就是模 10^K 的意思。

可以把先计算除了 2 和 5 因子的答案，然后把多出来的 2 因子乘上去， 因为 2 因子数量大于等于 5 因子数量，注意取模。


int f[2][9], f2[2][9], m[9];
vector<pair<int, int>> q[int(5e6 + 1)];
int ans[int(1e5 + 1)];

ll quickPow(ll a, ll b, ll m) {
    ll r = 1;
    while (b) {
        if (b % 2) r = (r * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return r;
}

void init() {
    m[0] = 1;
    for (int i = 1; i <= 8; i++) m[i] = m[i - 1] * 10;
    for (int i = 1; i <= 8; i++) f[0][i] = f2[0][i] = 1;
    
    ll a = 0, b = 0;
    for (int i = 1; i <= 5e6; i++) {
        int cur = i % 2, pre = cur ^ 1;
        
        int t = i;
        while (t % 2 == 0) {
            a++;
            t /= 2;
        }
        while (t % 5 == 0) {
            a--;
            t /= 5;
        }
        b += a;
        
        for (int j = 1; j <= 8; j++) {
            f2[cur][j] = (1LL * f2[pre][j] * t) % m[j];
            f[cur][j] = (1LL * f[pre][j] * f2[cur][j]) % m[j];
        }
        for (auto [k, id] : q[i]) {
            ans[id] = f[cur][k];
            ans[id] = (1LL * ans[id] * quickPow(2, b, m[k])) % m[k];
        }
    }
}

void solve() {
    int t;
    cin >> t;
    vector<int> k(t + 1);
    for (int i = 1; i <= t; i++) {
        int n;
        cin >> n >> k[i];
        q[n].push_back({k[i], i});
    }
    init();
    
    for (int i = 1; i <= t; i++) {
        string a(to_string(ans[i]));
        for (int j = 1; j <= k[i] - (int) a.size(); j++) {
            cout << '0';
        }
        cout << a << endl;
    }
    
}

K.寂寞沙洲冷 https://ac.nowcoder.com/acm/contest/71344/K

经典分数规划，没学过的可以看这里 https://oi-wiki.org/misc/frac-programming/

二分查找答案 ans，设当前的二分中点为 mid，对选用的边的客流量之和 sum(v[i]) 比上花费之和 sum(c[i])>=mid进行移项，得到 sum(v[i] - mid * c[i]) >= 0。

容易发现可以分开计算每一条边的贡献 W, 然后跑最小生成树算法，在森林内恰好有 K 棵树时，判定是否合法并移动左右边界。


void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    k = n - 1 - (k - 1);
    vector<array<int, 4>> e(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> e[i][0] >> e[i][1] >> e[i][2] >> e[i][3];
    }
    //sum(e[i][2]) / sum(e[i][3]) >= ans
    //sum(e[i][2]) >= ans * sum(e[i][3])
    //sum(e[i][2]) - ans * sum(e[i][3]) >= 0
    //sum(e[i][2] - ans * e[i][3]) >= 0
    cout << fixed << setprecision(6);
    long double left = 0, right = 1e4, ans = 0;
    for (int i = 1; i <= 40; i++) {
        long double mid = left + (right - left) / 2;
        sort(e.begin() + 1, e.end(), [&](array<int, 4> a, array<int, 4> b) -> int {
            return (a[2] - 1LL * mid * a[3]) > (b[2] - 1LL * mid * b[3]);
        });
        int cnt = 0;
        vector<int> root(n + 1);
        iota(root.begin() + 1, root.end(), 1);
        function<int(int)> find = [&](int x) -> int {
            if (root[x] != x) root[x] = find(root[x]);
            return root[x];
        };
        long double sum = 0;
        for (int j = 1; j <= m && cnt < k; j++) {
            auto [x, y, v, c] = e[j];
            x = find(x), y = find(y);
            if (x == y) continue;
            sum += v - 1LL * mid * c;
            cnt++;
            root[x] = y;
        }
        
        if (sum >= 0) {
            left = mid;
            ans = mid;
        } else {
            right = mid;
        }
    }
    
    cout << ans << endl;
}

L. 动手学自然语言处理 https://ac.nowcoder.com/acm/contest/71344/L

对每个状态 S, 记录它所有后继状态里面出现次数最大的那个。

看成从每个句子开头进行匹配了，写了个字典树，喜提两发 WA。


void solve() {
    map<string, map<string, int>> tr;
    map<string, string> mx;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        string pre;
        cin >> pre;
        for (int j = 2; j <= k; j++) {
            string cur;
            cin >> cur;
            int cnt = ++tr[pre][cur];
            int mxcnt = tr[pre][mx[pre]];
            if (cnt > mxcnt || (cnt == mxcnt && mx[pre] > cur)) {
                mx[pre] = cur;
            }
            pre = cur;
        }
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        string first;
        cin >> first;
        cout << first << ' ';
        for (int j = 2; j <= 21; j++) {
            if (!mx.count(first)) break;
            first = mx[first];
            cout << first << ' ';
        }
        cout << endl;
    }

}

M.终不似，少年游 https://ac.nowcoder.com/acm/contest/71344/M

按题意进行模拟。

void solve() {
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 2; i < s.size(); i++) {
        string c(s.substr(i - 2, 3));
        if (c == "hzy") ans += 3;
        if (c == "zzy") ans += 3;
        if (c == "syh") ans += 3;
    }
    cout << ans << endl;
}

全部评论
求一下G题的dp方程是什么
点赞 回复 分享
发布于 2023-12-28 14:56 天津

相关推荐

09-23 12:28
门头沟学院 嵌入式软件工程师
点赞 评论 收藏
分享
09-24 18:07
门头沟学院 Java
被面试官骂到自闭
被面试官骂到自闭，现在怀疑自己到底真的适不适合互联网也不能说是骂吧，可能是他的语气过于严厉，大学三年确实除了校内的奖学金和基本证书几乎没有别的奖项了，也没有想着去实习，一放假就回家，那时候想着以后上班了回家时间就短了，万万没有想到原来假期是用来实习的被面试官说这么没有规划不如早点放弃回家考公，可是现在考公也很难啊。问我的三个优缺点，被一个又一个否定，秋招接到的面试说实话不多，可能因为简历确实空白，想着好不容易有个中大厂面试，要好好表现，结果一塌糊涂。高中好不容易才考上个211，也不想继续读研，算了，就抱怨抱怨，抱歉啦
奶龙带你风风光光：你没有错，错的是这个过度内卷的畸形就业环境
我的秋招日记
点赞 评论 收藏
分享
09-15 15:53
Java
避雷东软集团不把实习生当人看
投递东软集团等公司10个岗位
点赞 评论 收藏
分享
08-19 18:28
北京邮电大学 Java
点赞 评论 收藏
分享
09-26 16:38
中南大学 营销
点赞 评论 收藏
分享
评论
5
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 国企秋招，你投了吗？ #
18562次浏览 157人参与
# 应届生第一份工作最好去大厂吗？ #
23897次浏览 463人参与
# 思朗科技求职进展汇总 #
53363次浏览 380人参与
# 你在职场中沾染到的“坏”习惯 #
14904次浏览 119人参与
# 机械人，你最希望上岸的公司是？ #
184281次浏览 1899人参与
# 拿到offer之后，可以做些什么 #
32450次浏览 192人参与
# 携程求职进展汇总 #
620095次浏览 4557人参与
# 海尔求职进展汇总 #
8295次浏览 35人参与
# 你会为了工作牺牲生活吗？ #
43903次浏览 348人参与
# 机械只有转码才有出路吗？ #
140399次浏览 1629人参与
# 通信硬件岗投递时间线 #
25821次浏览 88人参与
# 贝壳求职进展汇总 #
28667次浏览 162人参与
# 央国企投递记录 #
111919次浏览 1451人参与
# 互联网回暖，腾讯要招5000人！ #
21626次浏览 584人参与
# 入职跑路最快的一次经历 #
32403次浏览 213人参与
# 机械求职避坑tips #
64952次浏览 441人参与
# 硬件开发岗知多少 #
17494次浏览 124人参与
# ___岗狗都不干，我干！ #
17747次浏览 121人参与
# 为什么国企只招应届生 #
201084次浏览 1223人参与
# kpi面有什么特征 #
79271次浏览 463人参与
# 校招谈薪技巧 #
47467次浏览 679人参与
# 歌尔求职进展汇总 #
65997次浏览 352人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务