HAOI 2016

OI&ACM, OI训练
  1. 1 食物链 (chain)
  2. 2 放棋子(chess)
  3. 3 地图(map)
  4. 4 字符合并(merge)
  5. 5 找相同子串(find)

HAOI结束了，第七，没有完成我(虐场)的目标
好吧其实还是开心自己可以进队了，继续加油吧

1 食物链 (chain)

给你\(n\)个物种和\(m\)条能量流动关系，求其中的食物链条数。
物种的名称为从\(1\)到\(n\)编号
\(m\) 行每行两个整数ai bi描述m条能量流动关系,其中 \(ai bi\) 表示能量从物种 \(ai\) 流向物种 \(bi\)
数据保证输入数据符合生物学特点，且不会有重复的能量流动关系出现
数据范围：\(1<=n<=100000\) \(0<=m<=200000\) 题目保证答案不会爆int

显然多么裸的拓扑排序呀，我居然20，这是为什么呢。。。
有一种形如机房里放的花（绿萝）的生物，只有一个点，啥也不吃，也不会被吃（反正我不吃），（因为高中生物里学的食物链指捕食食物链，没有分解者），然后这就不算是一条食物链了
然而脑残的我并没有想到，而且对拍的force用的搜索，也没有考虑这种情况 QAQ
默默看着神犇们AC了这道题，很忧伤

1
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
#include <cstdio>
#include <queue>
const int N=100005;
int n,m,ans,in_d[N],out_d[N],num[N],head[N],to[N*2],next[N*2];
std::queue<int> Q;
int main()
{
	freopen("chain.in","r",stdin);
	freopen("chain.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		to[i]=y;next[i]=head[x];head[x]=i;
		in_d[y]++;out_d[x]++;
	}
	for(int i=1;i<=n;i++) if(!in_d[i]&&out_d[i]) num[i]=1,Q.push(i); //考试没有写out_d[i] QAQ
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		{
			in_d[y]--;num[y]+=num[x];
			if(!in_d[y]) Q.push(y);
		}
	}
	for(int i=1;i<=n;i++) if(!out_d[i]) ans+=num[i];
	printf("%d\n",ans);
}

2 放棋子(chess)

给你一个\(N\times N\)的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放\(N\)个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。 数据范围：N<=200

考场上是这样的：
题面居然没有写0是障碍还是1是障碍，算了就当1写吧
写了个状压搜索，样例过了，那写个 \(N=3\) 的数据跑一下试试吧
然后就手推了2,3,4,5,发现好像和怎么放障碍并没有关系呀，而且好像每一次都乘了 \(n-1\) 呀
然后对于一个n 疯狂 造数据对拍，发现确实一样
然后把 \(n=1-20\) 打出来找规律，发现 \(f[i] = ( f[i-1] + f[i-2] ) \times (i-1)\)，我去这不是错排公式吗，我的智商呀，明明就是错排嘛，山东不是刚考嘛
打到23还是24发现爆long long了，我之前可是基本没写过高精的人呀，算了考场上想也没什么呀，然后打出来了5位压1位的高精
嗯，前面和暴力结果是一样的，后面肿么办。。。计算器随便算了几个（计算器范围也不够），貌似没错吧
算了，\(n<=20\) 写暴力，其他写正解，于是出现了solve1()和solve2()两个函数。。。
然后不小心听到了旁边的闵神举手问：“老师，程序大小限制是多少？” QAQ

1
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
#include <cstring>
#include <cstdio>
using namespace std;
const int mod=1e5;
int n;
long long g[25];
struct node { int len,a[100]; } f[205];
node operator + (const node &x,const node &y)
{
	node z;
	z.len=0;memset(z.a,0,sizeof(z.a));
	for(int i=1;i<=x.len||i<=y.len;i++)
	{
		z.a[i]+=x.a[i]+y.a[i];
		if(z.a[i]>=mod)
		{
			z.a[i+1]=z.a[i]/mod;
			z.a[i]%=mod;
		}
		while(z.a[z.len+1]) z.len++;
	}
	return z;
}
node operator * (const node &x,const int y)
{
	node z;
	z.len=0;memset(z.a,0,sizeof(z.a));
	for(int i=1;i<=x.len;i++)
	{
		z.a[i]+=x.a[i]*y;
		if(z.a[i]>=mod)
		{
			z.a[i+1]=z.a[i]/mod;
			z.a[i]%=mod;
		}
		while(z.a[z.len+1]) z.len++;
	}
	return z;
}
void Out_Put(node x)
{
	printf("%d",x.a[x.len]);
	for(int i=x.len-1;i>0;i--)
	  printf("%05d",x.a[i]);
	printf("\n");
}
int main()
{
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	scanf("%d",&n);
	f[2].len=1;f[2].a[1]=1;
	for(int i=3;i<=200;i++)
	  f[i]=(f[i-1]+f[i-2])*(i-1);
	Out_Put(f[n]);
}

