正文
1.Alex and a Rhombus
题目链接
题目大意：
给出一个整数n，下面给出当n=1、2、3的图：
计算第n个图，需要多少个方格组成。
输入：
一个整数𝑛 (1≤𝑛≤100)
输出：
需要的方格数量。
Examples
input
1
output
1
input
2
output
5
input
3
output
13
题目解析：
等差数列，1、3、5、、、2n-1；
两个等差数列，减去一个多余的2n-1,于是有：
一个等差数列和sum: (1+(2n-1)) x n/2
最终得到 ans = 2 x sum - (2n-1) = 2n^2 - 2n + 1。
int n;
cin >> n;
cout << 2 * n * n - 2 * n + 1 << endl;
2.Nick and Array
题目链接
题目大意：
有一个数组𝑎=[𝑎1,𝑎2,…,𝑎𝑛] ，可以对任意数进行下面的操作：
𝑎𝑖:=−𝑎𝑖−1；
每个数可以操作任意次；
要求 最后的乘积（𝑎1⋅𝑎2⋅…𝑎𝑛）最大。
输入：
第一行， 𝑛 (1≤𝑛≤10^5)
第二行，n个整数； 𝑎1,𝑎2,…,𝑎𝑛 (−10^6 ≤ 𝑎𝑖 ≤ 10^6)
输出：
一行，使得乘积最大的n个整数（𝑎1,𝑎2,…,𝑎𝑛）
Examples
input
4
2 2 2 2
output
-3 -3 -3 -3
input
1
0
output
0
题目解析：
题目的要求是乘积最大，但是数字有很多，最终的乘积肯定会很大。
再来看看题目的操作，其实就是x= -x-1;
如果操作两次呢？x = -(-x-1) -1 = x + 1 - 1 = x;
操作两次是变回x，那么可以知道对于每个数字只有1个选择：要么不操作，要么操作一次。
回头来看看乘积最大的要求，先不考虑正负的问题，要使得乘积最大，自然是每个数字越大越好。
容易知道，乘积对于负数有一个负负得正的作用，那么要使得乘积最大要满足两个条件：
1、所有的数字里不会出现单数的负数，否则结果一定是负数；
2、每个数字要尽可能的大；
分析这个操作x=-x-1，容易知道对于正数，当x操作一次之后，绝对值是+1；对于负数，当x操作一次之后，绝对值是-1；
综上，我们可以先将所有的数字全部变为负数，这样可以使得绝对值最大。
但是因为可能会出现单数的负数，此时我们需要选择一个负数变为整数，通过推导，我们会选择负数中绝对值最大的那个变为负数。
推导：
先假设有两个正整数x和y，并且x<y。
(x-1)y=xy-y
x(y-1)=xy-x
因为x<y,所以有(x-1)y < x(y-1)
int n;
cin >> n;
int index = -1;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] >= 0) {
a[i] = -a[i] - 1;
}
if (index == -1) {
index = i;
}
else if (a[i] < a[index]) {
index = i;
}
}
if (n % 2) {
a[index] = -a[index] - 1;
}
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
3.Valeriy and Deque
题目链接
题目大意：
有一个数组a，长度为n；
现在有一个操作，从数组最前面（a[0],a[1]）拿出两个数字假设是x，y；
如果x<y，则把x放在数组的最后面，把y放在数组的最前面；
如果x>=y,则把x放在数组的最前面，把y放在数组的最前面；
问这个操作进行若干次之后，拿出来的数字x、y是什么；
输入：
第一行，两个整数𝑛 and 𝑞 (2≤𝑛≤10^5, 0≤𝑞≤3⋅10^5)，分别表示数组长度和询问次数；
接下来有n个整数，𝑎1, 𝑎2, ..., 𝑎𝑛, where 𝑎𝑖 (0≤𝑎𝑖≤10^9)
接下来有q行，每行一个整数𝑚𝑗,(1≤𝑚𝑗≤10^18)
输出：
对于q个询问，每个输出一行，一行有两个整数x、y；
Examples
input
5 3
1 2 3 4 5
1
2
10
output
1 2
2 3
5 2
样例解释：
原始数组是[1,2,3,4,5]，在每次操作之前，数字的样子：（每次操作都是拿出前两个）
[1,2,3,4,5]
[2,3,4,5,1]
[3,4,5,1,2]
[4,5,1,2,3]
[5,1,2,3,4]
[5,2,3,4,1]
[5,3,4,1,2]
[5,4,1,2,3]
[5,1,2,3,4]
[5,2,3,4,1]
题目解析：
题目的样例已经很明显阐述了一个规律： 若干次之后，数组中最大值会始终占据第一位。
根据题目的其他描述，每次拿出来的A、B两个数字，在数组最大值放置在第一位之后，剩余的1~n-1的位置会不断轮换。
为了实现简单，我们不去记录他最大值是什么。
直接按照题目要求操作n次，记录其中每次操作的值；此时数组的最大值就会在最左边，接下来的操作会使得1~n-1数组开始循环。
对于q次询问，每次先看询问值mj是否小于n， 是的话可以直接用原来存储的值；
否则就直接取余，再从1~n-1找到下一个值。
为了实现方便，这里n次的模拟可以使用双端队列deque来辅助实现。
lld n, t;
cin >> n >> t;
deque<int> q;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
q.push_back(k);
}
for (int i = 1; i < n; ++i) {
int a = q.front();
q.pop_front();
int b = q.front();
q.pop_front();
ans[i] = make_pair(a, b);
if (a > b) {
q.push_front(a);
q.push_back(b);
}
else {
q.push_front(b);
q.push_back(a);
}
}
for (int i = 0; i < n; ++i) {
r[i] = q.front();
q.pop_front();
}
while (t--) {
lld k;
cin >> k;
if (k < n) {
cout << ans[k].first << " " << ans[k].second << endl;
}
else {
--k;
k = k % (n-1);
cout << r[0] << " " << r[k + 1] << endl;
}
}
4.Tolik and His Uncle
题目链接
题目大意：
有 n x m 的网格，小明站在第一个格子(1,1）；
小明可以跳到一个还未访问过格子，每次会产生一个向量(dx, dy)。
当小明访问完所有的格子时，希望所有的向量都是不重复的。
输入：
一行，𝑛,𝑚 (1≤𝑛⋅𝑚≤10^6)
输出：
如果无解，输出 -1.
如果有解，按照小明的访问顺序输出每个格子的坐标，一共n x m行，每行两个数字𝑥𝑖,𝑦𝑖 (1≤𝑥𝑖≤𝑛,1≤𝑦𝑖≤𝑚)
题目解析：
这是一道典型的构造类题目，需要我们去构造一个走法。
按照题目的要求，每次访问格子的向量不重复，那么产生越大的向量越好，因为越大越不会重复。
基于思路，我们可以知道，(1, 1)往(n, m)跳是最优的；
其次，(n, m)往(1, 2)跳也是OK的；
再接着，（1，2）可以往(n, m-1)跳；
循环往返，就可以得到一个序列。
以4x4的格子为例，走完第一行和最后一行之后，可以得到以下的向量：
(3, 3)
(-2, -3)
(1, 3)
(0, -3)
(-1, 3)
(2, -3)
可以看出来，这些向量都没有重复。
那么同理，对于第二行和倒数第二行，向量也不会重复。
综上，可以知道这个走法是合理的。
题目也不存在无解的情况。
cin >> n >> m;
for (int i = 0; i < n; ++i) {
vector<int> t(m);
a.push_back(t);
}
topX = topY = 0;
bottomX = n - 1, bottomY = m - 1;
topDir = 1;
bottomDir = -1;
bool isBottom = 0;
while (ans.size() < n * m) {
if (isBottom) { // jump bottom
ans.push_back(make_pair(bottomX, bottomY));
bottomY += bottomDir;
if (bottomY < 0) {
bottomY = 0;
bottomX--;
bottomDir = -bottomDir;
}
else if (bottomY >= m) {
bottomY = m - 1;
bottomX--;
bottomDir = -bottomDir;
}
}
else {
ans.push_back(make_pair(topX, topY));
topY += topDir;
if (topY < 0) {
topY = 0;
topX++;
topDir = -topDir;
}
else if (topY >= m) {
topY = m - 1;
topX++;
topDir = -topDir;
}
}
isBottom = !isBottom;
}
for (int i = 0; i < n * m; ++i) {
printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
}
总结
题目1意思很清晰，就是找规律；
题目2看着很复杂，实际上通过分析可以得到很简单做法；
题目3数字的取值范围很大，但实际上后面都是重复循环，同时样例也很好展示了循环当前情况；
题目4属于脑洞题，一时间能想到就简单，想不到的时候就很头疼；
网友评论