Atcoder ARC 082C/D
C - Together
传送门:http://arc082.contest.atcoder.jp/tasks/arc082_a
本题是一个数学问题。
有一个长度为n的自然数列a[1..n],对于每一个a[i],有三种操作:
①inc a[i];
②dec a[i];
③do nothing。
之后,选择一个自然数x,统计数列中等于x的元素的数目num(x),最大化答案。
考虑x有以下三种来源:
①x:=inc a[i],while a[i]==x-1;
②x:=dec a[i],while a[i]==x+1;
③x:=a[i],while a[i]==x。
于是,对于每一个x,num(x)的最大值为cnt(x-1)+cnt(x)+cnt(x+1)。
参考程序如下:
#include <stdio.h>
#define MAX_A 100010 int cnt[MAX_A]; int main(void)
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) {
int a;
scanf("%d", &a);
cnt[++a]++;
}
int ans = ;
for (int i = ; i < MAX_A; i++) {
int cur = cnt[i - ] + cnt[i] + cnt[i + ];
if (cur > ans) ans = cur;
}
printf("%d\n", ans);
return ;
}
D - Derangement
传送门:http://arc082.contest.atcoder.jp/tasks/arc082_b
本题是一个数学问题。
有一个长度为n的数列a[1..n],这是一个1..n的排列。有操作:交换相邻的两个元素。经过有限次交换操作,这个排列将满足:对任意1≤i≤n,有a[i]≠i。求最小的交换次数。
对于每一个位置,记a[i]=i的情形为X,a[i]≠i的情形为O,则考虑相邻元素的情形:
①“XO”(或“OX”):a[i]=i,a[i+1]=x(x≠i,i+1)。此时,交换a[i]和a[i+1],即有a[i]=x(x≠i,i+1),a[i+1]=i,为“OO”;
②“XX”:a[i]=i,a[i+1]=i+1。此时,交换a[i]和a[i+1],即有a[i]=i+1,a[i+1]=i,为“OO”。
于是,对于每一个X,若这个位置i<n,则交换a[i]和a[i+1];若这个位置为n,则交换a[n-1]和a[n]。自左向右检查即可。
可见,“XO”、“OX”、“XX”三种情形的交换次数均为1,统计出现以上情形的次数即可。
参考程序如下:
#include <stdio.h>
#define MAX_N 100001 int a[MAX_N]; int main(void)
{
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
int cnt = ;
for (int i = ; i <= n; i++) {
if (a[i] == i) {
cnt++;
if (i < n && a[i + ] == i + ) i++;
}
}
printf("%d\n", cnt);
return ;
}
最新文章
- java入门第三步之数据库连接
- ListView的CheckBox实现全部选中/不选中
- data Binding
- hdu4292Food(最大流Dinic算法)
- minix2.0内核组织结构与公用头文件说明
- 【python】bytearray和string之间转换,用在需要处理二进制文件和数据流上
- aix创建lv 在lv上创建文件系统
- create a new table for the query results
- smtplib 报错501
- 【翻译】Ext JS 6早期访问版本发布
- MySQL数据查询子查询语句
- 【Spark-core学习之四】 Spark任务提交
- 【题解】Luogu P4054 [JSOI2009]计数问题
- Nodejs学习笔记(十七)—浮点运算decimal.js
- JAVA volatile 解析
- 对于SQL Server 2008删除或压缩数据库日志的方法
- Python学习笔记(三十五)—内置模块(4)struct
- 微信小程序 - 自定义模态对话框
- 在windows中将Tomcat作为服务启动
- php端安装rabbitmq-c
热门文章
- 游戏人生(一),我的lua之旅:那些坑爹的CCBReaderLoad
- ExtJs--06--Ext.WindowGroup相关方法简单使用
- spring mvc文件上传,request对象转换异常
- Choose the best route HDU杭电2680【dijkstra算法 || SPFA】
- PCB Genesis加邮票孔(弧形连接位宽度校正)实现算法
- js form settimeout
- python 46 边界圆角 、a_img_list标签 、伪类选择器
- CSS自定义消息提示
- GO 协程 通道实例以及验证SnowFlake算法
- 【Oracle】表连接三种方式