Codeforces Educational Round 12 655ABCDE

Codeforces Educational Round 12 통과 수: 3 A: 처음에 공식 적 인 분류 토론 을 했 는데 폭력 이 야 말로 더욱 아름 다운 해법 이라는 것 을 알 게 되 었 습 니 다.
#include 
using namespace std;
const int MAXN = 10 + 5;
char str[MAXN];
int main()
{
    int x1, y1, x2, y2;
    while(scanf("%d%d%d%d", &x1, &y1, &x2, &y2) != EOF) {
        scanf("%s", str);
        int st = ((str[0] - '0') * 10 + (str[1] - '0')) * 60 + (str[3] - '0') * 10 + str[4] - '0';
        int en = st + y1;
        int ans = 0;
        int now = 300;
        while(now < 1440) {
            if(now + y2 > st && now < en) ans++;
            now += x2;
        }
        printf("%d
"
, ans); } return 0; }

B: 폭력 시 뮬 레이 션
#include 
using namespace std;
const int MAXN = 100 + 5;
int id[MAXN];
int pos[MAXN];
int n, m, l;
int remov(int mark)
{
    int res = id[mark];
    for(int i = res ; i >= 2 ; i--) {
        pos[i] = pos[i - 1];
        id[pos[i]] = i;
    }
    pos[1] = mark;
    id[mark] = 1;
    return res;
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &l) != EOF) {
        for(int i = 1 ; i <= l ; i++) {
            int u; scanf("%d", &u);
            pos[i] = u; id[u] = i;
        }
        int ans = 0;
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= m ; j++) {
                int u; scanf("%d", &u);
                int temp = remov(u);
//                printf("i = %d, j = %d, temp = %d
"
, i, j, temp); // for(int k = 1 ; k <= l ; k++) printf("%d ", pos[k]); // puts(""); // system("pause"); ans += temp; } } printf("%d
"
, ans); } return 0; }

C: 같은 욕심 을 계속 바 꾸 면 돼 요.
#include 
using namespace std;
const int MAXN = 2e5 + 5;
char str[MAXN];
int main()
{
    while(scanf("%s", str) != EOF) {
        int len = strlen(str);
        int now = 0;
        for(int i = 1 ; i < len ; i++) {
            if(str[i] == str[now]) continue;
            else {
//                printf("i = %d, now = %d
", i, now);
for(int j = now + 1 ; j <= i - 1 ; j += 2) { for(int k = 0 ; k < 26 ; k++) { // printf("j = %d, k = %d
", j, k);
if(j > 0 && str[j - 1] - 'a' == k) continue; if(j < len - 1 && str[j + 1] - 'a' == k) continue; str[j] = k + 'a'; break; } } now = i; } } int i = len; for(int j = now + 1 ; j <= i - 1 ; j += 2) { for(int k = 0 ; k < 26 ; k++) { // printf("j = %d, k = %d
", j, k);
if(j > 0 && str[j - 1] - 'a' == k) continue; if(j < len - 1 && str[j + 1] - 'a' == k) continue; str[j] = k + 'a'; break; } } cout << str << endl; } return 0; }

D: / * 부분 집합 의 구성 은 두 가지 만 있 을 수 있 습 니 다. 하 나 는 1 이 고 하 나 는 합 법 적 인 비 1 수 입 니 다. 하 나 는 합 법 적 인 비 1 수 입 니 다.
                         1 

