Problem A: 奇怪的排序
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 22 Solved: 13
[Submit][Status][Web Board]
Description
最近，Dr. Kong 新设计一个机器人Bill。这台机器人很聪明，会做许多事情。惟独对自然数的理解与人类不一样,它是从右往左读数。比如，它看到123时，会理解成321。让它比较23与15哪一个大，它说15大。原因是它的大脑会以为是32与51在进行比较。再比如让它比较29与30，它说29大。
给定Bill两个自然数A和B，让它将 [A，B] 区间中的所有数按从小到大排序出来。你会认为它如何排序？
Input
第一行： N 表示有多少组测试数据。
接下来有N行，每一行有两个正整数A B 表示待排序元素的区间范围。
2<=N<=5 1<=A<=B<=200000 B-A<=50。
Output
对于每一行测试数据，输出一行，为所有排好序的元素，元素之间有一个空格。
Sample Input
2
8 15
22 39
Sample Output
10 8 9 11 12 13 14 15
30 31 22 32 23 33 24 34 25 35 26 36 27 37 28 38 29 39
处理一下排序就好。。
#include<bits/stdc++.h>
using namespace std;
int T;
int s,e;
class A
{
public:
int now,ori;
};
bool operator < (const A &a,const A &b)
{
return a.now<b.now;
}
A a[1000000],b[1000000];
int n=0;
A calc(int t)
{
if(a[t].now)return a[t];
int tt=a[t].ori;
while(tt)
{
a[t].now*=10;
a[t].now+=(tt%10);
tt/=10;
}
return a[t];
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
n=0;
scanf("%d %d",&s,&e);
for(int i=s;i<=e;i++)
{
a[i].ori=i;
b[n++]=calc(i);
}
sort(b,b+n);
for(int i=0;i!=n;i++)
{
if(i)printf(" ");
printf("%d",b[i].ori);
}
printf("\n");
}
}
return 0;
} Problem B: 最强DE战斗力
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 30 Solved: 8
[Submit][Status][Web Board]
Description
春秋战国时期，赵国地大物博，资源非常丰富，人民安居乐业。但许多国家对它虎视眈眈，准备联合起来对赵国发起一场战争。
显然，面对多个国家的部队去作战，赵国的兵力明显处于劣势。战斗力是决定战争成败的关键因素，一般来说，一支部队的战斗力与部队的兵力成正比。但当把一支部队分成若干个作战队伍时，这个部队的战斗力就会大大的增强。
一支部队的战斗力是可以通过以下两个规则计算出来的：
1.若一支作战队伍的兵力为N，则这支作战队伍的战斗力为N；
2.若将一支部队分为若干个作战队伍，则这支部队的总战斗力为这些作战队伍战斗力的乘积。
比如：一支部队的兵力为5时的战斗力分析如下：
情况
作战安排
总的战斗力
1
1，1，1，1，1（共分为5个作战队伍）
11111=1
2
1，1，1，2 （共分为4个作战队伍）
111*2=2
3
1，2，2 （共分为3个作战队伍）
122=4
4
1，1，3 （共分为3个作战队伍）
113=3
5
2，3 （共分为2个作战队伍）
2*3=6
6
1，4 （共分为2个作战队伍）
1*4=4
7
5 （共分为1个作战队伍）
5=5
显然，将部队分为2个作战队伍（一个为2，另一个为3），总的战斗力达到最大！
Input
第一行： N 表示有N组测试数据。 (2<=N<=5)
接下来有N行，每行有一个整数Ti 代表赵国部队的兵力。 （1 <= Ti <= 1000）i=1，…N
Output
对于每一行测试数据，输出占一行，仅一个整数S， 表示作战安排的最大战斗力。
Sample Input
2
5
4
Sample Output
6
4
本来以为是dp，打个表就好了，然而打完一看，越界了。
1000个人，假如全2人两人分，是2^500，好吧不是DP而是个大数问题，那么问题来了。
是不是有最优的分解方式呢？
具体分析见：https://blog.csdn.net/u012349696/article/details/45098941
感谢大佬。
之后就模拟一下大数相乘就好。
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
int T,n;
int a[maxn];
int cnt=0;
void f(int t)
{
for(int i=0;i!=cnt;i++)
{
a[i]*=t;
}
int cnt2=0;
while(cnt2<=cnt)
{
if(a[cnt2]>9)
{
int nextt=cnt2+1;
a[nextt]+=(a[cnt2]/10);
a[cnt2]%=10;
if(nextt>=cnt)cnt++;
}
cnt2++;
}
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
memset(a,0,sizeof(a));
a[0]=1;
cnt=1;
scanf("%d",&n);
if(n<=4)printf("%d\n",n);
else
{
int re=n%3;
int de=n/3;
if(re==1)
{
de--;
re=4;
}
if(re)f(re);
while(de--)f(3);
for(int i=cnt-1;i>=0;i--)
{
printf("%d",a[i]);
}
printf("\n");
}
}
}
return 0;
} Problem C: 试 制 品
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 12 Solved: 6
[Submit][Status][Web Board]
Description
ZZ大学的Dr.Kong最近发现实验室的很多试制品都已经用完。由于项目经费有限，为了节省，Dr.Kong决定利用实验室现有的试制品来生成所缺的试制品。为此，Dr.Kong连续几天通宵达旦整理出一份研究资料并让研究生Bill去实验并统计能产生多少种所缺的试制品。
Bill从头到尾翻完所有的资料，发现资料上写满了一大堆的化学方程式，上面除了大小写英文字母、数字、加号、等号外，再也没有其他的符号了。其中，每个方程式都是A1+A2+……+Ap=B1+B2+……+Bq的形式， 表示试制品A1,A2,……和Ap反应，生成了试制品B1,B2,……,Bq。其中Ai和Bj都是一种单质或化合物的化学式(长度不超过10个字符)，1≤p,q ≤ 20 。每个方程式的总长不超过100个字符。有些试制品的化学式可能在现代社会的化学元素周期表里找不到，这是由于化学反应过程中可能又有物理反应导致的结果。
Bill头疼了，从哪个实验开始呢？你能帮助他吗？
Input
第一行： N 表示Dr.Kong写的化学方程式个数 （1≤ N ≤ 400）
接下来有N行, 每一行是一个方程式。
再接下来的一行：M 表示已有多少种试制品。 (1≤ M ≤500)
接下来有M行，每一行是已有的一种试制品的化学式。
Output
第一行包含一个数T，表示可以产生多少种所缺的试制品。
在接下来的T行中，按ASCII码升序输出产生的试制品的化学式。
Sample Input
4
H2O+Na=NaOH+H2
Cl2+H2=HCl
Fe+O2=Fe3O4
NaOH+HCl=H2O+NaCl
3
H2O
Na
Cl2
Sample Output
4
H2
HCl
NaCl
NaOH
这道题给我的启示就是，该暴力写就暴力写，不要总想着映射啊，优化啊，节省空间啊。
你先写出来个暴力的好不好。
一开始就想着优化，导致自己在编写的时候自己给自己找麻烦。
Orz
#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
int n,m;
map<string,int> map1;
set<string> set1;
int cnt=0;
bool vis[maxn];
class F
{
public:
set<string> s1,s2;
};
F f[maxn];
string str;
set<string> ans;
void init()
{
map1.clear();
for(int i=0;i!=maxn;i++)
{
f[i].s1.clear();
f[i].s2.clear();
}
set1.clear();
memset(vis,0,sizeof(vis));
ans.clear();
}
void out()
{
set<string>::iterator it;
for(it=set1.begin();it!=set1.end();it++)
{
cout<<*it<<endl;
}
cout<<endl;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
init();
cnt=1;
cin.get();
for(int i=0;i!=n;i++)
{
getline(cin,str);
string t="";
int j=0;
for(j=0;j!=str.size();j++)
{
if(str[j]=='=')break;
if(str[j]=='+')
{
f[i].s1.insert(t);
t="";
}
else
{
t+=str[j];
}
}
f[i].s1.insert(t);
j++;
t="";
for(;j!=str.size();j++)
{
if(str[j]=='+')
{
f[i].s2.insert(t);
t="";
}
else
{
t+=str[j];
}
}
f[i].s2.insert(t);
// set<string>::iterator it;
// for(it=f[i].s1.begin();it!=f[i].s1.end();it++)
// {
// cout<<*it<<" ";
// }
// cout<<" ----> ";
// for(it=f[i].s2.begin();it!=f[i].s2.end();it++)
// {
// cout<<*it<<" ";
// }
// cout<<endl;
}
scanf("%d",&m);
cin.get();
for(int i=0;i!=m;i++)
{
getline(cin,str);
set1.insert(str);
}
bool flag=1;
while(flag)
{
flag=0;
for(int i=0;i!=n;i++)
{
if(vis[i])continue;
bool flag1=1;
set<string>::iterator it;
for(it=f[i].s1.begin();it!=f[i].s1.end();it++)
{
if(set1.find(*it)==set1.end())
{
flag1=0;
break;
}
}
if(flag1==0)continue;
flag=1;
for(it=f[i].s2.begin();it!=f[i].s2.end();it++)
{
if(set1.find(*it)==set1.end())
{
ans.insert(*it);
set1.insert(*it);
}
}
vis[i]=1;
}
}
cout<<ans.size()<<endl;
set<string>::iterator it;
for(it=ans.begin();it!=ans.end();it++)
{
cout<<*it<<endl;
}
}
return 0;
} Problem D: 遥 控 器
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 6 Solved: 2
[Submit][Status][Web Board]
Description
Dr.Kong 有一台高级电视机，这台电视机可以接受100个频道（从0到99编号）。电视的配套遥控器有13个按钮：
1 2 3 ↑
4 5 6 ↓
7 8 9
— 0
当按"↑"键时，当前频道编号会增加1(如果当前为99频道，则会切换到0频道)。如果按"↓"键，当前频道编号会减小1(如果当前为0频道，则会切换到99频道)。当要切换到09频道时，可以直接在遥控器上按相应的键。当要切换到1099频道时，可以先按"—"键，然后按2个与频道编号相对应的数字键(即先按与频道编号的十位数字相对应的键，然后按与个位数字相对应的键)。
由于遥控器长时间的使用和某些未知原因，遥控器上的某些键已经坏了，不能再起作用了。现在你的任务是，能否告诉Dr.Kong，如何用最少的按键次数来将频道从编号X切换到编号Y。
Input
第一行： N 表示有N组测试数据。 (1<=N<=5)
对每组测试数据有5行，前4行包含遥控器上每个按键的信息。0表示对应的键坏了，1表示对应的键可以使用。第5行包含2个整数，分别是X 和 Y (0 <= X <= 99; 0 <= Y <= 99)。
Output
对每组测试数据输出一行，即将频道从编号X切换到编号Y所需要的最小按键次数。如果不可能将频道从编号X 切换到编号Y，则输出-1.
Sample Input
2
0 0 1 1
1 1 1 1
1 1 1
1 1
23 52
1 1 1 0
1 1 1 0
1 0 1
0 1
23 52
Sample Output
4
-1
最小的步数嘛，然后考虑到电视台的总数又不多，所以广搜一波就好。
但是注意采用那个 - 功能键，来进行双数台的跳转的时候需要用三步，可能比单步功能键慢。
我们在使用单步键时，要对这个进行一下优化距离就好
#include<bits/stdc++.h>
using namespace std;
int T;
bool on[13];
int x,y;
int dis[100];
void bfs()
{
memset(dis,0,sizeof(dis));
dis[x]=1;
queue<int> q;
q.push(x);
while(q.size())
{
int p=q.front();
q.pop();
//°´Ò»¸öÊý×Ö¼ü½øÐÐÌøתµÄ·½·¨
//µ¥²½¹¦Äܼü
for(int i=0;i!=10;i++)
{
if(!on[i])continue;
if(!dis[i])
{
dis[i]=dis[p]+1;
q.push(i);
}
}
//µ¥²½¹¦Äܼü
if(on[10])
{
int nextx=p+1;
if(nextx>99)nextx-=100;
//Èç¹ûûÓзÃÎʹý£¬»òÕßʹÓõ¥²½¼ü±È֮ǰµÄÈý²½¼ü¿ì£¬ÄÇôÎÒÃÇÖØмÆËã
if(!dis[nextx]||dis[p]+1<dis[nextx])
{
dis[nextx]=dis[p]+1;
q.push(nextx);
}
}
//µ¥²½¹¦Äܼü
if(on[11])
{
int nextx=p-1;
if(nextx<0)nextx+=100;
//Èç¹ûûÓзÃÎʹý£¬»òÕßʹÓõ¥²½¼ü±È֮ǰµÄÈý²½¼ü¿ì£¬ÄÇôÎÒÃÇÖØмÆËã
if(!dis[nextx]||dis[p]+1<dis[nextx])
{
dis[nextx]=dis[p]+1;
q.push(nextx);
}
}
//Èý²½¹¦Äܼü
if(on[12])
{
//Èç¹ûÄÜʹÓÃÌøת¼ü£¬ÄÇôÎÒÃÇ¿ÉÒÔÌøתµ½Á½Î»ÊýµĄ̈£¬
//ö¾ÙËùÓпÉÄܵĄ̈£¬±Ï¾¹ÎÒÃÇÊÇbfs
//ö¾ÙʮλÊýµÄÊý×Ö
for(int i=0;i!=10;i++)
{
if(!on[i])continue;
//ö¾Ù¸öλÊý
for(int j=0;j!=10;j++)
{
if(!on[j])continue;
int nextx=i*10+j;
if(!dis[nextx])
{
//ÓпÉÄÜʹÓõ¥²½°´¼üÒª°´Á½Ï²ÅÄܵ½£¬µ«°´Èý²½¼üһϵ½ÁË£¬
//ÎÒÃÇÒªÔÚµ¥²½¼üÄÇÀï¶ÔÕâÖÖ²»´ÏÃ÷µÄÈý²½¼ü½øÐÐÓÅ»¯
dis[nextx]=dis[p]+3;
q.push(nextx);
}
}
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
int t;
for(int i=1;i<=3;i++)
{
scanf("%d",&t);
on[i]=t;
}
scanf("%d",&t);on[10]=t;
for(int i=4;i<=6;i++)
{
scanf("%d",&t);
on[i]=t;
}
scanf("%d",&t);on[11]=t;
for(int i=7;i<=9;i++)
{
scanf("%d",&t);
on[i]=t;
}
scanf("%d",&t);on[12]=t;
scanf("%d",&t);on[0]=t;
scanf("%d %d",&x,&y);
// for(int i=0;i!=13;i++)
// {
// cout<<on[i];
// }
// cout<<endl;
// cout<<x<<y<<endl;
bfs();
if(dis[y]==0)
{
printf("-1\n");
}
else
{
printf("%d\n",dis[y]-1);
}
}
}
return 0;
} Problem E: 奇妙的图案
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 0 Solved: 0
[Submit][Status][Web Board]
Description
最近，Dr. Kong对几何图形发生了浓厚的兴趣。他发现在一个凸多边形里随意加上几个等半径的圆，再将圆涂成不同的颜色，就能构造出一幅美妙的图案。进而，Dr. Kong大发灵感，在此图案的基础上，又加入了几条连接凸多边形的两个不相邻顶点的直线，图形更加奇妙。
这时，Dr. Kong遇到了一个问题，他不想让加入的直线相互交叉，也不想让加入的直线穿过凸多边形里的任何一个圆，甚至不能与任何圆相切。
已经知道凸多边形的N个顶点的坐标，也知道了其中M个圆的圆心坐标和半径R。你能帮助Dr. Kong计算出可加上的满足所有条件的最多直线数吗？
Input
第1行： N M R 三个正整数
接下来有N行， 每一行为凸多边形一个坐标TXi TYi （i=1,…,N）
再接下来有M行，每一行为一个圆的圆心坐标PXj PYj （j=1，…,M）
Output
输出有一个整数， 表示可加上的最多直线数。
5≤ N ≤150 0≤ M ≤100 1≤ R ≤100,000 0≤ 所有坐标X，Y≤100,000
Sample Input
5 3 1
6 10
10 7
9 1
2 0
0 3
2 2
5 6
8 3
Sample Output
1
网上没搜到题解，个人感觉要涉及到分治的思想。
就是看看用一条边，把整个图形分成两半左边的最大值加右边的最大值，由于一个大块可能需要被求解很多次，所以我们采用记忆的方式来加速。但是。。。。，并不是太会写，也没有相关代码可以参考学习，那么我就暂时先不去磕这题了。
哦，还有样例的一个图，可以先放这里：
那个应该是话的不标准的原因，哈哈，我居然可以同时画两条不相交的线。。。
Problem F: Metric Matrice
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 8 Solved: 5
[Submit][Status][Web Board]
Description
nt j, determine if the distance matrix is “a metric” or not.
A distance matrix a[i][j] is a metric if and only if
1. a[i][i] = 0 2. a[i][j]> 0 if i != j 3. a[i][j] = a[j][i] 4. a[i][j] + a[j][k] >= a[i][k] i ¹ j ¹ k
Input
The first line of input gives a single integer, 1 ≤ N ≤ 5, the number of test cases. Then follow, for each test case,
-
Line 1: One integer, N, the rows and number of columns, 2 <= N <= 30
-
Line 2…N+1: N lines, each with N space-separated integers
(-32000 <=each integer <= 32000).
Output
Output for each test case , a single line with a single digit, which is the lowest digit of the possible facts on this list:
* 0: The matrix is a metric * 1: The matrix is not a metric, it violates rule 1 above * 2: The matrix is not a metric, it violates rule 2 above * 3: The matrix is not a metric, it violates rule 3 above * 4: The matrix is not a metric, it violates rule 4 above
Sample Input
2
4
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0
2
0 3
2 0
Sample Output
0
3
嗯，是个模拟题，没啥好说的，我居然还wa了一发。。。
#include<bits/stdc++.h>
using namespace std;
const int maxn=35;
int T,n;
int map1[maxn][maxn];
bool check1()
{
for(int i=0;i!=n;i++)
{
if(map1[i][i])return 0;
}
return 1;
}
bool check2()
{
for(int i=0;i!=n;i++)
{
for(int j=0;j!=n;j++)
{
if(i==j)continue;
if(map1[i][j]<=0)return 0;
}
}
return 1;
}
bool check3()
{
for(int i=0;i!=n;i++)
{
for(int j=0;j!=i;j++)
{
if(map1[i][j]!=map1[j][i])return 0;
}
}
return 1;
}
bool check4()
{
for(int i=0;i!=n;i++)
{
for(int j=0;j!=n;j++)
{
for(int k=0;k!=n;k++)
{
if(i==j||j==k||i==k)continue;
if(map1[i][j]+map1[j][k]<map1[i][k])return 0;
}
}
}
return 1;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
scanf("%d",&n);
for(int i=0;i!=n;i++)
{
for(int j=0;j!=n;j++)
{
scanf("%d",&map1[i][j]);
}
}
if(!check1())
{
printf("1\n");
}
else
if(!check2())
{
printf("2\n");
}
else
if(!check3())
{
printf("3\n");
}
else
if(!check4())
{
printf("4\n");
}
else
{
printf("0\n");
}
}
}
return 0;
}
京公网安备 11010502036488号