310Contest

为班内准备机考出的一套模拟题

#题目链接

A: T112882 wxl的找数游戏

#题意简述

若干个数中，有且仅有一个数字出现了一次，其余均出现两次。找到那个出现了一次的数。

#简要做法

观察到每个数均小于$1500$，我们可以用数组统计每个数字出现的次数。统计完后$O(n)$复杂度从小到大扫一遍，找到次数为一的数字，输出答案，退出循环。

#参考代码

#include <stdio.h>

---

想要更简单的做法？那我们首先需要学习异或的几条性质：

*异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。*

按位异或便是将数字转为二进制后右对齐，每一位进行异或运算。位数不同时则位数少的前面补零。

由按位异或的性质，我们不难发现：

1. 0 ^ x = x , x ^ x = 0
2. a ^ b = b ^ a
3. a ^ b ^ b = a ^ 0 = a

由此性质，本题出现两次的数字均可由异或运算化为0，从而直接得解。

#参考代码1

#include <stdio.h>

#题目链接

B: [T113497 wxl的午餐

#简要做法

将吃饭时间（即$b_{i}$）按从大到小排序，求出最长的吃完时间。

该做法基于贪心的思想，下面给出证明：

​ 我们不难发现，所有人吃完饭的最早时刻即为max{$b_i + \sum_{k=1}^ia_k$}。现在考虑相邻的两个人p、q。显然，是否调换p、q的顺序对于他们前面和后面的人的吃完饭时间均无影响。不妨设$b_p > b_q$，则有:

p在q前：

​ $time_p = () + a_p + b_p$

​ $time_q = () + a_p + a_q + b_q$

q在p前：

​ $time_{q1} = () + a_q + b_q$

​ $time_{p1} = () + a_q + a_p + b_p$

四项中的最大值显然出现在“q在p前”，因此要尽可能将b值大的往前放。

#参考代码

//std provided by yyn

---

UPD: 今天脑袋抽了，抄了个错误方法，大家忘掉就好。。。这个错误方法正确主要是我数据出水了（

求解正确答案是离不开排序的

#题目链接

C:[T112898 wxl的括号编辑器

#简要做法

基本就是模拟，题目说什么我们就做什么。记录好当前光标的位置，然后对相应位置进行修改即可。修改答案字符串的同时，在相同位置打好标记，以便于后续判断括号序列是否合法。

#参考代码

#include <stdio.h>

#题目链接

D: T112864 wxl的期末复习

#题意简述

找到最小的整数x，使得$x^2/a + \sqrt{x} >= n$。

#简要做法

首先注意到$n，a$均很大，因此答案可能会很大，需要用long long进行运算，否则会爆int（涉及平方运算时）。

50PTS做法：

​ 从小到大枚举，找到第一个满足条件的值，将其输出。时间复杂度$O(tn)$

#参考代码

#include <stdio.h>

100PTS做法：

​ 线性复杂度太慢，观察到趋势是单调的，我们可以用二分查找这个答案。时间复杂度$O(t\log_2n)$。

#参考代码

#include <stdio.h>

#题目链接

E: T112848 wxl的加权求和

#简要做法

首先注意到计算得到的数字可能会超出int范围，因此用long long储存变量数值。

70PTS：

​ 对于每一次询问，用循环计算出答案，时间复杂度$O(mn)$。

#参考代码

#include <stdio.h>

100PTS做法：

​ 我们想到对于每一次询问，我们都要对左右区间内的元素进行一次运算，但是这样想必是很浪费时间的。我们能否想到一个方法，使得将这个过程优化到$O(1)$的复杂度呢？

​ 要实现这样的目的，我们首先介绍前缀和的概念：

​ 我们定义前缀和$s_i=\sum_{k=1}^ia_k$，这样，想求$\sum_{i=l}^ra_i$，便可直接用$s_r-s_{l-1}$得到，时间复杂度为$O(1)$。

//前缀和实现

介绍完前缀和，我们如何达成本题的目的呢？

展开

$\sum_{i=l}^ra_i \cdot (i - l + 1)$为

$a[l]\cdot1 + a[l+1]\cdot2+……+a[r-1]\cdot(r-l)+a[r]\cdot(r-l+1)$

$=(s[l]-s[l-1])+..+(s[r-1]-s[r-2])\cdot(r-l)+(s[r]-s[r-1])\cdot(r-l+1)$

$=-(s[l-1]+s[l]+s[l+1]+…..+s[r-1])+(r-l+1) \cdot s[r]$

到这一步我们发现我们可以对s数组进行求和，于是再计算s的前缀和e

所求$=(r-l+1) \cdot s[r]-(e[r-1]-e[l-2])$

#参考代码

#include <stdio.h>