首页 > 代码库 > SnackDown Online Pre-elimination round A
SnackDown Online Pre-elimination round A
1. 应该n是偶数，就行吧。应该判断1个人，只能出现一次吧。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 8 void yes() {cout << "yes" << endl;} 9 void no() {cout << "no" << endl; }10 int n, c;11 int a[110];12 void solve() {13 memset(a, 0, sizeof a);14 cin >> n >> c;15 int x, y;16 bool tag = 0;17 for (int i = 0; i < c; i++) {18 cin >> x >> y;19 if(a[x] || a[y]) tag = 1;20 a[x] = a[y] = 1;21 }22 if(n % 2 == 1 || tag) no();23 else yes();24 }25 26 int main() {27 // freopen("test.in", "r", stdin);28 //freopen("test.out", "w", stdout);29 ios::sync_with_stdio(0);30 cin.tie(0); cout.tie(0);31 int _;32 cin >> _;33 while(_--)34 solve();35 return 0;36 }
2. 是否是一条蛇，这个浪费了一些时间。
首先#必须组成1个连通分量，多于1个的，肯定是不行的。然后还有其他情况。判断连通分量， dfs或者bfs扫就行。
1个连通分量怎么是一条蛇，我刚开始以为是dfs扫一遍，每一个点的只能有一个前驱和后继，但是这样枚举的复杂度很高，应该会tle。
考虑到只有2行，然后总左到右进行考虑， 每次先考虑上下， 再考虑向右走，然后check，长度是否是#的个数。注意，最左边的点，可能第一个是第一行往下走，或者是第二行往上走，都是可以的。
写的有点丑。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 int n; 8 string s[2]; 9 int c; 10 int cnt; 11 bool vis[2][510]; 12 int dx[] = {0, 0, 1, -1}; 13 int dy[] = {1, -1, 0, 0}; 14 bool check(int x, int y) { 15 if(x >= 0 && x < 2 && y >= 0 && y < n) return 1; 16 return 0; 17 } 18 void dfs(int x, int y) { 19 if(vis[x][y] || s[x][y] == ‘.‘) return; 20 vis[x][y] = 1; 21 cnt++; 22 for (int i = 0; i < 4; i++) { 23 int cx = x + dx[i], cy = y + dy[i]; 24 if(check(cx, cy)) { 25 dfs(cx, cy); 26 } 27 } 28 } 29 void yes() {cout << "yes" << endl; } 30 void no() {cout << "no" << endl; } 31 void solve() { 32 cin >> n; 33 cin >> s[0] >> s[1]; 34 //cout << s[0] << " " << s[1] << endl; 35 c = 0; 36 for (int i = 0; i < n; i++) { 37 if(s[0][i] == ‘#‘) c++; 38 if(s[1][i] == ‘#‘) c++; 39 } 40 int x, y; 41 x = y = -1; 42 for (int j = 0; j < n; j++) { 43 for (int i = 0; i < 2; i++) { 44 if(s[i][j] == ‘#‘) { 45 x = i; y = j; 46 break; 47 } 48 } 49 if(x != -1) break; 50 } 51 cnt = 0; 52 memset(vis, 0, sizeof vis); 53 dfs(x, y); 54 //cout << x << " " << y << endl; 55 //cout << c << " " << cnt << endl; 56 if(cnt != c) { 57 no(); return; 58 } 59 memset(vis, 0, sizeof vis); 60 int dx = x, dy = y; 61 //cout << x << " " << y << endl; 62 while(cnt > 0) { 63 vis[x][y] = 1; 64 cnt--; 65 if(cnt == 0) break; 66 if(s[1 - x][y] == ‘#‘ && !vis[1 - x][y]) { 67 x = 1 - x; 68 } else if(y + 1 < n && s[x][y + 1] == ‘#‘) { 69 y = y + 1; 70 } else { 71 break; 72 73 } 74 } 75 if(cnt == 0) { 76 yes(); return; 77 } 78 cnt = c; 79 //cout << x << " d " << y << endl; 80 x = 1 - dx, y = dy; 81 82 if(s[x][y] != ‘#‘) { 83 no(); return; 84 } 85 memset(vis, 0, sizeof vis); 86 while(cnt > 0) { 87 vis[x][y] = 1; 88 cnt--; 89 if(cnt == 0) break; 90 if(s[1 - x][y] == ‘#‘ && !vis[1 - x][y]) { 91 x = 1 - x; 92 } else if(y + 1 < n && s[x][y + 1] == ‘#‘) { 93 y = y + 1; 94 } else { 95 no(); 96 return; 97 98 } 99 }100 yes();101 }102 103 int main() {104 // freopen("test.in", "r", stdin);105 //freopen("test.out", "w", stdout);106 //ios::sync_with_stdio(0);107 //cin.tie(0); cout.tie(0);108 int _; cin >> _;109 while(_--)110 solve();111 return 0;112 }
3. 这个题目跟资格赛的题目有点像，但是比较难。考虑每个位置的上限是多少，多于这个数，肯定是要必须操作的。
是这样的形式， 1， 2,3 。。。3,2,1， 首先经过这样的缩减。找到必须的操作。 同时又可以观察到，如果第二个数为1， 然后第三个位置的上限就变为2了，而不是3. 这点也很容易想到。每个点只影响左右的点，然后左右的
点，再把这个值传递出去。最后的结果肯定是，没相邻的2个点，最多相差1，而且每个位置的值，都是这个位置可以到达的上限。然后操作，就很简单了，枚举每一个点作为中心， 用所有和减去这个数， 求的最小的需要操作次数，
最后，别忘了加上必须的操作次数。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 8 int n; 9 int a[maxn];10 void solve() {11 scanf("%d", &n);12 ll s = 0;13 for (int i = 1; i <= n; i++) {14 scanf("%d", &a[i]);15 }16 for (int i = 1; i <= n / 2; i++) {17 //cout << i << " " << a[i] << endl;18 //cout << n + 1 - i << " " << a[n + 1 - i] << endl;19 if(a[i] > i) {20 s += a[i] - i;21 a[i] = i;22 }23 if(a[n + 1 - i] > i) {24 s += a[n + 1 - i] - i;25 a[n + 1 - i] = i;26 }27 }28 n++;29 if(n % 2 == 0) {30 if(a[n / 2] > n / 2) {31 s += a[n / 2] - n / 2;32 a[n / 2] = n / 2;33 }34 }35 n--;36 //for (int i = 1; i <= n; i++)37 //cout << i << " ad " << a[i] << endl;38 set<pii> se;39 for (int i = 1; i <= n; i++) {40 se.insert({a[i], i });41 }42 int x, y;43 while(!se.empty()) {44 pii t = *se.begin();45 se.erase(se.begin());46 y = t.first; x = t.second;47 if(x - 1 > 0) {48 if(a[x - 1] > y + 1) {49 se.erase({a[x - 1], x - 1 });50 s += a[x - 1] - y - 1;51 a[x - 1] = y + 1;52 se.insert({a[x - 1], x - 1 });53 }54 }55 if(x + 1 <= n) {56 if(a[x + 1] > y + 1) {57 se.erase({a[x + 1], x + 1 });58 s += a[x + 1] - y - 1;59 a[x + 1] = y + 1;60 se.insert({a[x + 1], x + 1 } );61 }62 }63 }64 //for (int i = 1; i <= n; i++)65 // cout << i << " " << a[i] << endl;66 ll ts = 0;67 for (int i = 1; i <= n; i++)68 ts += a[i];69 ll res = INT_MAX;70 for (int i = 1; i <= n; i++) {71 res = min(res, ts - a[i] * a[i]);72 }73 printf("%lld\n", s + res);74 75 }76 77 int main() {78 //freopen("test.in", "r", stdin);79 //freopen("test.out", "w", stdout);80 int _;81 scanf("%d", &_);82 while(_--)83 solve();84 return 0;85 }
4. 连续的蛇，这个题写出目标方程，很容易简化为就是一个区间求一个点， 使得这些点到目标n个点的差的绝对值和最小。显然是一个二分问题，应该是凹的，但是，是整数上的，所以，用二分很容易做。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 8 int n; 9 ll l, a, b;10 ll s[maxn];11 12 ll work(ll x) {13 ll r = 0;14 for (int i = 0; i < n; i++)15 r += abs(s[i] - x);16 return r;17 }18 void solve() {19 scanf("%d%lld%lld%lld", &n, &l, &a, &b);20 for (int i = 0; i < n; i++) {21 scanf("%lld", &s[i]);22 }23 sort(s, s + n);24 for (int i = 0; i < n; i++)25 s[i] -= i * l;26 //sort(s, s + n);27 ll left = a, right = b - n * l;28 ll ta = left, tb = right;29 while(left < right) {30 ll mid = (left + right) / 2;31 ll x1 = work(mid - 1), x2 = work(mid), x3 = work(mid + 1);32 if(x2 <= x1 && x2 <= x3) {33 left = right = mid;34 } else if(x1 <= x2 && x2 <= x3) {35 right = mid - 1;36 } else {37 left = mid + 1;38 }39 //cout << left << " " << right << endl;;40 }41 if(left < ta) left = ta;42 if(left > tb) left = tb;43 printf("%lld\n", work(left));44 45 }46 47 int main() {48 //freopen("test.in", "r", stdin);49 //freopen("test.out", "w", stdout);50 int t;51 scanf("%d", &t);52 while(t--)53 solve();54 return 0;55 }
5. 保卫毒药，就是一个区间问题，注意到一条蛇，只会贡献水平或者垂直二选一，不能同时贡献。 然后先区分水平和垂直的线段， 然后转化为一维问题， 有一些线段， 求使得覆盖目标区间，最少需要多少线段。这个题目应该是比较
简单的吧，排序，然后遍历一般就可以了。 我手残，居然错了好几次。果然以前想的不明白，写的不熟练。
代码写的很丑的。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 8 int n, k, m; 9 int a[maxn][4]; 10 int tleft, tright; 11 bool check(int x, int y, int x1, int y1) { 12 //cout << x << " " << y << " " << x1 << " " << y1 << endl; 13 if(y < x1 || x > y1) return 0; 14 return 1; 15 } 16 int res; 17 bool f1, f2; 18 void work(vector<pii> & v, bool &f) { 19 f = 0; 20 if(v.size() == 0 || v[0].first > tleft) { 21 f = 1; 22 return; 23 } 24 int cur = tleft, r = tleft; 25 int cnt = 0; 26 int x, y; 27 bool in = 0; 28 for (int i = 0; i < v.size(); i++) { 29 x = v[i].first, y = v[i].second; 30 //cout << x << " " << y << " " << cur << " " << r << endl; 31 if(x > r + 1) { 32 f = 0; return; 33 } 34 if(x <= cur) { 35 if(y >= r) { 36 in = 1; 37 r = y; 38 } 39 if(i == v.size() - 1 && in) { 40 cnt++; 41 r++; 42 } 43 } else { 44 cnt++; 45 r++; 46 if(r > tright) break; 47 cur = r; in = 0; 48 i--; 49 } 50 51 } 52 //cnt++; 53 if(r <= tright) f = 1; 54 //cout << "r " << r << endl; 55 //cout << "cnt " << cnt << endl; 56 res += cnt; 57 } 58 void solve() { 59 scanf("%d%d%d", &n, &k, &m); 60 f1 = f2 = 0; 61 for (int i = 0; i < m; i++) { 62 for (int j = 0; j < 4; j++) 63 scanf("%d", &a[i][j]); 64 } 65 res = 0; 66 tleft = (n - k) / 2 + 1; 67 tright = tleft + k - 1; 68 //cout << tleft << " ads " << tright << endl; 69 vector<pii> v1, v2; 70 for (int i = 0; i < m; i++) { 71 int x, y; 72 x = min(a[i][0], a[i][2]); 73 y = max(a[i][0], a[i][2]); 74 if(check(x, y, tleft, tright)) { 75 //cout << x << " c1 " << y << endl; 76 v1.pb({x, y}); 77 } 78 x = min(a[i][1], a[i][3]); 79 y = max(a[i][1], a[i][3]); 80 if(check(x, y, tleft, tright)) { 81 82 v2.pb({x,y}); 83 } 84 } 85 sort(v1.begin(), v1.end()); 86 v1.erase(unique(v1.begin(), v1.end()), v1.end()); 87 sort(v2.begin(), v2.end()); 88 v2.erase(unique(v2.begin(), v2.end()), v2.end()); 89 work(v1, f1); 90 //cout << "asd" <<endl; 91 work(v2, f2); 92 if(f1 || f2) { 93 puts("-1"); 94 } else { 95 printf("%d\n", res); 96 } 97 } 98 99 int main() {100 //freopen("test.in", "r", stdin);101 //freopen("test.out", "w", stdout);102 int _;103 scanf("%d", &_);104 while(_--)105 solve();106 return 0;107 }108
6. 不会做。 后来发现，题目都没有仔细阅读，条件都没想清楚。 有时间看一下别人的题解吧。
Pre-elimination round B。 也开始了，但是round a过了，就不让做b了，我也没有看。就这样吧。
SnackDown Online Pre-elimination round A
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。