Codeforces Round #365 (Div. 2) （705A，705B（博弈），704A）

Hulk

题目链接：

http://codeforces.com/contest/705/problem/A

解题思路：

Just alternatively print "I hate that" and "I love that", and in the last level change "that" to "it".

Time Complexity: 

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(~scanf("%d",&n)){
        cout<<"I hate";
        for(int i = 2; i <= n; ++i){
            if(i&1)
                cout<<" that I hate";
            else
                cout<<" that I love";
        }
        cout<<" it"<<endl;
    }
    return 0;
}

Spider Man

题目链接：

http://codeforces.com/contest/705/problem/B

解题思路：

First of all, instead of cycles, imagine we have bamboos (paths). A valid move in the game is now taking a path and deleting an edge from it (to form two new paths). So, every player in his move can delete an edge in the graph (with components equal to paths). So, no matter how they play, winner is always determined by the parity of number of edges (because it decreases by 1 each time). Second player wins if and only if the number of edges is even. At first it's even (0). In a query that adds a cycle (bamboo) with an odd number of vertices, parity and so winner won't change. When a bamboo with even number of vertices (and so odd number of edges) is added, parity and so the winner will change.

Time Complexity: 

AC代码：

#include <bits/stdc++.h>
using namespace std;

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

Thor

题目链接：

http://codeforces.com/problemset/problem/704/A

解题思路：

Consider a queue e for every application and also a queue Q for the notification bar. When an event of the first type happens, increase the number of unread notifications by 1 and push pair (i, x) to Q where i is the index of this event among events of the first type, and also push number i to queue e[x].

When a second type event happens, mark all numbers in queue e[x] and clear this queue (also decreese the number of unread notifications by the number of elements in this queue before clearing).

When a third type query happens, do the following:

while Q is not empty and Q.front().first <= t:
	i = Q.front().first
	x = Q.front().second
	Q.pop()
	if mark[i] is false:
		mark[i] = true
		e[v].pop()
		ans = ans - 1 // it always contains the number of unread notifications

But in C++ set works much faster than queue!

Time Complexity: 

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
queue<int> que;
map<int,int> mp;
int vis[N];

int main(){
    int n,q;
    while(~scanf("%d%d",&n,&q)){
        mp.clear();
        while(!que.empty())
            que.pop();
        memset(vis,0,sizeof(vis));
        int type,x,sum = 0,readed = 0;
        for(int i = 0; i < q; ++i){
            scanf("%d%d",&type,&x);
            if(type == 1){
                que.push(x);
                ++vis[x];
            }else if(type == 2){
                mp[x] += vis[x];
                sum += vis[x];
                vis[x] = 0;
            }else if(type == 3 && readed < x){
                x -= readed;
                while((!que.empty()) && (x--)){
                    int tmp = que.front();
                    if(mp[tmp])
                        --sum,--mp[tmp];
                    else
                        --vis[tmp];
                    que.pop();
                    ++readed;
                }
            }
            printf("%d\n",que.size()-sum);
        }
    }
    return 0;
}