SRM630DIV2_html/css_WEB-ITnose

第一次TC，本来以为AK了，结果1000分还是被系统cha掉了，不过倒是也cha掉了房间其他人赚了不少

A：字符串长度才50，直接简单的模拟即可
B：结点个数才10，先做一边floyd，找出两两之间路径，然后暴力枚举选哪些点，判断可不可以，如果可以的话，记录下最大个数
C：一开始的做法是，构造出rank数组后，对于连续的一段，都放a，然后最后一个放b即可，以为这样构造出来的肯定是字典序最小的，结果被系统cha掉了。
正确做法：一开始先构造出sa数组，暴力枚举每个位置，非'a'的，只要减1，保证字典序小了，在去构造一下sa数组，判断一下两个后缀数组一不一样，如果所有位置都不一样，说明这个是字典序最小的

代码：

A:

#include #include #include #include #include #include 

#include #include #include #include #include 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 a, vector b, vector 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<

#include #include #include #include using namespace std;typedef pair 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";    }};