AtCoder Beginner Contest 131 题解

 

A - Security


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 100100 points

Problem Statement

The door of Snuke's laboratory is locked with a security code.

The security code is a 44-digit number. We say the security code is hard to enter when it contains two consecutive digits that are the same.

You are given the current security code SS. If SS is hard to enter, print Bad; otherwise, print Good.

Constraints

  • SS is a 44-character string consisting of digits.

Input

Input is given from Standard Input in the following format:

SS

Output

If SS is hard to enter, print Bad; otherwise, print Good.


Sample Input 1 Copy

Copy

3776

Sample Output 1 Copy

Copy

Bad

The second and third digits are the same, so 37763776 is hard to enter.


Sample Input 2 Copy

Copy

8080

Sample Output 2 Copy

Copy

Good

There are no two consecutive digits that are the same, so 80808080 is not hard to enter.


Sample Input 3 Copy

Copy

1333

Sample Output 3 Copy

Copy

Bad

Sample Input 4 Copy

Copy

0024

Sample Output 4 Copy

Copy

Bad

太水

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int a[N];
int n;
int main()
{
    // scanf("%d",&n);
    string s;
    cin>>s;
    for(int i=0;i<s.length()-1;i++)
	{
		if(s[i]==s[i+1])
		{
			cout<<"Bad"<<endl;
			return 0;
		}
	}
	cout<<"Good"<<endl;
	return 0;
 
}

 

B - Bite Eating


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 200200 points

Problem Statement

You have NN apples, called Apple 11, Apple 22, Apple 33, ..., Apple NN. The flavor of Apple ii is L+i−1L+i−1, which can be negative.

You can make an apple pie using one or more of the apples. The flavor of the apple pie will be the sum of the flavors of the apples used.

You planned to make an apple pie using all of the apples, but being hungry tempts you to eat one of them, which can no longer be used to make the apple pie.

You want to make an apple pie that is as similar as possible to the one that you planned to make. Thus, you will choose the apple to eat so that the flavor of the apple pie made of the remaining N−1N−1 apples will have the smallest possible absolute difference from the flavor of the apple pie made of all the NN apples.

Find the flavor of the apple pie made of the remaining N−1N−1 apples when you choose the apple to eat as above.

We can prove that this value is uniquely determined.

Constraints

  • 2≤N≤2002≤N≤200
  • −100≤L≤100−100≤L≤100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN LL

Output

Find the flavor of the apple pie made of the remaining N−1N−1 apples when you optimally choose the apple to eat.


Sample Input 1 Copy

Copy

5 2

Sample Output 1 Copy

Copy

18

The flavors of Apple 11, 22, 33, 44, and 55 are 22, 33, 44, 55, and 66, respectively. The optimal choice is to eat Apple 11, so the answer is 3+4+5+6=183+4+5+6=18.


Sample Input 2 Copy

Copy

3 -1

Sample Output 2 Copy

Copy

0

The flavors of Apple 11, 22, and 33 are −1−1, 00, and 11, respectively. The optimal choice is to eat Apple 22, so the answer is (−1)+1=0(−1)+1=0.


Sample Input 3 Copy

Copy

30 -50

Sample Output 3 Copy

Copy

-1044

也水

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int a[N];
int n,L;
int main()
{
    scanf("%d%d",&n,&L);
    int sum=0;
    for(int i=1;i<=n;i++)
	{
		a[i]=L+i-1;
		sum+=a[i];
	}
	int sum1=sum;
	int ans;
	int cha=1e9;
	for(int i=1;i<=n;i++)
	{
		sum1=sum;
		sum1-=a[i];
		if(abs(sum1-sum)<cha)
		{
			ans=sum1;
			cha=abs(sum1-sum);
		}
	}
	
	cout<<ans<<endl;

	return 0;
 
}

 

 

C - Anti-Division


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

You are given four integers AA, BB, CC, and DD. Find the number of integers between AA and BB (inclusive) that can be evenly divided by neither CC nor DD.

