【Codeforces】Codeforces Round #53

Problem A (div 2)

输出个就完事了。

时间复杂度为

#include <cstdio>

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        printf("%d\n", n);
        for(int i = 0; i < n; i++)
        {
            if(i)printf(" ");
            printf("1");
        }
        printf("\n");
    }
    return 0;
}

Problem B (div 2)

首先找出尽可能多的可以选出来并删掉的【两个连续且相同的字母】。这个可以用类似括号匹配的方法维护一个栈来完成。
设找到的字母对数为，那么当为奇数时先手必胜，否则先手必败。

时间复杂度为

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    string s;
    while(cin >> s)
    {
        stack<char> stk;
        int ans = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if((!stk.empty()) && (s[i] == stk.top()))
            {
                ans++;
                stk.pop();
            }
            else
            {
                stk.push(s[i]);
            }
        }
        if(ans & 1)
        {
            cout << "Yes" << endl; 
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

Problem A (div 1)

把4*4的网格划成上下两个部分。分别是两行四列的区域。将竖的放到其中一个区域，横的放到另外一个区域。这样的话就永远有空位可以放了。

时间复杂度为

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int mp[5][5];

void Clean(int x, int y)
{
    int cntx = 0, cnty = 0;
    for(int i = 0; i < 4; i++)
    {
        cntx += mp[x][i];
        cnty += mp[i][y];
    }
    if(cntx == 4)
    {
        for(int i = 0; i < 4; i++)
        {
            mp[x][i] = 0;
        }
    }
    if(cnty == 4)
    {
        for(int i = 0; i < 4; i++)
        {
            mp[i][y] = 0;
        }
    }
}

pair<int, int> getAns(int a)
{
    if(a == 0)
    {
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(mp[i][j] != 0)continue;
                if(mp[i+1][j] != 0)continue;
                mp[i][j] = 1;
                mp[i+1][j] = 1;
                Clean(i, j);
                Clean(i+1, j);
                return make_pair(i+1, j+1);
            }
        }
    }
    else
    {
        for(int i = 2; i < 4; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(mp[i][j] != 0)continue;
                if(mp[i][j+1] != 0)continue;
                mp[i][j] = 1;
                mp[i][j+1] = 1;
                Clean(i, j);
                Clean(i, j+1);
                return make_pair(i+1, j+1);
            }
        }
    }
    return make_pair(-1, -1);
}

int main()
{
    string s;
    while(cin >> s)
    {
        memset(mp, 0, sizeof(mp));
        for(int i = 0; i < s.length(); i++)
        {
            pair<int, int> pr = getAns(s[i] - '0');
            cout << pr.first << " " << pr.second << endl;
        }
    }
    return 0;
}

后续待补充