首页 > 其他分享 >CF1329A Dreamoon Likes Coloring 题解

CF1329A Dreamoon Likes Coloring 题解

时间:2022-10-11 20:48:12浏览次数:58  
标签:std CF1329A Coloring const 题解 long using include any

提供一个简短的题解:
首先如果所有长度加起来还不到 \(n\) 直接无解。
可以直接贪心,把第 \(i\) 条线段的右端点放在 \(n-i+1\) 这个位置,就可以最省长度(只占一个点)而且不会遗漏,如果左端点小于 \(1\) 也判无解。
操作完之后发现左边有一些没染色的格子,把最后盖上去的线段往左拖过来首位相接就行了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<tuple>
#include<numeric>
#define siz(x) int((x).size())
#define cauto const auto
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using std::cin;using std::cout;
using std::max;using std::min;
using std::tie;using std::ignore;
template<typename any>inline void cmin(any &x,const any &y){if(y<x)x=y;}
template<typename any>inline void cmax(any &x,const any &y){if(x<y)x=y;}
template<typename any,typename...args>inline void cmax(any &x,const any &y,const args &...z){cmax(x,y);cmax(x,z...);}
template<typename any,typename...args>inline void cmin(any &x,const any &y,const args &...z){cmin(x,y);cmin(x,z...);}
using loli=long long;
using uloli=unsigned long long;
using lodb=long double;
using venti=__int128_t;
using pii=std::pair<int,int>;
using inlsi=const std::initializer_list<int>&;
using bsi=std::basic_string<int>;
using bsc=std::basic_string<char>;
constexpr venti operator""_vt(uloli x){return venti(x);}
constexpr int N=1e5+1,inf=0x3f3f3f3f;
int n,m,p1=1,p2=inf,l[N],p[N];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>m;for(int i=1;i<=m;i++)cin>>l[i];
	if(std::accumulate(l+1,l+1+m,0ll)<n)return cout<<"-1",0;
	for(int i=1;i<=m;i++)if(cmin(p2,p[i]=n-i+2-l[i]),p2<=0)return cout<<"-1",0;
	for(int i=m;p1<=p2;i--)p[i]=p1,p1+=l[i];
	for(int i=1;i<=m;i++)cout<<p[i]<<' ';
	return 0;
}

标签:std,CF1329A,Coloring,const,题解,long,using,include,any
From: https://www.cnblogs.com/bxjz/p/CF1329A.html

相关文章

  • YACS 2022年9月月赛 甲组 T1 游戏体验 题解
    目前还没有时间写题解,疯狂复习$CSP$复赛中,这题是个线段树(自己可以探究一下,是动态的)先贴个标程,需要的,请#include<bits/stdc++.h>usingnamespacestd;intn,m,a[10000......
  • UVa 11300 Spreading the Wealth 题解
    非常好的一道数学题。原题链接(洛谷)原题链接(UVa)题目分析(参考刘汝佳《算法竞赛入门经典\(\cdot\)训练指南》)本身看起来很复杂。不要急,我们慢慢分析。首先,每个人最终......
  • CF1237F 题解
    传送门题意给你一个\(n\timesm\)的棋盘,上面已经放了\(k\)个\(1\times2\)的骨牌。对于一个骨牌的每个格子,不能有其他骨牌的格子与它在同一行、同一列。你可以......
  • 在实际开发中遇到的各种问题解决方案
    目录第一问:使用axios异步请求完成数据导出(Excel)(基于hutool工具包)(1.1)编写后台接口,获取到response对象以及前端传来的数据,使用@RequestBody获取到需要进行导出的数据id(1.1.1)......
  • [BalticOI 2010] Mines 题解
    你谷linklojlink提供一种时间复杂度正确的高妙做法。首先题目有一条隐藏条件是保证\(n\not\equiv2\pmod3\)或\(m\not\equiv2\pmod3\),需要通过观察数据得到。我们......
  • 2022 ICPC 网络赛(II) H Fast Fourier Transform题解
    简要题意给你一棵树,你可以选若干节点为关键点,定义一个选点方案的价值为:所有路径上没有关键点的点对的距离之和。求所有选点方案的价值之和。题解一开始和队友都读错题了......
  • SCOI 萌萌哒 题解
    下决心写一道题写一篇题解。题目链接考虑暴力,直接并查集合并相同的数,和今天T1一样。考虑优化这个暴力。因为今天T1题解说要倍增,所以考虑一个长的跟ST表一样的倍增。具......
  • 洛谷 P3488 [POI2009]LYZ-Ice Skates 题解
    错解每次跑二分图匹配,时间复杂度显然爆炸。时间复杂度:我被杀手皇后摸过了正解引入Hall定理:设二分图中\(G=<V_1,V_2,E>,|V_1|\le|V_2|\),则G中存在\(V_1\)到......
  • 【题解】XXI Opencup GP of Tokyo Count Min Ratio
    有\(R\)个红球,\(B\)个蓝球和一个绿球,同色球之间无区别。将其任意排列,令\(l_R,l_B,r_R,r_B\)分别为绿球左/右边的红/蓝球数量。定义一个方案的权值为\(\max\{x\i......
  • Criss Cross OJ【R001】8月月赛I题解合集
    R0011.「T1」积木高塔Solution返回题目简要题意:给定一个矩阵,以及其每一格中完全相同立方体的高度(即个数),求:这座高塔最高点的高度。这座高塔从第\(1\)层到最高......