*/
#include 
using namespace std;
const int MAXN = 2e6 + 5;
bool prime[MAXN];
void init()
{
    for(int i = 0 ; i < MAXN ; i++) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i = 2 ; i < MAXN ; i++) {
        if(prime[i] == false) continue;
        for(int j = i + i ; j < MAXN ; j += i)
             prime[j] = false;
    }
}
int n;
struct Node
{
    int u, id;
}a[1000 + 5];
bool cmp(Node a, Node b) {return a.u < b.u;}
int main()
{
    init();
    while(scanf("%d", &n) != EOF) {
        for(int i = 1 ; i <= n ; i++) scanf("%d", &a[i].u), a[i].id = i;
//        puts("zero");
        sort(a + 1, a + 1 + n, cmp);
//        puts("zero2");
        int mark = n + 1;
        int zeronum = 0;
        for(int i = 1 ; i <= n ; i++) {
            if(a[i].u != 1) {
                mark = i;
                break;
            }
            else zeronum++;
        }
        int ans1 = zeronum;
        int re = -1;
        for(int i = mark ; i <= n ; i++) if(prime[1 + a[i].u]) {ans1++; re = a[i].u; break;}
//        puts("first");
        int ans2 = 0;
        int re2, re3;
        re2 = re3 = -1;
        for(int i = mark ; i <= n ; i++) {
            for(int j = i + 1 ; j <= n ; j++) {
                if(prime[a[i].u + a[j].u]) {
                    ans2 = 2;
                    re2 = a[i].u, re3 = a[j].u;
                }
            }
        }
//        puts("second");
        int ans3 = 1;
        if(ans1 >= ans2 && ans1 >= ans3) {
            printf("%d
"
, ans1); int f = 1; for(int i = 1 ; i < ans1 ; i++) printf("%d ", 1); if(re != -1) printf("%d", re); else printf("%d", 1); puts(""); } else if(ans2 >= ans1 && ans2 >= ans3) { printf("%d
"
, ans2); printf("%d %d
"
, re2, re3); } else { printf("%d
%d
"
, ans3, a[1].u); } } return 0; }

E: / * 이전 모든 수의 이 또는 화 를 알 고 있 는 sum [l, r] = sum [1, l - 1] ^ sum [1, r]
                   
         

*/
#include 
using namespace std;
#define LL long long
const int MAX = 31;
const int MAXN = 1e6 + 5;
const int MAXM = MAX * MAXN;
int num[MAXM];
int ne[MAXM][2];
int cnt;
int n, k;
string toS(int u)
{
    string str = "";
    while(u) {
        if(u & 1) str += '1';
        else str += '0';
        u /= 2;
    }
    while(str.size() < MAX - 1) str += '0';
    reverse(str.begin(), str.end());
    return str;
}
int query(string str, string st)
{
    int now = 0;
    int ans = 0;
    int mark = 0;
    while(now < str.size() && mark != -1) {
        if(str[now] == '0' && st[now] == '0') {
            if(ne[mark][1] != -1) ans += num[ne[mark][1]];
            mark = ne[mark][0];
        }
        else if(str[now] == '0' && st[now] == '1') {
            mark = ne[mark][1];
        }
        else if(str[now] == '1' && st[now] == '0') {
            if(ne[mark][0] != -1) ans += num[ne[mark][0]];
            mark = ne[mark][1];
        }
        else if(str[now] == '1' && st[now] == '1') {
            mark = ne[mark][0];
        }
        now++;
    }
    if(mark != -1)
        ans += num[mark];
    return ans;
}
void ins(string str)
{
    int u = 0;
    for(int i = 0 ; i < str.size() ; i++) {
        int j = str[i] - '0';
        if(ne[u][j] == -1) ne[u][j] = ++cnt;
        num[u]++;
//        printf("%d ", u);
        u = ne[u][j];
    }
    num[u]++;
//    puts("");
}
int main()
{
    while(scanf("%d%d", &n, &k) != EOF) {
        memset(num, 0, sizeof num);
        memset(ne, -1, sizeof ne);
        long long ans = 0;
        cnt = 0;
        int sum = 0;
        string st = toS(k);
        for(int i = 0 ; i <= n ; i++) {
            int u;
            if(i > 0)
                scanf("%d", &u);
            else u = 0;
            u = u ^ sum;
            string str = toS(u);
            int temp = query(str, st);
//            printf("i = %d, temp = %d, u = %d
", i, temp, u);
// cout << str << endl; ans = ans + temp; // cout << str << endl; ins(str); sum = u; } printf("%I64d
"
, ans); } return 0; }

좋은 웹페이지 즐겨찾기