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;
}
京公网安备 11010502036488号