题目1:B. Not Dividing
这个题有点奇怪,他的大意就是给定一个数组,可以对数组中的任意一个数做+1操作,保证a(i+1)不被a(i)整除,但是总次数不能超过2*n
感觉这就是一个结论吧,就是随便加,因为题目里保证一定能得出来结果
代码:
#include
#include
using namespace std;
const int length = 1e5 + 5;
typedef long long ll;
ll reco[length];
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;scanf_s("%d", &n);for (int i = 0; i < n; i++){scanf_s("%lld", &reco[i]);if (reco[i] == 1)reco[i]++;}for (int i = 1; i < n; i++){while (reco[i] % reco[i - 1] == 0)reco[i]++;}for (int i = 0; i < n; i++){printf("%lld ", reco[i]);}printf("\n");}
}
题目2:C. Scoring Subsequences
这个题的大意就是满足公式,并且数组满足递增的次序,且数组中的每一个数在[1,n]区间之内。取最大的子序列长度使得其有指定公式最大值,并且序列最长,公式如下:
既然序列递增,把子序列的最后一个数看作第一个,让这个数除以1,那么序列的最后一个数应该除以序列长度,那么只要让从后往前找到的那个数大于序列长度即可,找的时候要贴着找,因为后面的数大
代码:
#include
#include
const int length = 1e5 + 5;
using namespace std;
int dp[length];
int reco[length];
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;scanf_s("%d", &n);for (int i = 1; i <= n; i++){scanf_s("%d", &reco[i]);}dp[1] = 1;for (int i = 2; i <= n; i++){int l = 0;int r = i+1;while (l < r - 1){int mid = (l + r) / 2;int tmp = i - mid + 1;if (reco[mid] >= tmp){r = mid;}elsel = mid;}dp[i] = i - r + 1;}for (int i = 1; i <= n; i++)printf("%d ", dp[i]);printf("\n");}
}
上一篇:智能优化算法之粒子群算法