今日试题
Resource distribution
题目描述
某国家划出一块矿产资源丰富的土地，并给予许多优惠政策，来招募大型的资源开发商来进行开发。
这块土地可以被划分成6*6的网格，在这些网格*有4个煤矿和4个铁矿，每个矿藏占一格。现在要将这些资源平均分配给四个应招的公司A，B，C，D进行开发（每个公司开发一个煤矿和一个），同时要将这块土地平分成四块给这四个公司以便管理。
M
I
M
M M I
I
I
图1 一种矿藏的分布 图2 一种合理的划分方案
为减少争议，应按以下的要求进行划分：
1．土地只能沿网格线进行划分；
2．为了集中管理，中心的四个网格已经分给四个公司建立总控站；
3．每个公司分得的土地必须都与本公司的总控站连通；
4．这四块土地的大小，形状必须相同；
5．每个公司的土地恰好包含一个煤矿和一个铁矿；
6．每个公司的土地必须连成一片。
现在这个国家需要一种合理的划分方案，以及所有可能的划分方案的总数。请编程来解决这个问题。
输入文件
输入文件中存放一个6*6的矩阵表示这个土地的地形，其中每个元素为一个字母（中间无空格），M表示煤矿，I表示铁矿，N表示无矿。每组数据至少包含一组合理的解。
输出文件
输出文件中应包含一组合理的解。划分方案也用一个6*6的矩阵表示，其中每一个元素为字母A，B，C，D中的一个（相邻两字母间无空格），表示这一格土地分给哪一个公司。
如果有多组解，输出任意一组即可。
样 例
Input Output
NNNNNM
NNNNIN
NNNMNN
NNMMIN
NNINNN
NNNNIN CCAAAA
CCABAA
CAABBB
CCCDDB
DDCDBB
DDDDBB
Operator Encryption
题目描述
考古学发现，几千年前古梅文明时期的数学非常的发达，他们懂得多位数的加法和乘法，其表达式和运算规则等都与现在通常所用的方式完全相同（如整数是十进制，左边是高位，最高位不能为零；表达式为中缀运算，先乘后加等），唯一的区别是其符号的写法与现在不同。有充分的证据表明，古梅文明的数学文字一共有13个符号，与 0,1,2,3,4,5,6,7,8,9,+,*,= 这13个数字和符号（称为现代算符）一一对应。为了便于标记，我们用13个小写英文字母a,b,…m代替这些符号（称为古梅算符）。但是，还没有人知道这些古梅算符和现代算符之间的具体对应关系。
在一个石壁上，考古学家发现了一组用古梅算符表示的等式，根据推断，每行有且仅有一个等号，等号左右两边为运算表达式（只含有数字和符号），并且等号两边的计算结果相等。
假设这组等式是成立的，请编程序破译古梅算符和现代算符之间的对应关系。
输入文件
输入文件的第一行为等式的个数N（1<=N<=1000），以下N行每行为一个等式。
每个等式的长度为5个字符到11个字符。
输出文件
如果不存在对应关系能够满足这组等式，输出“noway”和一个换行/回车符。
如果有对应关系能够满足这组等式，输出所有能够确定的古梅算符和现代算符的对应关系。每一行有两个字符，其中第一个字符是古梅算符，第二个字符是对应的现代算符。输出按照字典顺序排序。
样 例
Input Output
2
abcdec
cdefe a6
b*
d=
f+
样例说明
在上例中，可能对应的现代表达式为{6*2=12，2=1+1}，{6*4=24，4=2+2}，{6*8=48，8=4+4}。可见，能够确定的对应关系只有a对应6，b对应*，d对应=，f对应+，应该输出；而{c,e}虽然能够找到对应的现代算符使得等式成立，但没有唯一的对应关系，不能输出。其他古梅算符{g,h…ms}完全不能确定，也不能输出。
Blocks Building
题目描述
单位立方体(unit cube)是一个1×1×1的立方体，它的所有角的x,y和z坐标都是整数。我们称两个单位立方体是连通的，当且仅当他们有一个公共的面；一个构形(solid)或者是一个单位立方体，或者是由多个单位立方体组成的连通物体(如图一所示)，它的体积就是它所含的单位立方体的个数。
一块积木(block)是一个体积不超过4的构形。如果两块积木可以平移、旋转(注意，不能成镜像)操作变得完全一样，我们就称它们属于同一类。这样，积木总共有12类(如图2所示)。图2中积木的不同颜色仅仅是为了帮助你看清楚它的结构，并没有其他的含义。
一个构形可以由若干块积木组成。如果用一些积木可以互不重叠的搭建出某个构形，那么就称这些积木是这个构形的一种分解(decomposition)。
你的任务是写一个程序,对于给定的一组积木种类和一个构形S,求出境可能少的积木个数,使得他们能够搭建出构形S。你只需给出这个最少的积木个数，以及这些积木各自所属的种类，而不必给出具体的搭建方案。
输入文件
在输入文件中，一个单位立方体用同一行中的三个整数x,y,z表示。坐标(x,y,z)是该单位立方体各个顶点坐标{(xi,yi,zi)|i=1..8}中xi+yi+zi最小的。
输入文件有两个。第一个输入文件描述了积木的不同种类，文件为block.in。在下问“输入输出样例”部分给出了一个types.in文件,他一次定义了图2所示的12中积木。注意：所有的测试数据都将统一采用该types.in文件。
每一种类的积木由连续的若干行描述。第一行市积木的种类编号I(1≤I≤12)；第二行是该类积木的体积V(1≤V≤4)；随后的V行每行包含三个整数x,y和z，表示组成该类积木的一个单位立方体，其中1≤x,y,z≤4。
输出文件
文件第一行是一个正整数M，表示使用积木的最少块数。
文件的第二行列出M个整数，表示搭建出构形S的M块积木各自的种类。
样 例
Input Output
18
2 1 1
4 1 1
2 3 1
4 3 1
2 1 2
3 1 2
4 1 2
1 2 2
2 2 2
3 2 2
4 2 2
2 3 2
3 3 2
4 3 2
4 2 3
4 2 4
4 2 5
5 2 5 5
7 10 2 10 12
方程的解数（equation）
问题描述
已知一个n元高次方程：
其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。
假设未知数1≤ xi ≤M, i=1,,,n，求这个方程的整数解的个数。
输入文件（equation.in）
文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。
输出文件（equation.out）
文件仅一行，包含一个整数，表示方程的整数解的个数。
输入样例
3
150
1 2
-1 2
1 2
输出样例
178
约束条件
1n6；1M150；
方程的整数解的个数小于231。
★本题中，指数Pi(i=1,2,……,n)均为正整数。
今日感想
把NOI、IOI的试题给咱做是闹哪样？？？
做了一天搜索，整个人都不好了
在一天的搜索中我得出了以下结论：
- 如果考试遇见正解为搜索的题目永远不要在打完其他题目之前做，否则就享受考试结束还没调好，最后其他题目没时间写成功爆0的“快感”吧
- 打出暴力以后一定要备份，之后每打完一个正确的剪枝一定要备份一次，既方便对拍检查正确性，又方便在考试结束却仍没调试完的时候采用之前的最优程序
- 剪枝一定得加一个检查一次，不然出错都不知道是哪里出的错
- 一定要注意细节，一个细节错误可能使整个程序崩溃
千里之堤，毁于蚁穴