A.Candies
- 输入一个数字n，输出满足(k > 1) && ((2 ^ k) - 1) * x == n的任意x值,由于n < 1e9，k由2开始枚举,找到符合条件的x输出。
B.Balanced Array
输入数组长度n，问是否存在这样的一个数组：1. 数组前一半均为偶数，后一半均为奇数;2.前一半和后一半数组中元素的和相等
- 后一半数组中为奇数，与前一半数组和相等即n/2 也是偶数
- 若满足上面的条件,从2开始枚举 n/2 个偶数输出并求和
- 从1开始枚举输出n/2 - 1个奇数并求和，最后输出之前偶数和与奇数和的差值
C. Alternating Subsequence
做的时候读题太粗心,只看到了最大和。WA了之后读了好几次题也没看到最长这个优先级最高的条件，一直在错误的地方修改......
-
题目中会输入一组长为n的数组，要求输出一个最长的交错子序列[1]的最大和
-
贪心:遍历数组,每个连续的同号子串取最值。
cin >> t;
while(t--){
cin >> n;
ans = mx = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
if(!i || a[i] * a[i - 1] < 0){
ans += mx;
mx = a[i];
}else{
mx = max(mx,a[i]);
}
}
cout << ans + mx << endl;
}
D. Constant Palindrome Sum
输入由n个整数组成的数组a,和整数k，替换数组中de一些元素为[1,k]中的任一元素，使数组满足：
- a[i] <= k
- a[i] + a[n - i + 1] = x,即对称的元素和为定值( 2 <= x <= 2k)
- 求最小替换元素的个数
对于确定的x，每对元素的交换次数确定
-
a + b = x
-
x ∈[min(a,b) + 1,max(a,b) + k + 1)，半开半闭的区间方便合并，获得最小和，最大和,差分，此区间 + 1--起始位置 + 2，左边界(闭)-1，右边界(开) +1
-
其它
交换次数存在一个最大值，当x = k + 1，为 n / 2（所有元素值的区间[1,k]）；对每一对元素，计算交换次数为1的区间，使用差分思想通过cnt数组在区间外+2，区间内+1，对每一对元素的和特殊处理；在枚举完所有的元素对后，将差分数组cnt修改为前缀和即为相应x的替换次数，ans 初始化为n / 2,遍历cnt数组寻找最小替换次数。。。
const int kN = 2e5 + 10,kM = 4e5 + 5;
int t,n,k,l,r,ans,a[kN],cnt[kM];
//替换最少数量的元素，数组中对称元素和满足 a[i] + a[n - i + 1] = x;x为某个定值
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >>t;
while(t--){
memset(cnt,0,sizeof(cnt));
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n / 2; i++){
l = min(a[i],a[n - i + 1]) + 1;
r = max(a[i],a[n - i + 1]) + k + 1;//区间左闭右开，便于合并
cnt[1] += 2;//差分 边界[2,l) 需要两次
cnt[l]--;//[l,r] 一次
cnt[r]++;
cnt[a[i] + a[n - i + 1]]--;//0
cnt[a[i] + a[n - i + 1] + 1]++;
}
for(int i = 2; i <= 2 * k; i++) cnt[i] += cnt[i - 1];//计算各个x值的替换次数
ans = n / 2;
for(int i = 1; i <= 2 * k; i++) ans = min(ans,cnt[i]);
cout << ans << endl;
}
return 0;
}
正负交替 ↩︎