首页 > 其他分享 >Codeforces 1004B Sonya and Exhibition 题解

Codeforces 1004B Sonya and Exhibition 题解

时间:2024-05-15 22:43:33浏览次数:27  
标签:int 题解 cin Codeforces Sonya 1004B define

题目简述

让你构造一个长度为 $n$ 的 $01$ 字符串。一个区间的价值为其中 $0$ 的数量乘以 $1$ 的数量,给出 $m$ 个区间,最大化它们的价值之和。

题目分析

设区间 $[l,r]$ 中 $1$ 有 $x$ 个,$0$ 有 $y$ 个,当 $x$ 和 $y$ 最接近的时候,$x \times y$ 最大,此结论可以用二次函数进行证明。接下来,考虑怎样构造使得 $x$ 与 $y$ 最接近。策略是交替输出 $0$ 和 $1$,这样做的正确性是显然的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
int n,m,l,r;
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
	For(i,1,n)
	{
		cin>>l>>r;
	} 
	For(i,1,m)
	{
		cout<<(i&1);
	}
	return 0;
}

标签:int,题解,cin,Codeforces,Sonya,1004B,define
From: https://www.cnblogs.com/zhuluoan/p/18194847

相关文章

  • AT_arc042_c的题解
    (一)非常妙的DP题,可惜被翻译毁了。题意:你有一堆零食,每个零食有两个值\(a_i\)和\(b_i\)。要求选出集合\(S\),使\(\sum_{i\inS}a_i-\min_{i\inS}a_i\lep\),求最大的\(\sum_{i\inS}b_i\)。一眼DP。先将\(a_i\)从小到大排序,每次循环更新\(dp_0\)的值为\(\max......
  • P10447 最短 Hamilton 路径 题解
    P10447最短Hamilton路径题解题目传送门题意:给定一张有向带权图(\(n\le20\))求点\(0\)到点\(n-1\)的最短哈密顿路径。这是一道状压DP模板题。在状态压缩DP中,我们将一个集合压成一个二进制数。设\(f_{u,i}\)为已经走了集合\(u\)中的节点,且现在在点\(i\)的最短......
  • CF1886E 题解
    CF1886E思路观察发现每个项目只与程序员数量和最小值有关,所以每个项目对应能力值连续的程序员最优。项目数\(m\le20\),状压。设\(dp_{i,s}\)为前\(i\)个程序员匹配的项目状态为\(s\)是否可行,无法接受。交换维度,改为\(dp_s\)表示状态\(s\)能与前缀\([1,i]\)匹配的......
  • 旅行 题解
    题目链接。题意简述给定一张有向图,求从点\(A\)走到点\(B\)的一条路径,这条路径满足:经过的边的权值总和是\(P\)的倍数。在满足条件\(1\)的情况下,经过的边的权值总和最小。题目分析本题可以使用分层图最短路来解决。仿照动态规划的思想,定义\(f_{x,y}\)表示从节点......
  • echarts图由于容器隐藏导致图表不显示问题解决办法
    开发过程中常常会遇到echarts图由于容器隐藏导致图表不显示问题,最简单的办法就是给容器元素加上宽度和高度容器加上固定的宽度和高度<divid="res"style="height:450px;width:1200px"></div>然而在实际开发中某些场景下,要求图表宽度100%显示,而计算容器的宽度有时又会十分的麻......
  • CF1965D Missing Subarray Sum题解
    题目链接点击打开链接题目解法感觉一点都不好想\fn因为最后的序列\(a\)是回文的,所以只有以中心点对称的子段和出现次数为奇数,其他都为偶数考虑有没有什么知道所有子段和的做法,可以方便推出缺失一个的答案令\(g_{l,r}\)为\(l\)到\(r\)的子段和知道\(g_{1,n}\)删......
  • P9175 [COCI2022-2023#4] Mreža 题解
    P9175[COCI2022-2023#4]Mreža题解前言我发现,有整体二分与主席树的地方总有莫队(不是那个莫队,是那个莫队)。知识点(树上)倍增,(树上)莫队,树状数组(“树”含量满满),分块。题意分析给定一棵树,每条边有一个权值\(v\),以及可以用一个花费\(c\)将它变成更大的权值\(s\)。再给定一......
  • Little Pony and Lord Tirek 题解
    LittlePonyandLordTirek题解\(\texttt{ProblemLink}\)题目大意给定长度为\(n\)的序列,第\(i\)个数有三个值:\(s_i,m_i,r_i\),每秒对于每个数执行\(s_i\leftarrow\min\{s_i+r_i,m_i\}\)。有\(m\)个查询,每次查询三个值:\(t,l,r\)查询时刻\(t\),\([l,......
  • [H&NCTF] maybe_xor题解
    maybe_xor感觉这道逆向题与其说是考逆向水平,倒不如说是考编写脚本的能力首先题目给了个远程地址,nc连接会回显ELF:接一串base64编码的东东,解码后发现是ELF文件。用IDA打开发现是从数据段读取24个字节到栈上并进行异或,每个字节异或的值都不同,但异或后的结果不会写回栈程序的目......
  • [题解] Flipping Game
    题目描述有n盏灯,每个灯有开和关两种状态。每按一次灯会变成相反的状态。给定灯初始的开关状态和结束的开关状态,若操作k轮,每轮要按m个不同的灯,问有多少种方法使灯由初始状态变到结束状态。题解需注意每轮要按不同的灯,若无这个条件,暴力计算组合数即可。要操作多轮,且每轮按灯的......