题意：给出n个字符串，求满足条件的最大下标值或层数
条件：该字符串之前存在不是 它的子串 的字符串
求解si是不是sj的子串，可以用kmp算法之类的。
strstr是黑科技，比手写的kmp快。if(strstr(s[i], s[j]) == NULL)，则Si不是Sj的子串。
还有一个重要的剪枝：对于一个串，如果当前找到的串是它的母串，则下一次这个串不用遍历。
#include <set> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; #define mem(x,y) memset(x, y, sizeof(x)) #define lson l,m,rt << 1 #define rson m+1,r,rt << 1 | 1 ? a : gcd(b, a % b);} int lcm(int a,int b){return a / gcd(a, b) * b;} int T, n; ][]; ]; int main() { scanf("%d", &T); ; Case <= T; Case++) { mem(vis, ); scanf("%d", &n); getchar(); ; i <= n; i++) { scanf("%s", s[i]); } ; ; i <= n; i++) { ; ; j >= ; j--) { if(vis[j]) continue; if(strstr(s[i], s[j]) == NULL)//sj 不是 si的子串 { ok = ; break; } else { vis[j] = ;//重要剪枝 } } if(ok) ans = i; } printf("Case #%d: %d\n", Case, ans); } ; }
题意：有n个庙经过长时间风吹雨打需要修补，只有两座（被标记为a，b）完好无损不需要修补，有两个和尚轮流去修补这n-2个庙，每个和尚每次只能修补一个庙标记为i，并要求i满足i=j+k或者i=j-k，每个庙只能被修建一次；其中j和k代表已经修建好的庙，Yuwgna先开始，问最后谁不能修建谁输；
更相减损术！（gcd里头：辗转相除法，更相减损术，自行百度）
更相减损术：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。所以它在1-n里头，只要是它的最小公因数的倍数的数都是可以选择的点，所以答案是n / gcd(x, y)主要是由i = j – k联想出来的。
#include <set> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; #define mem(x,y) memset(x, y, sizeof(x)) #define lson l,m,rt << 1 #define rson m+1,r,rt << 1 | 1 ? a : gcd(b, a % b);} int T, n, x, y; int main() { scanf("%d", &T); ; Case <= T; Case++) { scanf("%d%d%d", &n, &x, &y); int g = gcd(x, y); int cnt = n / g; printf("Case #%d: ", Case); printf( ? "Yuwgna" : "Iaka"); } ; }
题意：给你一个n个点，m个集合的图，每个集合中的点都可以以di的距离相互的到达，问你两个人同时从1和n出发，会在那个点相遇。
每个集合内部里的所有的边都是互通的，如果一个个连就要n²了，可以采用增加虚拟结点的方式，来减少点。虚拟一个s，一个e，把他们连接起来。
; i <= m; i++) { int w, num; int s = n + i, e = n + i + m; scanf("%d%d", &w, &num); G[s].push_back(edge(e, w)); while(num--) { int x; scanf("%d", &x); G[e].push_back(edge(x, )); G[x].push_back(edge(s, )); } }
//题意：给你一个n个点，m个集合的图，每个集合中的点都可以以di的距离相互的到达，问你两个人同时从1和n出发，会在那个点相遇。 #include <set> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; #define mem(x,y) memset(x, y, sizeof(x)) #define lson l,m,rt << 1 #define rson m+1,r,rt << 1 | 1 ? a : gcd(b, a % b);} int lcm(int a,int b){return a / gcd(a, b) * b;} int T, n, m, Case; LL ans; ; const LL INF = 1e18; ; LL d1[ssize], d2[ssize]; struct edge { int to; LL co; edge(int tt, LL cc):to(tt), co(cc){} bool operator < (const edge &other)const { return co > other.co; } }; vector<edge>G[ssize]; void init() { ; i <= n + * m; i++) G[i].clear(); ans = INF; } void dijkstra(int s, LL dis[]) { ; i <= n + * m; i++) dis[i] = INF; priority_queue<edge>que; dis[s] = ; que.push(edge(s, dis[s])); while(!que.empty()) { edge p = que.top();que.pop(); int v = p.to; if(dis[v] < p.co) continue; ; i < G[v].size(); i++) { edge e = G[v][i]; if(dis[e.to] > dis[v] + e.co) { dis[e.to] = dis[v] + e.co; que.push(edge(e.to, dis[e.to])); } } } } void solve() { dijkstra(, d1); dijkstra(n, d2); ans = INF; ; i <= n; i++) { ans = min(ans, max(d1[i], d2[i])); } printf("Case #%d: ", Case); if(ans == INF) printf("Evil John\n"); else { printf("%I64d\n", ans); ; ; i <= n; i++) { if(ans == max(d1[i], d2[i])) cnt++; } ; i <= n; i++) { if(ans == max(d1[i], d2[i])) cnt--, printf("%d%c", i, cnt ? ' ' : '\n' ); } } } int main() { scanf("%d", &T); ; Case <= T; Case++) { scanf("%d%d", &n, &m); init(); ; i <= m; i++) { int w, num; int s = n + i, e = n + i + m; scanf("%d%d", &w, &num); G[s].push_back(edge(e, w)); while(num--) { int x; scanf("%d", &x); G[e].push_back(edge(x, )); G[x].push_back(edge(s, )); } } solve(); } ; }
