大四的萌新辣！

Codeforces-Round-636-Div-3

Posted on Edited on In Valine:

菜鸡的$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
/**
* Copyright(c)
* Author : tiketiskte
*/
#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:

1
2
3
4
5
6
5
2
4
6
8
10

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
/**
* Copyright(c)
* Author : tiketiskte
*/
#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;
       }
       //cout << 2 * n - 1 + n <<endl;[第一种解法]
       if(ans1 > ans2) {
           cout << ans1 - ans2 << endl;
       } else {
           cout << ans2 - ans1 << endl;
       }
    //    cout << endl;
    //    cout << "###1:" << ans1  << " " << "###2:" << ans2 << endl;
   }
//    system("pause");
   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：

1
2
3
4
2
-1
6
-2999999997

2.思路：

  1. 采用双指针$i$和$j$来用贪心求解。

    从序列开头 往后双指针 $i,j$计算，分别表示当前和下一个的下标。

    然后我们$while$一下，判断条件就是当$j + 1<= n$时，并且前后元素是异号的时候, $ans$加上该同号区间的最大值。然后将$j$的值赋给$i$，继续处理下一个区间。

  2. codeforces上给了一个更为清晰的写法 但大致原理是相同的：

    就是寻找当前同号区间中的最大值，然后和下一个区间（与上一个区间异号）的最大值相加就是$ans$。注意更新$i j $的区间值。

  3. 采用$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
//写法1 or 2
/**
* Copyright(c)
* Author : tiketiskte
*/
#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;
   }
//    system("pause");
   return 0;
}
//写法3
/**
* Copyright(c)
* Author : tiketiskte
*/
#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];
//dp[i][0].first表示前i项交错子序列以正数结尾的最长长度
//dp[i][0].second表示前i项交错子序列以正数结尾的最长长度的最大和
//dp[i][1].first表示前i项交错子序列以负数结尾的最长长度
//dp[i][1].second表示前i项交错子序列以负数结尾的最长长度的最大和
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]));
           }
        //    cout << endl;
        //    cout << "###1:" << dp[i][0].first << " " << "###2:" << dp[i][0].second << endl;
        //    cout << "$$$1:" << dp[i][1].first << " " << "$$$2:" << dp[i][1].second << endl;
       }
       pair<int, ll>ans;
       ans = max(dp[n][0], dp[n][1]);
       cout << ans.second << endl;
   }
   system("pause");
   return 0;
}