放一些这段时间模拟赛的题
似乎很多题我都忘记了?!?
就当复习了

完备匹配

时间限制:2s空间限制:256MB

Description

有一个两边点集大小都是$n$的二分图。他本来是一个完全二分图(即把图中的顶点分成两个集合,使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连)。

每条边都有一个边权。对一个匹配,在匹配中边的边权的总和为这个匹配的价值。但是由于某些原因,这个二分图中的$k$条边不见了。

他想知道现在这个二分图还有几种完备匹配(如果图的所有顶点都与某匹配中的一条边相关联,则称此匹配为完备匹配)方案,并且所有完备匹配的价值的总和是多少。

Input

第一行,一个正整数$n$。

接下来有$n$行,每行$n$个整数,第$i$行第$j$个整数$w_{i,j}$,表示点$i$向另一个点集中的点$j$边的权值。注意点从$0$开始标号。

接下来一行,一个正整数$k$,表示有多少条边不见了。

接下来$k$行,每行两个整数$u,v$,表示点$u$向另一个点集中的点$v$边不见了。

Output

一行两个整数,第一个数为完备匹配的个数,第二个数为所有完备匹配的价值总和,由于数字较大,请对$10^9+7$取模。

Sample Input

5
2 3 4 5 6
5 4 3 2 1
7 6 5 4 3
5 6 7 8 9
3 4 5 6 7
3
1 2
2 2
3 4

Sample Output

60 1408

Hint

对于$100%$的数据,$n\leq 300$, $k\leq 20$ , $0\leq w_{i,j}\leq 500$。

Solution

这是一道要用到容斥原理的题

先考虑第一问。首先如果没有不可选的边,那么完备匹配数就是$n!$

然后我们可以惊喜的地发现$k$非常的小,只有20,那么我们就可以对不可选地边进行 $2^k$ 次枚举,
根据容斥原理,将奇数条不可选的边产生地方案数从总方案数中减去,将偶数条的方案数加上

那么这个方案数该怎么计算呢?假设我们现在枚举出$sum$条边,由于一共需要$n$条边,其中$sum$条边已经确定,那么方案数就是$(n-sum)!$

第二问其实也是同样的道理,首先算出全部边可选的情况下的权值总和
再将枚举出的边根据数量奇偶性在答案中加减,要注意的是在这个过程中不能有两条被选中的边有同一个顶点

Code

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
#include <cstdio>
using namespace std;
const int mod=1e9+7;
int n,K,g[310][310],sum[2][310],x[25],y[25],u[25],v[25],vis[2][310];
long long jc[310],ans1,ans2,Sigma,tmp;
void dfs(int k,int Sum,int sigma,int num){
if(k==K+1) {
ans1+=(Sum&1)?mod-jc[n-Sum]:jc[n-Sum];
if(ans1>=mod) ans1%=mod;
tmp=(sigma*jc[n-Sum-1]%mod+num*jc[n-Sum]%mod)%mod;
ans2+=(Sum&1)?mod-tmp:tmp;
if(ans2>=mod) ans2%=mod;
return;
}
dfs(k+1,Sum,sigma,num);
if(vis[0][u[k]]||vis[1][v[k]]) return;
x[Sum+1]=u[k];
y[Sum+1]=v[k];
sigma+=g[u[k]][v[k]]-sum[0][u[k]]-sum[1][v[k]];
vis[0][u[k]]=1;
vis[1][v[k]]=1;
for(int i=1;i<=Sum;i++)
sigma+=g[x[i]][v[k]]+g[u[k]][y[i]];
dfs(k+1,Sum+1,sigma,num+g[u[k]][v[k]]);
vis[0][u[k]]=0;
vis[1][v[k]]=0;
}
int main(int argc, char const *argv[])
{
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
scanf("%d",&g[i][j]),sum[0][i]+=g[i][j],sum[1][j]+=g[i][j];
Sigma+=sum[0][i];
}
jc[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
scanf("%d",&K);
for(int i=1;i<=K;i++)
scanf("%d%d",&u[i],&v[i]);
dfs(1,0,Sigma,0);
printf("%lld %lld\n",ans1,ans2);
return 0;
}

图书列表

时间限制:1s空间限制:256MB

Description

