首页 > 其他 > 详细

训练赛后补题 05

时间:2020-07-09 09:12:31      阅读:73      评论:0      收藏:0      [点我收藏+]

2020-06-29 个人训练赛后补题

我真的欠下了好多题啊,唉,F题补得太久了。

QAQ我好菜

废话不多说,下面是题目:

技术分享图片

突然自信JPG……所以,我当时为毛不写?

//////------------写代码ing

……QAQ我还是太天真了,超时了。

以下是我的超时代码

 1 #pragma warning (disable:4996)
 2 #include <iostream>
 3 #include<algorithm>
 4 #pragma warning (disable:4996)
 5 #include <iostream>
 6 #include<algorithm>
 7 #include<stdio.h>
 8 #include<math.h>
 9 #include<string.h>
10 #include<string>
11 #define MAX1 100005            /*1e5 + 5*/
12 #define MAX2 1000000005        /*le9 + 5*/
13 #define MAX3 200005            /*1e5 + 5*/
14 #define MAX4 5005            /*5e3 + 5*/
15 #define MAX5 1005            /*1e3 + 5*/
16 #define T1 27
17 #define T2 27
18 #define T3 18
19 using namespace std;
20 typedef long long int ll;
21 #define MOL 998244353
22 
23 char num1[MAX3], num2[MAX3];
24 int main() {
25     int L1, L2;
26     //左移乘,右移除
27     while (scanf("%d %d", &L1, &L2) != EOF) {
28         scanf("%s %s", num1, num2);
29         //cout << num1 << endl;
30         //cout << num2 << endl;
31         strrev(num1);
32         strrev(num2);
33         int ans[MAX3] = { 0 };
34         int L2y = L2;
35         char* p = num2;
36         int i;
37         while (L2) {
38             if (L1 > L2) {
39                 for (i = 0; i < L2; i++) {
40                     ans[i] += ((p[i] == 1 && num1[i] == 1) ? 1 : 0) - 0;
41                 }
42             }
43             else {
44                 for (i = 0; i < L1; i++) {
45                     ans[i] += ((p[i] == 1 && num1[i] == 1) ? 1 : 0) - 0;
46                 }
47             }
48             //cout << "b:" << p << endl;
49             //"对ans增加s1&s2所代表的的十进制数的值"
50             p = p + 1;
51             L2--;
52             //"之后s2的值变为原来的一半(向下取整)"
53         }
54         int turn2 = 1;
55         int sum = 0;
56         for (int k = 0; k < (L1 > L2y ? L1 : L2y); ++k) {
57             //cout << k << ":" << ans[k] << ":" << sum << endl;
58             sum += ans[k] * turn2 % MOL;
59             sum %= MOL;
60             turn2 *= 2;
61             turn2 %= MOL;
62         }
63         printf("%d\n", sum);
64     }
65     return 0;
66 }

行叭修一修我的代码

//////----------修代码ing

我先简化了一下自己的代码语言逻辑,这样子看起来干净多了【捂脸】

 1 //简化代码语言后的主函数:
 2 int main() {
 3     int L1, L2;
 4     //左移乘,右移除
 5     while (scanf("%d %d", &L1, &L2) != EOF) {
 6         scanf("%s %s", num1, num2);
 7         //cout << num1 << endl;
 8         //cout << num2 << endl;
 9         strrev(num1);
10         strrev(num2);
11         int ans[MAX3] = { 0 };
12         int L2y = L2;
13         char* p = num2;
14         int i;
15         while (L2) {
16             for (i = 0; i < (L1 < L2y ? L1 : L2y); i++) {
17                 if (num1[i] == 1)
18                     ans[i] += (p[i] == 1 ? 1 : 0);
19             }
20             //cout << "b:" << p << endl;
21             //"对ans增加s1&s2所代表的的十进制数的值"
22             p = p + 1;
23             L2--;
24             //"之后s2的值变为原来的一半(向下取整)"
25         }
26         int turn2 = 1;
27         int sum = 0;
28         for (int k = 0; k < (L1 > L2y ? L1 : L2y); ++k) {
29             //cout << k << ":" << ans[k] << ":" << sum << endl;
30             sum += ans[k] * turn2 % MOL;
31             sum %= MOL;
32             turn2 *= 2;
33             turn2 %= MOL;
34         }
35         printf("%d\n", sum);
36     }
37     return 0;
38 }

然后再是思维优化:

①从a的个位起到a第L2位上,与运算要经过L2到1次,但一旦某一次出现结果为0,那么后续次次为零。也就是说只要讨论a某位是1的时候加了b的几个1就行,0不用管。

②a与b的与运算仅涉及公有位数的计算,也就是说以短的一个为基础次数就够了。

优化后就是AC代码了:如下

 1 #pragma warning (disable:4996)
 2 #include <iostream>
 3 #include<algorithm>
 4 #pragma warning (disable:4996)
 5 #include <iostream>
 6 #include<algorithm>
 7 #include<stdio.h>
 8 #include<math.h>
 9 #include<string.h>
10 #include<string>
11 #define MAX1 100005            /*1e5 + 5*/
12 #define MAX2 1000000005        /*le9 + 5*/
13 #define MAX3 200005            /*1e5 + 5*/
14 #define MAX4 5005            /*5e3 + 5*/
15 #define MAX5 1005            /*1e3 + 5*/
16 #define T1 27
17 #define T2 27
18 #define T3 18
19 using namespace std;
20 typedef long long int ll;
21 #define MOL 998244353
22 
23 char num1[MAX3], num2[MAX3];
24 int main() {
25     ll L1, L2;
26     //左移乘,右移除
27     while (scanf("%lld %lld", &L1, &L2) != EOF) {
28         scanf("%s %s", num1, num2);
29         //cout << num1 << endl;
30         //cout << num2 << endl;
31         ll ct = 0;
32         ll num2s[MAX3] = { 0 };
33         for (ll x = 0; x < L2; ++x) {
34             if (num2[x] == 1)ct++;
35             num2s[x] = ct;
36         }
37         strrev(num1);
38         strrev(num2);
39         ll L2y = L2;
40         char* p = num2;
41         ll i, j;
42         ll turn2 = 1;
43         ll sum = 0;
44         for (i = 0; i < (L1 < L2y ? L1 : L2y); ++i) {
45             if (num1[i] == 1) {
46                 sum += num2s[L2-1] * turn2 % MOL;
47                 sum %= MOL;
48             }
49             turn2 *= 2;
50             turn2 %= MOL;
51             L2--;
52         }
53         printf("%lld\n", sum);
54     }
55     return 0;
56 }

不用longlong也会报错,因为数据比较大。

训练赛后补题 05

原文:https://www.cnblogs.com/nfyyzz/p/13270276.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!