各省省选浙江oi zjoi2011一试2011zjsx1试题

1、2011 年浙江省省队选拔赛第一试Overview题目名称看最小割程序名giftmoviemincut输入文件名monument.ovie.incut.in输出文件名monument.outmovie.outmincut.out测试点数目201015每个测试点分值5 分10 分15,1每个 15 分2,3,4,5,6每个 3 分7,8,9,10每个 4 分119 分12,13,14 每个 10 分时间限制2s1s1s空间限制128M128M128M题目类型传统题传统题传统题(gift)的生日就要到了，决定送一件自己亲手做工艺品使自己的礼物与众不同。具体来说已经通过某种方式制作出了一个 pqr

2、的木块（由pqr 个小木块组成）。但由于手艺不精，现在这个木块中的有些小木块是有问题的(有裂缝、里面是空心等等)，这样的去的。是不可能直接送出于是决定在这个木块中再挖出一个 aab 的子木块(即要求挖出的长方体木块存在两条长度相等的相邻边)，当然这个子木块中是不能包含有问题的小木块的。为了使这个木块上能包含的图案，希望从所有可行的方案中挑取 4ab 的值最大的方案。但光检测木块中哪些地方有问题就已经耗尽了体力，作为的好友，你能帮帮吗？【输入说明】每个输入文件中仅包含一个测试数据。第一行包含三个由空格隔开的正整数，p,q,r。接下来有 pq 行，每行包含 r 个字符，每个字符只可能是P(Poor

3、) 或者N(Nice)，表示该小木块有问题或者没问题。具体的说，第 1+(yp+x-p)行的第z 个字符描述的是坐标为(x,y,z)的小木块情况。(1=x=p,1=y=q,1=z=r)【输出说明】输出文件仅包含一个整数，表示最佳方案的 4ab 的值。【样例输入】3 2 5PNNNN PNNNN NPPNP PNNNP NNNNP PPNNP【样例输出】24【数据范围】对于 100%的数据，0p,q,r=150，输入中至少包含一个N(movie)看到了难得的假期，班上组织大家去看。但由于假期里看的人太多，很难做到让全班看上同一场，最后大家在一个偏僻的小胡同里找到了一家院。但这家院分配座位的方式很

4、特殊，具体方式如下：1.院的座位共有K 个，并被标号为 1K，每个人买完票后会被随机指定一个座位，具体来说是从 1K 中等可能的随机选取一个正整数，设其为 L。2.如果的步骤。L 的座位是空位，则这个座位就分配给此人，否则将 L 加一，继续前面3.如果在第二步中不存在L 的座位，则该人只能站着看，即所谓的站票。班上共有N 人（包括能够有座位的概率是多少。自己），作为数学者，想知道全班都【输入说明】输入文件第一行有且只有一个正整数T，表示测试数据的组数。第 2T+1 行，每行两个正整数 N,K，用单个空格隔开，其含义同题目描述。【输出说明】输出文件共包含T 行。第i 行应包含两个用空格隔开的整数

5、 A,B，表示输入文件中的第 i 组数据的为 A/B。（注意，这里要求将【样例输入】31 12 12 2【样例输出】1 10 13 4化为既约分数）【数据范围】对于 20%的数据N,K=10对于 100%的数据T=50,N,K=200最小割(mincut)在图论课上学到了一个新的概念最小割，下课后写下了如下这段话：在笔记本上“对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 s,t 不在同一个部分中，则称这个划分是关于 s,t 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 s,t 的最小割指的是在关于 s,t 的割中容量最小的割

6、”现给定一张无向图，容量不超过x 呢”的疑问，有若干个形如“图中有多少对点它们的最小割的虽然很想回答这些问题，但最近忙着挖木块，于是作为仍然是的好友，你又有任务了。【输入说明】输入文件第一行有且只有一个正整数T，表示测试数据的组数。对于每组测试数据，第一行包含两个整数n,m，表示图的点数和边数。下面m 行，每行 3 个正整数u,v,c(1=u,v=n,0=c=106)，表示有一条权为 c 的无向边(u,v)接下来一行，包含一个整数q，表示询问的个数 下面q 行，每行一个整数x，其含义同题目描述。【输出说明】对于每组测试数据，输出应包括 q 行，第 i 行表示第 i 个问题的于点对(p,q)和(q,p)，只统计一次（见样例）。【样例输入】15 010【样例输出】10。