现在小G作为图书管理员,他的第一份工作是重新安排一些图书。他得到了一张列表,每个表项具有以下格式:
CATEGORY1/CATEGORY 2/…./CATEGORY n/BOOKNAME
这表示图书BOOKNAME位于目录CATEGORY n下, 目录CATEGORY n 位于目录CATEGORY n-1下,目录CATEGORY n-1位于目录CATEGORY n-2下, 以此类推。也就是说,每个表项是由最后的一本图书,以及该图书所属的若干目录按照层级依次组成的。我们称CATEGORY1为一级目录,而CATEGORY 2为二级目录,以此类推。例如:

  1. MATH/GRAPH THEORY
  2. ART/HISTORY/JAPANESE HISTORY/JAPANESE ACIENT HISTORY
  3. ART/HISTORY/CHINESE HISTORY/THREE KINDOM/RESEARCHES ON LIUBEI
  4. ART/HISTORY/CHINESE HISTORY/CHINESE MORDEN HISTORY
  5. ART/HISTORY/CHINESE HISTORY/THREE KINDOM/RESEARCHES ON CAOCAO

小G认为这份列表很不容易阅读和查找,于是他决定按照以下规则制作一份新列表,用缩进来体现图书与目录之间的层级关系:

  1. n级目录之前有$4\times (n-1)$个空格的缩进。
  2. 直接隶属于n级目录的图书前有$4\times n$个空格的缩进。
  3. 直接隶属于目录X目录与图书按照字典序列在目录X之后,但所有目录位于所有图书之前。
  4. 所有一级目录按照字典序先后列出。

例如,上面的列表转化后将变为:

ART
    HISTORY
        CHINESE HISTORY
            THREE KINDOM
                RESEARCHES ON CAOCAO
                RESEARCHES ON LIUBEI
            CHINESE MORDEN HISTORY
        JAPANESE HISTORY
            JAPANESE ACIENT HISTORY
MATH
    GRAPH THEORY

请写一个程序帮助小G完成这项工作。

Input

输入原列表,共包含不超过30本图书,以一个数字0结尾。
每行列出一个表项,表项是一个由大写字母、数字、“/”和空格构成的字符串,长度不超过100。
一本图书可能在列表中出现多次,但在转化后的列表中,它应该只出现一次。但是若同名的图书或目录若在不同的目录结构下,则认为他们是不相同的。换句话说,一个图书或目录由以它的名字为结尾的前缀唯一确定。

Output

输出新列表。本试题采用逐字节比较,行末请勿输出多余空格,文末以恰好一个换行符结尾。

Sample Input

B/A
B/A
B/B
0
A1/B1/B32/B7
A1/B/B2/B4/C5
A1/B1/B2/B6/C5
A1/B1/B2/B5
A1/B1/B2
A1/B1/B2/B1
A1/B3/B2
A3/B1
A0/A1
0

Sample Output

B
    A
    B
A0
    A1
A1
    B
        B2
            B4
                C5
    B1
        B2
            B6
                C5
            B1
            B5
        B32
            B7
        B2
    B3
        B2
A3
    B1

Solution

模拟题,将每行数据读入后,先在整个字符串后面加上一个’/‘方便处理,每次到一个’/‘,将前面的一串字符取出,根据其是否在行末判断是目录还是书籍,并作标记,然后记录到子目录列表中,记录时注意判重复,只有在当前子目录中没有的名称才新建,否则直接进入已有的目录

对每一个目录我们用一个数组记录其子目录,最后会形成一个树形结构,
注意,为了方便处理,我们可以将所有一级目录定为一个虚拟出来的根目录的子目录

将所有数据读完之后,将每一个子目录列表按照题目规定的顺序进行排序,然后从虚拟的根目录开始dfs按照顺序输出就可以了

