光棍节过了，光棍们为了不想再过明年的光棍节，准备组队去向女神求爱。
女神面对一群光棍，准备进行一次筛选，筛选的条件就是看谁的运气比较好，自古运气就是实力的一部分嘛。
女神首先会给每个光棍编号（编号从0开始），但是光棍不知道，然后，女神要求光棍们给自己送随意数量的玫瑰，玫瑰数量由光棍们自己决定，可以不送，然后女神会数每个光棍送上来的玫瑰数，当光棍送给女神的玫瑰数量和女神给光棍的编号一样时，那么他就通过了女神第一轮的考验。
现在，告诉你女神总共收到的玫瑰数，同时告诉你每个玫瑰分别是谁送的，请找出能进入女神考验第二轮的幸运小光棍~
Input
输入包含多组数据，每组数据的第一行输入一个N，表示女神共收到N朵玫瑰，之后第二行输入N个数字，第i个数字表示第i朵玫瑰是谁送的。（0<=N<=100,0<= a[i] <=10^9,a[i]表示第i个数）；
Output
对于每组输入数据，输出通过第一轮筛选的幸运小光棍的编号，编号从小到大的顺序输出，每两个数中间有一个空格。
每两组输出数据之间有一个空行。
Sample Input
7
0 1 2 2 3 3 3
4
0 1 2 2
Sample Output
1 2 3
1 2
代码：
/*
思路：用数组标记+set输出
分析：
1 题目有个很大的陷进就是ai可以达到10^9，但是n最大只有100。那么根据n的值，我们可以知道最多有几个人。
2 假设现在有n朵玫瑰，那么最少一个人就是这个人送了n朵；最多n个人，每个人送一朵。所以可以知道当输入的ai>n的时候是没有用的，编号为ai的人根本送不了ai朵花（ai>n），所以只要把符合的找到然后用一个数组标记即可
3 输出的时候利用set的性质就可以。
代码：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
#define MAXN 110
int n;
int vis[MAXN];
int main(){
int num;
while(scanf("%d" , &n) != EOF){
memset(vis , 0 , sizeof(vis));
for(int i = 0 ; i < n ; i++){
scanf("%d" , &num);
if(num <= n)/*满足条件*/
vis[num]++;
}
set<int>s;
for(int i = 0 ; i <= n ; i++){
if(vis[i] == i)/*符合的插入set*/
s.insert(i);
}
/*输出*/
set<int>::iterator it;
it = s.begin();
printf("%d" , *it);
for(it++; it != s.end() ; it++)
printf(" %d" , *it);
printf("\n");
}
return 0;
}
第二题 谁能受到女神的垂怜之第二轮
恭喜通过了第二轮的光棍们！
不得不说，现在的光棍们运气都十分的好，因此，通过第一轮的人数还是太多了，无奈之下，女神绞尽脑汁想出了第二轮筛选方法，那就是，比谁的脑子反应快！
规则是这样的，女神告诉光棍们一个时间，包括了小时，分钟和秒，然后再告诉一个x，要让大家抢答，问在女神给出的时间的基础下，在经过了x秒之后的时间是多少？（不会出现24:00:00这样的时间，23:59:59之后的经过一秒的时间应该是00:00:00）;
Input
输入包含T组数据，第一行首先输入一个T，表示有T组数据，之后有T行输入数据，每行含有四个正整数，分别表示小时，分钟，秒，X。
Output
对于每组输入数据，首先输出他是第几组输出数据，之后再输出在女神给出的时间下经过x秒之后的时间，输出格式详见样例输出。对于不满足24小时计时原理的输入，则直接输出“u at keng wo!!”（不包含双引号）；
Sample Input
3
23 59 59 1
00 00 00 1
24 00 00 1
Sample Output
Case 1:
00:00:00
Case 2:
00:00:01
Case 3:
u at keng wo!!
代码：
/*
思路：枚举秒分时进行处理即可
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main(){
int t , h , m , x;
int Case = 1;
scanf("%d" , &n);
while(n--){
printf("Case %d:\n" , Case++);
scanf("%d%d%d%d" , &t , &h , &m , &x);
if(t < 0 || t >= 24 || h < 0 || h >= 60 || m < 0 || m >= 60)
printf("u at keng wo!!\n");
else{
int tmp = m+x;
m = tmp%60;
tmp = tmp/60;
tmp = h+tmp;
h = tmp%60;
tmp = tmp/60;
tmp = t+tmp;
t = tmp%24;
printf("%02d:%02d:%02d\n", t , h , m);
}
}
return 0;
}
第三题 sailspark的奇怪癖好
Sail有一个奇怪的癖好，喜欢养奇怪的宠物，虽然在省长要来检查，学校严明禁止养宠物，但他还是孜孜不倦的在自己的衣柜里养了一种很神奇的宠物，就暂时叫它spark吧。
Spark算是一种物种，里面包含着很多个种类，sail想对不同种类的spark进行混养，来了解在混养的时候，spark是否会发生什么变异等。
Spark是一种很神奇的物种，它不允许在自己的生活环境里有着另一只和他相同种类的spark存在，因此，在spark的生活范围内，对于每一个种类的spark只会有一只存在，要是有两只同一种类的spark生活在一起，有一只必将死去。
现在，首先sail对每一种类的spark进行编号（从0开始），假设刚开始的时候sail的衣柜是空的，之后，sail会定期往衣柜里放入某个种类的spark，或者定期查看里面所有的spark。
现在，给你两个操作，分别表示sail往衣柜里放某个种类的spark或者看柜子里spark的信息或者拿出某个种类的spark，请按照要求输出sail需要的信息。
操作1，添加，格式为“add x”，x表示加入的编号为x的spark种类的宠物一只。
操作2：查看所有spark，格式为“look”，之后按照字典序输出现在衣柜里包含的spark的相应的种类编号，每两个编号之间包含一个空格。
操作3：删除，格式为“delete x”，x表示sail将编号为x的spark种类的宠物拿出来，要是现在衣柜里没有第x种spark，则输出“error”，要是有则什么都不输出。
Input
输入数据直到文件尾，每一行代表一个操作。
Output
在读到“look”操作后，输出相应的信息。
Sample Input
add 0
look
add 1
look
add 1
look
delete 2
Sample Output
0
0 1
0 1
error
代码：
/*
思路：模拟
分析：
1 题目给定的只有三种操作，那么只要按照这三个操作进行模拟即可
2 开一个vis数组专门用来标记是否有该物种，初始化为0。假设现在加入一个编号为x的物种，那么就把vis[x] = 1，标记为1说明柜子里面有这个物种。
当遇到look的时候那么只要遍历这个数组遇到vis[i] = 1的就输出；如果是删除先判断是否vis[x] = 1，如果不是肯定是error，否则把vis[x] = 0重新标记为0说明没有该物种。
代码：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
#define N 10
char str[N];
int vis[MAXN];
int main(){
int num , mark , pos;
memset(vis , 0 , sizeof(vis));
pos = 0;
while(scanf("%s" , str) != EOF){
if(str[0] == 'a'){
scanf("%d" , &num);
vis[num] = 1;
}
if(str[0] == 'l'){
mark = 0;
for(int i = 0 ; i < MAXN ; i++){
if(vis[i]){
if(mark)
printf(" %d" , i);
else{
printf("%d" , i);
mark = 1;
}
}
}
printf("\n");
}
if(str[0] == 'd'){
scanf("%d" , &num);
if(!vis[num])
printf("error\n");
else
vis[num] = 0;
}
}
return 0;
}
第四题 简单的第k大
题目描述:
ACM世界有限无限科技不科技股份不股份有限无限公司开始了一年一度的校招。
本年度的问题只有一个：给定一个长度为n的只含字母的字符串，字典序第k大的子串是什么？
ACM的校招很特别，只要你答对了本道题，你可以不参加后续的面试直接进入公司。元芳，你看几个人能进ACM公司？
输入：
第一行是一个数字t，接着t块数据，每块数据包括两行，第一行是长度为n的字符串（n<=100000),只含字母，第二行是一个数字k(1<=k<=100000)。
输出:
每组数据输出相应的字符串，如果第k大的子串不存在请输出"No such line."。
每组数据后跟一空行。
样例输入:
3
orz
1
mm
2
abab
7
样例输出:
o
m
b
代码：
/*
思路：优先队列
分析：
1 假设有一个长度为len的字符串，那么这个字符串的全部的子串的个数为(1+2+3...+len) = len*(len+1)/2。
2 所以如果输入的k>len*(len+1)/2即2*k > len*(len+1)的时候那么肯定是不存在这种子串的。
3 那么我们利用优先队列
最开始先用字符数组s[]里面存入1个字符，因为肯定是1个字符开始，然后出队再将出队的那个字符的下一个字符合并再压入队列中，出队k-1次后第k次出队的就是第k大的。
比如abc，先进a,b,c，然后a先出，接着ab进，就这样反复模拟...
4 优先队列做法时间复杂度o(klogN),当k很大的时候是不可行的。
代码：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100010
int t , k;
char str[MAXN];
struct Node{
char s[MAXN];
int pos;
int index;
friend bool operator<(Node a , Node b){
if(strcmp(a.s , b.s) > 0)
return true;
return false;
}
};
priority_queue<Node>q;
int main(){
scanf("%d" , &t);
while(t--){
scanf("%s%d" , str , &k);
int len = strlen(str);
if(k*2 > len*(len+1)){
printf("No such line.\n\n");
continue;
}
while(!q.empty())
q.pop();
for(int i = 0 ; i < len ; i++){
Node node;
node.pos = 0;
node.index = i;
memset(node.s , '\0' , sizeof(node.s));
node.s[node.pos++] = str[i];
q.push(node);
}
for(int i = 0 ; i < k-1 ; i++){
Node tmp = q.top();
q.pop();
if(tmp.index != len-1){
tmp.s[tmp.pos++] = str[++tmp.index];
q.push(tmp);
}
}
printf("%s\n\n" , q.top().s);
}
return 0;
}
第五题 胖哥爱麻将I
胖哥在代表学校出战第三十七届ACM国际大学生程序设计竞赛亚洲区天津站时被一道”Mahjong”的题目卡住，结果痛失金牌。胖哥因此对这个世界充满了怨念，同时胖哥决定怒打麻将七天七夜。
我不会告诉你胖哥在打麻将的时候总是一个人充当四个人的角色，所以他从不一缺三。那夜，胖哥麻将打累了，突然发现桌上的麻将摆放地和window7系统盘里的文件放置相像，而胖哥的电脑里有很多的神秘文件，于是他又想起他一直担心的问题。
Windows窗口每行可以存放m个图标，现在胖哥有n个文件，编号从左到右，从上到下依次为1到n，其中神秘的文件编号是从a到b。胖哥有很多亲密的女性朋友，他担心有天他在浏览神秘文件时被女性朋友发现，所以他在想如何用最短的时间删除a到b的这些文件。每次，胖哥可以用鼠标拖出一个矩形，然后按Del键+Enter键删除矩形里面的文件。但胖哥觉得这样太慢，所以每次拖动一个矩形后胖哥都按一次Ctrl键，保存之前的选择，最后按一次Del键+Enter键。
现在的问题是给定n、m、a、b，问最少拖动几次鼠标能把编号a到编号b的所有文件都选中。
输入要求:
第一行是一个整数t，表示测试数据有t组，
紧接着t行数据，每行四个整数n、m、a、b(1<=n<=m<=10^9,1<=a<=b<=n).
输出要求:
输出t行，每行一个数，表示把编号a到编号b的所有文件都选中的最少鼠标拖动次数。
intput:
2
114 3 9
205 2 20
output:
3
2
Hint:
第一组样例选择情况如下:
第二组样例选择情况如下:
代码：
/*
思路：模拟题
分析：
首先先分析一下a 和 b可能的情况
1 a在行初始位置，b在行末尾或者b = n。那么只要1次即可
2 a在行初始位置，b不在行末尾。那么只要2次
3 a不在行初始位置，b在行末尾或者b = n。那么只要2次
4 a不在行初始位置，b不在行末尾。如果a和b同行那么只要1次；如果a和b上下行那么2次；如果a和b不是上下行，但是a在b的右边一列，只要2次（注意这个类型）；其它都是3次。
代码：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t;
int n , m , a , b;
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d%d%d%d" , &n , &m , &a , &b);
if(a == b || a == 1 && b == n)
printf("1\n");
else{
if((a-1)%m == 0){
if(b%m == 0 || b == n)
printf("1\n");
else
printf("2\n");
}
else{
if(b%m == 0 || b == n)
printf("2\n");
else{
int x = (a-1)/m;
int y = (b-1)/m;
if(x == y)
printf("1\n");
else if (x+1 == y || (a-1)%m-(b-1)%m == 1)
printf("2\n");
else
printf("3\n");
}
}
}
}
return 0;
}
第六题胖哥爱麻将II
题目描述:
胖哥在代表学校出战第三十七届ACM国际大学生程序设计竞赛亚洲区天津站时被一道”Mahjong”的题目卡住，结果痛失金牌。胖哥因此对这个世界充满了怨念，同时胖哥决定打麻将打七天七夜。
胖哥有两个女朋友，他每天都要找其中一个打麻将。其中一个叫做Dasha，在师大之北，另一个叫Masha，在师大之南，去师大北面的公交车a分钟一班，去师大南面的公交车b分钟一班，胖哥很注重效率，所以每次公交车一来他就马上上车。如果两班公交车同时到达，胖哥会选择时间间隔a、b中较大的那班车。
假设公交车一直在开，当胖哥到达车站时，公交车可能已经开很久了，但是会有一个时刻两部车同时到达站点。请问胖哥更经常去哪个女朋友那里。
输入要求:
第一行是一个整数t，表示测试数据有t组，
紧接着t行数据，每行两个整数a,b(a != b,1 <=a,b<=1000000)。
输出要求:
输出t行，每行输出一个字符串。
如果胖哥经常去Dasha那里，输出Dasha,如果胖哥经常去Masha那里，输出Masha，否则输出Equal。
sampleinput:
3
37
53
23
sampleoutput:
Dasha
Masha
Equal
Hint(看第三组数据)：
两班车同时到达站点的周期是6，那么我们可以认为每个周期都是 (0, 6]
当胖哥在(0,2]时间段到达站点，他将和Dasha打麻将。
当胖哥在(2,3]时间段内到达站点，他将和Masha打麻将。
当胖哥在(3,4]时间段到达站点，他将和Dasha打麻将。
当胖哥在(4,6]时间段内到达站点，两部车同时在第6分钟到达站点，但他要去Masha那里。
这样，胖哥去Dasha和去Masha的概率一样，所以输出Equal。
代码：
/*
思路：求gcd然后判断即可。
分析：
1 根据题目的分析，肯定是要求哪种公交车的来的次数多。
2 根据数据，我们只要求出两个数的最小周期，所以应该先求一下最大公约数，然后求出这个最小周期。
假设输入为8 20。那么gcd为4，那么最小的周期为10。所以时间段可以分成如下0 2 4 5 6 8 10。那么我们就可以知道结果。
3 其实通过上面的分析，我们可以知道最后的结果只跟最小周期有关，而最小周期只跟a b除去最大公约数后的两个数有关，那么认真分析可以知道通过比较这个两个数就可以知道ans。
代码：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000010
int vis[MAXN];
int gcd(int a , int b){
return b == 0 ? a : gcd(b , a%b);
}
int main(){
int t;
int a , b , pos;
scanf("%d" , &t);
while(t--){
scanf("%d%d" , &a , &b);
int ansN , ansS;
int tmp = gcd(a , b);
a = a/tmp;
b = b/tmp;
ansN = b-1 , ansS = a-1;
if(a > b)
ansN++;
else
ansS++;
if(ansN > ansS)
printf("Dasha\n");
if(ansN < ansS)
printf("Masha\n");
if(ansN == ansS)
printf("Equal\n");
}
return 0;
}
第7题 众神的黄昏
题目描述:
西元1年，众神国界陷入混乱，天地崩塌，神神自危，纷纷逃离众神国界。
胖神所住的胖神神殿也不得幸免。胖神的神殿坐落于正方形的平原之上，神殿由8*8个房间构成。胖神所在的地点为M,神殿的出口只有一个为A，胖神每秒可以向周围8个房间瞬移，也可以原地不动。因为神殿还未完全沦为废墟，胖神不得瞬移到神殿之外。神殿中有许多充满神力的石像，这些石像遇人杀人、遇神杀神。在胖神神殿崩塌的过程中，这些石像每一秒都会想南移动一格。
给定8*8的图，图中一定有M和A,还有若干的石像，胖神能否脱离神殿？
输入:
第一行是一个整数t，t<=20,接着是t块数据，每块数据为8*8的地图。
输入:
胖神若能逃离神殿，输出"YES"，否则输出"NO".
样例输入:
2
.......A
........
........
........
........
SSS.....
........
M.......
.......A
........
........
........
........
SS......
........
M.......
样例输出:
NO
YES
代码：
/*
思路：状态性的BFS
分析：
1 在每个节点里面保存一张地图，然后判断当前点能否入对即可。注意是胖哥先走，然后石像掉落。注意石像掉落后是堆在最底下的位置。
2 其它就是按照BFS的思路搜索即可。
代码：
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define N 8
typedef char state[N][N];
int t;
struct Point{
int x;
int y;
state s;
friend bool operator==(Point &p1 , Point &p2){
if(p1.x == p2.x && p1.y == p2.y)
return true;
return false;
}
};
Point star , end;
int dir[8][2] = {
{-1,0},{-1,1},{0,1},{1,1},
{1,0},{1,-1},{0,-1},{-1,-1}
};
queue<Point>q;
int vis[N][N];
bool BFS(){
while(!q.empty())
q.pop();
memset(vis , 0 , sizeof(vis));
q.push(star);
vis[star.x][star.y] = 1;
while(!q.empty()){
Point p = q.front();
q.pop();
if(p == end)
return true;
for(int i = 0 ; i < 8 ; i++){
int x = p.x+dir[i][0];
int y = p.y+dir[i][1];
if(p.s[x][y] == 'S' || vis[x][y] || x < 0 || x >= 8 || y < 0 || y >= 8)
continue;
/*求出下一秒的状态*/
state tmpState;
memcpy(tmpState , p.s , sizeof(p.s));
for(int i = 6 ; i >= 0 ; i--){
for(int j = 0 ; j < 8 ; j++){
if(tmpState[i][j] == 'S'){
tmpState[i+1][j] = 'S';
tmpState[i][j] = '.';
}
}
}
/*如果不是‘S’就可以走，不能写成=='.'，因为有可能是‘M’和‘A’。*/
if(tmpState[x][y] != 'S'){
vis[x][y] = 1;
Point pp;
pp.x = x , pp.y = y;
memcpy(pp.s , tmpState , sizeof(tmpState));
q.push(pp);
}
}
}
return false;
}
int main(){
scanf("%d%*c" , &t);
while(t--){
star.x = 7 , star.y = 0;
end.x = 0 , end.y = 7;
for(int i = 0 ; i < 8 ; i++){
scanf("%s" , star.s[i]);
}
printf("%s\n" , BFS() ? "YES" : "NO");
}
return 0;
}
第8题
小Z喜欢游山玩水，每次到一个地方他都会收集他喜欢的叶子，并把他们做成标本，有一天他收集了n个叶子，
他想用一本书把这些叶子夹起来，将叶子夹在相邻的两页之间，由于一些不可抗拒的人为原因，
每个叶子都有一个权值si，表示这个叶子与其它任意一叶子之间必须要有至少si页，
同时这个叶子和封头封尾之间也至少要有si页，问这本书最少需要有多少页才能把全部的叶子都夹进去
Input
输入包含多组数据，首先是一个数字T，表示共有T组测试数据，
每组数据首先输入一个数n，1<=n<=100，表示有n个叶子，
之后一行有n个数，1<=每个数<=100，表示每个叶子的权值
Output
每组样例输出一个数，表示一本书最少需要有多少页才能把这些叶子全部都夹进去
Sample Input
3
1
3
2
3 2
3
2 2 2
Sample Output
6
8
8
代码：
/*
思路：水题
分析：排序一下即ok
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
int n , m;
int s[MAXN];
int main(){
scanf("%d" , &n);
int ans;
while(n--){
scanf("%d" , &m);
memset(s , 0 , sizeof(s));
for(int i = 0 ; i < m ; i++)
scanf("%d" , &s[i]);
sort(s , s+m);
ans = 0;
for(int i = 0 ; i < m ; i++)
ans += s[i];
ans += s[m-1];
printf("%d\n" , ans);
}
return 0;
}
第九题
给定平面上三个点A,B,C，保证三点不共线，求三角形中的一个点，使得这个点到三边的距离的平方和最短，要求输出这个值
Input
输入包含多组数据，首先是一个数字T，表示共有T组测试数据，
每组测试数据6给数，分别为x1,y1,x2,y2,x3,y3,代表A,B,C三个点的坐标，坐标的范围为-100000~100000
Output
每组样例输出一个数，表示这个距离的平方和，保留4位小数
Sample Iutput
2
-1 0 1 0 0 1.73205
-647.60 -717.48 294.91 94.83 561.19 277.59
Sample Output
1.0000
472.8026
Hint
第一组样例是等边三角形
思路：
1到三角形三边距离平方和最小----重心的等角共轭点。
2
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int t;
struct Point{
double x;
double y;
};
Point p1 , p2 , p3;
double Distance(Point a , Point b){
double tmpx = 1.0*(a.x-b.x)*(a.x-b.x);
double tmpy = 1.0*(a.y-b.y)*(a.y-b.y);
return sqrt(tmpx+tmpy);
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%lf%lf" , &p1.x , &p1.y);
scanf("%lf%lf" , &p2.x , &p2.y);
scanf("%lf%lf" , &p3.x , &p3.y);
double area;
area = fabs((p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y));
area /= 2;
double s1 = Distance(p1 , p2);
double s2 = Distance(p1 , p3);
double s3 = Distance(p2 , p3);
double ans = (4*area*area)/(s1*s1+s2*s2+s3*s3);
printf("%0.4lf\n" , ans);
}
return 0;
}
本文由双子座的等待原创，转载请注明出处！
