给自己搬了4个T并起到了自嗨的效果（：
啊不是吧我连自己搬得“模拟赛”都改不完题！？
A. 【BZOJ3012】First!
对每一个字符串分别考虑，先假设它是最小的，需要满足不能有另一个串是他的前缀，并且把它和所有字符串逐位比较，如果出现不相同的那么当前串的对应字符一定更小然后break，最终建出来图不能有环。
有向图判断环的方法：1.tarjan找到的强连通分量个数==总点数；2.拓扑排序后所有点的入度都减为0.
暴力建图会TTT，正确的建图方式是先建一棵Trie树，对同一层的点连边，恰好满足遇到不同及时结束。
toposort
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e4 + 2;
const int M = 3e5 + 5;
int n, ans;
bool ok[maxn];
string s[maxn];
queue<int> q;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct Trie
{
int tot, ch[M][26], in[26], e[26][26];
bool ed[M];
inline void insert(string x)
{
int u = 1, len = x.size();
for(int i=0; i<len; i++)
{
int v = x[i]-'a';
if(!ch[u][v]) ch[u][v] = ++tot;
u = ch[u][v];
}
ed[u] = 1;
}
inline void toposort()
{
while(!q.empty()) q.pop();
for(int i=0; i<26; i++) if(!in[i]) q.push(i);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int v=0; v<26; v++)
{
if(e[u][v])
{
in[v]--;
if(!in[v]) q.push(v);
}
}
}
}
inline bool check(string x)
{
fill(in, in+26, 0);
memset(e, 0, sizeof(e));
int u = 1, len = x.size();
for(int i=0; i<len; i++)
{
if(ed[u]) return 0;
int v = x[i]-'a';
for(int j=0; j<26; j++)
{
if(j != v && ch[u][j] && !e[v][j])
{
e[v][j] = 1; in[j]++;
}
}
u = ch[u][v];
}
toposort();
for(int i=0; i<26; i++) if(in[i]) return 0;
return 1;
}
}tr;
int main()
{
n = read(); tr.tot = 1;
for(int i=1; i<=n; i++)
{
cin >> s[i];
tr.insert(s[i]);
}
for(int i=1; i<=n; i++)
{
if(tr.check(s[i]))
{
ans++; ok[i] = 1;
}
}
printf("%d\n", ans);
for(int i=1; i<=n; i++)
{
if(ok[i]) cout << s[i] << endl;
}
return 0;
}tarjan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e4 + 2;
const int M = 3e5 + 5;
int n, ans, num, cnt;
bool ok[maxn], vis[26];
string s[maxn];
stack<int> stk;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct Trie
{
int tot, ch[M][26], e[26][26], dfn_c, low[26], dfn[26];
bool ed[M], ext[26];
inline void insert(string x)
{
int u = 1, len = x.size();
for(int i=0; i<len; i++)
{
int v = x[i]-'a';
if(!ch[u][v]) ch[u][v] = ++tot;
u = ch[u][v];
}
ed[u] = 1;
}
inline void tarjan(int x)
{
low[x] = dfn[x] = ++dfn_c;
vis[x] = 1;
stk.push(x);
for(int v=0; v<26; v++)
{
if(!e[x][v]) continue;
if(!dfn[v])
{
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v])
{
low[x] = min(low[x], dfn[v]);
}
}
if(low[x] == dfn[x])
{
cnt++;
int y;
//printf("cnt = %d\n", cnt);
do
{
y = stk.top(); stk.pop();
//printf("%d \n", y);
vis[y] = 0;
}while(y != x);
}
}
inline bool check(string x)
{
fill(ext, ext+26, 0);
fill(dfn, dfn+26, 0); dfn_c = 0;
fill(low, low+26, 0);
fill(vis, vis+26, 0);
memset(e, 0, sizeof(e));
int u = 1, len = x.size();
for(int i=0; i<len; i++)
{
if(ed[u]) return 0;
int v = x[i]-'a';
for(int j=0; j<26; j++)
{
if(j != v && ch[u][j] && !e[v][j])
{
e[v][j] = 1;
ext[v] = ext[j] = 1;
//printf("add %c %c\n", v+'a', j+'a');
//printf("ext[%d] = ext[%d] = 1\n", v, j);
}
}
u = ch[u][v];
}
num = cnt = 0;
for(int i=0; i<26; i++) if(ext[i]) num++;
for(int i=0; i<26; i++)
{
if(ext[i] && !dfn[i]) tarjan(i);
}
//printf("cmp: %d %d\n", num, cnt);
if(num != cnt) return 0;
return 1;
}
}tr;
int main()
{
n = read(); tr.tot = 1;
for(int i=1; i<=n; i++)
{
cin >> s[i];
tr.insert(s[i]);
}
for(int i=1; i<=n; i++)
{
if(tr.check(s[i]))
{
ans++; ok[i] = 1;
}
}
printf("%d\n", ans);
for(int i=1; i<=n; i++)
{
if(ok[i]) cout << s[i] << endl;
}
return 0;
}
B. 庆典
有向图每一次询问查询既满足s可达 i 又满足 i 可达t的 i 的数量，每个询问会加入k<=2条临时的边。所以就有一种暴力的写法是分别从s和t开始两次dfs染色(t走反图)，找到公共点的数量。
但是没有用到一个重要的性质，指向同一个点的两点之间一定有边相连，分析m=n-1的数据发现每个点的入度最多是1，因为不存在环所以至少有一个点没有入度，如果有两个点没有入度的话他们永远无法相遇，所以这是一棵真正的树，s的可达范围就是它的子树，t的(反图)可达范围就是它到根的距离，k=0可以直接dep相减。So I have 36 only.
关于有向图的连通性，先缩点没有影响，得到的有向无环图一定会有一个没有入度的点，这个点可以到达所有点。
所以现在这棵树的形态就像这样：(引用自OUYE2020)
统计每个点可达范围的时候，这些“跨代”的红色边对“子树”和“到根的链”这两种范围都没有用，用拓扑排序把它们去掉(具体就是每个点只留下使它入度减为0的最后一条边)，就变成了和部分分一样的树。
考虑有加边的情况：新的边可能使s拓展了一个新的子树，也可能使t获得了一条新的到根的反路，对子树和到根的链都只记录端点，对属于同一棵子树或同一条反向链的端点去重，本来端点就不可能到达的边不加入，由于k<=2需要存储的内容很少。
我没有图就只好再截一个了：
判断在子树内就用dfn进出的值比较大小就好了，我本来特判树上k=1的数据打算通过多次求LCA来判断这个结果写挂了……
还了解了一下vector区间删除第一个地址是起点，第二个是终点的下一个。
code是鹤的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 4;
int n, m, Q, k, root, f[maxn][22], bl[maxn], u1, v1, u2, v2;
int dfn[maxn], dfn_c, low[maxn], hd[maxn], tl[maxn], IN, fa[maxn];
bool vis[maxn];
vector<int> a, b, G1[maxn], G2[maxn], G[maxn];
int dp[maxn], dep[maxn], du[maxn], siz[maxn], num;
queue<int> q;
stack<int> stk;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void tarjan(int x)
{
low[x] = dfn[x] = ++dfn_c; stk.push(x); vis[x] = 1;
for(int v : G1[x])
{
if(!dfn[v]) tarjan(v), low[x] = min(low[x], low[v]);
else if(vis[v]) low[x] = min(low[x], dfn[v]);
}
if(dfn[x] == low[x])
{
num++; int y;
do
{
y = stk.top(); stk.pop();
bl[y] = num; vis[y] = 0;
}while(y != x);
}
}
void topo()
{
for(int i=1; i<=num; i++) if(!du[i]) root = i, q.push(i);
while(!q.empty())
{
int x = q.front(); q.pop();
for(int v : G2[x])
{
du[v]--;
if(!du[v]) q.push(v), fa[v] = x, G[x].push_back(v);
}
}
}
void dfs(int x)
{
hd[x] = ++IN; f[x][0] = fa[x];
dp[x] = dp[fa[x]] + siz[x], dep[x] = dep[fa[x]] + 1;
for(int i=1; i<20; i++) f[x][i] = f[f[x][i-1]][i-1];
for(int v : G[x]) dfs(v);
tl[x] = IN;
}
int lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
for(int i=19; i>=0; i--) if(dep[f[u][i]] >= dep[v]) u = f[u][i];
if(u == v) return u;
for(int i=19; i>=0; i--)
{
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
}
return f[u][0];
}
void addedge(int u, int v)
{
bool ok = 0;
for(int i=0; i<(int)a.size(); i++)
{
if(hd[u]>=hd[a[i]]&&hd[u]<=tl[a[i]]) ok = 1;
}
if(ok)
{
int h = 0;
for(int i=0; i<(int)a.size()&&h>=0; i++)
{
if(hd[v]>=hd[a[i]]&&hd[v]<=tl[a[i]]) h = -1;
if(h>=0&&hd[a[i]]>hd[v]&&hd[a[i]]<=tl[v]) h = 1, a[i] = v;
}
for(int i=0; i<(int)a.size(); i++)
{
bool ok = 1;
for(int j=0; j<i; j++) if(a[j] == a[i]) ok = 0;
if(!ok) a.erase(a.begin()+i, a.begin()+i+1), i--;
}
if(h == 0) a.push_back(v);
}
ok = 0;
for(int i=0; i<(int)b.size(); i++)
{
if(hd[b[i]]>=hd[v]&&hd[b[i]]<=tl[v]) ok = 1;
}
if(ok)
{
int h = 0;
for(int i=0; i<(int)b.size()&&h==0; i++)
{
if(hd[b[i]]>=hd[u]&&hd[b[i]]<=tl[u]) h = -1;
if(h==0&&hd[u]>hd[b[i]]&&hd[u]<=tl[b[i]]) h = 1, b[i] = u;
}
if(h == 0) b.push_back(u);
}
}
int main()
{
n = read(), m = read(), Q = read(), k = read();
for(int i=1; i<=m; i++)
{
int u = read(), v = read();
G1[u].push_back(v);
}
for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
for(int x=1; x<=n; x++)
{
siz[bl[x]]++;
for(int v : G1[x])
{
if(bl[v] != bl[x])
{
G2[bl[x]].push_back(bl[v]); du[bl[v]]++;
}
}
}
topo(); dfs(root);
while(Q--)
{
int s = read(), t = read();
a.clear(), b.clear(); u1 = v1 = u2 = v2 = 0;
a.push_back(bl[s]), b.push_back(bl[t]);
if(k > 0) u1 = bl[read()], v1 = bl[read()];
if(k > 1) u2 = bl[read()], v2 = bl[read()];
if(u1 == v1) u1 = v1 = 0;
if(u2 == v2) u2 = v2 = 0;
if(u1) addedge(u1, v1);
if(u2) addedge(u2, v2);
if(u1) addedge(u1, v1);
int ans = 0;
for(int i=0; i<(int)a.size(); i++)
{
for(int j=0; j<(int)b.size(); j++)
{
int c = a[i], d = b[j];
if(hd[d]>=hd[c]&&hd[d]<=tl[c])
{
int lc = fa[c], glc;
for(int l=0; l<j; l++)
{
glc = lca(d, b[l]);
if(dep[glc] > dep[lc]) lc = glc;
}
ans += dp[d]-dp[lc];
}
}
}
printf("%d\n", ans);
}
return 0;
}
C.字符串问题
数据点4用hash判断前缀得到 10 pts。
code 10%
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e5 + 5;
int T, na, nb, L, R, m;
ull jc[maxn], h[maxn];
char s[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
T = read();
jc[0] = 1;
for(int i=1; i<=2e5; i++)
{
jc[i] = jc[i-1] * 131;
}
while(T--)
{
scanf("%s", s+1);
int len = strlen(s+1);
for(int i=1; i<=len; i++)
{
h[i] = h[i-1] * 131 + s[i] - 'A';
}
na = read();
assert(na == 1);//针对4
L = read(), R = read();
nb = read();
bool flag = 0;
for(int i=1; i<=nb; i++)
{
int l = read(), r = read();
if(flag) continue;
if(h[r]-h[l-1]*jc[r-l+1] == h[L+r-l]-h[L-1]*jc[r-l+1])
{
flag = 1;
}
}
m = read();
for(int i=1; i<=m; i++) read(), read();
if(flag) printf("-1\n");
else printf("%d\n", R-L+1);
}
return 0;
}
D.选课
重名的题好多啊，差点以为是那个树形dp的……
二进制枚举 15%
//小C你热爱学习？？热爱学分吧……
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 25;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int m, T, n[maxn], s[maxn], w[maxn][maxn], c[maxn][maxn], ch[maxn], gt;
int p, del[maxn][maxn], add[maxn][maxn], id[maxn][maxn], tot;
typedef pair<int, int> pii;
pii pos[maxn];
bool nt[maxn][maxn];
ll sum[maxn], res, sum2, ans=inf;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void check(int num)
{
res = 0; sum2 = 0; gt = 0;
for(int i=1; i<=m; i++) sum[i] = 0;
for(int i=1; i<=tot; i++)
{
if(num & (1<<i-1)) ch[++gt] = i;
}
for(int i=1; i<=gt; i++)
{
pii now = pos[ch[i]];
sum[now.first] += w[now.first][now.second];
sum2 += w[now.first][now.second];
res += c[now.first][now.second];
}
if(sum2 < T) return;
for(int i=1; i<=m; i++)
{
if(sum[i] < s[i]) return;
}
for(int i=1; i<=gt; i++)
{
for(int j=1; j<i; j++)
{
res -= del[ch[i]][ch[j]];
res += add[ch[i]][ch[j]];
if(nt[ch[i]][ch[j]]) return;
}
}
ans = min(ans, res);
}
int main()
{
m = read(); T = read();
for(int i=1; i<=m; i++)
{
n[i] = read(), s[i] = read();
for(int j=1; j<=n[i]; j++)
{
w[i][j] = read(), c[i][j] = read();
id[i][j] = ++tot;
pos[tot] = pii(i, j);
}
}
p = read();
for(int i=1; i<=p; i++)
{
int opt = read();
if(opt == 1)
{
int x1 = read(), y1 = read(), x2 = read(), y2 = read(), c = read();
del[id[x1][y1]][id[x2][y2]] = del[id[x2][y2]][id[x1][y1]] = c;
}
else if(opt == 2)
{
int x1 = read(), y1 = read(), x2 = read(), y2 = read(), c = read();
add[id[x1][y1]][id[x2][y2]] = add[id[x2][y2]][id[x1][y1]] = c;
}
else
{
int x1 = read(), y1 = read(), x2 = read(), y2 = read();
nt[id[x1][y1]][id[x2][y2]] = nt[id[x2][y2]][id[x1][y1]] = 1;
}
}
int mx = 1 << tot;
for(int i=0; i<mx; i++)
{
check(i);
}
printf("%lld\n", ans==inf?-1:ans);
return 0;
}标签：4.5,ch,NOIP,int,long,maxn,hd,&&,模拟 From： https://www.cnblogs.com/Catherine2006/p/16909414.html