Code

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
57
58
59
60
#include <cstdio>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
inline void read(string &s){
s.clear();
char ch=getchar();
while((ch<'A'||ch>'Z')&&(ch<'0'||ch>'9')&&ch!=' ') ch=getchar();
while(ch!='\n'&&ch!='\r') s+=ch,ch=getchar();
}
string s[1600],st,now;
int fa,lens,flg,cnt,son[1600][100],isbook[1600],is;
int cmp(const int &x,const int &y){
return isbook[x]==isbook[y]?s[x]<s[y]:isbook[x]<isbook[y];
}
void dfs(int u,int dep){
if(u){
for(int i=1;i<=4*(dep-1);i++) putchar(' ');
cout<<s[u]<<endl;
}
for(int i=1;i<=son[u][0];i++)
dfs(son[u][i],dep+1);
}
int main(int argc, char const *argv[])
{
read(st);
while(st[0]!='0'||st.length()>1){
st+='/';
lens=st.size(); now.clear();
fa=0;
for(int i=0;i<lens;i++){
if(st[i]=='/'){
flg=is=0;
if(i==lens-1) is=1;
for(int j=1;j<=son[fa][0];j++){
if(s[son[fa][j]]==now&&is==isbook[son[fa][j]]){
fa=son[fa][j];
flg=1;
break;
}
}
if(flg) {now.clear();continue;}
s[++cnt]=now;
son[fa][++son[fa][0]]=cnt;
isbook[cnt]=is;
fa=cnt;
now.clear();
continue;
}
now+=st[i];
}
read(st);
}
for(int i=0;i<=cnt;i++)
sort(son[i]+1,son[i]+son[i][0]+1,cmp);
dfs(0,0);
return 0;
}

量化交易

时间限制:1s空间限制:128MB

Description

由于原题面实在太罗嗦,笔者稍微简化了一下

给出$n$个数,表示$n$天中股票的价格,每天可以买进或卖出一股,也可以什么也不做求$n$天后的最大收益

Input

每个测试点包含若干组数据,以EOF结尾。对于每组数据:
第一行1个整数N。
第二行N个正整数,相邻两个整数之间用1个空格隔开,表示每一天股票的价格。

Output

对于每组数据,首先按样例所示的格式“Case #k:”输出该组数据的编号,然后输出一个整数,表示applepi最大能够获得的利润。

Sample Input

6
2 6 7 3 5 6
8
1 2 3 4 5 6 7 8
10
15831 47573 60015 51368 32460 34125 43074 75172 54014 93578

Sample Output

Case #1: 8
Case #2: 16
Case #1: 161084

Hint

对于$50%$的数据,$1\leq N\leq 1000$。
对于$100%$的数据,$1\leq N\leq 100000$,股票价格不超过$100000$,每个测试点至多包含$5$组数据。

Solution

考场上想了半天贪心,最后还是只打了50分的暴力,结果发现只是自己的贪心姿势水平不够啊

我们先默认每天都是卖出的,然后维护一个堆,将每天的价格扔两个进去,
既然要卖出,那自然得有相应的买入,也就是从堆中取出一个价格,每天将答案加上当天价格减去取出的价格。第$n$天后的答案就是输出

那么来证明一下这个贪心正确性
首先在贪心过程中一个卖出一定对应一个买入,并且每一时刻堆中的价格都是在该时刻以前的,是可以选择的。这样就符合了题意
那么为什么这样贪心最优呢?要理解若一天的价格没有从堆中取出,则该天的操作时卖出,若取出一次则是不操作,若取出两次则是买入
而每次买入都是以当前可选的最低价格买入的,答案自然最优了

要注意,由于C++的优先队列默认是大根堆,程序实现时压入的是价格的相反数,和描述不太一样

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <queue>
using namespace std;
int x,T,n;
long long ans;
priority_queue<int>q;
int main(int argc, char const *argv[]){
while(scanf("%d",&n)!=EOF){
T++,ans=0;
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++){
scanf("%d",&x);
q.push(-x),q.push(-x);
ans+=x+q.top();
q.pop();
}
printf("Case #%d: %lld\n",T,ans);
}
return 0;
}

小象和老鼠

时间限制:1s空间限制:128MB

Description

还是那句话,原题面好罗嗦啊,来zip一下

给定一个$n\times m$的网格图,左上角为$(1,1)$ ,右下角为$(n,m)$ ,每个点上可能有若干只老鼠。

现在要从找出一条从左上角到右下角的路径,使沿途遇到的老鼠数量最少(“遇到”的定义是在路径上某一点的四联通快内,相同老鼠不重复计数),走的时候只能向下或向右

Input

第一行包含两个用空格隔开的整数,$n$ 和 $m$。 接下来一个 $n \times m$ 的矩阵表示动物园的地图。其中 表示第 行第 列上老鼠的数量。 若 $a_{i,j}=0$ 则表示当前位置上没有老鼠($(1,1)$也可能存在老鼠)。

Output

输出一个整数,表示路线最小的数量是多少。

Sample Input

3 9
0 0 1 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0
1 0 0 1 0 0 1 0 0

Sample Output

9

Hint

