2019中山纪念中学夏令营-Day9[JZOJ]（第六次模拟赛）

Begin

（题目的排序方式：Unkown其实是按心情排的）

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

异或：(摘自百度百科)

异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为： a⊕b = (¬a ∧ b) ∨ (a ∧¬b) 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。 异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。 异或略称为XOR、EOR、EX-OR 程序中有三种演算子：XOR、xor、⊕。 使用方法如下 z = x ⊕ y z = x xor y

运算法则

编辑 1. a ⊕ a = 0 2. a ⊕ b = b ⊕ a 3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c; 4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c. 5. a ⊕ b ⊕ a = b. 6.若x是二进制数0101，y是二进制数1011； 则x⊕y=1110 只有在两个比较的位不同时其结果是1，否则结果为0

2019.08.09【NOIP普及组】模拟赛C组

如需查看原题（如果luogu有原题的话,部分题只是题意相近），请点击每道题的标题！！！

第4题 【2298. 异或】提高+/省选-

 

 

2298. 异或 
(File IO): input:gcdxor.in output:gcdxor.out

时间限制:  1000 ms  空间限制: 262144 KB  具体限制  

题目描述

SarvaTathagata是个神仙，一天他在研究数论时，书上有这么一个问题：求不超过n两两的数的gcd。
SarvaTathagata这么神仙的人当然觉得这个是sb题啦。学习之余，他还发现gcd的某一个特别好的性质：如果有两个数i,j满足gcd(i,j)=i^j(这里的^为c++中的异或)的话，那么这两个数组成的数对(i,j)就是一个nb的数对(这里认为(i,j)和(j,i)为相同的，并不需要计算2次)。
当然，SarvaTathagata并不会只满足于判断一个数对是否nb，他还想知道满足两个数都是不超过n并且nb的数对有多少个。
由于SarvaTathagata实在是太神仙了，他认为这种题实在是太简单了。于是他找到了你，看看你是否能解决这个问题。  

输入

共一行一个整数n，含义如题所述。

输出

一行一个整数，表示nb的数对的个数。  

样例输入

样例输入1
12
样例输入2
123456

样例输出

样例输出1
8
样例输出2
214394

 

数据范围限制

 

提示

题目给的提示有问题，为了不影响您的做题体验（然而做这种 bian tai 题怎么可能会有做题体验感呢），就划掉了。

样例1中共有八对，分别是： {1,3},{1,5},{1,7},{1,9},{2,6},{1,11},{2,10},{4,12}。

这道题依然是bao li chu qi ji打表找规律，对于gcd(a,b)和a xor b(xor 表示异或)

有：

解：设a>b

a xor b 严格大于等于a-b;(为什么？可以去某百科看看异或的性质，以及减号在二进制下的情况)

而gcd(a,b)严格小于等于a-b(很容易想通的呀)

又因为gcd(a,b)=a xor b;

所以gcd(a,b)=a-b=a xor b;

程序就只用枚举gcd(a,b)和它的倍数就可以了

代码实现：

 

 1 #include <cstdio>
 2 #define rr register
 3 int n,ans;
 4 int main()
 5 {
 6     freopen("gcdxor.in","r",stdin);
 7     freopen("gcdxor.out","w",stdout);
 8     scanf("%d",&n);
 9     for(int c=1;c<=n;++c)
10     {
11         for(int a=c+c;a<=n;a+=c)
12         {
13             if(a-c==(a^c))
14                 ans++;
15         }
16     }
17     printf("%d",ans);
18 }

xor

 

 

 

第1题 【2297. 棋盘】（暂无原题）

2297. 棋盘 
(File IO): input:chess.in output:chess.out

时间限制:  1000 ms  空间限制: 262144 KB  具体限制   Goto ProblemSet

题目描述

众所周知，国际象棋的棋盘是一个网格。国际象棋中有一种旗子叫象。象每次移动可以斜着走任意格。即假设一只象在网格(x,y)，每次移动可以选择一个正整数k，使象移到(x-k,y-k),(x-k,y+k),(x+k,y-k),(x+k,y+k)中的一个格子。
现有若干组询问，每组询问给出两个格子(x,y),(u,v)，你需要回答一只象如果初始时在(x,y)，能否通过若干步(可以不走)到达(u,v)。  

输入

第一行一个正整数T，表示询问数量。
接下来T行，每行四个正整数x,y,u,v，表示一组询问。

输出

T行，每行一个”Yes”或”No”(不含引号)，表示你的回答。  

样例输入

5
1 1 2 2
2 3 2 2
1 2 4 3
3 4 2 2
1 1 1 1

样例输出

Yes
No
Yes
No
Yes

 

数据范围限制

对于30%的数据，0<T<=5,0<x,y,u,v<=4
对于50%的数据，0<T<=10,0<x,y,u,v<=500
对于100%的数据，0<T<=100,0<x,y,u,v<=10^8

 我的思路：

可以先模拟找规律读懂题，把题意弄明白了以后就可以想到以下情况一定成立（假设出发点坐标x,y,下面的k取值范围：全体整数）

x+k,y+k；

x+2k,y;(走法例子：1.x+k,y+k;2.x+k,y-k)

x,y+2k;

也就是说，最后处理过的结果是2的倍数，就可以走到，否则不能.

我们先控制一个变量相同，现在就只用处理另外一个了；

我们控制起始点x1与终点x2相同

具体做法：y1+=x2-x1;x1+=x2-x1;

现在再管两个y之间的距离即可

如果是偶数，输出Yes，否则输出No

代码实现：

 

 1 #include <cstdio>
 2 #define rr register
 3 int n,x1,x2,y1,y2;
 4 int main()
 5 {
 6     freopen("chess.in","r",stdin);
 7     freopen("chess.out","w",stdout);
 8     scanf("%d",&n);
 9     for(rr int i=1;i<=n;i++)
10     {
11         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
12         if(x1==x2 && y1==y2)
13         {
14             printf("Yes\n");
15             continue;
16         }
17         int a,b;
18         a=x2-x1;
19         x1+=a;
20         y1+=a;
21         b=y2-y1;
22         if(b%2==0)
23         {
24             printf("Yes\n");
25         }
26         else
27         {
28             printf("No\n");
29         }
30     }
31 }

chess

 

 

 

第2题 【2295.栈】（未找到原题）

 

2295. 栈 
(File IO): input:stack.in output:stack.out

时间限制:  1000 ms  空间限制: 524288 KB  具体限制   Goto ProblemSet

题目描述

 

输入

输出

 

样例输入

5
1 4 3 5 2

样例输出

1 2 4 3 5

 

数据范围限制

 

提示

依次使用操作 1、2、1、1、1、1、2、3、3、2 可以得到样例输出 1 2 4 3 5 。

 

 第3题 【2296.神殿】

 

2296. 神殿 
(File IO): input:temple.in output:temple.out

时间限制:  1500 ms  空间限制: 524288 KB  具体限制   Goto ProblemSet

题目描述

 

输入

输出

 

样例输入

样例输入1
2 2
+*
*U
1 1 2 2
样例输入2
2 3
<><
><>
1 1 2 1

样例输出

样例输出1
-1
样例输出2
4

 

数据范围限制

 

提示

题目标中的特殊符号：<>^v+*|-

 

 

End

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