抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

T1:优秀的拆分

首先排除所有奇数,然后考虑如果这个数大于2的k次方,那就从 [公式] 一直减下去,如果出现了0那么就成功,否则失败

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>
int s[] = {0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,1048576*2,1048576*2*2,1048576*2*2*2,1048576*2*2*2*2,1048576*2*2*2*2*2};
int vis[20], mx;
int q;
using namespace std;
int main() {

cin >> q;
if(q % 2) {
cout << -1;
return 0;
}
for(int i = 0; i < sizeof(s)/sizeof(int); i ++) {
if(q < s[i]) {
mx = i;
break;
}
}
for(int i = mx; i > 0 && q; i --) {
if(q >= s[i]) {
cout << s[i] << ' ';
q -= s[i];
}
}
}

T2:直播领奖

这是一个动态排序问题,首先考虑到sort的时间复杂度会超限,注意到数据只有600,那么不妨桶排序,只有 O(600n) ,比 O(n²logn)更优秀

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;
int a[605];
int main() {
int n, w, t, acc;
cin >> n >> w;
for(int p = 1;p <= n;p ++){
cin >> t;
a[t] ++;
acc = max(1, p * w / 100);
for(int i = 600;i >= 0;i --){
acc -= a[i];
if(acc <= 0){
cout << i << ' ';
break;
}
}
}
}

T3:表达式


这个题确实有点难,不妨考虑先用栈把表达式转换为一棵树,再来把每个叶节点的值求出来,如果这个叶节点的值会影响整个树的值,那么把原有的结果取反。

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
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
char str[N], ch[N];
int n, x[N], son[N][2], m, book[N], s;
stack<int> q;
int dfs1(int u) {
if(u <= n) return x[u];
if(ch[u] == '!') return x[u]=!dfs1(son[u][0]);
else if(ch[u]=='&') {
x[u] = 1;
x[u] &= dfs1(son[u][0]);
x[u] &= dfs1(son[u][1]);
return x[u];
} else if(ch[u]=='|') {
x[u] = 0;
x[u] |= dfs1(son[u][0]);
x[u] |= dfs1(son[u][1]);
return x[u];
}
}

void dfs2(int u) {
book[u] = 1;
if(u > n) {
if(ch[u]=='!') dfs2(son[u][0]);
else {
if(ch[u] == '&') {
if(x[son[u][0]]) dfs2(son[u][1]);
if(x[son[u][1]]) dfs2(son[u][0]);
}
if(ch[u] == '|') {
if(!x[son[u][0]]) dfs2(son[u][1]);
if(!x[son[u][1]]) dfs2(son[u][0]);
}
}
}
}

int main() {
gets(str);
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &x[i]);
int len = strlen(str);
m = n;
for(int i = 0; i < len; i ++) {
if(str[i] == 'x') {
i ++;
int t = 0;
while(str[i] != ' ') {
t = t * 10 + str[i] - '0';
i++;
}
q.push(t);
} else if(str[i] == '|' || str[i] == '&') {
int t1 = q.top();
q.pop();
int t2 = q.top();
q.pop();
m ++;
son[m][0] = t1;
son[m][1] = t2;
q.push(m);
ch[m] = str[i];
} else if(str[i] == '!') {
int t = q.top();
q.pop();
m ++;
son[m][0] = t;
q.push(m);
ch[m] = str[i];
}
}
int root = q.top();
int res = dfs1(root);
dfs2(root);
scanf("%d", &s);
for(int i = 1; i <= s; i ++) {
int k;
cin >> k;
if(!book[k]) printf("%d\n",res);
else printf("%d\n",res^1);
}

return 0;
}

T4:方格取数

直接考虑蛇形走法,然后很容易的就能推出式子

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005;
LL dp[N][N];
int n, m, w[N][N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin >> w[i][j];
}
}
memset(dp, -0x3f3f3f3f, sizeof(dp));
dp[1][0] = 0;
for(int j = 1;j <= m;j ++){
LL s = -0x3f3f3f3f;
for(int i = 1;i <= n;i ++){
s = max(dp[i][j-1], s) + w[i][j];
dp[i][j] = max(s, dp[i][j]);
}
s = -0x3f3f3f3f;
for(int i = n;i >= 1;i --){
s = max(dp[i][j-1], s) + w[i][j];
dp[i][j] = max(s, dp[i][j]);
}
}
cout << dp[n][m];
return 0;
}

评论