首页 > 代码库 > SRM 630 DIV2
SRM 630 DIV2
SRM 630 DIV2
第一次TC,本来以为AK了,结果1000分还是被系统cha掉了,不过倒是也cha掉了房间其他人赚了不少
A:字符串长度才50,直接简单的模拟即可
B:结点个数才10,先做一边floyd,找出两两之间路径,然后暴力枚举选哪些点,判断可不可以,如果可以的话,记录下最大个数
C:一开始的做法是,构造出rank数组后,对于连续的一段,都放a,然后最后一个放b即可,以为这样构造出来的肯定是字典序最小的,结果被系统cha掉了。
正确做法:一开始先构造出sa数组,暴力枚举每个位置,非‘a‘的,只要减1,保证字典序小了,在去构造一下sa数组,判断一下两个后缀数组一不一样,如果所有位置都不一样,说明这个是字典序最小的
代码:
A:
#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <set> #include <map> #include <string> using namespace std; class DoubleLetter { public: string ableToSolve(string S) { while (1) { int n = S.length(); string tmp = ""; int flag = 1; for (int i = 0; i < n - 1; i++) { if (S[i] == S[i + 1]) { flag = 0; for (int j = 0; j < n; j++) { if (j == i || j == i + 1) continue; tmp += S[j]; } break; } } if (flag) break; S = tmp; } if (S == "") return "Possible"; else return "Impossible"; } };
B:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; class Egalitarianism3Easy { public: int bitcount(int x) { int ans = 0; while (x) { ans += (x&1); x >>= 1; } return ans; } int maxCities(int n, vector<int> a, vector<int> b, vector<int> len) { int g[15][15]; for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++) { if (i == j) g[i][j] = 0; else g[i][j] = 1000000000; } for (int i = 0; i < n - 1; i++) g[a[i]][b[i]] = g[b[i]][a[i]] = len[i]; for (int k = 1; k <= n; k++) { for (int i = 1 ; i <= n; i++) { for (int j = 1; j <= n; j++) { g[i][j] = min(g[i][j], g[i][k] + g[k][j]); } } } int tmp[15], tn; int ans = 1; for (int i = 1; i < (1<<n); i++) { tn = 0; for (int j = 0; j < n; j++) { if (i&(1<<j)) { tmp[tn++] = j + 1; } } int ss = -1; int flag = 0; for (int j = 0; j < tn; j++) { for (int k = j + 1; k < tn; k++) { if (ss == -1) ss = g[tmp[j]][tmp[k]]; else { if (ss != g[tmp[j]][tmp[k]]) { flag = 1; break; } } } if (flag) break; } if (flag == 0) ans = max(ans, bitcount(i)); } return ans; } };
C:
#include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; typedef pair<string, int> pii; class SuffixArrayDiv2 { public: string smallerOne(string s) { int n = s.length(); pii save[55]; for (int i = n - 1; i >= 0; i--) { string tmp = ""; for (int j = i; j < n; j++) tmp += s[j]; save[i].first = tmp; save[i].second = i; } sort(save, save + n); for (int t = 0; t < n; t++) { if (s[t] == 'a') continue; string ss = s; ss[t]--; pii sav[55]; for (int i = n - 1; i >= 0; i--) { string tmp = ""; for (int j = i; j < n; j++) tmp += ss[j]; sav[i].first = tmp; sav[i].second = i; } sort(sav, sav + n); int k = 0; for (; k < n; k++) if (save[k].second != sav[k].second) break; if (k == n) return "Exists"; } return "Does not exist"; } };
SRM 630 DIV2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。