对于 $10%$ 的数据,$1\leq N,M\leq 5$。
对于 $100%$ 的数据,$1\leq N,M\leq 1000$ , $0\leq A_{i,j}\leq 100$。

Solution

一开始写了个记搜妄想能过,结果发现自己太天真了。。。还好DP并不难想

单独考虑每一步遇到的老鼠数量,发现只有上一步走之前所处的位置有可能与这一步走完后所处位置上遇到的老鼠有重复。

那么我们用 $f[0..1][i][j]$ 表示上一步是向下还是向右,$i,j$ 表示所处位置,
这样 $f[0][i][j]$ 就从 $f[i-1][j]$ 两种状态转移过来, $f[1][i][j]$ 从 $f[i][j-1]$ 转移过来

注意初始值将 $f[0..1][1][1]$ 都赋成 $(1,1)$ 能看到的老鼠数

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,a[1100][1100],f[2][1100][1100],tmp;
int main(int argc, char const *argv[]){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
memset(f,0x3f,sizeof f);
f[0][1][1]=f[1][1][1]=a[1][1]+a[1][2]+a[2][1];
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++){
tmp=a[i][j-1]+a[i][j+1]+a[i-1][j]+a[i+1][j];
if(i==1&&j==1) continue;
f[0][i][j]=tmp+min(f[0][i-1][j]-a[i-1][j],f[1][i-1][j]-a[i-1][j]-a[i][j-1]);
f[1][i][j]=tmp+min(f[0][i][j-1]-a[i][j-1]-a[i-1][j],f[1][i][j-1]-a[i][j-1]);
}
printf("%d\n",min(f[0][n][m],f[1][n][m]));
return 0;
}

量子模型

时间限制:1s空间限制:128MB

Description

小 W 所在学校的物理学水平全国闻名,因此吸引来了大量民间科学爱好者。某一天, 一位自称能做出诺贝尔奖级别成果,颠覆人类物理学框架的民间科学爱好者拦住了小 W, 和小 W 分享了一种小 W 闻所未闻的量子模型: 一个量子的状态可以用一个有序三元组来表示,如果该量子的状态是$(x,y,z)$,则能够发生如下六种之一的跃迁,转移到另一个状态(如果原状态$(x,y,z)$满足这种跃迁发生的前提条件的话)。

前提条件 跃迁后状态
$z < min(2y-x,x)$ 或者 $z > max(2y-x,x)$ $(2y-x,y,z)$
$z < min(2x-y,y)$ 或者 $z > max(2x-y,y)$ $(x,2x-y,z)$
$y < min(2z-x,x)$ 或者 $y > max(2z-x,x)$ $(2z-x,y,z)$
$y < min(2x-z,z)$ 或者 $y > max(2x-z,z)$ $(x,y,2x-z)$
$x < min(2y-z,z)$ 或者 $x > max(2y-z,z)$ $(x,y,2y-z)$
$x < min(2z-y,y)$ 或者 $x > max(2z-y,y)$ $(x,2z-y,z)$

所有的量子的初始状态都是$(i,j,k)$,且总满足 $i+k=2·j$ ,现在对于任意的一个状态$(x,y,z)$ , 定义三元函数 $dist(x,y,z) = (𝑖,𝑗,𝑘)$ 最少需要 $𝑑𝑖𝑠𝑡(𝑥,𝑦,𝑧)$ 次跃迁可以变成状态 $(𝑥,𝑦,𝑧)$ 。这位 民间科学爱好者同时声称,如果将一个量子一生中所有达到过的看作一个集合 S,那么 S 将 满足:

  1. $|S| = n$
  2. $max(𝑑𝑖𝑠𝑡(𝑥,𝑦,𝑧)|(𝑥,𝑦,𝑧) ∈ 𝑆) = 𝑚$

他想知道有多少种不同的集合 S 满足上述条件。

Input

5 个以空格隔开的整数:i j k n m

Output

含一个整数,表示满足条件的集合 S 有多少种,为了方便起见,你只要输 出这个数字对 2016 取模的结果。

Sample Input

1 2 3 2 1
1 2 3 3 2

Sample Output

2
4

Hint

对于 $30%$ 的测试数据 $n,m \leq 10$
对于 $50%$ 的测试数据 $m,n \leq 50$
对于 $100%$ 的测试数据 $m,n \leq 150$ , $−50 \leq i,j,k \leq 50$

Solution

