题解：P13202 [GCJ 2016 #3] Teaching Assistant

chinazhanghaoxun · 2025-08-10 21:50:22 · 题解

P13202 Teaching Assistant - Solution

Problem Statement

给定 T 个由 C 和 J 构成的字符串，按照题意的方式求出一种使得题集得分最多的方式。

Analysis

看到要求最大值，考虑贪心。

由不同情况，简单分析可得：

• 若 s[i]=s[i+1]，我只要令申请的题集编号也等于 s[i] 就可以得到 10 分
• 若找不到 s[i]=s[i+1]，那么令题集编号为 C 和 J 中的任意一个都可以得到最优分数 5 分

Approach

使用栈存储此前未配对成功的字符，若当前找到相等字符，弹出，ans\gets ans+10。否则继续压入栈中，等待下一轮匹配。

相等字符匹配完后一定会剩下，设为 rest 个字符，且它们相邻一定是不同的。则这一部分产生的贡献为 \frac{rest}2 \times 5。

因此，总答案就是 ans+\frac{rest}2 \times 5，完成一次询问。

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,cases=1;
    cin>>t;
    while(t--){
        string s;
        int n,ans=0;
        stack<char> st;
        cin>>s;
        n=s.size();
        for(int i=0;i<n;i++){
            if(!st.empty() && s[i]==st.top()){
                st.pop();
                ans+=10;
            }else{
                st.push(s[i]);
            }
        }
        cout<<"Case #"<<cases<<": "<<ans+st.size()/2*5<<endl;
        cases++;
    } 
    return 0;
}