noip2021训练5
Link
SDOI2010 地精部落
法一：
首先有两个性质
- 在一个波动序列中，若 \(i\) 和 \(j\) 不相邻，那么交换 \(i,j\) 后依然是一个波动序列。
- 把波动序列中的 \(a_i\) 都改为 \(n+1-a_i\)，还是一个波动序列，且山峰与山谷相反。
设 \(f_{i,j}\) 表示选 \([1,i]\) 这些数，第一个为山峰且为 \(j\) 的方案数（山谷与山峰的方案数是一样的）
转移 \(f_{i,j}=f_{i,j-1}+f_{i-1,i-j+1}\)
若 \(j\) 与 \(j-1\) 不相邻（\(j\) 表示的是数而不是位置），交换后仍是合法的，所以是 \(f_{i,j-1}\)。
若 \(j\) 与 \(j-1\) 相邻，因为第一个数 \(j\) 为山峰，所以 \(j-1\) 必为山谷，此时确定了第一个为 \(j\)，所以一共选了 \(i-1\) 个数，根据性质二，\(j-1\) 为山谷的方案数数与 \((i-1)+1-(j-1)\) 为山峰的方案数是相同的，所以是 \(f_{i-1,i-j+1}\)
最后答案为 \(\sum_{i=1}^nf_{n,i}\)
转移时可以用滚动数组优化一下空间
法二：
设 \(f_{i,0/1}\) 分别表示长度为 \(i\) 且第一位为山峰/山谷的方案数。
转移时可以按最大的数分成两半，然后将两边的方案数乘起来，再乘上一个组合数。
因为最大的数必定是山峰，与它相邻的必定是山谷，所以根据其位置 \(j\) 的奇偶性，可以得到前面一段的第一位为山峰还是山谷，同理可得后面一段的。
然后就可以转移了。
其中组合数为在 \(i-1\) 个数中选 \(j\) 个放在前面，也就是 \(C_{i-1}^j\)。
Code
#include
#include
#define ll long long
using namespace std;
const int N = 4210;
int n, p;
int f[N][2], C[N][N];
int main()
{
ios :: sync_with_stdio(false);
cin >> n >> p;
f[0][0] = f[0][1] = 1;
f[1][0] = f[1][1] = 1;
for(int i = 0; i <= n; i++)
{
C[i][0] = 1;
for(int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
}
for(int i = 2; i <= n; i++)
{
for(int j = 0; j < i; j++)
{
if(j & 1) f[i][1] = (f[i][1] + (ll)C[i - 1][j] * f[j][1] % p * f[i - 1 - j][0] % p) % p;
else f[i][0] = (f[i][0] + (ll)C[i - 1][j] * f[j][0] % p * f[i - 1 - j][0] % p) % p;
}
}
cout << (f[n][0] + f[n][1]) % p << endl;
return 0;
}
// A.S.
HAOI2010 软件安装
首先不难想到缩点，因为环内的点必须全选才能产生贡献
由于一个软件最多依赖另外一个软件，所以得到了一棵树，然后就是树上背包板子了
要保证选了父亲才能选其儿子
我写的 \(O(n^3)\) 的
不过这种题好像可以处理出 dfs 序，然后就可以 \(O(n^2)\) dp 了？
Code
#include
#define pb push_back
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 110;
const int M = 510;
int n, m, a[N], b[N], fa[N];
vector g[N];
vector G[N];
int dfn[N], low[N], tim;
bool vis[N];
int stk[N], top, cnt, id[N];
int val[N], deg[N], w[N], v[N];
void tarjan(int u)
{
dfn[u] = low[u] = ++tim;
stk[++top] = u;
vis[u] = 1;
for(auto v : g[u])
{
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
int x; cnt++;
do {
x = stk[top--];
w[cnt] += a[x];
v[cnt] += b[x];
id[x] = cnt;
vis[x] = 0;
} while(x != u);
}
return;
}
int f[N][M];
void dfs(int u)
{
for(int i = w[u]; i <= m; i++)
f[u][i] = v[u];
for(auto v : G[u])
{
dfs(v);
for(int i = m; i >= w[v]; i--)
for(int j = 0; j <= i - w[u]; j++)
f[u][i] = max(f[u][i], f[u][i - j] + f[v][j]);
}
return;
}
int main()
{
read(n), read(m);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1; i <= n; i++) read(b[i]);
for(int i = 1; i <= n; i++) read(fa[i]), g[fa[i]].pb(i);
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++)
for(auto j : g[i])
if(id[i] != id[j])
G[id[i]].pb(id[j]), deg[id[j]]++;
for(int i = 1; i <= cnt; i++)
if(!deg[i]) G[0].pb(i);
dfs(0);
write(f[0][m]), putchar('\n');
return 0;
}
// A.S.
BJWC2012 冻结
分层图最短路板子
一定要注意边的数量，算不清就开大点！！！
Code
#include
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 2600;
const int M = 2e5;
int n, m, k;
struct edge
{
int v, w, nxt;
} e[M];
int head[N], tot;
void link(int u, int v, int w)
{
e[++tot] = (edge) {v, w, head[u]};
head[u] = tot;
}
queue que;
int dis[N];
bool vis[N];
void spfa()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
que.push(1), vis[1] = 1;
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = 0;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(dis[v] > dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
if(!vis[v]) que.push(v), vis[v] = 1;
}
}
}
return;
}
int main()
{
read(n), read(m), read(k);
for(int i = 1, u, v, w; i <= m; i++)
{
read(u), read(v), read(w);
for(int j = 0; j <= k + 1; j++)
{
int x = u + j * n, y = v + j * n;
link(x, y, w), link(y, x, w);
link(x, y + n, w >> 1), link(y, x + n, w >> 1);
}
}
spfa();
int ans = 1e9;
for(int i = 1; i <= k + 1; i++)
ans = min(ans, dis[i * n]);
write(ans), putchar('\n');
return 0;
}
// A.S.
SDOI2012 Longge 的问题
经典数学题
求 \(\sum_{i=1}^n\gcd(i,n)\)
考虑对于每个 \(\gcd\) 有几个 \(i\)，统计贡献。
设 \(cnt(x)\) 表示 \([1,n]\) 中与 \(n\) 的最大公因数为 \(x\) 的数的个数
\[cnt(x)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^{\left\lfloor \frac{n}{x}\right\rfloor}[\gcd(i,\left\lfloor \frac{n}{x}\right\rfloor)=1] \]我们发现 \(cnt(x)=\phi(\left\lfloor \frac{n}{x}\right\rfloor)\)
所以原式可以化简为
\[\sum_{i=1}^n=\sum_{d|n}d\sum_{i=1}^n[\gcd(i,n)=d]=\sum_{d|n}d\times\phi(\left\lfloor \frac{n}{d}\right\rfloor) \]然后 \(O(\sqrt{n})\) 枚举 \(d\)，\(O(\sqrt{n})\) 单点求 phi就可以了。
Code
#include
#define int long long
using namespace std;
int phi(int x)
{
int res = x;
for(int i = 2; i * i <= x; i++)
{
if(x % i == 0)
{
res = res / i * (i - 1);
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x - 1);
return res;
}
signed main()
{
int n, ans = 0;
scanf("%lld", &n);
for(int i = 1; i * i <= n; i++)
{
if(n % i == 0)
{
ans += i * phi(n / i);
if(n / i != i) ans += n / i * phi(i);
}
}
printf("%lld\n", ans);
return 0;
}
// A.S.
NOI2015 程序自动分析
并查集开两倍，分别表示是否相等
Code
#include
#include
#include
#include
using namespace std;
const int N=1e6+10;
struct node
{
int x,y,e;
}a[N];
int num[N<<1],cnt;
int f[N];
int Find(int a)
{
return f[a]==a?a:f[a]=Find(f[a]);
}
bool cmp(node A,node B)
{
return A.e>B.e;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n*2;i++) f[i]=i;
cnt=-1;
memset(num,0,sizeof(num));
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
num[++cnt]=a[i].x;
num[++cnt]=a[i].y;
}
sort(num,num+cnt);
int tot=unique(num+1,num+1+cnt)-num;
for(int i=1;i<=n;i++)
{
a[i].x=lower_bound(num,num+tot,a[i].x)-num;
a[i].y=lower_bound(num,num+tot,a[i].y)-num;
}
for(int i=1;i<=n;i++) f[i]=i;
sort(a+1,a+1+n,cmp);
int flag=0;
for(int i=1;i<=n;i++)
{
int fx=Find(a[i].x),fy=Find(a[i].y);
if(a[i].e==1) f[fx]=fy;
else if(fx==fy) {flag=1;break;}
}
if(!flag) puts("YES");
else puts("NO");
}
return 0;
}
// A.S.
JSOI2008 最小生成树计数
首先有一个性质：不同的最小生成树中权值相同的边的个数是相同的（比较显然？）
因为 具有相同权值的边不会超过10条，所以可以直接暴力。
先求出最小生成树中每个权值有几条边。
处理出权值相同的边，排序后存一下同一个权值的左右端点，对可以构成生成树的边进行乘法原理即可。
使用搜索，并随时判断是否出现了环。
Code
#include
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 110;
const int M = 1010;
const int p = 31011;
int n, m, cnt;
struct edge
{
int u, v, w;
friend bool operator < (edge x, edge y)
{
return x.w < y.w;
}
} e[M];
struct node
{
int l, r, num;
} a[M];
int f[N];
void init()
{
for(int i = 1; i <= n; i++) f[i] = i;
}
int Find(int a)
{
return f[a] == a ? a : Find(f[a]);
}
int sum;
void dfs(int id, int now, int k)
{
if(now == a[id].r + 1)
{
if(k == a[id].num) sum++;
return;
}
int x = Find(e[now].u), y = Find(e[now].v);
if(x != y)
{
f[x] = y;
dfs(id, now + 1, k + 1);
f[x] = x, f[y] = y;
}
dfs(id, now + 1, k);
}
int main()
{
read(n), read(m);
for(int i = 1; i <= m; i++)
read(e[i].u), read(e[i].v), read(e[i].w);
sort(e + 1, e + 1 + m);
init();
int tot = 0;
for(int i = 1; i <= m; i++)
{
if(e[i].w != e[i - 1].w) cnt++, a[cnt - 1].r = i - 1, a[cnt].l = i;
int x = Find(e[i].u), y = Find(e[i].v);
if(x != y) f[x] = y, a[cnt].num++, tot++;
}
a[cnt].r = m;
if(tot != n - 1)
{
puts("0");
return 0;
}
init();
int ans = 1;
for(int i = 1; i <= cnt; i++)
{
sum = 0;
dfs(i, a[i].l, 0);
ans = ans * sum % p;
for(int j = a[i].l; j <= a[i].r; j++)
{
int x = Find(e[j].u), y = Find(e[j].v);
if(x != y) f[x] = y;
}
}
write(ans), putchar('\n');
return 0;
}
// A.S.
HEOI2014 南园满地堆轻絮
使得最大值最小，肯定要二分答案
考虑如何 chk，贪心的想，因为要使序列不下降，所以要尽量让前面的更小，所以就很好写了。
复杂度 \(O(n\log n)\)
Code
#include
#define int long long
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 5e6 + 5;
int n, sa, sb, sc, sd, a[N], mod;
int b[N];
int F(int x)
{
return (sa * x % mod * x % mod * x % mod + sb * x % mod * x % mod + sc * x % mod + sd) % mod;
}
bool chk(int x)
{
memcpy(a, b, sizeof(b));
a[1] -= x;
for(int i = 2; i <= n; i++)
{
if(a[i - 1] <= a[i]) a[i] = max(a[i] - x, a[i - 1]);
else if(a[i - 1] - a[i] > x) return false;
else a[i] = a[i - 1];
}
return true;
}
signed main()
{
read(n), read(sa), read(sb), read(sc), read(sd), read(a[1]), read(mod);
for(int i = 2; i <= n; i++)
a[i] = (F(a[i - 1]) + F(a[i - 2])) % mod;
memcpy(b, a, sizeof(a));
int l = 1, r = mod, ans;
while(l <= r)
{
int mid = (l + r) >> 1;
if(chk(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
write(ans), putchar('\n');
return 0;
}
// A.S.
HNOI2012 矿场搭建
首先，如果有割点，那么两边的点肯定要分开讨论，这里把两边的点定义为“组”。
下面进行分类讨论：
- 如果该组内没有割点，那么至少设置两个出口
- 如果有一个割点，那么只需要设置一个。因为如果不是割点坍塌，可以走出去
- 如果有两个割点，就不需要设置，因为不管哪个坍塌，都可以走出去
方案数直接乘法原理就行了。
Code
#include
#define ll long long
#define pb push_back
using namespace std;
namespace IO
{
template
inline bool read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return x;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 510;
int n, m, Case;
vector g[N];
int dfn[N], low[N], tim, vis[N];
bool cut[N];
void tarjan(int u, int s)
{
int ch = 0;
dfn[u] = low[u] = ++tim;
vis[u] = 1;
for(auto v : g[u])
{
if(!dfn[v])
{
tarjan(v, s);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u] && u != s) cut[u] = 1;
if(u == s) ch++;
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(u == s && ch >= 2) cut[u] = 1;
return;
}
ll ans, tot;
int id, num, cnt;
void dfs(int u)
{
vis[u] = id;
num++;
for(auto v : g[u])
{
if(cut[v] && vis[v] != id)
cnt++, vis[v] = id;
if(!vis[v]) dfs(v);
}
return;
}
void Clear()
{
tim = 0, id = 0;
ans = 0, tot = 1;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(vis, 0, sizeof(vis));
memset(cut, 0, sizeof(cut));
for(int i = 1; i <= n; i++) g[i].clear();
n = 0;
}
int main()
{
while(read(m))
{
Clear();
for(int i = 1, u, v; i <= m; i++)
{
read(u), read(v);
g[u].pb(v), g[v].pb(u);
n = max(n, max(u, v));
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i, i);
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++)
{
if(vis[i] || cut[i]) continue;
id++, num = 0, cnt = 0;
dfs(i);
if(!cnt) ans += 2, tot *= (ll)num * (num - 1) / 2;
else if(cnt == 1) ans++, tot *= (ll)num;
}
printf("Case %d: ", ++Case);
write(ans), putchar(' ');
write(tot), putchar('\n');
}
return 0;
}
// A.S.
Luogu P4198 楼房重建
见第一题
JOISC 2014 Day1 有趣的家庭菜园
树状数组+贪心
网上搜了一下，发现大部分题解是从小到大处理的，但是这样遇到相同的高度会很麻烦，所以这里从大到小进行计算。
对于第 \(i\) 株植物，因为我们从大到小枚举，所以在 \(i\) 前面的都是 \(>h_i\) 的，我们需要将 \(i\) 移动到最旁边，要么到左边，要么到右边。
发现可以用树状数组维护前缀和，能直接查询到左边需要交换几次，到右边的次数就是前面植物的个数减去到左边的次数。
对于高度相同的，要取出来后同统一查询答案，然后再统一插入树状数组，因为两边有高度相同也是合法的。
答案就是每株植物到两边的较小次数的和。
Code
#include
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 3e5 + 5;
int n;
struct node
{
int val, id;
friend bool operator < (node x, node y)
{
return x.val > y.val;
}
} a[N];
int c[N];
void add(int x, int y)
{
for(; x <= n; x += x & -x)
c[x] += y;
}
int qry(int x)
{
int res = 0;
for(; x; x -= x & -x)
res += c[x];
return res;
}
int main()
{
read(n);
for(int i = 1; i <= n; i++)
read(a[i].val), a[i].id = i;
sort(a + 1, a + 1 + n);
long long ans = 0;
for(int i = 1, pos = 1; i <= n; i++)
{
if(a[i].val != a[i - 1].val)
for(; pos < i; pos++)
add(a[pos].id, 1);
int pre = qry(a[i].id);
ans += min(pre, pos - 1 - pre);
}
write(ans), putchar('\n');
return 0;
}
// A.S.
APIO2009 采油区域
神奇的 dp
dp 本身并不难，难在思路
因为要选 \(3\) 块，所以直接 dp 并不好做，考虑分别算出 \(3\) 块，将它们拼起来。
对于 \(n\times m\) 的矩形，处理出四个数组，分别表示 \((i,j)\) 左上、右上、左下、右下的 \(k\times k\) 的最大的矩形。
a | b
--|--
c | d
然后分六种情况讨论
- 上中下
- 左中右
- 左上+右上+下
- 左+右上+右下
- 左上+左下+右
- 上+左下+右下
代码看似很毒瘤，实际上都是重复的
还要说一下 luogu 的数据比较水，最好去 bzoj 上交
Code
#include
#include
#include
#define int long long
using namespace std;
const int N = 1510;
int n, m, k, s[N][N];
int a[N][N], b[N][N], c[N][N], d[N][N];
/*
a | b
--|--
c | d
*/
int get_sum(int x, int y)
{
return s[x][y] - s[x - k][y] - s[x][y - k] + s[x - k][y - k];
}
void calc()
{
for(int i = k; i <= n; i++)
for(int j = k; j <= m; j++)
a[i][j] = max(get_sum(i, j), max(a[i - 1][j], a[i][j - 1]));
for(int i = k; i <= n; i++)
for(int j = m - k + 1; j >= 1; j--)
b[i][j] = max(get_sum(i, j + k - 1), max(b[i - 1][j], b[i][j + 1]));
for(int i = n - k + 1; i >= 1; i--)
for(int j = k; j <= m; j++)
c[i][j] = max(get_sum(i + k - 1, j), max(c[i + 1][j], c[i][j - 1]));
for(int i = n - k + 1; i >= 1; i--)
for(int j = m - k + 1; j >= 1; j--)
d[i][j] = max(get_sum(i + k - 1, j + k - 1), max(d[i + 1][j], d[i][j + 1]));
}
int rd()
{
int x = 0;
char c = getchar();
while(!isdigit(c)) c = getchar(), cout << c << endl;
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
return x;
}
signed main()
{
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%lld", &s[i][j]), s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
calc();
int ans = 0;
for(int i = k; i <= n; i++)
for(int j = k; j <= m; j++)
{
ans = max(ans, b[i - k][1] + get_sum(i, j) + d[i + 1][1]);
ans = max(ans, c[1][j - k] + get_sum(i, j) + d[1][j + 1]);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
ans = max(ans, a[i][j] + b[i][j + 1] + c[i + 1][m]);
ans = max(ans, a[n][j] + b[i][j + 1] + d[i + 1][j + 1]);
ans = max(ans, a[i][j] + c[i + 1][j] + b[n][j + 1]);
ans = max(ans, a[i][m] + c[i + 1][j] + d[i + 1][j + 1]);
}
printf("%lld\n", ans);
return 0;
}
// A.S.
JSOI2007 建筑抢修
反悔贪心
对 \(t2\) 按升序排序，对于第 \(i\) 个，如果不能在 \(t2\) 内完成，那么前 \(i\) 个就最多只能修 \(i-1\) 个，贪心的取 \(t1\) 最小的就行了，只需要用堆维护一下。
Code
#include
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 150005;
int n;
struct node
{
int t1, t2;
friend bool operator < (node x, node y)
{
return x.t2 < y.t2;
}
} a[N];
priority_queue que;
int T, ans;
int main()
{
read(n);
for(int i = 1; i <= n; i++)
read(a[i].t1), read(a[i].t2);
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++)
{
if(T + a[i].t1 > a[i].t2)
{
if(a[i].t1 < que.top())
{
T -= que.top();
que.pop();
T += a[i].t1;
que.push(a[i].t1);
}
}
else
{
T += a[i].t1;
que.push(a[i].t1);
ans++;
}
}
write(ans), putchar('\n');
return 0;
}
// A.S.
JSOI2007 文本生成器
AC自动机上 dp
正难则反
用总数减去不合法的，dp 时只需要保证不经过单词的结尾。
设 \(f_{i,j}\) 表示长度为 \(i\)，在AC自动机上走到了 \(j\) 的方案数，转移的时候判一下是不是单词的结尾就行了。
最后答案 \(ans=26^m-\sum_{i=1}^{tot}f_{m,i}\)
Code
#include
#include
#include
#include
using namespace std;
const int N=6010;
const int p=1e4+7;
char s[110];
int trie[N][30],tot,f[110][N];
bool val[N];
void ins(char s[])
{
int len=strlen(s),c=0;
for(int i=0;ique;
int fail[N];
void build()
{
for(int i=0;i<26;i++)
if(trie[0][i]) que.push(trie[0][i]);
while(!que.empty())
{
int c=que.front();
que.pop();
for(int i=0;i<26;i++)
{
if(trie[c][i]) fail[trie[c][i]]=trie[fail[c]][i],val[trie[c][i]]|=val[fail[trie[c][i]]],que.push(trie[c][i]);
else trie[c][i]=trie[fail[c]][i];
}
}
}
int qpow(int a,int b)
{
int res=1;
a%=p;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
ins(s);
}
build();
f[0][0]=1;
for(int i=0;i HNOI2006 超级英雄
二分图最大匹配板子
Code
#include
#include
#include
using namespace std;
const int N = 2010;
int n,m;
vector G[N];
int tim, match[N],t[N],ans[N];
bool dfs(int u)
{
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(t[v] == tim) continue;
t[v] = tim;
if(!match[v] || dfs(match[v]))
{
match[v] = u;
ans[u] = v - m;
return true;
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
G[i].push_back(m + x);
G[i].push_back(m + y);
}
int sum = 0;
tim = 1;
for(int i = 1; i <= m; i++, tim++)
if(dfs(i)) sum++;
else break;
printf("%d\n", sum);
for(int i = 1; i <= sum; i++)
printf("%d\n",ans[i]);
return 0;
}
// A.S.
ZJOI2006 物流运输
观察到 \(n\le 100,m\le 20\)
这不随便写（？但其实还是挺难的
先考虑如何 dp
设 \(f_i\) 表示到第 \(i\) 天的最小花费
转移 \(f_i=min\{f_{j}+g_{j+1,i}\times (i-j)+k\}\)
表示第 \(j\) 天换路线，从 \(j+1\) 到 \(i\) 天不换路线，其中 \(g_{j+1,i}\) 就表示其最小花费，这个是可以 \(O(n^3m)\) 枚举两天并去掉不能走的点，然后 \(O(n\log n)\) 跑最短路预处理的（够暴力吧
Code
#include
#define ll long long
using namespace std;
namespace IO
{
template
inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
return;
}
template
inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 110;
int t, n, k, m, d;
struct edge
{
int v, w, nxt;
} e[N * N];
int head[N], tot;
void link(int u, int v, int w)
{
e[++tot] = (edge) {v, w, head[u]};
head[u] = tot;
}
queue que;
int dis[N];
bool vis[N], flag[N], cl[N][N];
void spfa()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
que.push(1), vis[1] = 1;
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = 0;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(flag[v]) continue;
if(dis[v] > dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
if(!vis[v]) que.push(v), vis[v] = 1;
}
}
}
return;
}
ll g[N][N], f[N];
void dp()
{
for(int i = 1; i <= t; i++)
{
f[i] = g[1][i] * i;
for(int j = 1; j < i; j++)
f[i] = min(f[i], f[j] + g[j + 1][i] * (i - j) + k);
}
return;
}
int main()
{
read(t), read(n), read(k), read(m);
for(int i = 1, u, v, w; i <= m; i++)
{
read(u), read(v), read(w);
link(u, v, w), link(v, u, w);
}
read(d);
for(int i = 1, p, a, b; i <= d; i++)
{
read(p), read(a), read(b);
for(int j = a; j <= b; j++) cl[p][j] = 1;
}
for(int i = 1; i <= t; i++)
for(int j = 1; j <= t; j++)
{
memset(flag, 0, sizeof(flag));
for(int k = 1; k <= n; k++)
for(int p = i; p <= j; p++)
if(cl[k][p]) flag[k] = 1;
spfa();
g[i][j] = dis[n];
}
dp();
write(f[t]);
return 0;
}
// A.S.