袁绍的刁难(recruitment.c/cpp/pas, 1s, 128M)
[题目描述]
黄巾之乱后，郭嘉到了袁绍的统辖地区，结果袁绍想给我们的郭嘉大大一个下马威，且正值他招募将领的时候，于是乎，袁绍就让郭嘉大大去替他招募将领。
这时候有很多很多的将领到袁绍处报到，每个将领的编号依次为1、2、3……N，第i个将领的武力值为3^(i-1)。
袁绍需要我们的郭嘉大大招纳任意个将领，而郭嘉选中的将领有一个“总武力值”为各个将领的武力值之和。例如：郭嘉这一次招募了第一个将领和第三个将领，那么“总武力值”为1+9=10。
袁绍想知道，他可以获得的第k大的“总武力值”是多少，请你帮助我们的郭嘉大大告诉袁绍这个第k大的“总武力值”。
[输入格式]
输入数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。
[输出格式]
输出包含n行，每行输出一个对应的结果。
[输入样例]
1
7
[输出样例]
13
[样例说明]
郭嘉能够拿到的总武力值从小到大为1、3、4、9、10、12、13……所以第7大的总武力值是13。
[数据范围]
对于50%的数据，有k≤5000。
对于100%的数据，有k≤2^31-1。
游历的路线(lines.pas/c/cpp, 1s, 128Ms)
[题目描述]
我们的郭嘉大大经过一段时间发现了袁绍这个人干大事而惜身，见小利而忘义，又逢曹操在招兵买马，决定逃离袁绍去投曹操，而我们的曹操在第M天招募良材，我们的郭嘉大大既不能早去，也不能晚去，于是乎，他就趁着这一段时间到其他的城市游历一番，而每两个城市之间只能坐马车来往，由于我们的郭嘉大大很贪钱，他想用最少的费用，所以需要我们帮他求出这一个最小的费用。
[输入格式]
第一行包含两个数n，m， 表示有n个城市，和m天后曹操招纳良材。城市一就是郭嘉所在的城市，城市n就是曹操处。接下来n * (n – 1)行描述马车乘坐表。第2到第n行就是描述的城市1到2… n的马车乘坐表，第n + 1到第2n – 1行描述的城市2到城市1，3..n的马车乘坐表……对每一行，首先有一个数T，表示城市I到城市J的马车以T为周期，接下来有T个数，表示每天的马车的价格，如果价格为0则表示没有马车可坐。（n <= 100, m <= 200, T <= 20， Price <= 50000）
[输出格式]
如果存在这样的路线使郭嘉第m天到达曹操处，则输出最少的费用，否则输出0！
[输入样例]
3 5
2 130 150
3 75 0 80
2 110 100
4 60 70 60 50
3 0 135 140
2 70 80
[输出样例]
355
老师的询问(baffles.c/cpp/pas, 1s, 128M)
[题目描述]
东汉末年，颖川书院，有一日老夫子给他的学生出了一道问题，书院中有一口清澈见底的池塘（什么都看得见），老夫子要吃鱼，池塘里有很多很多鱼，而池塘是一个n*m的矩形，他希望放置最少的挡板，将池塘分成很多个矩形（包括正方形），使得每个矩形里有且只有一条鱼，而作为老夫子学生的郭嘉很想完成这个任务，所以他把这个任务交给了你，希望你能很快地解决问题。
例如n=4，m=3时的一种情况（0表示小方格内无鱼，1表示有鱼）：
0 1 0
0 0 0
1 0 1
0 0 0
可以这么分：
0 1 0
0 0 0
– – –
1|0 1
0|0 0
由于池塘边框不需要放置挡板，所以这个分割方案所需的挡板总长度为5。
[输入数据]
第一行有两个整数n和m（1≤n,m≤32），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。
[输出数据]
对于每组输入数据，输出一行：一个数字，所需挡板的最短总长度。
[输入样例]
4 3
0 1 0
0 0 0
1 0 1
0 0 0
[输出样例]
5
游历的路线(lines.pas/c/cpp, 1s, 128Ms)
[题目描述]
我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（N现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细。
[输入格式]
输入文件的第一行为N，第二行至第N+1行为N*N的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能将消息直接传递给奸细J）。
[输出格式]
输出文件只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。
[输入样例]
8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0
[输出样例]
2
Leave a Reply