A. Candies
题意
给定一个整数，判断是否存在
思路
先对公式进行预处理 明显是一个等比数列
化简后得到
因为答案一定存在 所以用快速幂从小到大枚举即可
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
#define mem(n,a) memset(n,a,sizeof(n))
#define rep(i,be,en) for(int i=be;i<=en;++i)
#define pre(i,be,en) for(int i=en;i>=be;--i)
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;LL quick_pow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans *= a;a *= a;b >>= 1;}return ans;
}
int main() {int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 2;i <= 32;++i) {int t = quick_pow(2, i) - 1;if (n % t == 0) {printf("%d\n", n / t);break;}}}return 0;
}
B. Balanced Array
题意
构造一个长度为n的数列，n为偶数，使得前![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S4DY4w2x-1594654027477)(https://www.nowcoder.com/equation?tex=%5Cdfrac%20%7Bn%7D%7B2%7D "图片标题")]](https://img-blog.csdnimg.cn/20200713233009124.png)
个数全为偶数
后
个数全为奇数
并且使前后区间和相等
思路
观察样例可知 n/2为奇数时不能构造出来
n/2为偶数时 对前面的偶数按顺序构造，后面的n/2-1个奇数也按顺序构造，用最后一个奇数补足与偶数和的差值使前后区间和相等
容易知道最后一个奇数应该为
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
#define mem(n,a) memset(n,a,sizeof(n))
#define rep(i,be,en) for(int i=be;i<=en;++i)
#define pre(i,be,en) for(int i=en;i>=be;--i)
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;int main() {int t;cin >> t;while (t--) {int n;cin >> n;if ((n / 2) & 1)puts("NO");else {puts("YES");int t = 2;for (int i = 1;i <= n / 2; ++i)printf("%d ", t), t += 2;t = 1;for (int i = 1;i <= n / 2 - 1; ++i)printf("%d ", t), t += 2;printf("%d\n", n / 2 - 1 + n);}}return 0;
}
C. Alternating Subsequence
题意
从给定序列中选择一个正负交替的子序列使得子序列的和最大
思路
双指针，每次扫过一个正负号相同的区间，找到区间的最大值作为子序列的元素
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
#define mem(n,a) memset(n,a,sizeof(n))
#define rep(i,be,en) for(int i=be;i<=en;++i)
#define pre(i,be,en) for(int i=en;i>=be;--i)
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 200010;int a[N];int np(int a) {if (a < 0)return 1;else return 2;
}int main() {int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1;i <= n;++i)cin >> a[i];LL ans = 0;int s, p, maxn;p = 1;while (p <= n) {s = p;maxn = a[p];while (np(a[s]) == np(a[p]) && p <= n) {maxn = max(maxn, a[p]);++p;}ans += maxn;}cout << ans << endl;}return 0;
}
D. Constant Palindrome Sum
题意
给一个长度为n的数列和一个k 要求用不大于k的数替换数组中的任意一个数 使 所有关于数组对称的两个位置的元素和相等 即
问最少替换多少次
思路
刚开始我想先算出每两个数对的和出现次数最多的当作x 再根据x与其他组数对的大小计算答案 后来发现这种方法是不可行的 因为每个数对和都不一样的情况是可能出现的 这时候无法判断到底选哪个作为x更合适
后来 看到别人的博客 才想起来下面这种方法
即 算出每个数对的和 并且记录该数对每一个x的贡献 再选择一个最小的当作答案
很容易分情况讨论
令minn = min(a[i], a[n - i + 1])
maxn = max(a[i], a[n - i + 1])
t = a[i] + a[n - i + 1]
delta代表差分数组
因为数组元素的范围是 [1,k]
所以数对的取值范围为 [2,2*k]
①x取 [2,minn] 时 即使较大的那个数改成了1 还是不符合这个范围 所以需要两个都改变
②x取 [minn + 1,maxn + k] 时，只需要改变其中一个数字即可
③x取 [maxn + k + 1, 2 * k] 时，两个都需要改变
④因为当数对和为x时 不需要改变任何一个数字 而第二部已经把这种情况包括了 所以需要减去 即 delta[x]–
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
#define mem(n,a) memset(n,a,sizeof(n))
#define rep(i,be,en) for(int i=be;i<=en;++i)
#define pre(i,be,en) for(int i=en;i>=be;--i)
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 200010;int a[N], delta[N << 1];int main() {int t;cin >> t;while (t--) {memset(delta, 0, sizeof delta);int n, k;cin >> n >> k;for (int i = 1;i <= n;++i)cin >> a[i];for (int i = 1;i <= n / 2;++i) {int t = a[i] + a[n - i + 1];int minn = min(a[i], a[n - i + 1]);int maxn = max(a[i], a[n - i + 1]);delta[2] += 2;delta[minn + 1] -= 2;delta[maxn + k + 1] += 2;delta[2 * k + 1] -= 2;delta[minn + 1] ++;delta[maxn + k + 1]--;delta[x]--;delta[x + 1]++;}LL ans = INF;for (int i = 2;i <= 2 * k;++i) {delta[i] += delta[i - 1];ans = min(ans, (LL)delta[i]);}cout << ans << endl;}return 0;
}