找点值代进去,发现其实每种状态 $(x,y,z)$ 都刚好会符合三种条件(除了$(x,y,z)$时等差数列的情况),也就是说在任何时刻量子都可以跳跃到三种状态,其中有一种会与当前状态的上一状态重复

那么一个初始状态 $(i,j,k)$ 的所有可到达的状态呈现一个完全二叉树形态,那就可以用树形DP了

首先题目要求状态集合中有 $n$ 种状态, 并且其中与初始状态 $dist$ 最大的为 $m$。也就是说要找到包含完全二叉树上 $n$ 个点的集合, 并且至少包含一个第 $m$ 层的点。 由于是完全二叉树,所以同一层的节点都是一样的,DP时枚举第几层就可以了

用 $f[i][j][0..1]$ 表示当前枚举到的结点处在第 $i$ 层,集合中已经有 $j$ 个结点, $0..1$ 表示是否可以到达第 $m$ 层
DP时从下往上枚举层数,每次从下一层转移过来 然后枚举集合中的总节点个数和左儿子集合中的点数就可以了

发现其实 $i$ 这一维可以滚动掉,那就滚动一下呗

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
const int mod=2016;
using namespace std;
int f[2][160][2],x,y,z,n,m,dep;
int main(int argc, char const *argv[])
{
scanf("%d%d%d%d%d",&x,&y,&z,&n,&m);
f[m&1][1][1]=f[m&1][0][0]=1;
for(int i=m-1;i>=0;i--){
dep=i&1; //用于滚动数组
memset(f[dep],0,sizeof f[dep]); //滚动时记得初始化
for(int j=0;j<=n;j++)
for(int k=0;k<j;k++){
(f[dep][j][0]+=f[!dep][k][0]*f[!dep][j-k-1][0])%=mod;
(f[dep][j][1]+=f[!dep][k][1]*f[!dep][j-k-1][0]%mod
+f[!dep][k][1]*f[!dep][j-k-1][1]%mod
+f[!dep][k][0]*f[!dep][j-k-1][1]%mod)%=mod;
}
f[dep][0][0]=1;
}
printf("%d\n",f[0][n][1]);//答案为根节点下状态数为n,且能到达第m层的方案数
return 0;
}

abcd

时间限制:1s空间限制:128MB

Description

有4个长度为$N$的数组$a,b,c,d$。现在需要你选择$N$个数构成数组$e$,数组 $e$ 满
足 $a_i \leq e_i \leq b_i$以及

并且使得

最大。

Input

输入文件名为$abcd.in$。
输入文件共 $N+1$ 行。
第 1 行包含1个正整数$N$。
第 $i+1$ 行包含4个整数 $a[i],b[i],c[i],d[i]$ 。

Output

输出文件名为 $abcd.out$ 。
输出共1行,包含1个整数,表示所给出公式的最大值。输入数据保证一定有
解。

Sample Input

5
-1 1 2 5
-2 2 1 2
0 1 1 3
-2 -1 3 10
-2 2 3 9
10
1 10 1 7
-10 10 2 0
-10 10 2 2
-10 10 2 0
1 10 1 0
-10 10 2 0
10 10 2 0
1 10 1 0
-10 10 2 0

Sample Output

2
90

Hint

对于 $100\%$ 的数据,$N\leq 200 , -25\leq a[i]<b[i]\leq 25 , 1\leq c[i]\leq 20 , 0\leq p[i]\leq 100000$ 。

Solution

令 num[i]=e[i]-a[i] , 则 0≤num[i]≤b[i]-a[i] ,

需要求 的最大值

所以 $b[i]-a[i]$ 是物品数量限制,num[i] 是 i 物品的选取数量,c[i] 是物品大小,$\Sigma (-a[i]*c[i])$ 是背包容量,$d[i]$ 是物品价值。原问题就变成了多重背包问题。

然后用单调队列优化一下就可以A掉此题

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <algorithm>
using namespace std;
int a[210],b[210],c[210],d[210],ans,n;
int f[100010],v;
int main(int argc, char const *argv[]){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]),
v-=a[i]*c[i],ans+=a[i]*d[i];
for(int i=1;i<=v;i++) f[i]=-2e9;
for(int i=1;i<=n;i++)
for(int j=v;j>=0;j--)
for(int k=0;k*c[i]<=j&&k<=b[i]-a[i];k++)
f[j]=max(f[j],f[j-c[i]*k]+d[i]*k);
printf("%d\n",f[v]+ans);
return 0;
}