HNUCM2020年春季ACM集训队热身赛-第7场题解
KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的菱形图案。
输入多组输入，一个整数（2~20）。
输出针对每行输入，输出用“”组成的菱形，每个“”后面有一个空格。每输出一个菱形的后面需要空一行。
样例输入2
3
4
*
* *
* * *
* *
*
*
* *
* * *
* * * *
* * *
* *
*
*
* *
* * *
* * * *
* * * * *
* * * *
* * *
* *
*
模拟输出
#include
#define ll long long
using namespace std;
const int maxn=1e5+5;
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i=n;i>=0;--i){
for(int j=1;j<=i;++j)putchar(' ');
for(int j=i;j<=n;++j)printf("* ");
putchar('\n');
}
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j)putchar(' ');
for(int j=i;j<=n;++j)printf("* ");
putchar('\n');
}
putchar('\n');
}
return 0;
}
问题 B: 迷路的牛牛
题目描述
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。
样例输入3
LRR
E
求模运算
将四个方向用数组存起来char dir[4]={‘N’,‘E’,‘S’,‘W’};
初始位置为0，向右转可以看成+1，向左转可以看成-1，最后避免得到一个负数，+4000再对4取模
#include
#define ll long long
using namespace std;
const int maxn=1e5+5;
char s[maxn];
char dir[4]={'N','E','S','W'};
int main()
{
int n,now=0;
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;++i){
if(s[i]=='R')++now;
else --now;
}
printf("%c\n",dir[(now+4000)%4]);
return 0;
}
问题 C: 俄罗斯方块
题目描述
小易有一个古老的游戏机，上面有着经典的游戏俄罗斯方块。因为它比较古老，所以规则和一般的俄罗斯方块不同。
荧幕上一共有 n 列，每次都会有一个 1 x 1 的方块随机落下，在同一列中，后落下的方块会叠在先前的方块之上，当一整行方块都被占满时，这一行会被消去，并得到1分。
有一天，小易又开了一局游戏，当玩到第 m 个方块落下时他觉得太无聊就关掉了，小易希望你告诉他这局游戏他获得的分数。
第一行两个数 n, m
第二行 m 个数，c1, c2, … , cm ， ci 表示第 i 个方块落在第几列
其中 1 <= n, m <= 1000, 1 <= ci <= n
小易这局游戏获得的分数
样例输入3 9
1 1 2 2 2 3 1 2 3
2
因为方块是1×1的说明列中没有空格
消去的行数也就是最低的列的高度
#include
#define ll long long
using namespace std;
const int maxn=1e5+5;
int num[maxn];
int main()
{
int n,m,x,ans=maxn;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d",&x);
++num[x];
}
for(int i=1;i<=n;++i)ans=min(ans,num[i]);
printf("%d\n",ans);
return 0;
}
问题 D: 坐标移动
题目描述
开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。
输入：合法坐标为A(或者D或者W或者S) + 数字（两位以内）
坐标之间以;分隔。
非法坐标点需要进行丢弃。如AA10; A1A; %; YAD; 等。
下面是一个简单的例子 如：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
处理过程：
起点（0,0）
+ A10 = （-10,0）
+ S20 = (-10,-20)
+ W10 = (-10,-10)
+ D30 = (20,-10)
+ x = 无效
+ A1A = 无效
+ B10A11 = 无效
+ 一个空 不影响
+ A10 = (10,-10)
结果 （10， -10）
注意请处理多组输入输出。
输入一行字符串。（字符串长度<=1000）
输出
最终坐标以,分隔。
A10;S20;W10;D30;X;A1A;B10A11;;A10;
样例输出10,-10
字符串处理
对输入的；之间的字符串判断合法性
必须是一个大写字母接数字
再获取数字模拟坐标移动
#include
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
char s[1005];
int main()
{
while(~scanf("%s",s+1)){
int ls=strlen(s+1),x=0,y=0;
for(int i=1;i<=ls;++i){
int j=i,ju=0,num=0;
while(j=4)ju=1;//第一个字符是否是大写字母
for(int k=i+1;k<j;++k){//后续的字符是否是数字
if(!isdigit(s[k])){
ju=1;
break;
}
}
for(int k=i+1;k<j;++k)//获取数字
num=num*10+s[k]-'0';
if(ju==0){//模拟坐标移动
if(s[i]=='A')x-=num;
else if(s[i]=='D')x+=num;
else if(s[i]=='W')y+=num;
else if(s[i]=='S')y-=num;
}
i=j;
}
printf("%d,%d\n",x,y);
}
return 0;
}
问题 E: IP地址和掩码
题目描述
请解析IP地址和对应的掩码，进行分类识别。要求按照A/B/C/D/E类地址归类，不合法的地址和掩码单独归类。
所有的IP地址划分为 A,B,C,D,E五类：
A类地址1.0.0.0~126.255.255.255;
B类地址128.0.0.0~191.255.255.255;
C类地址192.0.0.0~223.255.255.255;
D类地址224.0.0.0~239.255.255.255;
E类地址240.0.0.0~255.255.255.255。
私网IP范围是：
10.0.0.0～10.255.255.255
172.16.0.0～172.31.255.255
192.168.0.0～192.168.255.255
子网掩码为二进制下前面是连续的1，然后全是0。（例如：255.255.255.32就是一个非法的掩码）
注意二进制下全是1或者全是0均为非法。
IP地址为32位，每8位用.隔开，输入大于32位的IP地址或.与.之间含有数字以外字符的IP地址均为非法IP
注意：
1 . 类似于【0...*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时可以忽略
2 . 私有IP地址和A,B,C,D,E类地址是不冲突的
多行字符串。每行一个IP地址和掩码，用~隔开。
输出统计A、B、C、D、E、错误IP地址或错误掩码、私有IP的个数，之间以空格隔开。
样例输入10.70.44.68~255.254.255.0
1.0.0.1~255.0.0.0
192.168.0.2~255.255.255.0
19…0.~255.255.255.0
1 0 1 0 0 2 1
…繁琐的模拟题…容易漏掉某些判断
需要注意的是判断IP合法性和掩码合法性是独立的，也就是说如果IP不合法而且掩码不合法，错误IP地址或错误掩码数+2
代码有注释~
#include
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int ans[10];
ll a[10];
bool ju1(string s){//IP合法性判断
int ls=s.size(),num,x=0;
for(int i=0;i<ls;++i)
if(s[i]!='.'&&!isdigit(s[i])){//判断是否有除'.'和数字外的其他字符
++ans[6];
return false;//有则不合法
}
for(int i=0;i<ls;++i)if(s[i]=='.')++x;//判断有几个'.'
if(x!=3){++ans[6];return false;}//'.'数量不等于3说明不合法
for(int i=0,j;i<ls;i=j+1){
j=i,num=0;
while(j<ls&&s[j]!='.')++j;//获取下一个'.'的位置
if(j==i){++ans[6];return false;}//两个.之间必须有数字
for(int k=i;k255){++ans[6];return false;}//11111111=255 超过8位说明不合法
}
return true;//否则合法
}
bool ju2(string s){//掩码合法性判断
int ls=s.size(),num,x=0;
vector w;
memset(a,0,sizeof(a));
for(int i=0;i<ls;++i)
if(s[i]!='.'&&!isdigit(s[i])){//判断是否有除'.'和数字外的其他字符
++ans[6];
return false;//有则不合法
}
for(int i=0;i<ls;++i)if(s[i]=='.')++x;//判断有几个'.'
if(x!=3){++ans[6];return false;}//'.'数量不等于3说明不合法
for(int i=0,j;i<ls;i=j+1){
j=i,num=0;
while(j<ls&&s[j]!='.')++j;//获取下一个'.'的位置
if(j==i){++ans[6]; return false;}//两个.之间必须有数字
for(int k=i;k255){++ans[6];return false;}//11111111=255 超过8位说明不合法
for(int i=7;i>=0;--i)//拆分成二进制
w.push_back((num>>i)&1);
}
if(w[0]==0||w[w.size()-1]==1){++ans[6];return false;}//掩码先是连续的1后是连续的0
int now=0;
while(w[now]==1)++now;//获取1和0的分界
for(int i=1;i<now;++i)//判断前一部分是否全1
if(w[i]==0){++ans[6];return false;}
for(int i=now;i<w.size();++i)//判断后一部分是否全0
if(w[i]==1){++ans[6];return false;}
return true;
}
void ju3(string s){
int ls=s.size(),cnt=0;
memset(a,0,sizeof(a));
for(int i=0,j;i<ls;i=j+1){
j=i,++cnt;
while(j<ls&&s[j]!='.')++j;
for(int k=i;k=1&&a[1]=128&&a[1]=192&&a[1]=224&&a[1]=240&&a[1]=16&&a[2]>s){
int ls=s.size(),pl=0,ju=0;
while(pl<=ls&&s[pl]!='~')++pl;//找到划分点~
s1=s.substr(0,pl);//截取IP地址
s2=s.substr(pl+1);//截取掩码
ju=ju1(s1)&&ju2(s2);//对IP地址和掩码分别判断合法性
if(ju)ju3(s1);//IP的分类
}
for(int i=1;i<=7;++i){
printf("%d%c",ans[i],i==7?'\n':' ');
}
return 0;
}
问题 F: 简单错误记录
题目描述
开发一个简单错误记录功能小模块，能够记录出错的代码所在的文件名称和行号。
处理：
1、 记录最多8条错误记录，循环记录（或者说最后只输出最后出现的八条错误记录），对相同的错误记录（净文件名称和行号完全匹配）只记录一条，错误计数增加，出现时间以第一次出现为准，当作一条错误记录处理；
2、 超过16个字符的文件名称，只记录文件的最后有效16个字符；
3、 输入的文件可能带路径，记录文件名称不能带路径。
一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。(字符串长度<=1000)
输出将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开。
样例输入E:\V1R2\product\fpgadrive.c 1325
样例输出fpgadrive.c 1325 1
按题意模拟~
#include
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
struct node{
char a[20];
int x,num;
}ans[maxn];
char ss[20],s[1005];
int main()
{
int cnt=0,x;
while(~scanf("%s %d",s+1,&x)){
int ls=strlen(s+1),lss=ls;
while(s[lss]!='\\')//获取最后一个\的位置
--lss;
for(int i=max(lss+1,ls-15),j=1;i<=ls;++i,++j){//获取净文件名称
ss[j]=s[i];
if(i==ls)ss[j+1]='\0';
}
int ju=1;
for(int i=1;i<=cnt;++i){
if(strcmp(ans[i].a+1,ss+1)==0&&ans[i].x==x){//判断前面有没有出现过
++ans[i].num;
ju=0;
break;
}
}
if(ju){//没有则添加
strcpy(ans[++cnt].a+1,ss+1);
ans[cnt].num=1;
ans[cnt].x=x;
}
}
for(int i=max(1,cnt-7);i<=cnt;++i){//最多取最后8个输出
printf("%s %d %d\n",ans[i].a+1,ans[i].x,ans[i].num);
}
return 0;
}
问题 G: 验证密码
题目描述
密码要求:
1.长度超过8位；
2.包括大小写字母.数字.其它符号,以上四种至少三种；
3.不能有相同长度超2的子串重复；
说明:长度超过2的子串。
一组或多组长度超过2的子符串。每组占一行。（字符串长度小于1000）
输出如果符合要求输出：OK，否则输出NG。
样例输入021Abc9000
021Abc9Abc1
021ABC9000
021$bc9000
OK
NG
NG
OK
（）
判断相同长度超2的子串重复，只需要找到长度为3的两个相等字符串就行（更长的包含长度为3的）
两层for循环枚举两个字符串的起点进行判断
#include
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
char s[maxn];
int a[10];
int main()
{
while(~scanf("%s",s+1)){
memset(a,0,sizeof(a));
int ls=strlen(s+1);
for(int i=1;i<=ls;++i){
if(isdigit(s[i]))a[1]=1;//是数字
else if(isupper(s[i]))a[2]=1;//大写字母
else if(islower(s[i]))a[3]=1;//小写字母
else a[4]=1;//其他
}
if(a[1]+a[2]+a[3]+a[4]<3||ls<=8){
printf("NG\n");
continue;
}
int ju=1;
for(int i=1;i<=ls;++i){//枚举第一个字符串的起点
for(int j=i+3;j+2<=ls;++j){//枚举第二个字符串的终点
if(s[i]==s[j]&&s[i+1]==s[j+1]&&s[i+2]==s[j+2]){
ju=0;
break;
}
}
if(ju==0)break;
}
if(ju)printf("OK\n");
else printf("NG\n");
}
return 0;
}
问题 H: 名字的漂亮度
题目描述
给出一个名字，该名字有26个字符串组成，定义这个字符串的“漂亮度”是其所有字母“漂亮度”的总和。
每个字母都有一个“漂亮度”，范围在1到26之间。没有任何两个字母拥有相同的“漂亮度”。字母忽略大小写。
给出多个名字，计算每个名字最大可能的“漂亮度”。
多组输入。
每组输入一个整数N，后续N个名字。（名字全部由字母组成，长度小于1e5）
每个名称可能的最大漂亮程度。
样例输入2
zhangsan
lisi
192
101
“漂亮度"不能重复，那就让出现次数多的拥有更大的"漂亮度”
对每一个字母出现次数计数
sort降序排序…
#include
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
char s[maxn];
int num[35];
bool cmp(int a,int b){
return a>b;
}
int main()
{
int t;
while(~scanf("%d",&t)){
while(t--){
memset(num,0,sizeof(num));
scanf("%s",s+1);
int ls=strlen(s+1);
for(int i=1;i<=ls;++i)
num[tolower(s[i])-'a'+1]++;
int ans=0;
sort(num+1,num+27,cmp);
for(int i=1;i<=26;++i)
ans+=(26-i+1)*num[i];
printf("%d\n",ans);
}
}
return 0;
}
名字在哪啊
原创文章 169获赞 62访问量 2万+
关注
私信
展开阅读全文
作者：名字在哪啊
