首页 > 代码库 > SnackDown Online Qualifier 2017
SnackDown Online Qualifier 2017
好久没做题了，然后就想着随便做一个。无奈cf都是晚上，然后就看见这个，随便做做。
资格赛，只要做出来1题就行了，4天的时间。
1. 水题
1 #include <iostream> 2 #include <stdio.h> 3 4 using namespace std; 5 6 int n; 7 string s; 8 void yes() { 9 cout << "Valid" << endl;10 }11 void no() {12 cout << "Invalid" << endl;13 }14 void solve() {15 cin >> n >> s;16 int t = 0;17 for (char c : s) {18 if(c == ‘H‘) {19 if(t == 0) {20 t = 1;21 } else {22 no();23 return;24 }25 } else if(c == ‘T‘) {26 if(t == 1) {27 t = 0;28 } else {29 no();30 return;31 }32 }33 }34 if(t != 0) no();35 else yes();36 }37 38 int main() {39 //freopen("test.in", "r", stdin);40 int _;41 cin >> _;42 while(_--)43 solve();44 return 0;45 }
2. 就是 1， 2,3，。。，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 = 1e2 + 10; 7 8 int n; 9 int a[maxn];10 void yes() {cout << "yes" << endl;}11 void no() {cout << "no" << endl;}12 void solve() {13 cin >> n;14 for (int i = 1; i <= n; i++) cin >> a[i];15 if(n % 2 == 0) {16 no(); return;17 }18 for (int i = 1; i <= n / 2 + 1; i++) {19 if(i != a[i] || a[i] != a[1 + n - i]) {20 no(); return;21 }22 }23 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 }
3. 这个题，我写的很麻烦， 上来先判断线段的类型，有三种，点，水平和垂直，然后每2种进行考虑。
只要一个是点， 就判断这个点是不是在另一个线段上。
2条线段类型相同， 都是水平或者垂直， 这个时候， 必须共线才满足条件，否则不满足。
2条线段类型不同，这个时候，2条线段的有一个端点重合，才是满足的。
就是，上面的这三种情况。
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 type, mx, ma, mb; 8 void work(int x, int y, int a, int b) { 9 type = mx = mb = -1;10 if(x == a && y == b) {11 type = 3;12 ma = x; mb = y;13 return;14 }15 if(x == a) {16 type = 1;17 mx = x;18 ma = min(y, b);19 mb = max(y, b);20 } else {21 type = 2;22 mx = y;23 ma = min(x, a);24 mb = max(x, a);25 }26 }27 void yes() {28 cout << "yes" << endl;29 }30 void no() {31 cout << "no" << endl;32 }33 void solve() {34 int x, y, a, b;35 cin >> x >> y >> a >> b;36 work(x, y, a, b);37 int xt = type, xx = mx, xa = ma, xb = mb;38 cin >> x >> y >> a >> b;39 work(x, y, a, b);40 //cout << xt << " " << type << endl;41 if(xt == type) {42 if(xt == 3) {43 if(xa == ma && xb == mb) {44 yes();45 } else {46 no();47 }48 return;49 }50 if(xx != mx) {51 no();52 return;53 }54 if(xa > mb || ma > xb) {55 no();56 return;57 }58 yes();59 } else {60 if(xt == 3) {61 if((xa == mx && xb >= ma && xb <= mb) || (xb == mx && xa >= ma && xa <= mb)) {62 yes();63 64 } else {65 no();66 }67 return;68 }69 if(type == 3) {70 if((ma == xx && mb >= xa && mb <= xb) || (mb == xx && ma >= xa && ma <= xb)) {71 yes();72 } else no();73 return;74 }75 if((xx == ma || xx == mb) && (mx == xa || mx == xb)) {76 yes();77 return;78 }79 no();80 }81 }82 83 int main() {84 //freopen("test.in", "r", stdin);85 //freopen("test.out", "w", stdout);86 ios::sync_with_stdio(0);87 cin.tie(0); cout.tie(0);88 int _; cin >> _;89 while(_--)90 solve();91 return 0;92 }
4. 大蛇吃小蛇，先从小到大排序，然后对于一次查询，大于等于l的都是满足要求的， 这个是二分， 然后判断剩下的最多能凑成几条蛇。
剩下的能凑成几条，也是判断一种状况， 左边的蛇都被吃掉，右边的蛇变长成l，看需要的个数是否是左边的个数， 这个过程也是二分，然后就完了。
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 int n, q; 8 int a[maxn]; 9 ll s[maxn];10 ll work(int x, int y) {11 return s[y] - s[x - 1];12 }13 void solve() {14 memset(a, 0, sizeof a);15 memset(s, 0, sizeof s);16 scanf("%d%d", &n, &q);17 for (int i = 1; i <= n; i++) {18 scanf("%d", &a[i]);19 //s[i] = s[i - 1] + a[i];20 }21 sort(a + 1, a + n + 1);22 for (int i = 1; i <= n; i++)23 s[i] = s[i - 1] + a[i];24 int k;25 while(q--) {26 scanf("%d", &k);27 int t = lower_bound(a + 1, a + n + 1, k) - a;28 //cout << t <<endl;29 int res = n + 1 - t;30 int left = 1, right = t - 1, ed = t - 1;31 while(left < right) {32 int mid = (left + right) / 2;33 ll st = 1ll * (ed - mid) * k - work(mid + 1, ed);34 //cout << st << " " << mid << endl;35 if(st > mid) {36 left = mid + 1;37 } else right = mid;38 //cout << left << " " << right << " " << mid << endl;39 }40 //cout << left << " " << right << endl;41 if(left == right)42 res += ed - left;43 printf("%d\n", res);44 }45 }46 47 int main() {48 //freopen("test.in", "r", stdin);49 //freopen("test.out", "w", stdout);50 int _;51 scanf("%d", &_);52 while(_--)53 solve();54 return 0;55 }
SnackDown Online Qualifier 2017
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。