题意 给你一个长度为n的序列，你每次可以将一个序列分割成两个连续的的子序列，分割的代价为原序列的总和。现在允许你在初始时将序列重新排列一次。问分割成n个长度为1的序列的最大总代价是多少？ 输入描述 第一行一个数n表示原序列的长度；接下来一行n个数a_i表示原序列的第i个数。2<=n<=1000000<=a_i<=10000 输出描述 一行一个整数表示答案。 解析 很简单的贪心，每一次切割我们都要把全部都加起来，我们只要保证越大的数在数列中带的越久，那么他对结果的贡献就越多，所以我们每一次切割都从小往大的走，每一次都把数列中当前最小的一个数切割出去，这样子越...

题意 Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！ 输入描述 第一行，两个正整数n和s，表示城市个数和第一天住宿的城市s。接下来n-1行，每行两个整数x和y，表示城市x与城市y之间有一条双向道路。 输出描述 ...

题意 n支队伍一共参加了三场比赛。一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。(x, y), (y, x)算一组。 输入描述 第一行一个整数n，表示队伍数； 接下来n行，每行三个整数a[i], b[i], c[i]，分别表示i在第一场、第二场和第三场比赛中的名次；n 最大不超过200000请在这里输入引用内容 输出描述 输出一个整数表示满足条件的(x,y)数；64bit请用lld 解析 题目的意思就当有一场比赛的排名比对方更高的时候，就觉得自己比对方更强，然后题目中的x比y强的同时，y...

题意 求以xx结尾的长度为ll的不下降正整数数列一共有多少个。对911451407911451407取模 输入描述 本题有多组数据。第一行一个正整数TT，表示数据组数。对于每组数据：两个用空格隔开的整数l, xl,x。 输出描述 T行，每行一个答案。 解析 看了隔壁大佬的博客大佬博客 打表找规律 最后得出递推式 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int mod = 911451407;...

题意 给定一个长度为 n 的数组。要求相临的数大小不相同，假如相临数的相同，你可以通过将 a[i]+1 来改变它的大小，但是需要付出 b[i]的代价，同时对于每个 a[i]只能加一次。问你付出的最小代价。 输入描述 第 1 行 1 个整数 n，表示数组长度为 n接下来 n 行，每行 2 个正整数 a[i]与 b[i]，表示 a 数组中的第 i 个数，以及将第 i 个数+1 的代价。对于20%的数据，保证b[i] = 1对于另外10%的数据，保证所有a[i]相等对于另外10%的数据，保证所有的a[i]不相等对于100%的数据，1<=n<=2e5，0<=a[i]、b[i]&...

题意 埋和莫曾经是好朋友。埋是文科学霸，而莫却只是一个 OI 蒟蒻。一天，埋碰到一道难题跑来问莫。题目是这样的：有五个数字，分别是 5、2、1、3、9.莫可以取任意数字，每个数字可以取无限次。如：取两个 5，则组合为：55；取 2 与 1，则组合为：21。现在要问你所有组合中第 C(n, m)%1e9+7 (n>=m) 个数有多大？ 输入描述 第 1 行一个数 t，表示询问的次数接下来 t 行，每行两个数 n, m；详情见题目描述。数据范围：对于20%的数据，保证t=1对于10%的数据，保证n=m对于所有数据，保证1<=t<=10001<=m<=n<=...

题意 犇犇是一只贪玩的牛。他最喜欢的游戏是夹娃娃。已知有 n 个娃娃排成一排，犇犇可以控制夹子的位置和夹子的宽度。每个娃娃的价值为整数 w[i]，犇犇想知道，他夹起的l 到r 个娃娃的总价值是多少 输入描述 第 1 行两个正整数 n，k。n 表示娃娃的个数，k 表示询问的次数第 2 行 n 个正整数，表示数组 w，第 i 个数字表示 w[i]接下来的 k 行，每行两个正整数 l，r。表示犇犇抓起来的娃娃的范围。数据范围：对于20%的数据，保证l=r对于30%的数据，保证n<=100对于20%的数据，保证k<=100对于所有数据：1<=n<=1e5, 1<=...

<h2>解析</h2>这个题目如果只看前半部分不难想到这个题目就是一个多维的dp，后面的描述具有一定的迷惑性，但是并不能影响这个题目用dp的做法，看了一些大佬的代码都对后面的那些进行了分析，个人感觉不做分析也可以做。 首先我们来看这个题目，我们可以看成两个人在两个管子里取球，然后取球相同的情况，稍后解释为什么能看成这个模型，我们可以设置一个dp数组dp[i][j][k][l]，表示第一个人在第一个管子里取i个，在第二个管子里取j个，第二个人在第一个管子里取k个，第二个管子里取l个。但是这个四维数组无论是时间还是空间，在这个题目中明显都不能...

题意 在网友的国度***有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。 在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。 两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个...

题意 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。 输入描述 第一行包含一个整数 n ，表示大臣的人数。第二行包含两个整数...

题意 在遥远的米♂奇♂妙♂妙♂屋里住着一群自然数，他们没事就喜欢拆♂开自己来探♂究。现在他们想知道自己最多能被拆分成多少个不同的自然数，使得这些自然数相乘的值等于被拆分的数。 输入描述 第1行输入一个整数T，代表有T组数据。第2-T+1行，每行输入一个整数n，代表需要被拆分的数。数据保证：0<T≤100，0<n≤109。 输出描述 输出一共T行，第i行输出一个整数，代表第i行输入的n最多可以被拆分成多少个不同的自然数。 解析 拆分的话就直接穷举，直接从最小的开始穷举，从一开始穷举到n，但是很明显从某一个位置开始后面的穷举就没有必要了。 除了1以外，所有的数都存在一个...

题意 小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全 毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。 输入描述 第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑...

解析 1.前m次操作可以用前缀和模拟区间加，得到每个糖糖的新能力值后从后往前维护每个队伍的最大值，当前糖糖的能力值如果大于后面敌对队伍糖糖的最大值，也就是比后面的糖糖都强，那么他存活，反之白给。复杂度θ (n)。 2.如果从前往后判断第i糖糖能不能存活，还要搜索后面i-1个糖糖，复杂度θ (n^2)。 代码 #include<bits/stdc++.h> using namespace std; int mx[2],sum[50005],b[50005],team[50005],n,m,t,c; int main(void) { cin>>t; wh...

A,小A买彩票 题意 小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。 0≤n≤30 输入描述 一行一个整数N，为小A购买的彩票数量 输出描述 输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。 解析 首先他要能不亏本，那么买一张的时候要买到3或者4，两张的时候要总和超过6，可以是33，34，43，44，24，42，这么多种情况，所以我们就...