考试历程
8 ：30 开始考试
8：40 快速浏览了T1并想了一下，是一道质数的题目，准备打表，打到一半的时候发现空间复杂度会爆，于是改打质数筛暴力了
9：30打完T1开始看T2刚开始没思路，先看了T3，跟着样例打了一点，估计可以拿点分吧
9：50打完了T3会看T2发现了一点规律（后来知道是错的）跟着思路写了一点。
10：10看T4了想了大概10分钟的样子，觉得还行就写了个暴力
10：40+ 写完了T4，开始检查了
预估分数
100 + 30 + 30 + 0 =160
实际分数
30 + 0 + 50 + 0 = 80
赛后总结
啊啊啊啊啊，别人是10年OI一场空，不开long long一场空，为什么我是开了long long 一场空啊啊啊啊啊啊啊我要是第一题不开long long就100了啊啊啊啊，其他的都是我思路没想对，下次加油吧。
题解
1. 镜面质数
题目ID：20313必做题100分
时间限制: 1000ms
空间限制: 262144kB
题目描述
如果一个质数镜像反转（即将该数各个位上数字反转）后仍然是质数，那么就称这个质数为镜像质数。例如质数1313反转后为3131，则1313为一个镜像质数。
现在给定一个整数 N，请求出整数1∼ N范围内有几个镜像质数。
注意：求范围内的镜像质数时，质数和镜像反转后的数都需在范围内。详见样例1解释。
输入格式
一个整数 N。
输出格式
一个整数，表示整数1∼ N范围内镜像质数的个数。
样例
Input 1
20
Output 1
5
Input 2
100000
Output 2
1759
样例解释
针对样例1：1∼ 201∼ 20内镜像质数有： {2,3,5,7,11}{2,3,5,7,11}，结果为55。
注意：质数1313和1717反转后不在范围1∼ 201∼ 20内，不算入此范围内的镜像质数
数据范围
对于 30%30% 的数据，1≤N≤103；
对于 50%50% 的数据，1≤N≤106；
对于 100%100% 的数据，1≤N≤5×107。
这是一道反转数加上质数筛的题目
首先我们先写一个质数筛
inline void init()
{
st[1] = true;
for (int i = 2; i <= n; i++)
{
if (!st[i])
{
ar[++idx] = i;
}
for (int j = 1; j <= idx; j++)
{
if (i * ar[j] > n)
{
break;
}
st[i * ar[j]] = true;
if (i % ar[j] == 0)
{
break;
}
}
}
}再在主函数里加上判断反数合不合法的函数就信了
int res = 0;
for (int i = 1; i <= idx; i++)
{
int z = ar[i];
int temp = 0;
while (z)
{
temp = temp * 10 + z % 10;
z /= 10;
}
if (temp <= n && !st[temp])
{
res++;
}
}最后提醒大家：不要无脑开long long不然向我一样爆0两行泪！！！！！
附上ACcode
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 5e7 + 10;
int ar[N], idx, n;
bool st[N];
inline void init()
{
st[1] = true;
for (int i = 2; i <= n; i++)
{
if (!st[i])
{
ar[++idx] = i;
}
for (int j = 1; j <= idx; j++)
{
if (i * ar[j] > n)
{
break;
}
st[i * ar[j]] = true;
if (i % ar[j] == 0)
{
break;
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
init();
int res = 0;
for (int i = 1; i <= idx; i++)
{
int z = ar[i];
int temp = 0;
while (z)
{
temp = temp * 10 + z % 10;
z /= 10;
}
if (temp <= n && !st[temp])
{
res++;
}
}
cout << res << "\n";
return 0;
}2. 百万富翁的第二次实验
题目ID：20307必做题100分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述
马克吐温有一本非常著名的小说《百万英镑》，这本小说中主角最后归还了百万英镑给两位富翁。但结果就是两位富翁依然有无穷的问题需要进行社会实验，于是，他们打算进行第二次社会实验。那就是不同财富值的人在一场舞会上会发生什么事情。为了满足自己的好奇，百万富翁们邀请了全伦敦所有人来自己的舞会。舞会开始后他们就后悔了，因为来的人太多了，而且很多人的财富都相同，统计起来太费事了。所以百万富翁们找到你，希望你根据来舞会的时间，找出在一段时间内，来舞会的所有人财富值都互不相同的人数。
输入格式
第一行输入一个n表示有n个人参与舞会。
按照时间顺序输入n个人的财富值。
输出格式
输出在一段时间内参加舞会的所有人财富值都互不相同的人数的最大值。
样例
Input 1
Output 1
4
数据范围
每个人的财富值不超过100000000000
0 <= n <= 1000000
这道题看着有点玄乎，其实理一理就会发现很简单
首先看样例
7 2 3 4 5 5 6 7
先边里到第一个数7，发现没有和7一样的数，往下遍历
7 2 3 4 5 5 6 7
没有发现一样的，往下
7 2 3 4 5 5 6 7
没有一样的，往下
7 2 3 4 5 5 6 7
往下
7 2 3 4 5 5 6 7
在往下就发现一样的了
于是就吧前面的删掉
7 2 3 4 5 5 6 7
于是就得到了4
所以样例是这么得来的，根据这个思路往下写就可以A了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
map<int, int>mp;
int ar[N], n, res;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1, l = 0; i <= n; i++)
{
cin >> ar[i];
if (mp[ar[i]] > 0)
{
int z = mp[ar[i]];
for (; l <= z; l++)
{
mp[ar[l]] = 0;
}
l--;
}
mp[ar[i]] = i;
res = max(res, i - l);
}
cout << res << "\n";
return 0;
}这题就有1e9的大小了，所以要开long long
3. 蛋滚派对
题目ID：20297必做题100分
最新提交：
Accepted
100 分历史最高：
Accepted
100 分
时间限制: 2000ms
空间限制: 524288kB
题目描述
“趴着好难受啊蛋！我要透不过气了蛋！”
“我也不想仰着睡啊蛋！！！”
“那咱俩都翻过来睡呗蛋！”
n 个蛋蛋排成一排睡觉，有些蛋蛋喜欢趴着睡，有些则喜欢仰着睡。你可以做任意次操作，使得相邻的两个蛋蛋都翻过来睡。它们最开始都有个愉悦值，对于任何一个蛋蛋，翻过来之后愉悦值都会变成原来的相反数。
请你最大化它们的愉悦值之和，并回答这个值。
注意：第 11 个蛋蛋和第 n 个蛋蛋不相邻！
输入格式
第一行一个正整数 n，表示蛋蛋的数量。
第二行 n 个整数，其中第 i 个整数 ai 表示第 i 个蛋蛋的初始愉悦值。
输出格式
一个整数，表示操作后的最大愉悦值之和。
样例
Input 1
3 -10 5 -4
Output 1
19
Input 2
5 10 -4 -8 -11 3
Output 2
30
Input 3
11 -1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000
Output 3
10000000000
样例解释
样例一中，1,21,2 翻滚，2,32,3 翻滚，最后愉悦值为 {10,5,4}{10,5,4}，总和为 1919。
样例二中，2,32,3 翻滚，4,54,5 翻滚，最后愉悦值为 {10,4,8,11,−3}{10,4,8,11,−3}，总和为 3030。
数据范围
对于数据 1∼41∼4 ：1≤n≤4000
对于数据 5∼205∼20 ：1≤≤n≤105
对于所有数据：−109≤ai≤109
这道题本来是想骗个分的，结果没骗到，后来改了就A了
我是想有0的情况直接输出sum，没有的话再abs一下求出来，结果sum加时写错了不然A了。。。
没有什么好说的，上代码
#include <bits/stdc++.h>
using namespace std;
long long a[114514], minx = 1145141919810, sum = 0, sumf;
signed main()
{
bool uuu = 0;
long long sumf = 0;
long long n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += abs(a[i]);
if (a[i] < 0)
{
sumf++;
}
if (a[i] == 0)
{
uuu = 1;
}
minx = min(abs(a[i]), minx);
}
if (uuu)
{
cout << sum;
return 0;
}
if (sumf % 2 == 0)
{
cout << sum;
return 0;
}
cout << sum - minx * 2;
return 0;
}最后就是我们亲（tao）爱（yan）的T4了
4. 小信的鸡舍
题目ID：20314必做题100分
时间限制: 1000ms
空间限制: 262144kB
题目描述
小信的Stardew农场是一个N×N的矩阵，由于农场水土流失严重，每个单位土地的高度都不同，第i行第j列的土地高度为Ai,j。
小信想在农场里选一块K×K的土地来建造他的鸡舍，但他是一个极致的完美主义者，每个K×K的区域中都有K2个土地高度，他希望在所有的K×K区域中选择土地高度中位数最小的那一块区域来作为鸡舍的建造位置。
小信认为K×K区域中K2个土地高度应该是第(⌊2K2⌋+1)高的数，但他笨手笨脚，他想知道建造鸡舍的土地高度最小的中位数是多少，他需要你的帮助！
输入格式
第一行输入两个整数N和K(1≤K≤N≤800)，分别表示农场的长宽和建造鸡舍的长宽。
接下来N行，每行N个整数Ai,j，表示第i行第j列的土地高度为,j(0≤Ai,j≤109)。
输出格式
输出一个整数，表示所有K×K区域中的土地高度最小中位数。
样例
Input 1
3 2 1 7 0 5 8 11 10 4 2
Output 1
4
Input 2
3 3 1 2 3 4 5 6 7 8 9
Output 2
5
样例解释
对于样例#1，(i,j)表示第i行第j列，可以选择的2×22×2区域为：{(1,1),(1,2),(2,1),(2,2)},{(1,2),(1,3),(2,2),(2,3)},{(2,1),(2,2),(3,1),(3,2)},{(2,2),(2,3),(3,2),(3,3)}{(1,1),(1,2),(2,1),(2,2)},{(1,2),(1,3),(2,2),(2,3)},{(2,1),(2,2),(3,1),(3,2)},{(2,2),(2,3),(3,2),(3,3)}，2K=2，则中位数应为第(⌊222⌋+1=3)(⌊222⌋+1=3)个数，四个区域的中位数分别为：5,7,5,45,7,5,4，所以小信应该选择第四个区域来建造他的鸡舍。
数据范围
对于10%10%的数据，1≤101≤K≤N≤10，0≤1000≤Ai,j≤100。
对于20%20%的数据，1≤601≤K≤N≤60，0≤1090≤Ai,j≤109。
对于100%100%的数据，1≤8001≤K≤N≤800，0≤1090≤Ai,j≤109。
这题嘛，
就是二分求中数，但是我好像没有怎么听懂
磨了1个小时终于打出来了但是还是没有听太懂，有人再来给我讲讲嘛
AC代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10;
map<int, int>mp;
int ar[N][N], n, res, k, temp;
int br[N][N];
inline bool check(int mid)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
br[i][j] = ar[i][j] <= mid ? 1 : 0;
br[i][j] = br[i][j] + br[i - 1][j] + br[i][j - 1] - br[i - 1][j - 1];
if (i >= k && j >= k)
{
int z = br[i][j] - br[i - k][j] - br[i][j - k] + br[i - k][j - k];
if (z >= temp)
{
return true;
}
}
}
}
return false;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
temp = (k * k + 1) / 2;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> ar[i][j];
}
}
int l = 0, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid))r = mid;
else l = mid + 1;
}
cout << l << '\n';
return 0;
}这就是我今天的比赛总结了，最后，祝大家学业有成，金榜题名
