昨晚训练赛打到23:00,又打了一场cf,前面两题做的挺顺畅的,第三题可能是太累了犯了个很傻逼的错(C题n小于1000,但是输入是数据量为2n,我只开了1111的数组,结果太累了把RE当成了TLE,一直在优化时间,其实第一发的代码改大数组就能过的),本来应该很快就能搞完三题的,结果就过了两道题,掉大分了。说到底还是不够细心,练得不够多,吃一堑长一智吧!
A. Puzzle From the Future(模拟 贪心)
题意:
有两个01序列a b,先将a和b不进位相加得到c(例如010110 + 110101 = 120211),再将c连续相同的数字用一个数字代替(例如1112200 = 120),将其表示成十进制数得到d,故(102>21 , 012<101, 021=21),现在告诉你a,让你求b使得d尽量大。
题目分析:
要d尽量大就要使得c尽量长,即a+b后保证没有连续的长度,其次要使得每位数字尽量大,且位数越高的地方数字要尽可能的高,所有从最高位开始向后遍历a,b的第一位一定为1,然后根据上一位确定当前应该是1还是0(如果当前是1不会使得当前位和上一位数字一样就为1,否则为0),依次确定每一位即可得到b。
代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
string a,b;
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
b.clear();
int n;
cin >> n >> a;
int past = a[0] - '0' + 1;
b += '1';
for(int i = 1; i <n; i++) {
if(past == a[i] - '0' + 1) {
b += '0';
past = a[i] - '0';
}
else {
b += '1';
past = a[i] - '0' + 1;
}
}
cout << b << endl;
}
return 0;
}
B – Different Divisors
题意:
给你数字d,要你求出最小的整数a,a满足至少4个因子,且任意两个因子的差大于等于d。
题目分析:
首先1是所有数字的因子,肯定要选,然后我们可以找到两个素数,分别为大于等于1+d的最小素数和大于等于1+2d的最小素数,作为a的另外两个因子,然后将这两个素数相乘当做a的最后一个因子,同时这个因子就是a。
代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int primes[maxn], cnt; // primes[]存储所有素数
bool st[maxn]; // st[x]存储x是否被筛掉 0是素数
void get_primes() {
for (int i = 2; i <= maxn-10; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= maxn / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main(int argc, char const *argv[]) {
get_primes();
int t;
cin >> t;
while(t--) {
int d;
cin >> d;
int now = 1+d;
int ans;
while(st[now]!=0) now++;
ans = now;
now += d;
while(st[now] != 0) now++;
ans *= now;
cout << ans << endl;
}
return 0;
}
C – Array Destruction
题意:
给你有2n个数字的数组,要你任选一个数字x,执行操作:删去数组中任意两个和为x的数字,再将两个数字中较大的数当做x,重复执行此操作。问你是否存在x使得可以删完所有的数,若可以输出YES和x以及操作过程,否则输出NO。
题目分析:
首先由于x每次变成选取的两个数字中较大的那个,所以我们第一次必须选上数组中最大的数(否则最大的那个数肯定删不掉),我们先把数组排好序,那么x就变成了$a[i] + a[2n](0 \le i \le 2*n-1)$,所以枚举所有的i就可以确定第一个x的数值,剩下的问题就是如何快速验证某个x是否可行,我的做法是直接模拟,用vis记录是否已经选取,再加上一点剪枝过的,还有一种做法是用mutilset,这是一种查找和删除都是nlogn的数据结构,实现起来更加简洁。
代码:
代码1
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[2111];
bool vis[2111];
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
n *= 2;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
int f = 0;
for (int k = 1; k <= n - 1; k++) {
queue<PII> q;
int cnt = 2;
for (int i = 0; i <= n; i++) vis[i] = 0;
vis[k] = vis[n] = 1;
q.push({k, n});
int now = a[n];
int i = n;
while (i >= 1) {
i--;
if (vis[i] == 1) continue;
int flag = 0;
for (int j = 1; j < i; j++) {
if (vis[j] == 1) continue;
if (a[j] + a[i] == now) {
vis[i] = vis[j] = 1;
q.push({j, i});
now = a[i];
flag = 1;
cnt += 2;
break;
}
if (a[j] + a[i] > now) break;
}
if (flag == 0) break;
}
if (cnt == n) {
f = 1;
puts("YES");
cout << a[q.front().first]+a[q.front().second] << endl;
while (q.size()) {
cout << a[q.front().first] << ' ' << a[q.front().second]<< endl;
q.pop();
}
break;
}
}
if (f == 0) puts("NO");
}
return 0;
}
代码2:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[2111];
bool flag;
int n;
vector<PII> ans;
bool judge(int x) {
ans.clear();
multiset<int> s;
for (int i = 1; i <= n; i++) s.insert(a[i]);
for (int i = 0; i < n / 2; i++) {
auto it = --s.end();
int now = *it;
s.erase(it);
it = s.find(x - now);
if (it == s.end()) return false;
int other = *it;
s.erase(it);
ans.push_back({now, other});
x = now;
}
return true;
}
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while (t--) {
cin >> n;
n *= 2;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
flag = 0;
for (int k = 1; k <= n - 1; k++) {
int x = a[k] + a[n];
if (judge(x)) {
flag = 1;
puts("YES");
printf("%d\n", x);
for (int i = 0; i < ans.size(); i++)
printf("%d %d\n", ans[i].first, ans[i].second);
break;
}
}
if (flag == 0) puts("NO");
}
return 0;
}