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也会报错,因为数据比较大。
原文:https://www.cnblogs.com/nfyyzz/p/13270276.html