【LOJ】#2210. 「HNOI2014」江南乐
2024-10-06 09:46:37
LOJ#2210. 「HNOI2014」江南乐
感觉是要推sg函数
发现\(\lfloor \frac{N}{i}\rfloor\)只有\(O(\sqrt{N})\)种取值
考虑把这些取值都拿出来,能取到这个值的\(i\)是一个区间\([l,r]\)
如果\(r - l + 1 = 1\),那么直接算这个数的答案即可(\(\lfloor \frac{N}{i}\rfloor\)的石子有奇数堆还是偶数堆,\(\lfloor \frac{N}{i}\rfloor + 1\)的石子有奇数堆还是偶数堆,异或起来即可)
如果\(r - l + 1 > 1\),证明这个区间里既有奇数又有偶数
其中\(\lfloor \frac{N}{i}\rfloor + 1\)有\(N - i\lfloor \frac{N}{i} \rfloor\)堆
\(\lfloor \frac{N}{i}\rfloor\)有\(i - (N - i\lfloor \frac{N}{i} \rfloor)\)堆
由于\(N\)和\(\lfloor \frac{N}{i}\rfloor\)奇偶性确定了,我们只要枚举两种不同奇偶性的\(i\)计算两种情况的游戏值就可以了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define ba 47
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int T,F;
int sg[100005],N;
unordered_map<int,int> zz;
void Process() {
for(int i = 0 ; i < F ; ++i) {
sg[i] = 0;
}
for(int x = F ; x <= 100000 ; ++x) {
zz.clear();
for(int i = 2 ; i <= x ; ++i) {
int r = x / (x / i);
int t = x / i;
if(r - i + 1 == 1) {
int k = 0;
if((x % r) & 1) k ^= sg[x / i + 1];
if((r - (x % r)) & 1) k ^= sg[x / i];
zz[k] = 1;
}
else {
if(t % 2 == 0) {
if(x & 1) {
zz[sg[x / i + 1] ^ sg[x / i]] = 1;
zz[sg[x / i + 1]] = 1;
}
else zz[sg[x / i]] = 1;
}
else {
if(x & 1) {
zz[sg[x / i + 1] ^ sg[x / i]] = 1;
zz[sg[x / i]] = 1;
}
else zz[sg[x / i + 1]];
}
}
i = r;
}
while(zz.count(sg[x])) sg[x]++;
}
}
void Solve() {
int a,ans = 0;
read(N);
for(int i = 1 ; i <= N ; ++i) {
read(a);
ans ^= sg[a];
}
if(ans) putchar('1'),space;
else putchar('0'),space;
}
int main(){
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
read(T);read(F);
Process();
for(int i = 1 ; i <= T ; ++i) {
Solve();
}
return 0;
}
最新文章
- 使用html和css的一些经验
- openfalcon客户端自定义push 传输到transfer
- 快来玩“Gift大转盘”百分百赚好礼
- DatabaseError: no such table: django_session
- android 提高进程优先级 拍照永不崩溃(闪退)
- nyoj 118 修路方案(最小生成树删边求多个最小生成树)
- Codeforces Round #200 (Div. 1) C. Read Time 二分
- 采用subversion管理iOS资源
- Struts2 cookie的存取
- 使用FileSystemWatcher捕获系统文件状态
- php 多维数组 arrayList array()
- MYSql和PHP计算数据性能
- STM32M CUBE实现printf打印调试信息以及实现单字节接收
- visual Studio 2017 扩展开发(一)《向Visual Studio菜单栏新增一个菜单》
- 解决报错:IncompleteElementException: Could not find result map...
- LAMP基础
- 说说cglib动态代理
- 大数据学习之HDFS基本API操作(下)06
- 简单的dfs题 --- POJ1321 棋盘问题
- 基于Servlet的Echarts例子(2018-12-26更新)
热门文章
- 二分算法题目训练(四)——Robin Hood详解
- P1026 统计单词个数——substr
- weui-wxss框架实现博远企信小程序
- 使用 Nexus3 Repository Manager 搭建 npm 私服
- kafka简介&;使用
- 配置mysql远程访问
- openstack instance change storage dir
- How can I get a Netty server to reload a TLS certificate when it is renewed?
- sklearn里计算roc_auc_score,报错ValueError: bad input shape
- 002-02-RestTemplate-初始化调用流程