本文代码均省略库和namespace声明，其中read()函数是读入数值的函数。
A. Candies
Recently Vova found n candy wrappers. He remembers that he bought x candies during the first day, 2x candies during the second day, 4x candies during the third day, …, 2k−1x candies during the k-th day. But there is an issue: Vova remembers neither x nor k but he is sure that x and k are positive integers and k>1.Vova will be satisfied if you tell him any positive integer x so there is an integer k>1 that x+2x+4x+⋯+2k−1x=n. It is guaranteed that at least one solution exists. Note that k>1.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (3≤n≤109) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer x and integer k>1 that x+2x+4x+⋯+2k−1x=n.Output
Print one integer — any positive integer value of x so there is an integer k>1 that x+2x+4x+⋯+2k−1x=n.
对式子 x + 2x + 4x + ⋯ + 2k−1x = n 提取公因式，得到：(1 + 2 + 4 + ⋯ + 2k−1) x = n
把它概括为：Ax = n (A = 1 + 2 + 4 + ⋯ + 2k−1)
容易知道，如果存在一个 k (k > 1) 使得上式成立，则 A 一定是 Σ(1..2k−1) ，题目只说存在这样一个 k (k > 1) ，则意味着前述Σ式求得的所有 A 均可使用。于是我们枚举所有可能的 A ，判断有没有正整数 x 满足 Ax = n 即可。
int T;
long long calc[100000],n;
int main()
{
for (register int i=1;i<=30;++i) // 计算30次即可满足所有n对应的要求
calc[i]=calc[i-1]+pow((long long)2,i-1); // 预处理所有可能的 “A”
for(read(T);T;--T)
{
read(n);
for (register int i=2;i<=30;++i)
{
if(n%calc[i]==0)
{
printf("%lld\n",n/calc[i]);
break;
}
}
}
return 0;
}
B. Balanced Array
You are given a positive integer n, it is guaranteed that n is even (i.e. divisible by 2).You want to construct the array a of length n such that:
- The first n/2 elements of a are even (divisible by 2);
- the second n/2 elements of a are odd (not divisible by 2);
- all elements of a are distinct and positive;
- the sum of the first half equals to the sum of the second half (∑ai (i=1,2,...,n/2) = ∑ai (i=n/2+1,...,n)).
If there are multiple answers, you can print any. It is not guaranteed that the answer exists.You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.The only line of the test case contains one integer n (2≤n≤2⋅105) — the length of the array. It is guaranteed that that n is even (i.e. divisible by 2).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n ≤ 2⋅105).
Output
For each test case, print the answer — "NO" (without quotes), if there is no suitable answer for the given test case or "YES" in the first line and any suitable array a1,a2,…,an (1≤ai≤109) satisfying conditions from the problem statement on the second line.
- 当 n/2 为奇数的时候，奇数个奇数的和为奇数，奇数个偶数的和为偶数，不可能存在满足题意的情况，应该输出
NO - 当 n/2 为偶数的时候，偶数按 2 4 6 8 ... 的顺序输出 n/2 个，并记录所有偶数和为 sum1 ，奇数按 1 3 5 7 ... 的顺序输出 n/2-1 个，并记录已输出的奇数和为 sum2 ，最后输出一个 sum2 - sum1 （一定是奇数）即可。
int T,n,sum1,sum2;
int main()
{
for(read(T);T;--T)
{
read(n);
sum1=sum2=0;
if((n/2)&1) { printf("NO\n"); continue; };
printf("YES\n");
for (register int i=2;i<=n;i+=2) printf("%d ",i),sum1+=i;
n>>=1;
for (register int i=1;i<n;++i) printf("%d ",2i-1),sum2+=2i-1;
printf("%d\n",sum1-sum2);
}
return 0;
}
C. Alternating Subsequence
Recall that the sequence b is a a subsequence of the sequence a if b can be derived from a by removing zero or more elements without changing the order of the remaining elements. For example, if a = [1,2,1,3,1,2,1], then possible subsequences are: [1,1,1,1], [3] and [1,2,1,3,1,2,1], but not [3,2,3] and [1,1,1,1,2].You are given a sequence a consisting of n positive and negative elements (there is no zeros in the sequence).
Your task is to choose maximum by size (length) alternating subsequence of the given sequence (i.e. the sign of each next element is the opposite from the sign of the current element, like positive-negative-positive and so on or negative-positive-negative and so on). Among all such subsequences, you have to choose one which has the maximum sum of elements.
In other words, if the maximum length of alternating subsequence is k then your task is to find the maximum sum of elements of some alternating subsequence of length k.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.The first line of the test case contains one integer n (1≤n≤2⋅105) — the number of elements in a. The second line of the test case contains n integers a1,a2,…,an (−109≤ai≤109,ai≠0), where ai is the i-th element of a.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105).
Output
For each test case, print the answer — the maximum sum of the maximum by size (length) alternating subsequence of a.
因为要最长的正负序列，所以如果 a1 是正数，则这个序列一定是正数开头，否则这个序列一定是负数开头。然后我们在每一个正数片段和负数片段各自找到最大值，相加即可。
const int MAXN=200005;
long long T,n,a[MAXN],ans,tmp;
int main()
{
for(read(T);T;--T)
{
read(n);
ans=0;
a[n+1]=0;
for (register int i=1;i<=n;++i) read(a[i]);
bool flag=(a[1]>0);
tmp=a[1];
for (register long long i=2;i<=n+1;++i)
{
if(flag)
{
if(a[i]>0)
{
tmp=max(tmp,a[i]);
} else {
flag=!flag;
ans+=tmp;
tmp=a[i];
}
} else {
if(a[i]<0)
{
tmp=max(tmp,a[i]);
} else {
flag=!flag;
ans+=tmp;
tmp=a[i];
}
}
}
printf("%lld\n",ans);
}
return 0;
}
