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为偶数，使得前
个数全为偶数
后
个数全为奇数并且使前后区间和相等
思路
观察样例可知 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; }
