佛山2015市选2比赛总结

佛山2015市选2比赛总结
题目

比赛经历

看一遍题目发现是做过的题,但当时没有讲,做了和没做一样
然后感觉当时多少分现在可能也差不多了【flag】
一年过去sa依然不会,因为这不是noip的范围,然后省选计划还没到哪里……
这就是所谓知识盲区吧,虽然知道但也没办法,手头上还有不少任务
于是就安心爆零吧……

评测经历

T2的stl怎么fail了?少了40暴力分
然后T3居然忘记删除输出调试了,少了20暴力分
其实当时也想过要不要检查,但是今天本来就没多少分,不想检查了
最后[0/100]+[10/100]+[0/100]+[0/100]=10/400
两天差距甚大啊,直接加上了“倒数”两个字,变成了倒数rk2……
%xgc今天翻盘遥遥领先

T1_Analysis

请先思考后再展开

据说这是一道很套路的sg题目
主要就是学会sg有个核心公式(以后补教程)
$$
sg(i)=mex { sg(i-j)|gcd(i,j)=1 }
$$
然后这个$gcd(i,i-j)=1$
然后取值的话不太好想,但证明其正确性灰常简单
如果是质数,sg=质数序数+1
如果是合数,sg=sg(最小质因数)+1

然后按照套路(异或)起来就好了

T1_Code_std

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXNUM=1000001;
int pr=0,prime[100000];
int sg[MAXNUM];
bool v[MAXNUM];
void pre()
{
memset(v,1,sizeof v);
sg[1]=1;//定义
for(int i=2;i<MAXNUM;i++)
{
if(v[i]) prime[++pr]=i,sg[i]=pr+1;
for(int j=1;j<=pr and i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=0;
sg[i*prime[j]]=sg[prime[j]];//最小的【与其互质】
if(i%prime[j]==0) break;
}
}
}
int main()
{
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
pre();
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
ans^=sg[t];
}
if(ans==0) puts("Bob");
else puts("Alice");
}
}

T2_Analysis

请先思考后再展开

sam和sa都不会……
hash好像也没什么必要吧
反正弃了

T3_Analysis

请先思考后再展开

主要思路是,进行了前面的第一轮后,就变成一个子问题
找规律神题,细节很多,不想写

T4_Analysis

请先思考后再展开

没人会的神题……

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/88c1.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%