前三题还是比较水的。除了C题受制于英文理解成了正负交替子序列和最大值当成了条dp，也都没浪费什么时间
A. Candies
数学题
$$x=\frac{n}{2^k-1}$$
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-04-22 22:11:28
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
* @ProbTitle:
*/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//(2^k-1)=n;
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll p = 2;
while (n % ((1 << p) - 1) != 0)
{
++p;
}
cout << n / ((1 << p) - 1) << endl;
}
return 0;
}
B. Balanced Array
也算个数学题，显然可以推出来n只有是4的倍数的时候才可以，在奇数最后一个补上前面奇数拉下的差值即可
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-04-22 22:12:41
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
* @ProbTitle:
*/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//n%4==0
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
if (n % 4 != 0)
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
for (int i = 1; i <= n / 2; i++)
{
cout << i * 2 << " ";
}
for (int i = 1; i <= n / 2 - 1; i++)
{
cout << i * 2 - 1 << " ";
}
cout << n - 1 + n / 2 << endl;
}
}
return 0;
}
C. Alternating Subsequence
因为是要找最长的里面的最大值（注意先要保证最长）也就是说每一次遇到正负交替的时候一定要进行更新，而当符号相同时更新大值即可。小贪心
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-04-22 22:14:07
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
* @ProbTitle:
*/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200005];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
ll cursum = a[0];
ll flag = a[0]; //保存上一个
for (int i = 1; i < n; i++)
{
if (a[i] > 0)
{
if (flag < 0) //上一个为负 本次读+
{
cursum += a[i];
flag = a[i];
}
else if (flag > 0 && a[i] > flag) //上一个为+ 本次读-
{
cursum += (a[i] - flag);
flag = a[i];
}
}
else if (a[i] < 0)
{
if (flag > 0) //上一个为+ 本次读-
{
cursum += a[i];
flag = a[i];
}
else if (flag < 0 && a[i] > flag) //上一个为-本次读+ 更新更大的
{
cursum += (a[i] - flag);
flag = a[i];
}
}
}
cout << cursum << endl;
}
return 0;
}