Codeforces Round #713 div.3 题解
快速跳转：
A:Spy Detected!
B:Almost Rectangle
C:A-B Palindrome
D:Corrupted Array
E:Permutation by Sum
F:Education
G:Short Task
A:Spy Detected!
题目入口：
题意：
给你一个正整数的序列，其中除了一个数以外其他数都一样，你需要输出那个唯一不同的数的位置。
思路：
用数组同时存储每个数的值和它在原序列中的位置，以每个数的值进行排序。
此时唯一不同的那个数要么在排序后序列的最前端，要么在排序后序列的最后端。我们只需要使排序后的序列的第一个元素和最后一个元素分别与除这两个位置以外的其他数比较一下，输出值不同的那一个就ok了。
代码：
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
struct Node {
int num; //元素的值
int index; //元素在原序列的位置
};
bool cmp(Node n1, Node n2) {
return n1.num < n2.num;
}
vector<Node>a;
void solve() {
int n;
cin >> n;
a.clear();
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].num;
a[i].index = i + 1;
}
sort(a.begin(), a.end(), cmp);
if (a[0].num != a[1].num) {
cout << a[0].index << endl;
}
else {
cout << a[n - 1].index << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
B:Almost Rectangle
题目入口：
题意：
输出在一个n乘n的表中以两个*为顶点的面积最小的矩形。
思路：
-
分类讨论：
-
(1) 当两个星号在同一列时，最小矩形一定为该两个星号水平平移一个单位形成的矩形。
(2)当两个星号在同一列时，最小矩形一定为该两个星号竖直平移一个单位形成的矩形。
(3)当两个星号不满足(1) (2)时，最小矩阵一定为以该两个星号连线为对角线的矩形。
代码：
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
struct Point {
int r;
int c;
};
char g[405][405];
vector<Point>pos;
void solve() {
int n;
cin >> n;
pos.clear();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> g[i][j];
if (g[i][j] == '*') {
pos.push_back({ i,j });
}
}
}
if (pos[0].r == pos[1].r) {//在同一行上
if (pos[0].r + 1 < n) {
g[pos[0].r + 1][pos[0].c] = '*';
g[pos[1].r + 1][pos[1].c] = '*';
}
else {
g[pos[0].r - 1][pos[0].c] = '*';
g[pos[1].r - 1][pos[1].c] = '*';
}
}
else if (pos[0].c == pos[1].c) {//在同一列上
if (pos[0].c + 1 < n) {
g[pos[0].r][pos[0].c + 1] = '*';
g[pos[1].r][pos[1].c + 1] = '*';
}
else {
g[pos[0].r][pos[0].c - 1] = '*';
g[pos[1].r][pos[1].c - 1] = '*';
}
}
else {//以这两个*为对角线
g[pos[0].r][pos[1].c] = '*';
g[pos[1].r][pos[0].c] = '*';
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << g[i][j];
}
cout << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
C:A-B Palindrome
题目入口：
题意：
有一个只由’0’、‘1’和’?‘组成的字符串，其中的’?'可被’0’或‘1’替换。
问能不能将给定的字符串通过上述操作变成一个回文串且字符串中’0’和’1’的数量分别与a和b相等。
思路：
对于长度为n的字符串S中的字符S[i]都应该有S[i] == S[n - i -1]
- S[i]和S[n - i - 1]中只存在一个’?‘时，把’?'变为相等的字符就行，同时相应的a或者b应该减1。
- S[i]和S[n - i - 1]都不为’?'且不相等时，输出-1。
通过上述规则我们更新a和b的值，此时得到的是一个只含有相对位置都为’?'的字符串。
当a或b大于1时，相对位置的两个’?‘可以被变成’0’或’1’，用双指针模拟这个过程就可以了，若a或b都不满足条件的时候，输出-1。
注意长度为奇数的字符串，要特判一下中间的位置
代码：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string str;
void solve() {
int a, b;
cin >> a >> b;
cin >> str;
for (int i = 0; i < str.size(); ++i) {
if (str[i] == '?')
str[i] = str[str.size() - i - 1];
}
//更新一下a和b的值
a -= count(str.begin(), str.end(), '0');
b -= count(str.begin(), str.end(), '1');
int l = 0, r = str.size() - 1;
while (l <= r) {
if (l == r) {
if (str[l] == '?') {
if (a) {
str[l] = '0';
--a;
}
else {
str[l] = '1';
--b;
}
}
}
else {
if (str[l] == '?' && str[r] == '?') {
if (a > 1) {
str[l] = str[r] = '0';
a -= 2;
}
else if (b > 1) {
str[l] = str[r] = '1';
b -= 2;
}
}
}
++l;
--r;
}
//判断一下是否为回文串
string rev = str;
reverse(rev.begin(), rev.end());
if (rev == str && a == 0 && b == 0)
cout << str << endl;
else
cout << -1 << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D:Corrupted Array
题目入口：
题意：
有一个长度为n的正整数数组a，通过以下的方式可以得到数组b：
- a的所有元素是b的前n个元素（a长度就为n，所以b在这一步操作中是和a相等的）
- a的所有元素的和是b的n+1个元素
- b的n+2个元素是一个任意数x（1≤x≤109)
- b数组中的所有元素的顺序被打乱
现在给定一个b数组，输出可能存在的a数组，若不存在则输出-1。
思路：
b数组在未被打乱之前，b的第n+1个元素一定大于前n个元素（因为它是前n个元素的总和）。
那么对于x无非有两种情况：
- x小于或等于b[n+1]
- x大于b[n+1]
所以我们可以对被打乱后的b数组进行一次排序，当x满足第一种情况时：
- 排序后的b数组的前n+1项元素的和一定大于第n+2项
- x为排序后b数组的前n+1项元素和减去第n+2项
当x满足第二种情况时：
- x一定在排序后的b数组的最后一项（n+2项）
- 排序后的b数组第n+1项元素一定为前n项元素的和
所以我们只需要判断一下排序后的b数组的n+1为元素是不是前n项的和，若不是则检查前n+1项的和与第n+2项的差（x）能否在前n+1个元素中找到即可。
代码：
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
void solve() {
int n;
cin >> n;
n += 2;
long long del = -1; //用于记录x是否被找到
long long sum = 0;
vector<long long>a(n);
set<long long>s; //前缀和每次更新时，便插入当前的元素
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
bool flag = false;
for (int i = 0; i < n; ++i) {
sum += a[i];
s.insert(a[i]);
if (i == n - 3 && sum == a[n - 2]) {
flag = true;
//弹出前n项和 和 x，之后直接进行输出
a.pop_back();
a.pop_back();
break;
}
else if (i == n - 2 && sum > a.back() && s.find(sum - a.back()) != s.end()) {
flag = true;
del = sum - a[n - 1];
a.pop_back(); //弹出前n+1项的和
break;
}
}
if (del != -1 && flag) {
bool al = false;
for (auto x : a) {
if (!al && x == del) {//遇到与x相同的值则不输出（此过程只进行一次）
al = true;
continue;
}
cout << x << ' ';
}
cout << endl;
}
else if (flag) {
for (auto x : a)
cout << x << ' ';
cout << endl;
}
else {
cout << -1 << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E:Permutation by Sum
题目入口：
题意：
给你四个正整数n，l，r，s。
将1，2，3，…，n重新排列，使得在l到r区间内元素的加和等于s。
思路：
区间长度为（r - l + 1）
这题如果有解，那么一定满足下面的两种情况：
- 1+2+3+…+（r - l + 1）小于等于s
- （n - (r - l + 1) + 1) + (n - (r - l + 1) + 2) + … + n大于等于s
所以我们只需要从最小值向s贪心即可：将1+2+3+…+（r - l + 1）的和 与 s的差平均加到每个数上，若差的值小于（r - l + 1），则分配到后几个数上。（若分配到前几个数上，有可能出现前几个数加和后与后面的数重复的情况）
代码：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void solve() {
int n, l, r, s, dis;
cin >> n >> l >> r >> s;
dis = r - l + 1;
vector<int>ans(n + 1, -1);
vector<bool>vis(n + 1, false);
if (s < dis * (1 + dis) / 2 || s > dis * (2 * n + 1 - dis) / 2) {
cout << -1 << endl;
return;
}
int now = dis * (1 + dis) / 2; //当前得到的前(r - l + 1)项的和
int cnt = 0; //计数，now与s的差平均分配了几次
int left = 0; //记录now与s的不能被平均分配的差
while (now + (cnt + 1 ) * dis <= s && dis + (cnt + 1) <= n) {
++cnt;
}
left = s - (now + cnt * dis);
for (int i = l, num; i <= r; ++i) {
num = (i - l + 1) + cnt;
if (i <= r - left);
else
num += 1;
if (!vis[num]) {
ans[i] = num;
vis[num] = true;
}
}
int index = 1;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
while (index >= l && index <= r)
++index;
ans[index] = i;
++index;
}
}
for (int i = 1; i <= n; ++i)
cout << ans[i] << ' ';
cout << endl;
return;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F:Education
题目入口：
题意：
Polycarp想换一台价格为c的新电脑，现在有n个工作，每个工作的日薪是ai，i越大ai则越大（换句话说a就是个单调递增数列）。从当前职位i想要升职到职位i+1需要bi的价格，问Polycarp最少需要多少天能买到电脑。（Polycarp最初在a1的职位）
思路：
dp，对于每个工作能买到电脑的所需天数为：
- 由a1职位攒钱升职到当前职位的天数+在当前职位攒钱买到电脑的天数
之后找出最少的天数就ok了。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void solve() {
int n;
long long c;
cin >> n;
cin >> c;
vector<long long>a(n + 1);
vector<long long>b(n);
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n - 1; ++i)
cin >> b[i];
long long ans = 0x3f3f3f3f;
long long proDays = -1; //记录升职到当前职位所需的天数
long long left = 0; //Polycarp剩余的钱
for (int i = 1; i <= n; ++i) {
++proDays;
ans = min(ans, proDays + ((c - left) + a[i] - 1) / a[i]);
if (i == n)
break;
proDays += ((b[i] - left) + a[i] - 1) / a[i];
left = left + a[i] * (((b[i] - left) + a[i] - 1) / a[i]) - b[i];
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
G:Short Task
题目入口：
题意：
一个正整数n的所有因子和等于c。现在给出c，求满足该条件的最小的n。
思路：
暴力，借用埃氏筛的思想将每个正整数k的因子i加到ak上，之后遍历整个a数组，记录一下可以得到c的最小值。
时间复杂度O(nlogn)
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = (int)1e7 + 5;
void solve() {
vector<int>res(MAXN, 0);
vector<int>ans(MAXN, 0x3f3f3f3f);
//i一定是j的因子 可以理解为一个数n = k*i（k为常量）
for (int i = 1; i < MAXN; ++i) {
for (int j = i; j < MAXN; j += i) {
res[j] += i;
}
}
for (int i = 1; i < MAXN; ++i) {
if(res[i] < MAXN)
ans[res[i]] = min(ans[res[i]], i);
}
int t, c;
cin >> t;
while (t--) {
cin >> c;
if (ans[c] == 0x3f3f3f3f)
cout << -1 << endl;
else
cout << ans[c] << endl;
}
}
int main() {
solve();
return 0;
}