菜鸡的$div3$补题现场……
A:Candies
1.题目描述:
给你一个n, 让你找到满足$x + 2x + 4x + \dots + 2^{k-1} x = n $ 的$x$整数值。其中 $k > 1$
input:
1 2 3 4 5 6 7 8
| 7 3 6 7 21 28 999999999 999999984
|
output:
1 2 3 4 5 6 7
| 1 2 1 7 4 333333333 333333328
|
2.思路
考虑:
我们令$k = 2$ 开始遍历$k$即可,整除时输出$x$然后$break$。
3.代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std;
int t, n; int main() { IOS cin >> t; while(t--) { cin >> n; for(int k = 2; ; k++) { if(n % ((1 << k) - 1) == 0) { cout << n / ((1 << k) - 1) << endl; break; } } } system("pause"); return 0; }
|
B:Balanced Array
1.题目描述
给$n$(保证n是偶数),然后找一个序列长度是$n$
- 前$\frac{n}{2}$个序列元素是偶数
- 后$\frac{n}{2}$个序列元素是奇数
- 所有元素都是正整数
- 前$\frac{n}{2}$和后$\frac{n}{2}$的和相等 即:
input:
output:
1 2 3 4 5 6 7
| NO YES 2 4 1 5 NO YES 2 4 6 8 1 3 5 11 NO
|
2.思路:
构造题
我们首先判断 对于给定的$n$,是否存在满足题目要求的序列。
如果$n / 2 % 2 ==1$证明无解 输出$”NO”$。举例证明即可:
当$n = 6$时,前半部分长度和后半部分长度均为$3$,则其和不可能相等。
判断一下$n / 2$之后即可【注意此处的写法 开采用$continue$来继续处理】……
接下来我们就可以去构造两个长度为$\frac{n}{2}$的序列。
令 $cnt = \frac{n}{2}$
通过$for$循环输出每次的$i$我们可以把前$cnt$次的偶数序列构造完毕。
通过$for$循环输出每次的$i$我们可以把前$cnt- 1$次的技术序列构造完毕 但前$cnt$项与上边每一项相比 少了$1$ 于是我们后边对于第$cnt$项输出$2 * cnt - 1 + cnt$.[上边偶数项对应$-1 + $前边缺少的每一项累加起来的和]
我才用的是另一种方法:设置两个标记计算两个$sum$ 然后判断一下$sum$之间的大小 然后输出差即可。
3.代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std;
int t, n; int main() { IOS cin >> t; while(t--) { int ans1 = 0, ans2 = 0; cin >> n; n /= 2; if(n % 2 == 1) { cout << "NO" << endl; continue; } cout << "YES" << endl; for(int i = 1; i <= n; i++) { cout << 2 * i << " "; ans1 += i * 2; } for(int i = 1; i < n; i++) { cout << 2 * i - 1 << " "; ans2 += 2 * i - 1; } if(ans1 > ans2) { cout << ans1 - ans2 << endl; } else { cout << ans2 - ans1 << endl; } }
return 0; }
|
C:Alternating Subsequence
1.题目描述
交错子序列问题
定义:如果一个序列$a$可以通过删除$0$个或多个元素而不改变其余元素的顺序而得到$b$,那么称:$b$是$a$的子序列。
给你一个不包含$0$的长度为$n$的正负元素序列。
你的任务是找到一个具有最大元素总数的交错子序列. 交错序列就是下一个元素的符号与当前元素的服好相反.[类似 $+-+$/$-+-$]
$n$的范围:$1 \le n \le 2 \cdot 10^5$
input:
1 2 3 4 5 6 7 8 9
| 4 5 1 2 3 -1 -2 4 -1 -2 -1 -3 10 -2 8 3 8 -4 -15 5 -2 -3 1 6 1 -1000000000 1 -1000000000 1 -1000000000
|
output:
2.思路:
采用双指针$i$和$j$来用贪心求解。
从序列开头 往后双指针 $i,j$计算,分别表示当前和下一个的下标。
然后我们$while$一下,判断条件就是当$j + 1<= n$时,并且前后元素是异号的时候, $ans$加上该同号区间的最大值。然后将$j$的值赋给$i$,继续处理下一个区间。
codeforces上给了一个更为清晰的写法 但大致原理是相同的:
就是寻找当前同号区间中的最大值,然后和下一个区间(与上一个区间异号)的最大值相加就是$ans$。注意更新$i j $的区间值。
采用$dp$.
详见代码注释
3.代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std; const int maxn = 2e5 + 6; int t, n; ll a[maxn]; int main() { IOS cin >> t; while(t--) { memset(a, 0, sizeof(a)); ll ans = 0; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n; i++) { int j = i; ll now = a[i]; while(j + 1 <= n && ((a[i] > 0 && a[j + 1] > 0) || (a[i] < 0 && a[j + 1] < 0))) { j++; now = max(now, a[j]); } i = j; ans += now; } cout << ans << endl; }
return 0; }
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std; const int maxn = 2e5 + 5; pair<int, ll>dp[maxn][2];
int t, n; int a[maxn]; int main() { IOS cin >> t; while(t--) { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[i][0] = make_pair(0, 0); dp[i][1] = make_pair(0, 0); } for(int i = 1; i <= n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i][0]); dp[i][1] = max(dp[i - 1][1], dp[i][1]); if(a[i] > 0) { dp[i][0] = max(dp[i - 1][0], make_pair(dp[i - 1][1].first + 1, dp[i - 1][1].second + a[i])); } else { dp[i][1] = max(dp[i - 1][1], make_pair(dp[i - 1][0].first + 1, dp[i - 1][0].second + a[i])); } } pair<int, ll>ans; ans = max(dp[n][0], dp[n][1]); cout << ans.second << endl; } system("pause"); return 0; }
|