Constraints

  • 1≤A≤B≤10181≤A≤B≤1018
  • 1≤C,D≤1091≤C,D≤109
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

AA BB CC DD

Output

Print the number of integers between AA and BB (inclusive) that can be evenly divided by neither CC nor DD.


Sample Input 1 Copy

Copy

4 9 2 3

Sample Output 1 Copy

Copy

2

55 and 77 satisfy the condition.


Sample Input 2 Copy

Copy

10 40 6 8

Sample Output 2 Copy

Copy

23

Sample Input 3 Copy

Copy

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3 Copy

Copy

532105071133627368

题意:

求[A,B]里既不能整除C又不能整除D的数。

分析:

(A,B](左边取不到)里可以整除C的数有B/C-A/C个,那答案就出来了

B/C-A/C+B/D-A/D-(B/e-A/e)(e为cd最小公倍数)

在判断一下左边界A,总的一减即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
//int a[N];
int n,L ;
LL gcd(LL a,LL b)
{
	return a == 0 ? b : gcd(b % a, a);
}
LL  a,b,c,d;
int main()
{
     cin>>a>>b>>c>>d;
     LL ans=b/c-a/c+b/d-a/d-(b/(c*d/gcd(c,d))-a/(c*d/gcd(c,d)));
     if(a%c==0) ans++;
     if(a%d==0) ans++;
     if(a%(c*d)==0) ans--;
   //cout<<ans<<endl;
     ans=b-a+1-ans;
     cout<<ans<<endl;

	return 0;
 
}

 

D - Megalomania


Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 400400 points

Problem Statement

Kizahashi, who was appointed as the administrator of ABC at National Problem Workshop in the Kingdom of AtCoder, got too excited and took on too many jobs.

Let the current time be time 00. Kizahashi has NN jobs numbered 11 to NN.

It takes AiAi units of time for Kizahashi to complete Job ii. The deadline for Job ii is time BiBi, and he must complete the job before or at this time.

Kizahashi cannot work on two or more jobs simultaneously, but when he completes a job, he can start working on another immediately.

Can Kizahashi complete all the jobs in time? If he can, print Yes; if he cannot, print No.

Constraints

  • All values in input are integers.
  • 1≤N≤2×1051≤N≤2×105
  • 1≤Ai,Bi≤109(1≤i≤N)1≤Ai,Bi≤109(1≤i≤N)

Input

Input is given from Standard Input in the following format:

NN
A1A1 B1B1
..
..
..
ANAN BNBN

Output

If Kizahashi can complete all the jobs in time, print Yes; if he cannot, print No.


Sample Input 1 Copy

Copy

5
2 4
1 9
1 8
4 9
3 12

Sample Output 1 Copy

Copy

Yes

He can complete all the jobs in time by, for example, doing them in the following order:

  • Do Job 22 from time 00 to 11.
  • Do Job 11 from time 11 to 33.
  • Do Job 44 from time 33 to 77.
  • Do Job 33 from time 77 to 88.
  • Do Job 55 from time 88 to 1111.

Note that it is fine to complete Job 33 exactly at the deadline, time 88.


Sample Input 2 Copy

Copy

3
334 1000
334 1000
334 1000

Sample Output 2 Copy

Copy

No

He cannot complete all the jobs in time, no matter what order he does them in.


Sample Input 3 Copy

Copy

30
384 8895
1725 9791
170 1024
4 11105
2 6
578 1815
702 3352
143 5141
1420 6980
24 1602
849 999
76 7586
85 5570
444 4991
719 11090
470 10708
1137 4547
455 9003
110 9901
15 8578
368 3692
104 1286
3 4
366 12143
7 6649
610 2374
152 7324
4 7042
292 11386
334 5720

Sample Output 3 Copy

Copy

