ACGO 第一次挑战赛题解
2024-02-26 16:03:32
发布于：新加坡
写得比较仓促，可能中文有语法问题，见谅。如果看不懂可以看代码。
T1 算数排列
思路：这道题可以使用贪心算法来解。尽可能的让大的数字去匹配[1..n]中排列的较大数字即可。例如当数组长度为10的时候，数字10和5同时都可以变换成5。我们应该选择让10变成5，让5变成2来尽可能地最大化去匹配每一个数字。通过记录一个vis数组来保存某一个数字是否被使用过。技术上没有难点，重点是思想上需要花费一些时间。
时间复杂度：对于每一组测试数据来说，时间复杂度约为。
本题的cpp代码如下。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt, t, n, vis[55];
int main(){
// 贪心
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
while(t--){
cnt = 0;
memset(vis, 0, sizeof vis);
cin >> n;
for (int i=1; i<=n; i++){
int tmp;
cin >> tmp;
while(tmp && (tmp > n || vis[tmp])) tmp >>= 1;
if (!vis[tmp] && tmp){
vis[tmp] = 1;
cnt++;
}
}
cout << (cnt == n ? "YES" : "NO") << endl;
}
return 0;
}
T2 数组片段匹配
思路：这道题也是一道贪心问题，比第一题来说要更好想。假设有10个数字，名称分别为a到e，其中d和i两个数字可以进行匹配。如下图所示：
a b c d e f g h i j
x x x 1 x x x x 1 x
我们的任务现在转变为寻找字母 'd' 和 'i' 在数列中共同索引为 'y' 且长度为 'k' 的区间。我们首先确定左端点，因为 'd' 和 'i' 的索引相同，所以左端点永远是数列的开头。接着我们确定右端点，同样地，右端点应该是数列的结尾。
设左端点为 'l'，右端点为 'r'，我们可以表示长度为 length = r - (d - l + 1) + 1;，简化后得到 r - l + 1。
接下来，我们来分析如何找到 'd' 的索引。我们可以创建一个名为 'vis' 的变量来记录每个数字上一次出现的索引。例如，'vis[5]' 就代表数字 '5' 上一次出现的索引。如果没有出现过，则在计算时需要忽略该数字。
时间复杂度：对于每一组测试数据来说，时间复杂度约为。
本题的cpp代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt, t, n, tmp;
int ans, vis[150005];
int main(){
// 贪心
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
/*
找到上一个的位置，由于xi=yi因此可以固定最端点。
l左端点的最值应该永远是a。接下来确定右端点。
r右端点取到最右端。
最后结果应该是r - (d - l + 1) + 1；
*/
while(t--){
ans = -1;
cin >> n;
memset(vis, 0, sizeof vis);
for (int i=1; i<=n; i++){
cin >> tmp;
// 查找tmp上一次出现的位置。
if (vis[tmp] != 0){
int l = i - vis[tmp] + 1;
int r = n;
ans = max(ans, r - l + 1);
} vis[tmp] = i;
}
cout << ans << endl;
}
return 0;
}
T3 敢的冒险者
思路：这道题可以看作是一道等差数列的变形。如果直接使用广搜或深搜来做的话是不可行的，时间会超时。因此考虑使用找规律的方法来完成本题。
首先考虑只向右边跳再向左边跳回来的情况。也就是先计算向右跳跃多少次可以刚好超越或等于x点。如果刚好等于x点，那么直接输出答案即可。否则的话就需要在某一步往前跳来跳到终点。例如终点是8，第一个刚好大于8的等差数列是1+2+3+4。只需要在第一步的时候往左跳跃就可以了-1+2+3+4。再比如终点是12，则等差数列应该为1+2+3+4+5=15，那么应该改成这样子1-1+3+4+5=12就可以了。
不难找出规律，由于等差数列的每一项都是严格递增的，那么等差数列的和与x的差就一定会出现在等差数列中。只需要想方设法把这一项的值给减去即可，即如果答案和等差数列的差值为m的话，那么只需要修改等差数列的第m/2项为-1即可。但是如果正好差1的话，只能直接往后走一步，没有别的办法。
时间复杂度：大约为。
本题的cpp代码如下，
#include <iostream>
using namespace std;
int t, x, y;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
while(t--){
cin >> x;
// 用等差数列求第k次跳跃。
int l=0, r=10000, ans;
while(l <= r){
int mid = (l + r) >> 1;
if ((1 + mid) * mid / 2 >= x){
r = mid - 1;
ans = mid;
} else l = mid + 1;
}
// 因为每一项与前面一项的差是线性递增的。
// 所以最后的结果和x差的数一定在等差数列中。
// 如果差k，那么只需要在第k/2步的时候往前走一步就好了。
// 但是如果正好差1的话，只能直接往后走一步，没有别的办法。
if (x + 1 == (1 + ans) * ans / 2) cout << ans + 1 << endl;
else cout << ans << endl;
}
return 0;
}
T4 超能战士
思路：先排序，排好序后这个数列就是单调递增的了。也就是说如果在第k次攻击的时候能打败第i个怪兽，那么前i-1个怪兽也可以被全部打败。接下来只需要从第i+1个怪兽开始二分最多可以打败多少个怪兽就可以了。
本题还需要减去剩余怪物攻击的最小值，通过一个数组minset记录即可。minset[i]表示从第i个怪兽开始到第n个怪兽攻击的最小值是memset[i]。
时间复杂度：对于每一组测试用例，时间复杂度大约为。
本题的cpp代码如下，
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int n, k, t;
struct monster{
int blood;
int attack;
} arr[100005];
int minset[100005];
bool cmp(monster a, monster b){
if (a.blood == b.blood) return a.attack > b.attack;
return a.blood < b.blood;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
while(t--){
memset(arr, 0, sizeof arr);
memset(minset, 0x7f, sizeof minset);
cin >> n >> k;
for (int i=1; i<=n; i++) cin >> arr[i].blood;
for (int i=1; i<=n; i++) cin >> arr[i].attack;
sort(arr+1, arr+n+1, cmp);
for (int i=n; i>=1; i--){
// 求出从第i个开始的最小伤害。
minset[i] = min(minset[i+1], arr[i].attack);
}
// 直接枚举次数的值应该是可行的。
// pre用于记录上n次枚举后的伤害，pre是累加的。
// nextm表示下一次搜索要从nextm+1开始。
int times = 0, pre = 0, nextm = 0;
bool flag = true;
while(true){
times += 1;
// 所有的怪兽都会减少k，
// 那么只需要找到排序后第一只大于k*times+pre的就可以了。
// 用二分查找
int l=nextm, r=n, ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if (k + pre >= arr[mid].blood){
l = mid + 1;
ans = mid;
} else r = mid - 1;
}
nextm = (ans == -1 ? nextm : ans + 1);
pre += k;
int minimum = 0x7f7f7f7f;
k -= minset[nextm];
if (nextm > n) break;
if (k <= 0) {
flag = false;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}
T5 迷宫L
思路：也是一道贪心问题。如果在一个2*2的方格中至少有两个空格，那么对于整一个n*m的地图来说，每一次使用L可以只消除一个方块。那么结果就应该是地图中所有需要消除方块的数量。否则，如果地图中所有方块都需要被消除，那么第一次消除的时候就会必须戏消除3个方块才可以。但在之后每次就消除一个方块就行，因此结果为n * m - 2。否则的话，第一次消除2个方块，之后每次使用技能只消除一个方块就可以了，因此结果为n * m - 1。
时间复杂度：对于每一组测试用例，时间复杂度大约为。
本题的cpp代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char c;
int t, n, m;
int map[505][505];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
while(t--){
cin >> n >> m;
int block = 0, flag = 0;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> c;
map[i][j] = c - '0';
if (map[i][j] == 1) block++;
}
}
for (int i=1; i<n && !flag; i++){
for (int j=1; j<m && !flag; j++){
// 但凡可以删除一个方块，答案就是方块数。
int cnt = 4 - (map[i][j] + map[i+1][j] + map[i][j+1] + map[i+1][j+1]);
if (cnt >= 2) flag = 1;
}
}
if (flag) cout << block << endl;
else if (block == n * m) cout << block - 2 << endl;
else cout << block - 1 << endl;
}
return 0;
}
T6 质数花瓣
思路：这道题用质数筛可以侥幸过，但提供一个暴力优化枚举的思路。
先展示一下质数筛的代码：
#include <iostream>
#include <cmath>
#include <bitset>
using namespace std;
int n, cnt;
int prime[10000005];
bitset<100000005> vis;
void primeSieve(int range){
vis[0] = vis[1] = 1;
for (int i=2; i<=range; i++){
if (!vis[i]){
prime[++cnt] = i;
}
for (int j=1; j<=cnt && i * prime[j] <= range; j++){
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
return ;
}
int main(){
cin >> n;
int l = pow(10, n-1);
int r = pow(10, n);
primeSieve(r);
for (int i=l; i<r; i++){
int num = i, flag = 1;
while(num){
if (vis[num]){
flag = false;
break;
}
num /= 10;
}
if (flag) cout << i << endl;
}
return 0;
}
暴力的优化过程，
这是完全暴力没有任何优化的代码，可以拿到70分。
#include <iostream>
using namespace std;
int main(){
int n,s = 1,e = 10;
cin >> n;
while(n>1){
s = s * 10;
e = e * 10;
n--;
}
for(int i=s;i<e;i++){
int flag = 1;
int origin= s;
for(int k= i;k!=0;k/=10){
if(k == 1) flag = 0;
for(int j = 2; j<k ;j++){
if(k % j == 0 && k !=2){
flag = 0;
break;
}
}
if(flag == 0) break;
}
if(flag == 1) cout << i << endl;
}
return 0;
}
考虑减少判断质数的次数，由于一个合数所有的因数都是成对出现的，因此在判断质数的时候可以减少一般的枚举范围。可以从减少到。代码如下：
#include <iostream>
using namespace std;
int main(){
int n,s = 1,e = 10;
cin >> n;
while(n>1){
s = s * 10;
e = e * 10;
n--;
}
for(int i=s;i<e;i++){
int flag = 1;
int origin= s;
for(int k= i;k!=0;k/=10){
if(k == 1) flag = 0;
for(int j = 2; j*j<k ;j++){
if(k % j == 0 && k !=2){
flag = 0;
break;
}
}
if(flag == 0) break;
}
if(flag == 1) cout << i << endl;
}
return 0;
}
对于每一个数字，要判断是否是一个质数花瓣，有从后往前判断和从前往后判断两种方法。不难想出，从左往右遍历的话速度会大大减少。因为判断一个小一点的数字是否是质数的成本比较低，可以通过从小到大判断的方式提前否决掉一些非质数花瓣。这样子可以拿到100的分数。但还不够完美，时间大约为600ms左右。
#include <iostream>
using namespace std;
int main(){
int n,s = 1,e = 10;
cin >> n;
while(n>1){
s = s * 10;
e = e * 10;
n--;
}
for(int i=s;i<e;i++){
int flag = 1;
int origin= s;
for(int k= i/origin;origin;origin/=10){
k = i/origin;
if(k == 1) flag = 0;
for(int j = 2; j*j<=k ;j++){
if(k % j == 0 && k !=2){
flag = 0;
break;
}
}
if(flag == 0) break;
}
if(flag == 1) cout << i << endl;
}
return 0;
}
继续考虑，继续考虑减少枚举的范围。假设如果数字1000不符合标准，那么其实就没有必要考虑1001和1002了，可以直接从2000开始判断。因此如果否决掉某一个数字之后，可以直接跳过许多数字。大大减少枚举范围。通过使用一个flag变量，记录否决掉的位数。下次枚举的时候直接进位即可。大功告成，时间大约为57ms左右。
#include <iostream>
#include <cmath>
using namespace std;
signed main(){
int n, s = 1,e = 10;
cin >> n;
s = pow(10, n-1);
e = pow(10, n);
for(int i=s;i<e;i++){
int flag = -1;
int origin = s;
for(int k=i/origin; origin; origin /= 10){
k = i / origin;
if (k == 1) flag = origin;
for(int j = 2; j * j <= k ;j++){
if(k % j == 0 && k != 2){
flag = origin;
break;
}
}
if (flag != -1) break;
}
if(flag == -1) {cout << i << endl;}
else i = (i / flag + 1) * flag - 1;
}
return 0;
}
有帮助，赞一个