Educational Codeforces Round 114 (Rated for Div. 2)

思路：

枚举，我们让出现先连续左括号和出现右括号的数量一一对应，我们从连续出现n个左括号开始枚举，下一次枚举是先连续出现n-1个左括号，在下一次是n-2……直到最后只能先有1个左括号为止，我们可以记录一个变量cnt，来记录当前的枚举，枚举一种情况后cnt++，即前半部分先枚举了n-cnt，然后再枚举cnt种

举个例子，当n为4时，所有情况为：

cnt = 0，-> （（（（））））

cnt = 1, -> （（（）））（）

cnt = 2, -> （（））（（））

cnt = 3, -> （）（（（）））

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int>PII;
typedef long long LL;
 
const int N = 100010;
 
int a[N];
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        int cnt = 0;
        for (int j = 1; j <= n; j++)
        {
            string res;
            for (int i = 1; i <= n - cnt; i++) res += "(";
            for (int i = 1; i <= n - cnt; i++) res += ")";
            for (int i = 1; i <= cnt; i++) res += "(";
            for (int i = 1; i <= cnt; i++) res += ")";    
 
            cnt++;
 
            cout << res << endl;
        }
 
    }
    return 0;
 
}

B. Combinatorics Homework

思路：

思维题，因为这题要我们判断，是否有正好m对，我们先算出cnt1最多可以组成多少对，再算出cnt2最少可以组成多少对，当m介于两者之间时，一定存在正好m对的情况，否则一定不存在

而由于三种字符最多可以组成的对数各为a - 1,b - 1, c - 1对，所以cnt1 = a + b + c - 3

最少的情况我们这么考虑，假设A的数量最多，而本来A可以组成a - 1对，而当我们在每两个A间都插入一个B或一个C后，对子数就变为最少，变为a - 1 - b - c对，当然这个答案可能是负的，但是当答案是负的的情况表示可以一个对子都没有，那么这种情况我们把cnt2置为0，表示有0个对子就好了。当然，这只是A最多的情况，当B最多或者C最多的情况同理，只要判断一下谁最多就好了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int>PII;
typedef long long LL;
 
const int N = 100010;
 
int a[N];
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int a, b, c, m;
        cin >> a >> b >> c >> m;
        int cnt1 = 0;
        cnt1 += a + b + c - 3;//最多可以组成的对子数
        int cnt2 = 0;//最少对子数
        if(a >= b && a >= c) cnt2 += a - b - c - 1;
        else if(b >= a && b >= c) cnt2 += b - a - c - 1;
        else if(c >= a && c >= b) cnt2 += c - b - a - 1;
        if (cnt2 < 0) cnt2 = 0;
        if (cnt2 <= m && cnt1 >= m) cout << "YES" << endl;
        else cout << "NO" << endl;
 
    }
    return 0;
 
}
//1 8 1 0
//abacaaaaaa
//3 2 1 0
//ababac
//3 2 1 1
//abbaca

C. Slay the Dragon

思路：

用lower_bound,

卡cin　

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

typedef pair<int, int>PII;
typedef long long LL;

const int N = 200010;

int n, m;
LL a[N];
LL x, y;
LL sum;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    sort(a + 1, a + n + 1);

    cin >> m;
    while (m--)
    {
        cin >> x >> y;
        int idx = lower_bound(a + 1, a + n + 1, x) - a;
        LL res = 1e18, minx = 0, maxx = 0;
        if (idx == n + 1)//如果找到了末尾,那么肯定是选最后的更优 
        {
            idx--;
            res = x - a[n];
            if (y - (sum - a[n]) > 0) res += y - (sum - a[n]);
        }
        else//选择idx的位置
        {
            LL tmp = 0;
            if (x > a[idx]) tmp += x - a[idx];
            if (y - (sum - a[idx]) > 0) tmp += y - (sum - a[idx]);
            res = min(res, tmp);

            tmp = 0; 
            idx--;
            if (idx != 0)
            {
                if (x > a[idx]) tmp += x - a[idx];
                if (y - (sum - a[idx]) > 0) tmp += y - (sum - a[idx]);
                res = min(res, tmp);
            }
        }
        
        cout << res << endl;
    }
    return 0;

}

真是个悲伤的故事。。。

Educational Codeforces Round 114 (Rated for Div. 2)

推荐阅读