今天被自己写的代码恶心到了……挂出来引以为戒
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 #include <bits/stdc++.h> using namespace std;const int maxn = 105 ;const int maxm = 55 ;char a[maxn][maxm];char result[maxn*maxm];int main () { int n, m; int num = 0 ; int length = 0 ; cin >> n >> m; for (int i=1 ; i<=n; i++) { scanf ("%s" , a[i]); } for (int i=1 ; i<=n; i++) { int k; for (k=i; k<=n; k++) { if (a[k][0 ] != '\0' ) { int j; for (j=0 ; j<m; j++) { if (a[i][j] != a[k][m-j-1 ]) { break ; } } if (j >= m) break ; } } if (k > n) { a[i][0 ] = '\0' ; } else if (k == i) { num++; } else { a[k][0 ] = '\0' ; num = num + 2 ; } } length = m * num; cout << length << endl; int r_num = 0 ; for (int i=1 ; i<=n; i++) { if (a[i][0 ] != '\0' ) { for (int j=0 ; j<m; j++) { result[r_num] = a[i][j]; r_num++; } } } for (int i=0 ; i<r_num; i++) { printf ("%c" , result[i]); } for (int i=0 ; i<r_num; i++) { printf ("%c" , result[r_num-i-1 ]); } return 0 ; }
1304A. Two Rabbits* 没什么好说的,签到题中的签到题,直接上代码。
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;typedef long long ll;ll x, y, a, b; int main () { int t; cin >> t; while (t--) { scanf ("%I64d %I64d %I64d %I64d" , &x, &y, &a, &b); if ((y-x) % (a+b) == 0 ) { ll round = (y-x) / (a+b); printf ("%I64d\n" , round); } else { cout << -1 << endl; } } return 0 ; }
1304B. Longest Palindrome* 其实思路真的挺简单的,就是需要细心。
遍历每个字符串,判断自身是否为palindrome。如果是,将该字符串放在中间;如果不是,那么再遍历后面的字符串,判断是否有一个字符串等于其反串。如果找到了一对,分列两边输出。
注意输出结果中只能有一个自身为palindrome的字符串。同时本题使用string
,并使用其reverse()
方法。
还要注意有好的代码习惯,不要一堆i, j, k
,不然会写得你崩溃。
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 #include <bits/stdc++.h> using namespace std;const int maxn = 105 ;string a[maxn]; string l[maxn]; string r[maxn]; string mid; bool flag[maxn];int left_num = 0 ;int mid_num = 0 ;int main () { memset (flag, true , sizeof (flag)); int n, m; cin >> n >> m; for (int i=0 ; i<n; i++) { cin >> a[i]; } for (int i=0 ; i<n; i++) { if (flag[i] == false ) continue ; string temp = a[i]; reverse (temp.begin (), temp.end ()); if (temp == a[i]) { mid = a[i]; if (mid_num == 0 ) mid_num++; } else { for (int j=i+1 ; j<n; j++) { if (flag[j] != false && a[j] == temp) { l[left_num] = a[i]; r[left_num] = a[j]; left_num++; flag[j] = false ; break ; } } } flag[i] = false ; } cout << left_num * 2 * m + mid_num * m << endl; for (int i=0 ; i<left_num; i++) { cout << l[i]; } if (mid_num == 1 ) cout << mid; for (int k=0 ; k<left_num; k++) { cout << r[left_num - k - 1 ]; } cout << endl; return 0 ; }
1304C. Air Conditioner* 实际上是一个比较简单的贪心算法。
假设当前时刻温度的最大值为$big$,最小值为$small$。则经过$k$分钟后,温度的最大值为$big+k$,最小值为$small-k$。若此时温度的范围与当前时刻来的客人的温度范围有交集,则说明此时仍可满足条件,否则不满足条件。若满足条件,求取当前时刻温度的最大范围,即$big = min(big, h[i])$,$small = max(small, l[i])$。
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 #include <bits/stdc++.h> using namespace std;typedef long long ll;const int maxn = 105 ;ll t[maxn]; ll l[maxn]; ll h[maxn]; int main () { int q; cin >> q; while (q--) { int n; ll m; cin >> n >> m; for (int i=1 ; i<=n; i++) cin >> t[i] >> l[i] >> h[i]; ll big = m; ll small = m; ll pre_time = 0 ; bool flag = true ; for (int i=1 ; i<=n; i++) { big = big + t[i] - pre_time; small = small - (t[i] - pre_time); if (big < l[i] || small > h[i]) { flag = false ; break ; } pre_time = t[i]; if (big > h[i]) big = h[i]; if (small < l[i]) small = l[i]; } if (flag == false ) cout << "NO" << endl; else cout << "YES" << endl; } return 0 ; }
1304D. Shortest and Longest LIS** 题意即找到从$1$到$n$的两组排列。第一组排列要求其LIS的长度最小,第二组排列要求其LIS的长度最大。并要求得出的排列满足题中所给的相邻两数间的大小关系。
先介绍一下LIS。Longest increasing subsequence (LIS)就是指一个序列的满足下列条件的子序列:序列中的元素为升序,且尽可能长。这个子序列不要求连续,也不要求唯一。
Shortest LIS
让序列在整体上看为递减的即可。首先将所有连续递增的部分分组,并设这些组的最大的大小为$m$,则LIS的长度不可能小于$m$。当我们构造这个序列使得LIS的长度等于$m$时,即为所求。
构造方法就是让序列整体上看为递减的即可。
Longest LIS
让序列在整体上看为递增的即可。这样所有连续递增的部分可以可以在LIS中,每个连续递减的部分都会有一个元素在LIS中。
题解中还留下了一个有意思的问题,怎么使得LIS的长度等于$k$?
我的思路是首先分类。设所有连续递增部分的长度和为$h$,分为$h<=k$和$h>k$两类情况讨论。具体实现以后再来填坑(挖坑*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 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 #include <bits/stdc++.h> using namespace std;const int maxn = 2 *1e5 + 5 ;int result[maxn];int main () { int t; cin >> t; while (t--) { memset (result, 0 , sizeof (result)); int n; string s; cin >> n >> s; int pre1 = 0 ; int max_num = n; for (int i=0 ; i<n; i++) { if (s[i] == '>' || i == n-1 ) { for (int j=i; j>=pre1; j--) { result[j] = max_num; max_num--; } pre1 = i+1 ; } } for (int i=0 ; i<n; i++) cout << result[i] << " " ; cout << '\n' ; int pre2 = 0 ; int min_num = 1 ; for (int i=0 ; i<n; i++) { if (s[i] == '<' || i == n-1 ) { for (int j=i; j>=pre2; j--) { result[j] = min_num; min_num++; } pre2 = i+1 ; } } for (int i=0 ; i<n; i++) cout << result[i] << " " ; cout << '\n' ; } return 0 ; }
1304E. 1-Trees and Queries
太难了,等我过段时间来补