HAOI 2016

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

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

1 食物链 (chain)

给你nn个物种和mm条能量流动关系,求其中的食物链条数。
物种的名称为从11nn编号
mm 行每行两个整数ai bi描述m条能量流动关系,其中 aibiai bi 表示能量从物种 aiai 流向物种 bibi
数据保证输入数据符合生物学特点,且不会有重复的能量流动关系出现
数据范围:1<=n<=1000001<=n<=100000 0<=m<=2000000<=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×NN\times N的矩阵,每行有一个障碍,数据保证任意两个障碍不在同一行,任意两个障碍不在同一列,要求你在这个矩阵上放N枚棋子(障碍的位置不能放棋子),要求你放NN个棋子也满足每行只有一枚棋子,每列只有一枚棋子的限制,求有多少种方案。 数据范围:N<=200

考场上是这样的:
题面居然没有写0是障碍还是1是障碍,算了就当1写吧
写了个状压搜索,样例过了,那写个 N=3N=3 的数据跑一下试试吧
然后就手推了2,3,4,5,发现好像和怎么放障碍并没有关系呀,而且好像每一次都乘了 n1n-1
然后对于一个n 疯狂 造数据对拍,发现确实一样
然后把 n=120n=1-20 打出来找规律,发现 f[i]=(f[i1]+f[i2])×(i1) f[i] = ( f[i-1] + f[i-2] ) \times (i-1)我去这不是错排公式吗,我的智商呀,明明就是错排嘛,山东不是刚考嘛
打到23还是24发现爆long long了,我之前可是基本没写过高精的人呀,算了考场上想也没什么呀,然后打出来了5位压1位的高精
嗯,前面和暴力结果是一样的,后面肿么办。。。计算器随便算了几个(计算器范围也不够),貌似没错吧
算了,n<=20 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来到了一个遥远的都市。这个都市有 NN 个建筑,编号从 11NN ,其中市中心编号为 11 ,这个都市有 MM 条双向通行的街道,每条街道连接着两个建筑,其中某些街道首尾相连连接成了一个环。Rin通过长时间的走访,已经清楚了这个都市的两个特点:
从市中心出发可以到达所有的建筑物。
任意一条街道最多存在与一个简单环中。
令Rin心花怒放的是,每个建筑物都会有拉面售卖。拉面有很多不同的种类,但对于Rin而言只有油腻程度的不同,因此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同,我们用一个正整数来表示拉面的油腻程度。
要知道,拉面可是Rin的最爱,但是现在到了下班高峰期,都市的交通变得非常的堵塞。Rin只能通过没有被堵死的街道通行,去品尝所在建筑物的拉面。
现在Rin想知道,如果她正在编号为 xx 的建筑物,那么在从市中心到 xx 的所有简单路径经过的街道都被堵死的情况下,Rin可以品尝到的拉面中(注意没有出现的拉面是不能算在里面的):
1.油腻程度 且品尝次数为奇数次的拉面有多少种?
2.油腻程度 且品尝次数为偶数次的拉面有多少种?
数据范围:N<=1e5 N <= 1e5 , M<=1.5×1e5 M <= 1.5 \times 1e5 , Q<=1e5 Q <= 1e5 , Ai<=1e6 Ai <= 1e6

考试时:
我去这是啥,仙人掌!我没写过呀!!!
算了打搜索吧(好像只有15)

4 字符合并(merge)

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

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

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<=2000001 <=n1,n2<= 200000 ,字符串中只有小写字母。

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