3 地图(map)

Hoshizora Rin是个特别好动的少女。
一天Rin来到了一个遥远的都市。这个都市有 \(N\) 个建筑，编号从 \(1\) 到 \(N\) ，其中市中心编号为 \(1\) ，这个都市有 \(M\) 条双向通行的街道，每条街道连接着两个建筑，其中某些街道首尾相连连接成了一个环。Rin通过长时间的走访，已经清楚了这个都市的两个特点：
从市中心出发可以到达所有的建筑物。
任意一条街道最多存在与一个简单环中。
令Rin心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于Rin而言只有油腻程度的不同，因此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来表示拉面的油腻程度。
要知道，拉面可是Rin的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。Rin只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。
现在Rin想知道，如果她正在编号为 \(x\) 的建筑物，那么在从市中心到 \(x\) 的所有简单路径经过的街道都被堵死的情况下，Rin可以品尝到的拉面中（注意没有出现的拉面是不能算在里面的）：
1.油腻程度 \(≤y\) 且品尝次数为奇数次的拉面有多少种？
2.油腻程度 \(≤y\) 且品尝次数为偶数次的拉面有多少种？
数据范围：\(N <= 1e5\) , \(M <= 1.5 \times 1e5\) , \(Q <= 1e5\) , \(Ai <= 1e6\)

考试时：
我去这是啥，仙人掌！我没写过呀！！！
算了打搜索吧（好像只有15）

4 字符合并(merge)

有一个长度为 \(n\) 的 \(01\) 串，你可以每次将相邻的 \(k\) 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 \(k\) 个字符确定。你需要求出你能获得的最大分数。
输入格式:
第一行两个整数 \(n\) ，\(k\) 。
接下来一行长度为 \(n\) 的 \(01\) 串，表示初始串。
接下来 \(2k\) 行，每行一个字符 \(ci\) 和一个整数 \(wi\) ，\(ci\) 表示长度为 \(k\) 的 \(01\) 串连成二进制后按从小到大顺序得到的第 \(i\) 种合并方案得到的新字符, \(wi\) 表示对应的第 \(i\) 种方案对应获得的分数。
数据范围: \(n <= 300\) , \(k <= 8\) , \(1 <= wi <= 1e9\) .

考试的时候想到区间DP了，愣是敲了两个半小时没调出来
还有出题人是几个意思，数据都给错了，01串给成了单个的数，你让直接读入字符数组的我们肿么办?! QAQ
f[i][j][t]表示把 \(i-j\) 区间变成 \(t\) 的最大收益

1
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
#include <iostream>
#include <cstring>
#include <cstdio>
int n,k,m,a[305],c[260],w[260];
long long ans,f[305][305][130];
int main()
{
	memset(f,-1,sizeof(f));
	scanf("%d%d",&n,&k);
	m=1<<k;
	for(int i=1,x;i<=n;i++)
		scanf("%1d",&x),f[i][i][x]=0;
	for(int i=0;i<m;i++) scanf("%d%d",&c[i],&w[i]);
	for(int len=1,end=1;len<n;len++,end=(len-1)%(k-1)+1)
		for(int i=1;i+len<=n;i++)
			for(int j=i+end-1;j<i+len;j+=k-1)
				for(int x=0;x<(1<<end);x++)
					if(f[i][j][x]!=-1)
						for(int y=0;y<=1;y++)
							if(f[j+1][i+len][y]!=-1)
							{
								if(end==k-1) f[i][i+len][c[(x<<1)+y]]=std::max(f[i][i+len][c[(x<<1)+y]],f[i][j][x]+f[j+1][i+len][y]+w[(x<<1)+y]);
								else f[i][i+len][(x<<1)+y]=std::max(f[i][i+len][(x<<1)+y],f[i][j][x]+f[j+1][i+len][y]);
							}
	for(int i=0;i<(m>>1);i++) ans=std::max(ans,f[1][n][i]);
	printf("%lld\n",ans);
}

5 找相同子串(find)

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
数据范围：\(1 <=n1,n2<= 200000\) ，字符串中只有小写字母。

半个小时敲了个三方暴力，20分。。。
gcx貌似后缀数组+线段树

DP 组合数学 拓扑排序