A Nowcoder Weekly Contest

语法题，判断即可。

void solve()
{
    int n;
    cin >> n;
    if(n < 1600)
        cout << "Rated\n";
    else cout << "Unrated\n";
}

B ICPC Medal

模拟题，只要铜牌能换银牌，一直处理即可。

void solve()
{
    int a, b , c, x, y;
    cin >> a >> b >> c >> x >> y;
    int p = 0, q = 0;
    do
    {
        p = c / x;           //兑换的银牌
        c = c % x;    		 //剩余的铜牌
        q = (b + p) / y;     //兑换的金牌
        b = (b + p) % y;
        a = a + q;      	 //获得的金牌
        c = c + q;      	 //副产物的铜牌+原有的
    } while(c >= x);
    cout << a << endl;
}

C Unique Number

前缀中所有元素加1，那么第一个元素一定最大，记这个为，如果,因为要不同数值的种类数 最大，因此令，这样一定最优。(如果后面有也不影响，如果没有，这样会使答案增加，因此一定最优。)否则，只能，最后输出val的种类数，我用set记录了一下，最后输出set大小即可

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    set<int> s;
    s.insert(a[0]);
    int val = a[idx];
    for(int i = idx + 1; i < n; i++)
    {
        if(a[i] >= val)
        {
            if(val - 1 >= 0)
            {
                val--;
                s.insert(val);
            }
        }
        else
        {
            s.insert(a[i]);
            val = a[i];
        }
    }
    cout << s.size() << endl;
}

D Balanced Array

这样求合法区间个数可以考虑每个以开头的贡献，比如以开头能扩展到，，那么这个贡献就是。平衡满足的条件常用队列去维护，我这里用了map，map内部自动有序(按第一关键字升序)，因此就是最小值，就是最大值。

退出循环时，说明当前已经扩展到,说明处的每一个都能扩展到,可以直接公式计算，我在写的时候又遍历一遍。其中也可以写成。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)	cin >> a[i];
    map<int, int> mp;
    int l = 1, r = 1, ans = 0;
    while (r <= n)
    {
        if (mp.empty())
        {
            mp[a[r]]++;
            r++;
            continue;
        }
        int minn = mp.begin()->first, maxn = mp.rbegin()->first;
        int x = a[r];
        if (a[r] - minn > 1 || maxn - a[r] > 1)    //产生不平衡的情况
        {
            ans += r - l;						   //l处可以产生的贡献
            mp[a[l]]--;							   //左边界右移，要去掉原左边界的影响
            if (mp[a[l]] == 0) mp.erase(a[l]);	   //最小值改变了
            l++;
        }
        else 
        {
            mp[a[r]]++;
            r++;
        }
    }
    //r>n时,l-n处的贡献为i-n
    for (int i = l; i <= n; i++)
        ans += n - i + 1;
    cout << ans << endl;
}

E Maximize The Sum

首先，无论怎么改变还是，改变以后变成，起负作用，因此均不考虑。现在考虑含有一个的情况：

1. ，进入循环，
2. 同上
3. 同上,

我们发现只有一个的情况能且只能变成有两个的情况，并且因为循环，的位置可以是三个中任意一位，放最后一位即可，这样可以一直推着跑，直到遇到的情况。

这样直接从左到右考虑一遍会，因为可能很长的字符串，只有右边或者中间有1，因此从左往右推一遍，再从右往左推一遍即可。

有的贪心题目也需要从左往右一遍，从右往左一遍，然后取最大值。

int cul(int n, vector<int> &a)	//引用直接改变原数组
{
     for(int i = 0, x, y, z; i < n - 2; i++) 
    {
        x = a[i], y = a[i + 1], z = a[i + 2];
        if((x & y & z) == 1 || (x | y | z) == 0)  
            continue;    	//全1,全0都跳过
        else    			//不管x,y,z有1个1还是两个1,都能转换成110的排列
            a[i] = 1, a[i + 1] = 1, a[i + 2] = 0;
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += a[i];
    return ans;
}
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(n, 0);
    for(int i = 0; i < n; i++)
    {
        a[i] = (s[i] == '0' ? 0 : 1);
    }
	cul(n, a);
    reverse(a.begin(), a.end());	//反转以后相当于从右往左
    ans = cul(n, a);
    cout << ans << endl;
}

F Palindromic Value

刚开始我也没头绪，后来发现有点像D题那样，求部分的答案，再整合成最终答案，似乎可以。

部分的答案怎么求呢 我开始先计算出对于每一个，从开始的回文串，并把末位的下标放到数组中。

发现如果要计算处价值，需要知到后面的价值， 因此从后往前遍历，对于每一个，遍历它的回文串右边界，总的价值处的价值，

写完后发现第二个样例就过不了，简单模拟一遍，发现每个回文串的价值少算了，因为以该回文串开始，后面可能有多种方案数，也就是说后面的每种方案数，都会使这个回文串的价值算一次，因此加上一个统计合法方案数的数组即可。

总结

1. 求每个开始的回文串的右边界(注意，不是最大回文串)，存到中；
2. 从右往左遍历，对于每个，遍历每个右边界，；
3. 最后输出即可。

我写这个判断回文串因为时间紧用了遍历的方法，时间复杂度为，理论上会超时，但中间有剪枝，常数因子不大，因此竟然过了，多谢苯环老师不卡。后面附上方法。

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> vec[n]; 
    //vec[i][j]记录以i开头的所有回文串的最后一个位置
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            bool flag = true;
            for(int l = i, r = j; l < r; l++, r--)
            {
                if(s[l] != s[r])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                vec[i].push_back(j);
        }
    }
    vector<int> dp(n + 1, 0), cnt(n + 1, 0);//dp[i]存i往后的价值和，cnt[i]存i往后的有效方案数
    cnt[n] = 1;//对于n-1处的字符来说，本身也算一种且只能算一次，因此后面的空回文串也算一种方案
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = 0; j < vec[i].size(); j++)
        {
            int r = vec[i][j];
            int len = r - i + 1;
            int w = cnt[r + 1];
            cnt[i] = (cnt[i] + cnt[r + 1]) % mod;
            dp[i] = (dp[i] + len * len % mod * cnt[r + 1]) % mod;
            if(r < n - 1)   //如果r不是最后一个字符，则可以继续往后扩展
                dp[i] = (dp[i] + dp[r + 1]) % mod;
        }
    }

    cout << dp[0] << endl;
}

    vector<int> vec[n];    //记录以i开头的所有回文串的最后一个位置
    //预处理
    vector<vector<bool>> flag(n, vector<bool>(n, false));
    //边界
    for (int i = 0; i < n; i++) 
        flag[i][i] = true;
    for (int i = 0; i + 1 < n; i++) 
        flag[i][i + 1] = (s[i] == s[i + 1]);
        
    for (int len = 3; len <= n; len++) 
    {
        for (int i = 0; i + len - 1 < n; i++) 
        {
            int j = i + len - 1;
            flag[i][j] = (s[i] == s[j] && flag[i + 1][j - 1]);
        }
    }

    for (int i = 0; i < n; i++) 
        for (int j = i; j < n; j++) 
            if (flag[i][j]) {
                vec[i].push_back(j);

其他的一样