这个难度有点迷，..我就捋一下顺序然后说吧，这个题目难度不是按照T题的日常难度来排的，我就顺便排一下..
暴0不开心 什么时候我能够AK一次呢 qwqq
CCL 的消遣(CCL)
[题目描述]
AS we know,CCL 是一个很无聊很无聊很无聊的人.有一天,CCL 注意到地面上有很多棍子,
于是,CCL 决定用这些棍子来消磨时间(这是要有多无聊啊).
CCL先将这些棍子排成一排.每根棍子有一个长度.CCL一次可以将2个相邻的棍子合并成
一根更长的棍子,合并出的棍子的长度为原来 2 根棍子的长度之和(具体的过程请参考样
例).CCL 想用最少的合并次数来将这些棍子变成一个长度不降的序列.
[输入格式]
输入文件的第一行有一个正整数 n,表示棍子的数目.
接下来一行 n 个正整数,依次表示每根木棍的长度.
[输出格式]
输出文件一行仅一个数,表示最少的合并次数.
[样例输入]
5
8 2 7 3 1
[样例输出]
3
[样例解释]
最优方案是将后 4 根木棍合并,形成一个长度为 13 的棍子,共需要 3 次合并操作.
合并后的序列为:8,13.
[数据范围]
10%的数据,N<=1500
20%的数据,N<=5000
50%的数据,N<=200000
100%的数据,N<=1000000,每根棍子的长度<=maxlongint
暴力过10分.. 那就写正解好了
#define fre yes
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
long long arr[maxn];
long long w[maxn],f[maxn],c[maxn];
long long n,k,ans;
template<typename T>inline void read(T&x)
{
x = 0;char c;int lenp = 1;
do { c = getchar();if(c == '-') lenp = -1; } while(!isdigit(c));
do { x = x * 10 + c - '0';c = getchar(); } while(isdigit(c));
x *= lenp;
}
int main()
{
#ifdef fre
freopen("CCL.in","r",stdin);
freopen("CCL.out","w",stdout);
#endif
memset(f,0x3f3f3f3f,sizeof(f));
read(n);
for (int i=1;i<=n;i++)
{
int x;
read(x);
arr[i] = x;
arr[i] = arr[i-1] + arr[i];
}
long long l = 1,r = 1; f[0] = 0; w[0] = 0;
for (int i=1;i<=n;i++)
{
while(l < r && arr[i] >= f[w[l+1]]) l++;
f[i] = arr[i] - arr[w[l]] + arr[i];
c[i] = c[w[l]] + i - w[l] - 1;
while(r > l && f[i] <= f[w[r]]) r--;
w[++r] = i;
} printf("%lld
",c[n]);
return 0;
}
春宵的烦恼(CWX) [题目描述] 春宵有一个烦恼:他的手太粗了!!!每次春宵想打开一个灯,他会把周围的 2 个灯的开关 (共 3 个开关)也按到.于是,为了打开一个灯,春宵需要多做许多操作,才能够将灯打开. 春宵很聪明,他总能找到一个方法使灯从一种初始状态转化为目标状态.但是春宵不知道 有没有更快捷的方法来达到目标状态.春宵也常常为此苦恼. 为了帮助春宵脱离苦海,请你写一个程序帮春宵找到从一种初始状态转化到一个结束状 态的最少的按开关的次数. [输入格式] 输入数据有多组测试数据. 输入第一行为一个正整数 t,表示测试数据的组数. 接下来 2*t 行,第 2*i-1 行是一个长度为 30 的 01 串,表示初始状态,第 2*i 行是一个长度为 30 的 01 串,表示结束状态.每两个数字间用一个空格隔开. [输出格式] 输出文件共 t 行.每行一个正整数表示最少的步数. [样例输入] 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [样例输出] 2 0 4 [样例解释] case1: 春宵可以按最左边和最右边的两个开关,这样会同时按到第1,2,29,30个灯的开关,从而达 到目标状态 Case2: 初始状态即为目标状态,春宵什么也不需要做. Case3: 春宵可以按第 2,4,27,29 个开关,从而达到目标状态. [数据约定] 30%的数据,01 串的后 20 位是 0. 60%的数据,01 串的后 10 位是 0. 100%的数据,T<=20. [提示] 第一个灯的状态只与第 1,2 个开关有关,最后一个灯的状态只与最后两个开关有关. 输入数据保证有解.
DRJ 的跃迁(DRJ) [题目描述] 在一个无限大的平面上有若干个 DRJ,每个 DRJ 都处于一个确定的点上.一个点上可能有 多个 DRJ.为了方便起见,我们将某一个 DRJ 所在的位置标为(0,0),所有的 DRJ 所处的位置恰好 都是整点(坐标为整数).我们称所有的 DRJ 所处位置构成的多元组为一个分布,用 S 来表示. 当一个 DRJ 处于不同的位置时,他会拥有不同的势能.在同一位置的两个 DRJ 的势能相等. 一个处于高能状态的 DRJ 可以通过跃迁到达低能状态,一个处于低能状态的 DRJ 也可以通过 跃迁到达高能状态.在跃迁的过程中势能的总量总是不变的. 一般地,我们设一个 DRJ 在(x,y)上的势能为 W[X,Y],那么有: (1) w[x,y]=w[x-1,y-1]+w[x-1,y] (2) w[x,y]=w[x-1,y-1]+w[x,y-1] (3) 若干势能之和为 A 的 DRJ 可以通过不断跃迁转化为任意分布的势能之和为 A 的 DRJ 例如,如果初始状态在点(10,10)上有一个 DRJ,那么他可以通过跃迁转化成一个位于(9,9) 的 DRj 和一个位于(9,10)的 DRJ.如果初始状态在点(9,9)和点(10,9)上分别有一个 DRJ,则他们可 以通过跃迁转化成一个位于点(10,10)的 DRJ. 为了研究 DRJ 之间的相互关系,我们称一对等价分布为一对可以通过跃迁而相互转化的 分布,一组 DRJ(简称 S)的 K 类分布(简称 K-S)是这样的一种分布: (1)K-S 与 S 是等价分布. (2)K-S 中所有的 DRJ 都在 Y=K 这条直线上. (3)K-S 中相邻两个整点上的 DRJ 不超过 1 个. 例如,((5,0),(4,1))的 1-S 分布为((5,1)). 很明显,当 k 确定时,一个分布 S 所对应的 K 类分布是唯一的.你的任务是对于给定的分布 S,求出 0-S. [输入格式] 输入文件的第一行为一个正整数 N,表示平面上有 N 个点上有 DRJ. 接下来有 N 行,每行三个整数 xi,yi,si,表示第 i 个点的坐标及位于 i 点上的 DRJ 的数量. 输入数据给出的第一个点的坐标是(0,0). [输出格式] 输出文件仅一行,包含若干个以空格隔开的整数.第 i 个整数 Ai 表示在 0-S 分布中,(Ai,0) 上有一个 DRJ.应注意这些整数应该以递增的顺序输出. [样例输入] 3 0 0 1 4 -1 1 4 0 1 [样例输出] 0 5 [样例解释] 第二,三个 DRJ 可以通过跃迁转化为 1 个位于(5,0)的 DRJ,这时所有的 DRJ 的分布状态是一 个合法的 0-S 分布,两个 DRJ 的位置分别为(0,0)和(5,0). [数据范围] 对于所有数据,N<=10000,Xi+Yi<=10000,Si<=10^8 输入数据保证合法.