[Codeforces 26E] MultiThreading
2024-09-30 14:42:31
Brief Intro:
给你n个数,每个数有2*CNT[i]个,让你构造一个序列
使得最终的Y值为W(其余见题面)
Solution:
就是一道纯构造的题目:
先把特殊情况特殊处理,接下来考虑一般情况:
如果让每种数字都连续放置,则对于每两个相同的A[i],Y则加一
要想最终Y=W,则要将多余的去除。于是这样构造:
A:1........1211...112 B:11..122..233...344...4.....nn
最终序列分为A段和B段,其中A段仅能使Y+=2,同时去除多余的项
剩余的先计算好后在B中连续放置即可
Code:
#include <bits/stdc++.h> using namespace std; template<class T> inline void putnum(T x)
{
if(x<)putchar('-'),x=-x;
register short a[]={},sz=;
while(x)a[sz++]=x%,x/=;
if(sz==)putchar('');
for(int i=sz-;i>=;i--)putchar(''+a[i]);
putchar(' ');
} int n,w,dat[],res[],sum=,pos=-; int main()
{
cin >> n >> w;
for(int i=;i<=n;i++)
{
cin >> dat[i],sum+=dat[i];
if(dat[i]==) pos=i;
} if(w< || w>sum || (n== && w!=sum) || (w== && pos==-))
return puts("No"),;
puts("Yes"); if(n==)
for(int i=;i<=*dat[];i++) putnum();
else if(w==)
{
dat[pos]--;
putnum(pos);
for(int i=;i<=n;i++)
for(int j=;j<=*dat[i];j++)
putnum(i);
putnum(pos);
}
else
{
w=w-;dat[]--;dat[]--;
for(int i=;i<=n;i++)
while(w && dat[i])
res[i]++,w--,dat[i]--;
putnum();
for(int i=;i<=n;i++)
for(int j=;j<=*dat[i];j++)
putnum(i);
putnum();putnum();
for(int i=;i<=*dat[];i++) putnum();
putnum();
for(int i=;i<=n;i++)
for(int j=;j<=*res[i];j++)
putnum(i);
}
return ;
}
Review:
对于构造题,要利用性质去除不符合条件的项
最新文章
- 页面与ViewModel(下)
- 运行DbVisualizer报the java_home environment viariable does not point to a working 32-bit JDK OR JRE错误
- IOS第七天(5:UiTableView 汽车品牌,复杂模型分组展示,A-Z索要列表) (2015-08-05 14:03)
- 织梦系统规律:查看网站是不是用dedecms建的
- Java注解配置
- 基础DOM和CSS操作(三)
- tahoma字体对中文字的影响
- linux下配置php Apache mysql
- 【模拟】【HDU1443】 Joseph
- 【网络协议】TCP中的四大定时器
- Orleans的集群构建
- SQLServer修改登陆账户信息
- twig模板基本学习
- js parseInt()与Number()区别
- 使用apksigner对apk进行v2签名
- Python 3下Matplotlib画图中文显示乱码的解决方法
- PCI 设备调试手段
- [django]django models最佳实战
- (转)awesome-text-summarization
- Lua程序设计(二)面向对象概念介绍
热门文章
- 证明spring中<;property name=";";>;这个双引号的内容只与setter方法有关,与一个类定义的字段和getter方法无关
- Socket和ServerSocket学习笔记
- ubuntu12.04 Qt WebKit编译
- C#与数据库的连接的三种方式
- loj6043 「雅礼集训 2017 Day7」蛐蛐国的修墙方案
- [POJ2954&;POJ1265]皮克定理的应用两例
- 【Luogu P3834】可持久化数组(可持久化线段树)
- mobius反演讲解
- Local Authentication Using Challenge Response with Yubikey for CentOS 7
- HDU1248 (完全背包简单变形)