Codeforces Round #401 (Div. 2)

题面：http://codeforces.com/contest/777

A. Shell Game

题意：一个常见的小游戏，有三个碗，有一个小球一开始放在中间的碗。然后会经过n次交换，已知第奇数次交换会将左边和中间的交换，偶数次时会将右边和中间的交换。告诉你经过n次以后，球在x位置，求球的原位置。
解法：找循环节，6次以后会循环。所以将读入的n模6以后模拟一下即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e4;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    n %= 6;
    int a[] = {0, 1, 2};
    for(int i = 1; i <= n; i++)
        if(i % 2)
            swap(a[0], a[1]);
        else
            swap(a[1], a[2]);
    cout << a[x] << endl;
    return 0;
}

B. Game of Credit Cards

题意：一个类似于田忌赛马的游戏。共有n轮，赢的人可以flick对方，如果是平局则双方不进行。两个人一个人可以任意调整出场顺序。先问你如何出场能够保证能flick对方最多次及最少能被flick多少次。
解法：贪心。要注意到，这两者所采取的策略是不同的。一个需要尽可能多的大于对方，另一个是需要尽可能多的大于等于对方。所以每次遇到一个数字，要找到一个最小的大于或者大于等于对方的数，如果不存在这样的数，则让当前最小的数去输这一局。

#include <bits/stdc++.h>
using namespace std;
int a[2000], b[2000];
bool vis[2000];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    for(int i = 0; i < n; i++)
    {
        a[i] = s1[i] - '0';
        b[i] = s2[i] - '0';
    }
    sort(b, b + n);
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int j = 0;
        for(j = 0; j < n; j++)
            if(!vis[j] && b[j] >= a[i])
            {
                vis[j] = 1;
                break;
            }
        if(j == n)
        {
            for(int j = 0; j < n; j++)
                if(!vis[j])
                {
                    vis[j] = 1;
                    break;
                }
            cnt++;
        }
    }
    cout << cnt << endl;
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < n; i++)
    {
        int j = 0;
        for(j = 0; j < n; j++)
            if(!vis[j] && b[j] > a[i])
            {
                cnt++;
                vis[j] = 1;
                break;
            }
        if(j == n)
        {
            for(int j = 0; j < n; j++)
                if(!vis[j])
                {
                    vis[j] = 1;
                    break;
                }
        }
    }
    cout << cnt << endl;
}

C.

题意：给定一个n*m的矩阵，定义一个区间是非递减序列：如果对于这个行号区间，存在一列使得这一列中的序列是非递减的。输入k组区间，问你他们是不是非递减序列区间。
解法：dp
定义dp[i]为以第i行作为末尾的最长的区间长度。这样的一个状态设计是具有无后效性的。显然每次状态转移都是以上一行中每一列中的长度转移而来的。
令non_desc[i]为某行第i列的最大长度，显然这个数组是可以滚动利用的。
每次计算完一行以后，将最大值保存到dp[i]中。
这道题还有一个问题就是没告诉你n和m的范围。一开始使用了vector a[maxn] 很费空间。
后来想到每次只需要两行两行处理，所以可以滚动数组即可。

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn][2];
int non_desc[maxn];
int dp[maxn];
int main()
{
    //    ios::sync_with_stdio(false);
    //    cin.tie(0);
    int n, m;
    scanf("%d%d", &n, &m);
    for(int j = 0; j < m; j++)
        scanf("%d", &a[j][0]);
    int f = 1;
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            scanf("%d", &a[j][f]);
        int maxlen = 0;
        for(int j = 0; j < m; j++)
        {
            if(a[j][f] >= a[j][!f])
                non_desc[j] = non_desc[j] + 1;
            else
                non_desc[j] = 0;
            maxlen = max(maxlen, non_desc[j]);
        }
        dp[i] = maxlen;
        f = !f;
    }
    //    for(int i = 0; i < n; i++)
    //        cout << dp[i] << endl;
    int k;
    scanf("%d", &k);
    while(k--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l--;r--;
        int maxlen = dp[r];
        if(maxlen >= r - l)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

D. Cloud of Hashtags

题意：给定一串字符串，要求处理后所有的字符串以字典序升序排列。每次可以删去一个字符串中最后一个字符，问最少可以删多少字符。
解法：暴力&贪心
从后向前处理，从前向后处理，如果遇到比后面的某个字符大，则将后续字符串全部删除。
也可以二分找到位置，代码中使用了二分。
所以这其实又是一道水题。

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int maxn = 5e5 + 10;
string s[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> s[i];
    for(int i = n - 2; i >= 0; i--)
    {
        int l = 1, r = (int)s[i].length() + 1;
        string q = s[i];
        if(q > s[i + 1])
        {
            for(int j = 0; j < 30; j++)
            {
                int mid = (l + r) / 2;
                q = s[i].substr(0, mid);
                if(q <= s[i + 1])
                    l = mid;
                else
                    r = mid;
            }
        }
        s[i] = q;
    }
    for(int i = 0; i < n; i++)
        cout << s[i] << endl;
    return 0;
}

E. Hanoi Factory

题意：背景是汉诺塔问题。给定一些盘子，每个盘子有内径和外径及其高度。一个盘子能够被放在上面的条件是它的外经比下方盘子的内径大并且比外径小。
解法：排序 & 栈
首先将所有的盘子按外径从大到小排序，再将内径从大到小排序。为什么内径也需要从大到小排序呢。是因为如果外径相同，内径越小，越有利于后面放盘子，因为上方盘子的内径要介于下方的内外径区间间。
然后再用一个栈模拟即可。
由于外径从大到小排序，所以外径已经满足要求，如果当前盘子的外径径小于栈顶的内径，那么显然下一个盘子也不能放（因为外径递减）。这个时候就将栈顶的元素弹出知道满足内径的条件。再放下一个盘子，每次更新记录最大值。
有一点遍历了所有可能性的感觉，要记住这种感觉。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
struct node{
    int a, b;//a为内径、b为外径
    ll h;
}r[maxn];
bool cmp(const node& x, const node &y)
{
    if(x.b == y.b)
        return x.a > y.a;
    return x.b > y.b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> r[i].a >> r[i].b >> r[i].h;
    sort(r, r + n, cmp);
    stack<node> q;
    q.push(r[0]);
    ll ans = r[0].h, len = r[0].h;
    for(int i = 1; i < n; i++)
    {
        while(q.size() && r[i].b <= q.top().a)
        {
            len -= q.top().h;
            q.pop();
        }
        len += r[i].h;
        q.push(r[i]);
        ans = max(len, ans);
    }
    cout << ans << endl;
    return 0;
}