Yes

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
//int a[N];
int n,L ;
struct node
{
	int id;
	int A,B;
}a[N];
bool cmp(node x,node y)
{
	if(x.B==y.B)
		return x.A<y.A;
	return x.B<y.B;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
	{
		cin>>a[i].A>>a[i].B;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	int t=0;
	for(int i=1;i<=n;i++)
	{
	//	cout<<a[i].A<<" "<<a[i].B<<" "<<t<<endl;
		if(t+a[i].A<=a[i].B)
		{
			t+=a[i].A;
		}
		else
		{
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
 
}

 

E - Friendships


Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 500500 points

Problem Statement

Does there exist an undirected graph with NN vertices satisfying the following conditions?

  • The graph is simple and connected.
  • The vertices are numbered 1,2,...,N1,2,...,N.
  • Let MM be the number of edges in the graph. The edges are numbered 1,2,...,M1,2,...,M, the length of each edge is 11, and Edge ii connects Vertex uiui and Vertex vivi.
  • There are exactly KK pairs of vertices (i, j) (i<j)(i, j) (i<j) such that the shortest distance between them is 22.

If there exists such a graph, construct an example.

Constraints

  • All values in input are integers.
  • 2≤N≤1002≤N≤100
  • 0≤K≤N(N−1)20≤K≤N(N−1)2

Input

Input is given from Standard Input in the following format:

NN KK

Output

If there does not exist an undirected graph with NN vertices satisfying the conditions, print -1.

If there exists such a graph, print an example in the following format (refer to Problem Statement for what the symbols stand for):

MM
u1u1 v1v1
::
uMuM vMvM

If there exist multiple graphs satisfying the conditions, any of them will be accepted.


Sample Input 1 Copy

Copy

5 3

Sample Output 1 Copy

Copy

5
4 3
1 2
3 1
4 5
2 3

This graph has three pairs of vertices such that the shortest distance between them is 22: (1, 4)(1, 4), (2, 4)(2, 4), and (3, 5)(3, 5). Thus, the condition is satisfied.


Sample Input 2 Copy

Copy

5 8

Sample Output 2 Copy

Copy

-1

There is no graph satisfying the conditions.

题意:

给你n与k,要求构造n个点,恰有k条距离为2 的路径的图

分析:

我们选取一个点当作中间节点,假设n=5

 

注意最多有3+2+1(即最多就有(n-2)*(n-1)/2)

连上一条你变会消除一条,模拟一下思路即可

接下来给出徐老爷的代码

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=200+10;
int vis[maxn][maxn];
struct Node
{
    int x,y;
    Node(){}
    Node(int a,int b):x(a),y(b){}
};
vector<Node >G;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(n==0)
    {
         printf("-1\n");
        return 0;
    }
    int m=n-1;
    int sum=(m)*(m-1)/2;
    if(k>sum)
    {
        printf("-1\n");
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        G.push_back(Node(i,n));
    }

    int i=1,j=2;
    while(sum!=k)
    {
        sum--;
        G.push_back(Node(i,j));
        j++;
        if(j==m+1) i++,j=i+1;
    }

    printf("%d\n",G.size());
    for(int i=0;i<G.size();i++)
    {
        printf("%d %d\n",G[i].x,G[i].y);
    }
}

 

版权声明:本文为sdz20172133原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sdz20172133/article/details/93375815

智能推荐

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

猜你喜欢

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...

创建一个Servlet项目流程(入门)

版本 IDEA 2020.2 JDK1.8 apache-tomcat-9.0.36 项目流程 一、IDEA中新建JaveEE项目 项目起名,选择项目存放地址,点击finish创建成功 进入项目后,右键选择项目,选择add Framework Support 选择Web Application,点击OK 此时项目文件夹 在WEB-INF下创建两个目录classes和lib 按ctrl+alt+sh...

Docker部署SpringCloud ELK+RabbitMQ日志

Docker部署SpringCloud ELK+RabbitMQ日志  Im_Coder 原文:https://www.jianshu.com/p/f773f23096a9 一、效果图 image.png 二、ELK是什么? ELK由ElasticSearch、Logstash和Kiabana三个开源工具组成。 其中Elasticsearch是个开源分布式搜索引擎,它的特点有:分布式,索...