SRM 630 DIV2_html/css_WEB-ITnose

SRM 630 DIV2

The first time I tried TC, I thought I had AK, but the 1000 points were still lost by the system, but I also lost the room and other people made a lot of money

A: The length of the string is only 50, you can simply simulate it directly
B: The number of nodes is only 10. First do one floyd to find the path between the two, and then violently enumerate which points to choose to determine whether it is possible. If If possible, record the maximum number
C: The initial approach is to construct the rank array, put a in each consecutive segment, and then put b in the last one, thinking that what is constructed in this way must be a dictionary. The one with the smallest sequence was eventually deleted by the system.
Correct approach: Construct the sa array at the beginning, and violently enumerate each position. If it is not 'a', just subtract 1 to ensure that the lexicographic order is small. Then construct the sa array and judge the two suffix arrays. If all positions are different, it means that this is the smallest dictionary order

Code:

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";    }};