除了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 天津

相关推荐

头像
01-29 21:09
蚌埠坦克学院 嵌入式软件开发
点赞 评论 收藏
分享
头像
02-02 11:17
浙江大学 全栈开发
2.2 基本概念
给LLM提示你可以通过简单的提示词（Prompts）获得大量结果，但结果的质量与你提供的信息数量和完善度有关。一个提示词可以包含你传递到模型的指令或问题等信息，也可以包含其他详细信息，如上下文、输入或示例等。你可以通过这些元素来更好地指导模型，并因此获得更好的结果。看下面一个简单的示例：提示词：&nbsp;The&nbsp;sky&nbsp;is&nbsp;输出：&nbsp;blue.&nbsp;如果你正在使用OpenAI&nbsp;Playground或其他任何LLM&nbsp;Playground，你可以按照以下屏幕截图中的方式提示模型：需要注意的是，当使用&nbsp;OpenAI&nbsp;的&nbsp;gpt-4&nbsp;或者&nbsp;gpt-3.5-turbo&nbsp;等聊天模型时，你可以使用三个不同的角色来构建&nbsp;...
提示词工程指南
点赞 评论 收藏
分享
01-08 16:51
字节跳动_后端开发(实习员工)
七站字节
现在已经流转了三个部门了
牛客76783384...：字节：不要放箭，活捉赵子龙
点赞 评论 收藏
分享
01-16 15:41
已编辑
中国科学院大学 FPGA工程师
点赞 评论 收藏
分享
01-31 15:05
浙江大学 算法工程师
点赞 评论 收藏
分享
评论
5
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 论秋招对个人心气的改变 #
3586次浏览 69人参与
# 牛客AI体验站 #
1839次浏览 63人参与
# 刚入职的你踩过哪些坑 #
2540次浏览 61人参与
# 在大厂上班是一种什么样的体验 #
2096次浏览 26人参与
# 程序员找工作至少要刷多少题？ #
4868次浏览 82人参与
# 关于春招/暑期实习，你想知道哪些信息？ #
2713次浏览 64人参与
# 一张图晒一下你的AI员工 #
1646次浏览 45人参与
# 为了减少AI幻觉，你注入过哪些设定？ #
1034次浏览 35人参与
# 我现在比当时_，你想录用我吗 #
2571次浏览 42人参与
# 程序员能干到多少岁？ #
3707次浏览 53人参与
# 产品人求职现状 #
320359次浏览 2422人参与
# AI Coding的使用心得 #
1482次浏览 38人参与
# 你的工资什么时候发？ #
55496次浏览 345人参与
# 实习，不懂就问 #
163079次浏览 1453人参与
# 你投了多少份简历了？ #
421542次浏览 3937人参与
# 金三银四，你有感觉到吗 #
679434次浏览 6047人参与
# 帆软软件工作体验 #
12493次浏览 67人参与
# 暑假倒计时，你都干了些啥？ #
40153次浏览 213人参与
# 晒晒你司的新年福利 #
2430次浏览 47人参与
# 软开人，秋招你打算投哪些公司呢 #
180036次浏览 1379人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务