P1642 规划
题目描述
某地方有N个工厂，有N-1条路连接它们，且它们两两都可达。每个工厂都有一个产量值和一个污染值。现在工厂要进行规划，拆除其中的M个工厂，使得剩下的工厂依然连成一片且 总产量/总污染 的值最大。
输入输出格式
输入格式：
第一行$N ,M(1<N<100,1<=M<N)$,表示工厂个数和要拆除的个数。
第二行$N$个正整数，表示每个工厂的产值$[1..10000]$
第三行$N$个正整数，表示每个工厂的污染值$[1..10000]$
接着$N-1$行，每行两个正整数$a b(1<=a,b<=N)$表示a,b之间相连。
输出格式：
总产量/总污染 的最大值，保留一位小数。
输入输出样例
输入样例#1：
1 | 3 2 |
输出样例#1：
1 | 4.0 |
solution
很简单的0/1分数规划然后$dp$判断是否可行。
答案是这样的：
$Answer = \frac{\sum{v_i}}{\sum{w_i}}$
对于当前我们二分的答案$k$ ， 我们希望它满足：
$k \leq \frac{\sum{v_i}}{\sum{w_i}}$
移项变形。
$\sum{v_i-kw_i} >= 0$
然后树上背包判断即可。
代码暂时咕咕咕。
P4304 [TJOI2013]攻击装置
题目描述
给定一个01矩阵，其中你可以在0的位置放置攻击装置。 每一个攻击装置（x,y）都可以按照“日”字攻击其周围的8个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1),(x+1,y+2),(x+2,y+1)
求在装置互不攻击的情况下，最多可以放置多少个装置。
输入输出格式
输入格式：
第一行一个整数N，表示矩阵大小为N*N。
接下来N行每一行一个长度N的01串，表示矩阵。
输出格式：
一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 4 |
说明
30%数据$N <= 50$
100%数据 $N<=200$
题解
这道题是这样的。
用$2n$个点来表示棋盘上的有效点（假设$n$个）
如果两个点直接有互相攻击关系，连边。
然后二分图最大独立集。
$O(n\sqrt{n})$
[TJOI2015]弦论
题目描述
为了提高智商,ZJY开始学习弦论。这一天,她在《 String theory》中看到了这样一道问题:对于一个给定的长度为n的字符串,求出它的第k小子串是什么。你能帮帮她吗?
输入输出格式
输入格式：
第一行是一个仅由小写英文字母构成的字符串s
第二行为两个整数t和k,t为0则表示不同位置的相同子串算作一个,t为1则表示不同位置的相同子串算作多个。k的意义见题目描述。
输出格式：
输出数据仅有一行,该行有一个字符串,为第k小的子串。若子串数目不足k个,则输出-1。
输入输出样例
输入样例#1：
1 | aabc |
输出样例#1：
1 | aab |
输入样例#2：
1 | aabc |
输出样例#2：
1 | aa |
输入样例#3：
1 | aabc |
输出样例#3：
1 | -1 |
说明
数据范围
对于10%的数据，$n ≤ 1000$。
对于50%的数据，$t = 0$。
对于100%的数据，$n ≤ 5 × 10^5, t < 2, k ≤ 10^9$。
题解
这是一道二合一
首先说说$SAM$的做法吧（$SAM$好做的多）。
对于那些不是复制而来的节点，如果$t=0$权值就是1，否则就是$Parent~tree$子树和（也就是$Endpos$大小).记为$f_u$
然后再做个$DAWG$上的简单$dp$（最好多开一个数组，我一开始直接加爆炸了）。
设$gu$表示从这个状态$u$为前缀有多少子串。
$g_u = \sum{(u,v) \in DAWG} g_v + f_u$
这样访问他的时候就能轻而易举判断以当前状态为前缀能贡献的子串个数。
最后在$SAM$上运用贪心和分治的思想，就是走这个点有多少个字典序靠前的子串，类似所有树上$k$大值的分治算法，从小的字符转移边开始走，如果$g_u \leq k$ , $k -= g_u$，换字典序+1的字符转移边，否则就走这条边。根到最后的状态就是我们求的子串。时间复杂度$O(nk)$,$k$是常数就$O(n)$
不怎么想写这个代码，就放个曲学长的参考代码吧qwq1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using namespace std;
int dis[N<<1],fa[N<<1],siz[N<<1],ch[N<<1][26],sz=1,root=1,last=root,len,t,k;
char s[N];
void insert(int x)
{
int pre=last,now=++sz;last=now;
dis[now]=dis[pre]+1;siz[now]=1;
for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
if (!pre) fa[now]=root;
else
{
int q=ch[pre][x];
if (dis[q]==dis[pre]+1)
fa[now]=q;
else
{
int nows=++sz;dis[nows]=dis[pre]+1;
fa[nows]=fa[q],fa[now]=fa[q]=nows;
memcpy(ch[nows],ch[q],sizeof ch[q]);
for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
}
}
}
int ton[N<<1],ti[N<<1],sum[N<<1];
void work()
{
for (int i=1;i<=sz;i++) ton[dis[i]]++;
for (int i=1;i<=len;i++) ton[i]+=ton[i-1];
for (int i=1;i<=sz;i++) ti[ton[dis[i]]--]=i;
for (int i=sz;i;i--)
if (t) siz[fa[ti[i]]]+=siz[ti[i]];
else siz[ti[i]]=1;
siz[root]=0;
for (int i=sz;i;i--)
{
sum[ti[i]]=siz[ti[i]];
for (int j=0;j<26;j++)
if (ch[ti[i]][j])
sum[ti[i]]+=sum[ch[ti[i]][j]];
}
}
int main()
{
scanf("%s%d%d",s+1,&t,&k);len=strlen(s+1);
for (int i=1;i<=len;i++) insert(s[i]-'a');
work();
if (k>sum[root]) return puts("-1"),0;
int now=root;
while((k-=siz[now])>0)
{
int p=0;
while(k>sum[ch[now][p]]) k-=sum[ch[now][p++]];
now=ch[now][p];
putchar('a'+p);
}
}
$SA$只想出来了$t=0$。
只需要把$LCP$的影响减掉就好了，像这样：
1 | for(int i = 1 ; i <= n ; ++i) |
然后$t=1$就不会啦。
然后想了想，看题解找找灵感胡出来一个不知道是不是正确的做法。
处理排好序的后缀的子串个数和（长度之和）。
枚举当前填到位置每一个字符，二分它的位置。然后$O(1)$利用我们算出的长度和数组计算出这个字符的个数$l$，够这位就填这个，不够$k-l$继续下一个字符，和后缀自动机有点像，多了个$log$.
时间复杂度$O(nklogn)$
我实在是不怎么适合OI，这题我累计想了3小时了吧。。
刚刚读错了题。。。
题目让求两字符串的最长公共子序列，我求了个最长公共子串还觉得很简单。。
然后就找到了匹配最长子串。
然后犯了及其弱智的错误：读入神错
由于我现在喜欢自己写字符串读入，结果这次把$>=z$都过滤了，注意，我过滤了z！！！我说怎么小字符集拍不出来，大的5分钟才好不容易出了一组。。。
然后
介绍下SAM求最长公共子串，是一个在线过程，我们一个一个查询匹配字符，正确性是这样的：最长的一个匹配子串会在它的结束为止那个字符查询时得到。
1 |
|