3n+1 问题(10)
Problem Description
考虑以下算法：
1. input n
2. print n
3. if n == 1 then STOP
4. if n is odd then n = 3 * n + 1
5. else n = n / 2
6. GOTO 2.
给定输入 22，将输出以下数字序列
据推测，对于任何输入值，上述算法都将终止。尽管算法很简单，但不知道这个猜想是否正确。
给定输入 n，可以确定输出的数字（包括 1）。对于给定的 n，这称为 n 的循环长度。在上面的例子中，22 的循环长度是 16。
对于任何两个数字 i 和 j，您将确定 i 和 j 之间（包括 i 和 j）所有数字的最大循环长度。
Input
输入将由一系列整数 i 和 j 组成（i ≤ j），每行一对整数（输入保证不超过 10 行）。所有整数将小于 100000 且大于 0。您应该处理所有整数对，并且对于每对确定 i 和 j 之间（包括 i 和 j）的所有整数的最大循环长度。
Output
对于每对输入整数 i 和 j，您应该输出 i，j，i 和 j 之间的最大循环长度。这三个数字应由一个空格分隔，一行中三个数字，每行输入一行输出。整数 i 和 j 必须以与它们出现在输入中相同的顺序出现在输出中（在同一行上）。
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
Hint
思路：
暴力打表or直接模拟
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int num[100010];
int cnt(int n)
{
int ans=0;
while(n!=1)
{
if(n%2==1)
n=3*n+1;
else
n/=2;
ans++;
}
return ans+1;
}
void init()
{
for(int i=1;i<=100000;i++)
num[i]=cnt(i);
}
int main()
{
init();
int n,m;
while(~scanf("%d%d",&n,&m))
{
int maxx=-1;
for(int i=n;i<=m;i++)
maxx=max(maxx,num[i]);
printf("%d %d %d\n",n,m,maxx);
}
return 0;
}
喵星人(5)
Problem Description
据说 CGY 家里的喵星人很聪明，会计算十以内的加法。例如：现有数字 1，2，喵星人会用“Mia~Mia~Mia~”来表达答案是 3。
现在有请你来写一个程序，模拟这个过程。
Input
输入在一行中给出两个区间在 [1,9] 的正整数 A 和 B，用空格分隔
Output
在一行中输出有 A+B 个“Mia~”(不包含引号)。
Sample Input
2 1
Sample Output
Mia~Mia~Mia~
Hint
思路：
题解？！//大家都过了，没什么好说啦
#include <iostream>
using namespace std;
int main()
{
int a,b;
string mia="Mia~";
cin>>a>>b;
for(int i=0;i<a+b;i++)
cout<<mia;
cout<<endl;
return 0;
}
变换数字(20)
Problem Description
开学的第一节课是高数课，由于翁哥第一节课讲的东西实在是太无聊了，FS 开始了“钓鱼”模式。SLF 看 FS 实在是太困了，就给了他一个问题：现在黑板有一个数字 N，那么将这个数字反转相加M次之后的数字是多少？例如现在的数字 N=87，M=4，那么 87+78 = 165，165+561=726，726+627=1353，1353+3531=4884，最后的答案为 4884。
FS 玩了十分钟后觉得太无聊了，于是把这个 easy problem 交给你。
Input
输入一行，N，M，其中 N 为不超过 100 位的正整数，N 为十进制数，M 为整数且 0<=M<=30
Output
输出一行 ans，其中 ans 代表最后的答案
Sample Input
87 4
Sample Output
4884
Hint
87+78 = 165
165+561 = 726
726+627 = 1353
1353+3531=4884
思路：
方法一：C++模拟大数相加，即获得一个数反转过来相加即可
方法二：用JAVA得BigInteger输入，然后reserve相加完事
题目都说了最大有100位的非负整数，当然是用大数啦，不然怎么可能是道20分题:)
#include <iostream>
#include <cmath>
using namespace std;
string get_add(string s,int n){
int len = s.size();
string t = s;
for(int i = 0;i < ceil((double)len);i++){
s[i] = (char) (s[i]+t[len-i-1]-'0');
}
for(int i = len-1;i >= 1;i--){
if(s[i]-'0'>=n){
s[i-1] = (char) (s[i-1]+1);
s[i] = (char) (s[i]-n);
}
}
t = "";
if(s[0]-'0'>=n){
t = "1";
s[0] = (char)(s[0]-n);
}
return t+s;
}
int main(){
string n;
int m;
cin>>n>>m;
while(m--){
n = get_add(n,10);
}
cout<<n;
return 0;
}
简单的问题(15)
Problem Description
现在给你一个包含 0~9 和 A~F 的字符串，你需要求出在这个字符串中出现次数最多的字符，然后你需要求出这个字符串组成的十六进制转换为十进制的数。
Input
第一行读入一个整数 T(1≤T≤10)，代表数据组数。
接下来给出 T 行，
每行给出这个字符串
输入保证数组长度 ≤ 15
Output
每组输出两行
第一行表示出现次数最多的字符和出现的次数，用空格隔开。若有相同的次数，则输出字典序最小的。
第二行表示转换的十进制数
Sample Input
1
22011
Sample Output
4884
Hint
思路：
按题意模拟，注意一下输出的数字要用long long来存
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
string str;
cin>>str;
int n=str.length(),cnt[20];
long long number=0;
memset(cnt,0,sizeof(cnt));
for(int i=n-1;i>=0;i--)
{
if('A'<=str[i]&&str[i]<='F')
{
cnt[str[i]-'A'+10]++;
number+=pow(16,n-1-i)*(str[i]-'A'+10);
}
else
{
cnt[str[i]-'0']++;
number+=pow(16,n-1-i)*((str[i]-'0'));
}
}
int maxx=-1,pos;
char maxxc;
for(int i=0;i<16;i++)
{
if(maxx<cnt[i])
{
maxx=cnt[i];
pos=i;
}
}
if(pos<10)
maxxc=(char)('0'+pos);
else
maxxc=(char)('A'+pos-10);
cout<<maxxc<<" "<<maxx<<endl;
cout<<number<<endl;
}
return 0;
}
CGY 的第一课(5)
Problem Description
CGY开始学习编程了，今天是他上的第一课，老师让他把输入的数字照着原样输出。
Input
输入一个实数
Output
输出输入的数字N
Sample Input
123.88
Sample Output
123.88
Hint
思路：
实数包括所有小数和整数，所以要用字符串输入输出
#include <iostream>
using namespace std;
int main()
{
string in;
cin>>in;
cout<<in<<endl;
return 0;
}
轰炸(10)
Problem Description
SLF 现在正准备用他的超能力轰炸一片区域，在这片区域中有 N 座建筑，每个建筑的血量都是 M，SLF 携带的炮弹只能对一座建筑造成 X 点伤害，但发射炮弹需要消耗他的能量,第一发炮弹的能量为 3 点,并且发射炮弹需要的能量每次递增两点，即下一发的能量=上一发的能量+2，幸运的是每当 SLF 摧毁了一座建筑，他都可以获得 Y 点能量，SLF 一开始共有 Z 点能量，现在 SLF 想知道他最多可以炸掉多少建筑。
Input
第一行读入一个整数 T，代表数据组数。
接下来给出T行，
每行给出N,M,X,Y,Z
1≤T≤10，1≤N≤100，1≤M≤100，1≤X≤M，1≤Y≤100，1≤Z≤100
Output
每组数据输出一行，代表最多可以炸掉多少建筑
Sample Input
1
5 5 2 1 20
Sample Output
1
Hint
摧毁一座建筑需要3发炮弹，需要的能量为3+5+7=15，摧毁一座建筑后获得1点能量，所以总能量变为20-15+1=6，第四发炮弹发射需要能量为9点，无法再次发射，所以总共摧毁一座建筑
思路：
按题意模拟计算。注意考虑可摧毁数量大于n的时候。
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m,x,y,z,t;
cin>>n>>m>>x>>y>>z;
if(m%x) t = (m/x)+1;
else t = m/x;
int s1 = t*t + 2*t;
m = n;
while(n>0){
z-=s1;
if(z<0) break;
n--;
s1+=t*t*2;
z+=y;
}
cout<<m-n<<endl;
}
}
LXY 背单词(20)
Problem Description
LXY终于开始学英语了，然而他的记忆力有限，每当他看完一段文章，他最多记住每个字母开头对应的一个单词。“既然只能记住一个单词，那么当然记住最大的那个啊”——LXY。然而怎么定义最大这个概念呢，LXY决定按照字典顺序，记住最大的那个单词。
现在我们知道LXY即将会看到的文本，你能确定他会记住哪些单词么？
注：输入文本中的所有不同单词不计大小写，比如“Apple”，“aPPle”或“APPLE”都被视为相同的单词apple
Input
输入一串文本，直至文件结束。
Output
按照每个字母开头对应的字典序最大的单词，没有则不输出，单词统一由小写字母组成，一行输出一个。
注：任何不属于字母的符号都会区分单词，包括回车、数字。
Sample Input
Adventures in Disneyland
Two blondes were going to Disneyland when they came to a fork in the
road. The sign read: "Disneyland Left."
So they went home.
Sample Output
adventures
blondes
came
disneyland
fork
going
home
in
left
road
so
two
when
Hint
思路：
方法一：直接按题意模拟，注意输入格式的问题
方法二：用sstream将非字符赋值为空格，分割出单词之后模拟即可
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
string word[30];
void init()
{
for(int i=0;i<26;i++)
word[i]="0";
}
int main()
{
string in;
init();
while(getline(cin,in))
{
transform(in.begin(),in.end(),in.begin(),::tolower);
int n=in.length();
string thisword="";
for(int i=0;i<=n;i++)
{
if((in[i]>='a'&&in[i]<='z')&&i!=n)
{
thisword+=in[i];
}
else if(thisword.length()>0)
{
int pos=(thisword[0]-'a');
if(thisword>word[pos])
word[pos]=thisword;
thisword="";
}
}
}
for(int i=0;i<26;i++)
if(word[i]!="0")
cout<<word[i]<<endl;
return 0;
}
垃圾装箱(15)
Problem Description
CGY 老是说自己是垃圾，于是有一天，CGY 做梦梦到了自己真的变成了垃圾，而且是很多很多的垃圾。
众所周知 LXY 是一个环保主义者，于是学院重点垃圾 CGY 的回收处理工作就交由 LXY 来全权负责。
垃圾 CGY 分为三类：棕色 CGY、绿色 CGY 和透明 CGY。LXY 分别从宿舍、课室和机房收集来三个箱子（毕竟垃圾 CGY 只会被丢在这几个地方），每个箱子都包含指定数量的棕色、绿色和透明 CGY。LXY 需要移动这些垃圾 CGY，使得每个箱子里仅包含一种 CGY，这样才方便迫害回收再利用。
问题在于 LXY 太胖了，每次移动 CGY 都需要消耗一定的力气，于是他想尽量减少移动的数量。//虽然 LXY 把 CGY 丢下楼的难度比吃生菜还简单（甚至能一次丢好几个）
出于此目的，可以假设每个箱子都足够大（毕竟 CGY 体积小而且还算是限定版垃圾）。
Input
输入包括多行，每行包含由空格分隔的 ⑨ 个整数。每三个整数表示第 i 个箱子中的棕色、绿色和透明 CGY 的数量。例如：
表示第一个箱子有 20 个透明 CGY，第二个箱子有 12 个绿色 CGY，第三个箱子有 15 个棕色 CGY。
垃圾 CGY 总数不会超过 2^31。
Output
对于每行输入，应输出每个箱子装的 CGY 的种类和最少的 CGY 移动数量。
大写字母 'B'，'G'，'C' 分别表示棕色、绿色和透明，字符串中的第 i 个字符表示第 i 个箱子中装的 CGY 的种类。
CGY 移动数量应在种类字符串后面，用空格隔开。
如果有多个解，则应输出字典序最小的种类字符串。
Sample Input
1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10
Sample Output
BCG 30
CBG 50
Hint
思路：
题目意思是三个混合装有三种不同物品的箱子，移动物品使得三个箱子只装同一种东西并要求移动的总数量最少。
因为只有BCG三种情况，枚举情况为321=6种，所以直接枚举所有箱子可能的情况即可，然后取最小值，顺带要注意题目中的字典序要求。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
string part[6]={"BCG","BGC","CBG","CGB","GBC","GCB"};
int part_sum[6],r[3][3];
int main()
{
while(~scanf("%d",&r[0][0]))
{
scanf("%d%d",&r[0][1],&r[0][2]);
for(int i=1;i<3;i++)
for(int j=0;j<3;j++)
scanf("%d",&r[i][j]);
memset(part_sum,0,sizeof(part_sum));
part_sum[0]=r[1][0]+r[2][0]+r[0][1]+r[1][1]+r[0][2]+r[2][2];
part_sum[1]=r[1][0]+r[2][0]+r[0][1]+r[2][1]+r[0][2]+r[1][2];
part_sum[2]=r[0][0]+r[2][0]+r[0][1]+r[1][1]+r[1][2]+r[2][2];
part_sum[3]=r[0][0]+r[1][0]+r[0][1]+r[2][1]+r[1][2]+r[2][2];
part_sum[4]=r[0][0]+r[2][0]+r[1][1]+r[2][1]+r[0][2]+r[1][2];
part_sum[5]=r[0][0]+r[1][0]+r[1][1]+r[2][1]+r[0][2]+r[2][2];
int minn=99999999,pos=-1;
for(int i=0;i<6;i++)
{
if(part_sum[i]<minn)
{
minn=part_sum[i];
pos=i;
}
}
cout<<part[pos]<<" "<<minn<<endl;
}
return 0;
}
301 网络修复(25)
Problem Description
这个学期以来，信息中心301的有线网络一直用不了，LXY和CGY为此很苦恼。在院长一声令下修好了灯之后，网络中心的人终于来301修复网络了。老师经过排查告诉LXY：301的交换机有多余的回路存在，导致局域网不能正常的工作。为了解决这个问题，必须拆掉多余的线路，保证任意两台交换机之间只有一条联通路存在。同时，由于网线的材质不同，每一条网线的延迟也不一样，LXY希望最后留下来的线路的延迟最小。
然而CGY在垃圾的梦中，LXY在捡垃圾，你能告诉他们该留下的线路延迟最小是多少么？
Input
第一行两个正整数n(n<=100),k(k<=n^2)
接下来的k行每行三个正整数i j m，表示i,j两台交换机之间有网线联通，延迟为m。
Output
最后留下的网线的最小延迟。
Sample Input
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
Sample Output
11
Hint
思路：
最小生成树模板题
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct temp{
int i,j,c;
}a[10010];
int f[110];
int find_father(int x){ return f[x]==x?x:f[x] = find_father(f[x]);}
bool cmp(temp&s1,temp&s2){return s1.c<s2.c;}
int main(){
int n,m,total = 0;
cin>>n>>m;
for(int i = 1;i<=n;i++) f[i] = i;
for(int i = 0;i<m;i++) cin>>a[i].i>>a[i].j>>a[i].c;
sort(a,a+m,cmp);
for(int i = 0;i<m;i++){
int x = a[i].i,y = a[i].j,c = a[i].c;
if(find_father(x) != find_father(y)){
f[find_father(x)] = find_father(y);
total+=c;
}
}
cout<<total;
return 0;
}
Best match(25)
Problem Description
总所周知，大名鼎鼎的 JB-ICPC 是一个三人组队的电子竞技比赛，只有三人齐心协力优势互补才能在比赛中 AC 尽可能多的题目。
香农先修班选出了 ⑨ 位优秀的 JBer，由他们进行组队参加新一年的 JB-ICPC 区域赛，争取为 SCNUSE 拿下尽可能多的奖，甚至是 World Final 名额。
SLF 和 FS 作为新一届先修班的负责人犯难了，因为他不知道如何将这几个人分成三个组，毕竟有些人的优势是重叠的导致总共能 AC 的题目数量较少。
又或者说有些人根本不想和某些人一起组队，毕竟人和人之间的关系总是要比算法难处理得多，对吧……
老前辈 LXY 给出战术指导换家，把所有能组合在一起的三人组合得出的 AC 题数统计起来，选出不重合的三组队员使得三队的 AC 数最高，就可以保证三队都能稳定打铁拿奖了。
SLF 和 FS 只得照办，统计出所有可能的组合，然后丢给决策自动机 CGY 来处理。问题在于，CGY 还在变成垃圾的梦里没醒来，那你懂我意思了吧？
Input
输入包含最多 100 个测试样例。
每个样例第一行是一个整数 n（0 < n < 81），即可能的组合数。
接下来的 n 行，每行包含 4 个正整数 a,b,c,s（1 ≤ a < b < c ≤ 9,0 < s < 10000），这意味着（a,b,c）这个组合可以 AC s 道题。（输入保证不会有重复出现的组合）
最后一组样例只有一个 0，不需要处理。
Output
对于每个测试样例，输出样例编号和最高分。如果组不成三支队，输出 -1。
Sample Input
3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0
Sample Output
Case 1: 6
Case 2: -1
Hint
思路：
n最大81，所以直接DFS暴力搜索，因为搜索次数最大为C(3,80),不会超时。
用DFS列出所有的组合的可能性，最后判断当前组合是否符合题意即没有重复的队员，符合就更新一下最大值即可。
#include <iostream>
#include <cstring>
using namespace std;
int n,a[100][4],t[3],res;
bool f[100];
void dfs(int curn){
if(curn == 3){
int curac = 0,tt;
bool flag[10] = {false};
for(int i = 0;i<3;i++){
tt = t[i];
curac+=a[tt][3];
for(int j = 0;j<3;j++)
flag[a[tt][j]] = true;
}
for(int i = 1;i<=9;i++)
if(!flag[i]) return;
res = max(res,curac);
return;
}
for(int i = 0;i<n;i++){
if(!f[i]){
f[i] = true;
t[curn] = i;
dfs(curn+1);
f[i] = false;
}
}
}
int main(){
int k = 0;
while(cin>>n &&n!=0){
for(int i = 0;i<n;i++)
cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
memset(f,false,sizeof(f));
res = -1;
dfs(0);
cout<<"Case "<<++k<<": "<<res<<endl;
}
return 0;
}
电子字典(25)
Problem Description
slf正在为他的英语考试做准备，为此他给自己写了一个电子字典，字典含有以下功能：
- 添加
添加操作的格式为：insert 单词 频次
例如：insert helpful 5
意思是添加helpful这个单词，频次为5。如果再次执行insert helpful 5 操作时，helpful的频次变为10。 - 删除
删除格式为：delete 单词
例如：delete helpful
意思是删除字典中helpful这个单词。
若当前版本的电子字典中没有要删除的单词，则输出”Empty”(不含引号)。 - 查询
查询的格式为：query 单词
例如：query ful
意思是查询当前版本的电子字典中以ful结尾的所有单词词频总和，然后输出结果。
Input
第一行读入一个整数 T，代表数据组数。
每组数据的第一行读入一个整数 N 代表操作数。
接下来 N 行，每行形容一个操作。
保证数据满足 1≤T≤10， 1≤N≤1000，insert操作的字符串总长度之和≤30000，所有字符串长度≤10000
输入只有小写字母
Output
根据题目要求输出
Sample Input
1
6
insert helpful 8
query ful
insert careful 9
query ful
delete helpful
query ful
Sample Output
8
17
9
Hint
思路：
按题意模拟，把输入的每一个单词都取出其所有后缀，然后插入map中。查询时直接查后缀的个数。
注意：某单词有可能是另外一个单词的后缀，例如单词e是Apple的后缀，所以删除某单词所有后缀的时候要注意有可能会把另外一个单词给删掉。
比较好想的办法就是采用两个map，一个dic记录后缀，一个com记录完整单词。
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<string,int> dic,com;//dic记录后缀，com记录完整单词，用于del
void ins(string str,int key);
void del(string str);
int que(string str);
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
while(n--)
{
string op,str;
cin>>op>>str;
if(op=="insert")
{
int key;
cin>>key;
ins(str,key);
}
else if(op=="delete")
{
del(str);
}
else
{
cout<<que(str)<<endl;
}
}
dic.clear();
com.clear();
}
return 0;
}
void ins(string str,int key)
{
if(com.count(str)==0)
com.insert(map<string,int>::value_type(str,key));
else
com[str]+=key;
int n=str.length();
for(int i=0;i<n;i++)
{
string insstr=str.substr(n-i-1);
if(dic.count(insstr)==0)
dic.insert(map<string,int>::value_type(insstr,key));
else
dic[insstr]+=key;
}
}
void del(string str)
{
if(com.count(str)==0)
cout<<"Empty"<<endl;
else
{
int num=com[str],n=str.length();
for(int i=0;i<n;i++)
{
string delstr=str.substr(n-i-1);
dic[delstr]-=num;
}
com.erase(str);
}
}
int que(string str)
{
if(dic.count(str)==0)
return 0;
return dic[str];
}
体育老师的烦恼(25)
Problem Description
学期结束了，学校准备将学生的体育成绩进行一个排名，具体排名规则如下。
首先按照学生的期末成绩进行排序，成绩高的在前。
其次是按照学生的期中成绩 40% 和平时成绩 60% 相加后的成绩进行排序，成绩高的在前。
最后是按照学生的学号进行排序，学号小的在前。
PS：所有学生的学号长度一致，数字小的在前。
数学不好的体育老师找到了 CGY 来帮他解决这个问题，CGY 觉得太简单的于是丢给背锅侠 FS 来做。由于这段时间 FS 实在是太忙了，于是将问题抛给了你。
Input
输入 n 表示学生人数(n<=10000)，接下来的 n 行，每行从前往后给出学生的学号(位数为 11 位)，学生姓名(不大于 10 位的字符串，无空格)，期末成绩(不大于 100 的非负整数)，期中成绩(不大于 100 的非负整数)，平时成绩(不大于 100 的非负整数)。
Output
输出 n 行，一人一行，输出格式与输入格式相同
Sample Input
6
20152000100 Tim 60 60 60
20052001323 Su 90 60 100
20173999099 Lily 90 90 80
20163334123 Ming 90 90 80
20143727429 Boy 90 80 90
20184732198 Tom 100 90 90
Sample Output
20184732198 Tom 100 90 90
20143727429 Boy 90 80 90
20052001323 Su 90 60 100
20163334123 Ming 90 90 80
20173999099 Lily 90 90 80
20152000100 Tim 60 60 60
Hint
思路：
本题考察结构体排序，不过有个注意点是要注意浮点数的精度误差。
最佳的做法就是采用整数来存，然后将期中成绩4，平时成绩6再来比较即可。
//float精度比double低所以会丢失一些精度，用float反而会AC，用double不考虑精度问题的话肯定是会WA的。
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Student{
string snumber;
string sname;
int ends;
int mid;
int pin;
int quan;
};
bool cmp(Student student1,Student student2)
{
if(student1.ends==student2.ends)
{
if(student1.quan==student2.quan)
{
return student1.snumber<student2.snumber;
}
else
{
return student1.quan>student2.quan;
}
}
else
return student1.ends>student2.ends;
}
Student student[10010];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>student[i].snumber>>student[i].sname>>student[i].ends>>student[i].mid>>student[i].pin;
student[i].quan=student[i].mid*4+student[i].pin*6;
}
sort(student,student+n,cmp);
for(int i=0;i<n;i++)
{
cout<<student[i].snumber<<" "<<student[i].sname<<" "<<student[i].ends<<" "<<student[i].mid<<" "<<student[i].pin<<endl;
}
return 0;
}
避铳(30)
Problem Description
我们希望在一块 n × n 的棋盘上放置 n 个象棋中的車，但受到以下限制：
· 第 i 个車只能放置在一个给定的左上角为 (xl[i],yl[i]) 和右下角为 (xr[i],yr[i]) 的矩形内，其中 1 ≤ i ≤ n，1 ≤ xl[i] ≤ xr[i] ≤ n，1 ≤ yl[i] ≤ yr[i] ≤ n。
· 任意两个車都不可以相互攻击，也就是不能放铳（迫真），也就是说，没有两个車可以占据同一列或同一行。
你的任务是找到有没有满足上述条件的車的放置。
Input
输入包含几个测试用例。每个的第一行包含一个整数 n（n ≤ 5000），即棋盘的大小。然后是 n 行，其中的第 i 行给出了 xl[i]，yl[i]，xr[i] 和 yr[i]。输入最后是一个 0，不需要处理。
Output
如果有这种放置 play，输出 "Tenpai"，反之输出 "Ron"。
Sample Input
8
1 1 2 2
5 7 8 8
2 2 5 5
2 2 5 5
6 3 8 6
6 3 8 5
6 3 8 8
3 6 7 8
0
Sample Output
Tenpai
Hint
思路：
因为車是只能攻击同一行或同一列的車，所以可以将这个二维问题分解为两个一维问题。
是否能在x上的若干个区域内选出n个不同的x值，在y上的若干个区域内选出n个不同的y值。(每个区域只能选一个值)
若都能满足则输出"Tenpai"，不能则输出"Ron"。
可以用贪心法来处理这个一维问题。
设若干个区域为[l,r]，对r值进行升序排序，如果r值相同则根据l值进行升序排序。
排完序之后从前往后遍历，再从li遍历取第一个没有被标记的值，如果这个值大于ri，则表明没有解，小于等于ri则将这个值标记。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct temp{
int x1,x2;
int y1,y2;
}a[5010];
bool cmp1(const temp&s1,const temp&s2){
if(s1.x2==s2.x2)
return s1.x1<s2.x1;
else
return s1.x2<s2.x2;
}
bool cmp2(const temp&s1,const temp&s2){
if(s1.y2==s2.y2)
return s1.y1<s2.y1;
else
return s1.y2<s2.y2;
}
bool visx[5010],visy[5010],flag;
int main(){
int n;
while(cin>>n && n!=0){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
flag = true;
struct temp t;
for(int i = 0;i<n;i++){
cin>>t.x1>>t.y1>>t.x2>>t.y2;
a[i] = t;
}
if(flag){
sort(a,a+n,cmp1);
for(int i = 0;i<n;i++){
t = a[i];
int curx = t.x1,x2 = t.x2;
while(visx[curx]){//寻找第一个未标记值
curx++;
}
if(curx>x2){//判断是否这个值是否超过当前区间最大值
flag = false;
break;
}
visx[curx] = true;
}
}
if(flag){
sort(a,a+n,cmp2);
for(int i = 0;i<n;i++){
t = a[i];
int cury = t.y1,y2 = t.y2;
while(visy[cury]){
cury++;
}
if(cury>y2){
flag = false;
break;
}
visy[cury] = true;
}
}
if(flag)
cout<<"Tenpai"<<endl;
else
cout<<"Ron"<<endl;
}
return 0;
}
总结：
//这次比赛涌现了好多meng男，tqltql
网友评论