日常三题选手…
题目描述
给定一个整数 $n$，$k$ 为大于 $1$ 的任意整数，求解方程 $x + 2x + 4x + \dots + 2^{k-1} x = n$。
解法
可以计算得出实质上在求 $(2^{k}-1)x=n$，枚举一下 $2^k-1$，对于 $n \mid 2^k-1$，输出 $x=\dfrac{n}{2^k-1}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int _,n;
ll idx[10005];
int main() {
idx[1]=1;
for(int i=2;i<=63;i++) idx[i]=pow(2,i)-1;
for(scanf("%d",&_);_;_--) {
scanf("%d",&n);
for(int i=2;i<=63;i++) {
if(n%idx[i]==0) {
printf("%d\n",n/idx[i]);
break;
}
}
}
return 0;
}
|
题目描述
给定一个正整数 $n(n \mid 2)$，构造一个长度为 $n$ 的数组 $a$ 使得 $a$ 的前半部分之和与后半部分之和相等，同时 $a$ 的前半部分都是偶数，后半部分都是奇数，$a$ 中每一个数都不相等。
解法
首先思考最小的部分（常用套路），发现 $n=2$ 一定无解，$n=4$ 一定有解。观察样例提示可以发现对于任意 $n \mid 4$ 都是有解的，其他则一定无解。构造方式也比较套路，对于 $1 \sim \dfrac{n}{2}$,$ai = 2^i$,对于 $\dfrac{n}{2}+1 \sim n$ , $a_i=a { i - \frac{n}{2} } - 1$ ,再对最后一个数处理一下 $a_n \gets a_n+\dfrac{n}{2}$，就成功的构造出来了。
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
| #include <bits/stdc++.h>
using namespace std;
int _,a[200005],n;
int main() {
for(scanf("%d",&_);_;_--) {
scanf("%d",&n);
if(n%4!=0) puts("NO");
else {
puts("YES");
int idx=0;
for(int i=2;i<=n;i+=2) {
a[++idx]=i;
}
for(int i=1;i<=n/2-1;i++) {
idx++;
a[idx]=a[idx-n/2]-1;
}
idx++;
a[idx]=a[idx-n/2]+n/2-1;
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\n");
}
}
return 0;
}
|
题目描述
给定长度为 $n$ 的序列 $a$，要求求出最长的一正一负的 $a$ 的子序列中的最大和。
解法
题目要求了最长，可以直接每一段连续区间中只取一个最大的，保证最终和最大。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int _,n,a[200005];
int main() {
for(scanf("%d",&_);_;_--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int i=1,maxx,minx;
ll sum=0;
while(i!=n+1) {
maxx=-0x3f3f3f3f;
minx=-0x3f3f3f3f;
while(a[i]>0&&i!=n+1) {
maxx=max(maxx,a[i]);
i++;
}
if(a[i-1]>0) sum+=maxx;
while(a[i]<0&&i!=n+1) {
minx=max(minx,a[i]);
i++;
}
if(a[i-1]<0) sum+=minx;
}
printf("%lld\n",sum);
}
return 0;
}
|
题目太神仙了，赛后看题解搞出来了，一时半会也不知道怎么做。
