#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
bool vis[110];
int main(void) {
memset (vis, false, sizeof (vis));
int n, m; scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
int x; scanf ("%d", &x);
for (int j=1; j<=x; ++j) {
int y; scanf ("%d", &y);
if (!vis[y]) vis[y] = true;
}
}
bool flag = true;
for (int i=1; i<=m; ++i) {
if (!vis[i]) {
flag = false; break;
}
}
if (flag) puts ("YES");
else puts ("NO");
return 0;
}
DFS+DP B - Longtail Hedgehog
题意：找一条递增的链，最后一个点的度数乘链的长度最大。
分析：DFS写搓了，记忆化搜索dp能优化复杂度，也可以直接两个for贪心解决。本以为不会有极端的数据的。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
vector<int> G[N];
int dp[N];
bool vis[N];
int n, m;
int DFS(int u) {
if (dp[u]) return dp[u];
dp[u] = 1;
for (int i=0; i<G[u].size (); ++i) {
int v = G[u][i];
if (v < u) dp[u] = max (dp[u], DFS (v) + 1);
}
return dp[u];
}
ll run(void) {
fill (dp+1, dp+1+n, 0);
ll ret = 0;
for (int i=1; i<=n; ++i) {
ret = max (ret, 1ll * DFS (i) * (int) G[i].size ());
}
return ret;
}
int main(void) {
scanf ("%d%d", &n, &m);
for (int u, v, i=1; i<=m; ++i) {
scanf ("%d%d", &u, &v);
G[u].push_back (v);
G[v].push_back (u);
}
printf ("%I64d
", run ());
return 0;
}
组合数学 D - Multipliers
题意：给定m个质因子p[]，有p[1]*p[2]*...*p[m] == n，问n所有因子的乘积 % 1e9 + 7。
分析：m个质因子可能有重复的，n = p[i] ^ k[i]，k[i]表示p[i]在乘积里贡献了几次，k[i] = (num[i] * (num[i] + 1)) / 2 * (num[j] + 1) (i != j);也就是p[j]可能出现有0,1,2...num[j]。由费马小定理：a ^ x = a ^ (x % (p - 1)) (mod p),k[i]能变形成：(num[i] / 2) * （num[j] + 1)，但是p - 1不是质数，不能用求2的逆元，可以用mod2 = 2 * （1e9 + 7) ???
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int MOD2 = 2ll * (MOD - 1);
int m;
int p[N], num[N];
int pow_mod(int x, ll n, int mod) {
int ret = 1;
while (n) {
if (n & 1) ret = 1ll * ret * x % mod;
x = 1ll * x * x % mod; n >>= 1;
}
return ret;
}
int main(void) {
scanf ("%d", &m);
for (int i=1; i<=m; ++i) {
scanf ("%d", &p[i]);
num[p[i]]++;
}
sort (p+1, p+1+m);
int n = unique (p+1, p+1+m) - p - 1;
int tot = 1;
for (int i=1; i<=n; ++i) {
tot = 1ll * tot * (num[p[i]] + 1) % MOD2;
}
int ans = 1;
for (int i=1; i<=n; ++i) {
ans = 1ll * ans * pow_mod (p[i], 1ll * num[p[i]] * tot / 2, MOD) % MOD;
}
printf ("%d
", ans);
return 0;
}
Trie || KMP C - Running Track
题意：给s和t字符串，问最少的分割t的子串来自s，输出起点和终点
分析：贪心的想法，每次求最长的子串，可以用字典树来查找也可以直接用KMP
Trie
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 2100 + 5;
const int INF = 0x3f3f3f3f;
struct Trie {
int ch[N*N][26], sz;
P pr[N*N];
int idx(char c) {
return c - 'a';
}
void clear(void) {
sz = 1; memset (ch[0], 0, sizeof (ch[0]));
}
void insert(char *str, int from, int dr) {
int u = 0;
for (int c, i=from; i>=0&&str[i]; i+=dr) {
c = idx (str[i]);
if (!ch[u][c]) {
memset (ch[sz], 0, sizeof (ch[sz]));
ch[u][c] = sz++;
}
u = ch[u][c];
pr[u] = make_pair (from, i);
}
}
void query(char *str, vector<P> &vec) {
int u = 0;
for (int c, i=0; str[i]; ++i) {
c = idx (str[i]);
if (!ch[u][c]) {
if (u == 0) {
vec.clear (); return ;
}
vec.push_back (pr[u]); u = 0; i--;
}
else u = ch[u][c];
}
vec.push_back (pr[u]);
}
}trie;
char s[N], t[N];
int main(void) {
scanf ("%s%s", &s, &t);
trie.clear ();
for (int i=0; s[i]; ++i) {
trie.insert (s, i, 1);
trie.insert (s, i, -1);
}
vector<P> ans;
trie.query (t, ans);
if (ans.size () == 0) {
puts ("-1"); return 0;
}
printf ("%d
", (int) ans.size ());
for (int i=0; i<ans.size (); ++i) {
printf ("%d %d
", ans[i].first + 1, ans[i].second + 1);
}
return 0;
}
KMP
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 2100 + 5;
const int INF = 0x3f3f3f3f;
char s[N], rs[N], t[N];
int fail[N];
void get_fail(char *P, int lenp) {
int i = 0, j = -1; fail[0] = -1;
while (i < lenp) {
if (j == -1 || P[j] == P[i]) {
i++; j++; fail[i] = j;
}
else j = fail[j];
}
}
P KMP(char *T, char *P) {
int lent = strlen (T), lenp = strlen (P);
get_fail (P, lenp);
int i = 0, j = 0, max_len = 0, beg = -1;
while (i < lent) {
while (j != -1 && T[i] != P[j]) j = fail[j];
i++; j++;
if (j > max_len) {
max_len = j; beg = i - j;
}
if (j == lenp) break;
}
return make_pair (beg, beg + max_len - 1);
}
bool add_answer(P p1, P p2, vector<P> &ans, int len, int &i) {
P ap = p1, bp = make_pair (len - p2.first - 1, len - p2.second - 1);
int la = p1.second - p1.first, lb = p2.second - p2.first;
if (p1.first == -1) {
if (p2.first == -1) return false;
ans.push_back (bp); i += lb;
}
else if (p2.first == -1) {
if (p1.first == -1) return false;
ans.push_back (ap); i += la;
}
else {
if (la > lb) {
ans.push_back (ap); i += la;
}
else {
ans.push_back (bp); i += lb;
}
}
return true;
}
int main(void) {
scanf ("%s%s", &s, &t);
int lens = strlen (s), lent = strlen (t);
for (int i=0; i<lens; ++i) rs[i] = s[lens-i-1];
vector<P> ans;
for (int i=0; i<lent; ++i) {
P pr1 = KMP (s, t + i);
P pr2 = KMP (rs, t + i);
if (!add_answer (pr1, pr2, ans, lens, i)) {
puts ("-1"); return 0;
}
}
printf ("%d
", (int) ans.size ());
for (int i=0; i<ans.size (); ++i) {
printf ("%d %d
", ans[i].first + 1, ans[i].second + 1);
}
return 0;
}