两个序列，a序列是一个12n的奇数排列，b是一个12n的偶数排列，如何交换使得a的字典序小于b。
思维题。两种写法，都是很棒的写法。和排序都有关，第一种没有直接排序，但是也有排序的思想。都是利用贪心，缩小了答案的范围。
#includeusing namespace std; #define int long long const int N = 1e5 + 5, mod = 998244353; int a[N], b[N]; struct node { int val, pos; } a1[N], b1[N]; signed main() { int t; cin >> t; a[0] = 1e9 + 7; while(t--) { int n; scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); a[i] = min(a[i], a[i - 1]); } for (int i = 1; i <= n; i++) scanf("%lld", &b[i]); int num = n; int ans = 1e9 + 7; for (int i = 1; i <= n; i++) { while(b[i] > a[num]) num--; ans = min(ans, num + i - 1); } cout << ans << endl; } return 0; }
如果a [ i ] > b [ num ] 的话，那么b [ num ] 之前的数一定无法和 a [ i ] 之后的数进行匹配。
#include(E) Easy Schedulingusing namespace std; #define int long long const int N = 1e5 + 5, mod = 998244353; int b[N]; struct node { int val, pos; bool operator < (const node &k) const { return val < k.val; } } a[N]; signed main() { int t; cin >> t; while(t--) { int n; scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i].val); a[i].pos = i; } for (int i = 1; i <= n; i++) scanf("%lld", &b[i]); sort(a + 1, a + 1 + n); int ans = 1e9 + 7; int num = 1; for (int i = 1; i <= n; i++) { while(a[i].val > b[num]) num++; ans = min(ans, num - 1 + a[i].pos - 1); } cout << ans << endl; } return 0; }
很多时候，尽量的的模拟题意，就能避开大多数wa。
这题就是一颗二叉树，每次最多选择p个节点进入准备，但是一开始只能选1个节点，然后是2,4,8个。但是不能超过p个。所以一个循环模拟就好了。
#include(D) Backspaceusing namespace std; #define int long long const int N = 500 + 5, mod = 998244353; signed main() { int t; cin >> t; while(t--) { int h, p; scanf("%lld%lld", &h, &p); int sum = (long long)pow(2, h) - 1; // cout << sum << endl; int k = 1; int ans = 0; for (int i = 1; k <= p; k *= 2, i++) { sum -= k; ans = i; if (sum <= 0) { // ans = i; break; } } int a1 = ceill(sum * 1.0 / p); cout << a1 + ans << endl; } return 0; }
输入字符是一个一个输入的，如果将其中一个字符替换成删除，那么就相当于原串删除两个字符。
这题倒过来验证t是否为s的子序列就好了，匹配得上，那就继续匹配，匹配不上，那就模拟删除操作，不知道dp怎么写。
#include© Penaltyusing namespace std; #define int long long const int N = 1e5 + 5, mod = 998244353; signed main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while(T--) { string s, t; cin >> s >> t; int lens = s.length(), lent = t.length(); int i = lens, j = lent; bool ck = 0; for (; i >= 0; ) { if (s[i] == t[j]) i--, j--; else i -= 2; if (j < 0) { ck = 1; break; } if (i < 0) break; } if (ck) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
一道回溯的dfs，但是写了好久，搜索的功底太差了。
想法就是遇见一个？就分成两支往下搜索。
有很多个细节没有注意到：
1.dfs和循环嵌套，这样写大大增加了复杂度，应该是阶乘级别的了。
2.两个分支往下的时候，要判断step是奇数还是偶数，奇数才能给a+1，偶数才能给b+1。
3.遇到能停止发球的情况，不能马上return，因为可能还有更优解。
4.形成分支往下搜索的时候，这一次的状态相当于已经确定了，要立即进行判断是否能停止发球，不能等进入下一个状态再进行判断。
#includeusing namespace std; #define int long long const int N = 1e5 + 5, mod = 998244353; int ans; string s; void dfs(int step, int a, int b) { if (step >= 10) { ans = min(ans, step); return; } if (s[step] == '1') { if (step & 1) a++; else b++; } int sa = (10 - step) / 2, sb = (10 - step) / 2; if (step & 1) sb++; if (a + sa < b || b + sb < a) { ans = min(ans, step); // printf("st = %lld, a = %lld, b = %lld, ans = %lldn", step, a, b, ans); // return; } if (s[step] == '?') { if (step & 1) { int sa = (10 - step) / 2, sb = (10 - step) / 2; if (step & 1) sb++; if (a + sa + 1 < b || b + sb < a + 1) { ans = min(ans, step); } dfs(step + 1, a + 1, b); } if ((step & 1) == 0) { dfs(step + 1, a, b + 1); int sa = (10 - step) / 2, sb = (10 - step) / 2; if (step & 1) sb++; if (a + sa < b + 1 || b + sb + 1 < a) { ans = min(ans, step); } } dfs(step + 1, a, b); } else dfs(step + 1, a, b); } signed main() { int T; cin >> T; while(T--) { cin >> s; s = " " + s; ans = 1e9 + 7; dfs(1, 0, 0); cout << ans << endl; } return 0; }
其实还有复杂度更低的O(N)的写法，也很好理解，贪心的将问号单一转为其中一方得分就好了，试两次，取min。
#includeJ. Jeopardy of Dropped Ballsusing namespace std; // 9 19 29 39 #define MAX 10000 int main(){ int T; cin >> T; while(T--){ string s; cin >> s; int A = 10; int B = 10; int scoreA = 0; int scoreB = 0; for(int i = 0; s[i] != ' '; i++){ if(i % 2 == 0){ if(s[i] == '1' || s[i] == '?') scoreA++; } if(i % 2 == 1){ if(s[i] == '1') scoreB++; } if(i % 2 == 0){ if(scoreA + 5 - (i+2)/2 < scoreB || scoreB + 5 - i/2 < scoreA){ A = i+1; break; } } else{ if(scoreA + 5 - (i+1)/2 < scoreB || scoreB + 5 - (i+1)/2 < scoreA){ A = i+1; break; } } } scoreA = 0; scoreB = 0; for(int i = 0; s[i] != ' '; i++){ if(i % 2 == 0){ if(s[i] == '1') scoreA++; } if(i % 2 == 1){ if(s[i] == '1' || s[i] == '?') scoreB++; } if(i % 2 == 0){ if(scoreA + 5 - (i+2)/2 < scoreB || scoreB + 5 - i/2 < scoreA){ B = i+1; break; } } else{ if(scoreA + 5 - (i+1)/2 < scoreB || scoreB + 5 - (i+1)/2 < scoreA){ B = i+1; break; } } } cout << min(A,B) << endl; } }
思路是正确的，用数据结构优化连续的2，来达到提高下落的速度。
但是为什么暴力都不TLE，而我不暴力却一直TLE，想不出来出了什么bug。
贴一下加了并查集的代码。
这题时限两秒，其实暴力模拟是能稳过的。
#includeE. Air Conditionersusing namespace std; #define int long long const int N = 1e3 + 5, mod = 1000000007; int mp[N][N]; int f[N][N]; int getf(int x,int y) { if (f[x][y] == x) return x; return f[x][y] = getf(f[x][y], y); } signed main() { int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%lld", &mp[i][j]); if (mp[i][j] == 2) f[i][j] = i + 1; else f[i][j] = i; } } while (k--) { int i = 1, j; scanf("%lld", &j); while(mp[i][j]) { if (mp[i][j] == 1) { f[i][j] = f[i + 1][j]; mp[i][j] = 2; j = j + 1; } else if (mp[i][j] == 3) { f[i][j] = f[i + 1][j]; mp[i][j] = 2; j = j - 1; } else i = getf(i, j); } printf("%lld ", j); } return 0; }
每个格子的温度其实都是由相邻格子提供；
如果一个点不能更新它的下一个点，那么，它后面的点都不可能会被它更新。
首先把空调的值都放好在对应的pos里。
试想，先考虑空调只能影响其右边的格子，从左往右遍历一遍，不断地取min；
再考虑空调对左边的格子的影响，从右往左遍历一遍。
#includeusing namespace std; #define int long long const int N = 3e5 + 5, INF = 0x3f3f3f3f; int a[N], pos[N]; int f[N]; signed main() { int q; cin >> q; while (q--) { int n, k; scanf("%lld%lld", &n, &k); for (int i = 1; i <= k; i++) scanf("%lld", &pos[i]); for (int i = 0; i <= n + 1; i++) f[i] = INF; for (int i = 1; i <= k; i++) { int x; scanf("%lld", &x); f[pos[i]] = x; } for (int i = 1; i <= n; i++) f[i] = min(f[i], f[i - 1] + 1); for (int i = n; i >= 1; i--) f[i] = min(f[i], f[i + 1] + 1); for (int i = 1; i <= n; i++) printf("%lld ", f[i]); printf("n"); } return 0; }
