codeforces 705B B. Spider Man(组合游戏)
题目链接:
2 seconds
256 megabytes
standard input
standard output
Peter Parker wants to play a game with Dr. Octopus. The game is about cycles. Cycle is a sequence of vertices, such that first one is connected with the second, second is connected with third and so on, while the last one is connected with the first one again. Cycle may consist of a single isolated vertex.
Initially there are k cycles, i-th of them consisting of exactly vi vertices. Players play alternatively. Peter goes first. On each turn a player must choose a cycle with at least 2 vertices (for example, x vertices) among all available cycles and replace it by two cycles with p andx - p vertices where 1 ≤ p < x is chosen by the player. The player who cannot make a move loses the game (and his life!).
Peter wants to test some configurations of initial cycle sets before he actually plays with Dr. Octopus. Initially he has an empty set. In thei-th test he adds a cycle with ai vertices to the set (this is actually a multiset because it can contain two or more identical cycles). After each test, Peter wants to know that if the players begin the game with the current set of cycles, who wins?
Peter is pretty good at math, but now he asks you to help.
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of tests Peter is about to make.
The second line contains n space separated integers a1, a2, ..., an (1 ≤ ai ≤ 109), i-th of them stands for the number of vertices in the cycle added before the i-th test.
Print the result of all tests in order they are performed. Print 1 if the player who moves first wins or 2 otherwise.
3
1 2 3
2
1
1
5
1 1 5 1 1
2
2
2
2
2 题意: 每次能把一个至少两个点的环变成两个环,现在问是先手还是后手胜? 思路: 最后都变成了1,那就看都变成1要操作多少次,跟奇偶有关; AC代码:
/************************************************
┆ ┏┓ ┏┓ ┆
┆┏┛┻━━━┛┻┓ ┆
┆┃ ┃ ┆
┆┃ ━ ┃ ┆
┆┃ ┳┛ ┗┳ ┃ ┆
┆┃ ┃ ┆
┆┃ ┻ ┃ ┆
┆┗━┓ ┏━┛ ┆
┆ ┃ ┃ ┆
┆ ┃ ┗━━━┓ ┆
┆ ┃ AC代马 ┣┓┆
┆ ┃ ┏┛┆
┆ ┗┓┓┏━┳┓┏┛ ┆
┆ ┃┫┫ ┃┫┫ ┆
┆ ┗┻┛ ┗┻┛ ┆
************************************************ */ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('\n');
} const LL mod=1e9+7;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=1e5+10;
const int maxn=2e3+14;
const double eps=1e-12; int a[N];
int main()
{
int n;
LL sum=0;
read(n);
For(i,1,n)
{
read(a[i]);
sum=sum+a[i]-1;
if(sum&1)printf("1\n");
else printf("2\n");
} return 0;
}
最新文章
- Qt5 Crash When Open File With QFileDialog
- 第四章 ngrok使用
- NoSQL介绍
- web自动化测试从入门到持续集成(selenium webdriver)
- 学习Yii框架,有哪些比较好的网站
- 【LATEX】个人版latex论文模板
- 关于 Be 主
- textarea高度自适应(转载)
- multiset和set
- 变量为空代表false
- JS不同浏览器图片载入处理
- C# DataTable按指定列排序
- oracle11g创建修改删除表
- apache make
- Python 中的进程与 锁
- Ubuntu16.04下同时安装Anaconda2与Anaconda3
- [转]MYSQL5.7版本sql_mode=only_full_group_by问题
- EA添加流程图
- Struts2_Struts标签大致内容
- DOM对象和js对象以及jQuery对象的区别
热门文章
- 试验笔记 - 使用7-ZIP压缩来减小APK安装包体积
- HDU 3461 Code Lock(并查集的应用+高速幂)
- php迭代器模式
- Space is not allowed after parameter prefix &#39;:&#39;
- 关于 php 调用 其他语言写的Web Service SOAP 接口的参数传递问题
- 【Python基础】之不同的文件在不同目录下导入指定模块的方法
- gitHub静态页面托管
- android 用webView作为编辑器 各种问题
- C语言--循环结构
- urllib库python2和python3具体区别