CodeForces 518E - Darth Vader and Tree(思路)
发布日期:2021-10-23 09:05:15 浏览次数:2 分类:技术文章

本文共 2703 字,大约阅读时间需要 9 分钟。

题意:给定一个n(1 <= n <= 10^5)长度的序列,其中有不确定的数字为'?',从前往后,每相邻k项加起来可得到一个n - k + 1长度的新序列,求是否存在一种解满足:

1、使这个n - k + 1的新序列递增;

2、如果有多解,求一种解使的所有数绝对值加起来最小。

若存在,则输出这个序列,否则输出"Incorrect sequence"。

每相邻k项加起来,例如a1,a2,a3,a4,每3项的话,是否满足递增即就是看是否有a1 + a2 + a3 < a2 + a3 + a4,化简后即a1 < a4,所以每隔k项必须递增。其次,如果有多解,那么让其中这些带问号的数的绝对值尽量靠近0,题目中还可能出现多个问号连在一起,对于这种情况需要看整段的前驱和后继。

一遍过,但代码写的挺麻烦,讨论情况太多了,以后要多学会汇总情况。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define fin freopen("in.txt", "r", stdin)#define fout freopen("out.txt", "w", stdout)#define pr(x) cout << #x << " : " << x << " "#define prln(x) cout << #x << " : " << x << endl#define Min(a, b) a < b ? a : b#define Max(a, b) a < b ? b : atypedef long long ll;typedef unsigned long long llu;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;const double pi = acos(-1.0);const double EPS = 1e-6;const int dr[] = { 0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const ll MOD = 1e9 + 7;const int MAXN = 100 + 10;const int MAXT = 100000 + 10;using namespace std;int n, k, a[MAXT];int main(){ while(scanf("%d%d", &n, &k) == 2){ memset(a, INT_INF, sizeof a); char s[20]; for(int i = 0; i < n; ++i){ scanf("%s", s); if(s[0] == '?') continue; sscanf(s, "%d", &a[i]); } bool flag = true; for(int i = 0; i < k; ++i){ int l = i, alllen = 0; for(int j = i; j < n; j += k){ ++alllen; if(a[j] == INT_INF) continue; if(j == l){ if(j != i && a[j] <= a[j - k]){ flag = false; goto op; } l = j + k; continue; } if(l - k < 0){ int tmp, len = (j - i) / k; if(len % 2) tmp = Min(len / 2, a[j] - 1); else tmp = Min(len / 2 - 1, a[j] - 1); for(int u = j - k; u >= i; u -= k) a[u] = tmp--; l = j + k; } else{ int tmp, len = (j - l) / k; if(len > a[j] - a[l - k] - 1){ flag = false; goto op; } if(len % 2){ tmp = Min(len / 2, a[j] - 1); if(tmp - len + 1 <= a[l - k]) tmp = a[l - k] + len; } else{ tmp = Min(len / 2 - 1, a[j] - 1); if(tmp - len + 1 <= a[l - k]) tmp = a[l - k] + len; } for(int u = j - k; u >= l; u -= k) a[u] = tmp--; l = j + k; } } if(l < n){ if(l - k < 0){ int tmp = -alllen / 2; for(int u = i; u < n; u += k) a[u] = tmp++; } else{ int len = (n - l) / k; int tmp = Max(-len / 2, a[l - k] + 1); for(int u = l; u < n; u += k) a[u] = tmp++; } } }op: if(!flag) printf("Incorrect sequence\n"); else{ for(int i = 0; i < n; ++i){ if(i) printf(" "); printf("%d", a[i]); } printf("\n"); } } return 0;}

 

转载于:https://www.cnblogs.com/tyty-TianTengtt/p/5997292.html

转载地址:https://blog.csdn.net/weixin_30549657/article/details/95796240 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:每一个你不满意的现在,都有一个你没有努力的曾经。
下一篇:学习日记 -操作系统搭建相关

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月15日 22时44分27秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

c语言对结构体排序中间变量,求助:c语言怎么实现结构体的排序? 总是弄不对啊... 2019-04-21
c语言宏定义只能在最前面吗,C语言宏定义注意事项 2019-04-21
android悬浮窗服务卡死,Android 悬浮窗兼容问题谈 2019-04-21
表格相关的html语言,HTML标记语言——表格标记 2019-04-21
web聊天界面html,PC端Web聊天界面+代码分享(HTML+CSS) 2019-04-21
cmake qt 添加路径 项目_CMake配置Qt工程 2019-04-21
使用python开发的软件协议_WEB开发——Python WSGI协议详解 2019-04-21
冰点下载器手机版apk_冰点文库下载器 2019-04-21
python信号采集代码_13行代码实现:Python实时视频采集(附源码) 2019-04-21
h5引入json_纯js直接引入json文件 2019-04-21
python格式化字符串总结_Python字符串处理方法总结 2019-04-21
python中true什么意思_python中的bool是什么意思 2019-04-21
jacobian 矩阵意义_Jacobian矩阵和Hessian矩阵的作用是什么? 2019-04-21
c++ jna 数据类型_JNA 使用总结 2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表? 2019-04-21
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21
mysql redis缓存层_redis实现缓存的两种方式 2019-04-21
mysql索引篇_MySQL索引篇 2019-04-21
有至少一个用MySQL_Mysql有用的面试题 2019-04-21
mysql删除后数据库没变化_mysql之delete删除记录后数据库大小不变 2019-04-21