浙江省赛补
比赛时，我还在一直纠结，5 3这条线为啥不行，结果下来才知道题目不能有重复点没有说，然后fdf说应该是2 7或者 2 5那条线，我也只能通过画图连猜想了。。。
#include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <iostream> using namespace std; int main() { int T; cin >> T; while(T--) { int n; cin >> n; int l = 0, r = n; if(n == 2) { printf("0 2 1 3 "); continue; } for(int i = 1; i < n; i++) { printf("%d %d ", l, r); l++, r++; } printf("%d %d ", n - 1, 3 * n - 2); } return 0; }
这个题就是分各种情况讨论，我可能代码写搓了有点长，导致有一处没考虑到就是
当一个牌是幸运牌排在最前面时，违反正常规则除了花色相同，值大于外，还有花色大于的情况，忘记考虑了。
#include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <iostream> using namespace std; const int maxn = 1e5 + 50; typedef long long ll; struct node { int por; int val; }; node cur[maxn]; int main() { int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d %d", &n, &m); int pos = 0; for(int i = 1; i <= n; i++) { char tmp[2]; scanf("%s", tmp); if(tmp[0] == 'C') { cur[i].por = 0; scanf("%d", &cur[i].val); } if(tmp[0] == 'B') { cur[i].por = 1; scanf("%d", &cur[i].val); } if(tmp[0] == 'D') { cur[i].por = 2; scanf("%d", &cur[i].val); } if(tmp[0] == 'W') { cur[i].por = 4; pos = i; } } int sum = 0; if(n == 1) ///n = 1的情况，全部都可以 { sum = m * 3; } else if(!pos) ///无 W { if((cur[1].por == cur[2].por && cur[1].val > cur[2].val)||(cur[1].por > cur[2].por)) ///第 1 个比其他大，就是幸运的 { sum = 1; } else { sum = 3 * m - n + 1; } } else if(pos == 1) ///有 W 第 1 个就是 W 说明幸运值在第2个之前 { sum = m * (cur[2].por) + cur[2].val - 1; } else if(pos == 2) ///第 2 个是 W,并且是最后一个 那么第 1 个可能是，还是第1个以后所有的 {///W在 2 以后包括2的其他位置 if(n == 2) { sum = m * (3 - cur[1].por) - cur[1].val + 1; } else { sum = m * (cur[pos + 1].por - cur[pos - 1].por) + cur[pos + 1].val - cur[pos - 1].val; } } else { if((cur[1].por == cur[2].por && cur[1].val > cur[2].val)||(cur[1].por > cur[2].por)) ///第 1 个比其他大，就是幸运的 { sum = 1; } else if(pos == n) ///W 在 n位置 { sum = m * (3 - cur[n - 1].por) - cur[n - 1].val; } else /// w 在 3 ~ n - 1 { sum += m * (cur[pos + 1].por - cur[pos - 1].por) + cur[pos + 1].val - 1 - cur[pos - 1].val; } } printf("%d ", sum); } return 0; }
upper_bound()还是比手写二分快，也可能是我优化没加够。
#include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <iostream> #include <map> #include <cmath> using namespace std; const int maxn = 5e5 + 50; typedef long long ll; const ll mod = 1e9; ll sum[31][maxn]; int a[maxn]; int main() { int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); for(int i = 1; i <= 30; i++) { sum[i][0] = 0; for(int j = 1; j <= n; j++) { sum[i][j] = (sum[i][j - 1] + a[j] / i) % mod; } } ll ans = 0; for(int i = 1; i <= m; i++) { ll p; scanf("%lld", &p); int l = 1, cur = 0; ll tmp = p; int res = 1; ll mp = 0; while(1) { if(l > n) break; cur = upper_bound(a + l, a + n + 1, tmp) - a; cur--; mp = (mp + sum[res][cur] + mod - sum[res][l - 1]) % mod; tmp = tmp * p; l = cur + 1; res++; } ans = (ans + (ll)i * mp % mod) % mod; } printf("%lld ", ans); } return 0; }
很难受了，对拍，先测有200组样例，结果tot = 0的时候没有memset,改正以后，又测了150组样例，50组小数据，50组中等数据，50组大数据，全部正确，仍然WA。。。
#include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <iostream> #include <map> #include <cmath> using namespace std; typedef long long ll; const int maxn = 1e3 + 10; char s[maxn]; int v[maxn]; ll dp[maxn][maxn]; vector<int> g; int cnt[maxn]; int main() { freopen("1.txt", "r", stdin); freopen("my.txt", "w", stdout); int T; scanf("%d", &T); while(T--) { g.clear(); int n; scanf("%d", &n); scanf("%s", s + 1); for(int i = 1; i <= n; i++) scanf("%d", &v[i]); for(int i = 1; i <= n; i++) { if(s[i] == ')') g.push_back(i); } memset(cnt, 0, sizeof(cnt)); memset(dp, 0, sizeof(dp)); int tot = g.size(); for(int i = 0; i < tot; i++) { int pos = g[i]; cnt[i] = 0; dp[i][0] = 0; for(int j = pos - 1; j >= 1; j--) { if(s[j] == '(') { cnt[i]++, dp[i][cnt[i]] = dp[i][cnt[i] - 1] + v[pos] * v[j]; } } } // printf("%lld ", dp[0][2]); for(int i = 1; i < tot; i++) { int last = cnt[i - 1]; // printf("%d ", last); ll tmp = -1e18; int dis = g[i] - g[i - 1] - 1; for(int j = cnt[i]; j >= 0; j--) { tmp = max(tmp, dp[i - 1][last]); int len = j >= dis ? dis : j; // printf("len = %d %lld tmp = %lld %lld ",len, dp[i][len], tmp, dp[i][j]); // dp[i][j] += dp[i][len] + tmp; dp[i][j] += tmp; // printf("%lld ", dp[i][j]); last--; } } ll ans = 0; if(tot == 0) { printf("0 "); continue; } for(int j = cnt[tot - 1]; j >= 0; j--) ans = max(ans, dp[tot - 1][j]); printf("%lld ", ans); } return 0; } /* 4 2 (( -7 -3 */