幽默的世界
洛谷十月月赛 幽默的世界题目描述
给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$,定义 $a$ 的一个连续子序列 $a_l,a_{l+1},\cdots,a_r$ 是幽默的,当且仅当:
$\sum\limits_{i=l}^ra_i>0$;
对于所有 $l\le x\le y<r$,满足 $\sum\limits_{i=x}^y a_i\le 0$。
$q$ 次询问,每次给定两个整数 $l,r$,查询满足以下条件的数对 $(l’,r’)$ 个数:
$l\le l’\le r’\le r$;
连续子序列 $a_{l’},a_{l’+1},\cdots a_{r’}$ 是幽默的。
输入格式
第一行输入两个整数 $n,q$。
接下来一行输入 $n$ 个整数,第 $i$ 个整数代表 $a_i$。
接下来 $q$ 行,每行输入两个整数 $l,r$,代表一次询问。
输出格式
对于每组询问,输出一行一个整数,代表答案。
样例输入
123456787 6-1 2 -1 -1 -1 2 -12 54 71 75 51 32 4
样例输出
12345612402 ...
『GROI-R2』不空白的画布
洛谷九月月赛『GROI-R2』 不空白的画布你有连续的 $n$ 个方格,每个方格上有一个初始颜色 $c_i$,且保证 $1\le c_i \le k$。
你可以操作至多 $m$ 次,每个操作为改变某个方格颜色,要求改变后的颜色范围仍在 $[1,k]$ 内。
我们称一个极长相同颜色连续段为一块,要求求出经过至多 $m$ 次操作后的最多块数。
输入格式
本题有多组测试数据。
第一行输入一个正整数 $T$ 表示数据组数。
对于每组测试数据,第一行输入三个正整数 $n,m,k$,表示画布的长度,坦尼尔作画的次数上限和颜色的取值范围。
第二行输入一个长度为 $n$ 的整数序列 $c$,表示画布上每个位置的初始颜色。
输出格式
对于每组测试数据,输出一行一个正整数,表示记忆碎片最多有多少个。
样例输入
1234523 1 32 2 25 2 42 2 2 2 3
样例输出
1235
样例解释
对于第一组测试数据,坦尼尔可以将从左到右的第二个位置涂成颜色 $1$,得到 $\{c_n\}=\{2,1,2\}$,块数为 $3$。
对于第二组测试数据,坦尼尔可以将从左到右的第二个位置涂成颜色 $1$, ...
对拍器与数据生成
对拍器模板1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>#define random(a, b) ((a)+rand()%((b)-(a)+1))using namespace std;void create_dataset() { ofstream fout("input.txt"); fout.close();}bool work() { create_dataset();//system("stand.exe < input.txt > stand.txt");//system("my.exe < input.txt > my.txt"); system("stand.exe < input.txt"); system("my.exe < input.txt"); r ...
20thZJCPC
省赛补题,顺序大致按难度(赛时通过人数)排列
CF的gym里暂时还没有今年省赛的题目上传,目前只查到了D/F/G/H/I的补题链接2023.08.22
A.Look and Say
翻译:
给一个数字序列,你需要使用以下方法“描述”它:
1.每段划分成最大的连续相同的数字;
2 . 对于每段,将其替换为段的长度加段中的数字。例如,“0” 应替换为 “10”, ”9999999999“ 应替换为“109”
3.将替换的段连接在一起并输出
输入:
第一行包含一个整数n,范围是[1,1000],表示输入序列的长度;
第二行为一个长度为n的序列,表示原始序列
输出:
输出转换后的序列
签到题,就是相同连续的数字压缩成长度+数字的组合输出
12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;int n, cnt = 1;char pre = '#', t;signed main() { freopen("input.tx ...
算法大赛2023-村庄
1234564 5 31 22 33 44 11 3
13
数据范围:2 <= N <= 10^51 <= K <= M <= 10^51 <= ai < bi <= N所有的村庄组合(ai, bi) 各不相同。将村庄看成点,桥看成边,显然一开始给你的一定是所有的点都可以通过某条边直接或者间接相连,那么村庄的组合就是$C_{n}^{2} = \frac{n*(n-1)}{2} $,即选出两个村庄进行组合。去除一些边后问你毁了多少个组合。所以思路就是求连通块,计算每个连通块有多少个点,用组合数的公式进行计算还剩下多少个点,计算之后再减去总的村庄组合。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<bits/stdc++.h>#define ll long long#define M 100005using namespace std;struct Node ...
E-梅莉的市场经济学
[传智杯 #5 初赛] E-梅莉的市场经济学题目背景梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析,为此她时常抱怨自己学不会,想退课。但是如果现在退掉的话这学期的学分就不够啦,因此她根据“梦中”的经历,“胡诌”了一个简单到不现实的市场模型,并依据这个模型编起了 essay。为了方便地编出图表,她需要写一个程序来查询每个时刻的市场贸易差。题目描述市场每一天的贸易差可以视为一个有周期性规律的数列a:$\color{red}[0],\color{blue}[0, 1, 0, -1, 0],\color{red}[0, 1, 2, 1, 0, -1, -2, -1, 0], \color{blue}[0, 1, 2,3, 2, 1, 0, -1, -2, -3, -2, -1, 0]\dots$。具体而言,a 可以被分为无穷段,第 i 段的内容为 $\{0, 1,\cdots,i,i-1, \cdots,0, -1, \cdots,-i, -i+1,\cdots 0\}$如下图所示,是将a数列内的前一些点绘制在坐标轴上的情况:现在梅莉对市场发起了 q次询问,每次她会给定 ...