题目描述：一共有 n个数，第 i 个数是 xixi 可以取 [li , ri] 中任意的一个值。设S=∑xi2，求 S 种类数。 输入描述：第一行一个数 n。然后 n 行，每行两个数表示 li，ri。 输出描述：输出一行一个数表示答案。 思路:其实是个背包。有n个组，每组选一个数，问最后背包能装的体积有多少种方案。直接分组背包求解的话。n组，每组最多n个数，最大体积为n^3,复杂度为n^5,显然会TLE。所以考虑用bitset优化，复杂度为  #include<bits/stdc++.h> using namespace std; bitset<1005000> a,b...

题目描述：小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n 个车站，编号为1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi的价格。i 号线有 ci个车站，而且这 ci个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 s 个车站坐地铁到第 t 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 s 可能大于 t） 输入描述：第一行输入四个正整数 n,m,s,t分别表示车站个数，地铁线数，起点站和终点站。第二行到第 m ...

题目描述有一个长度为N的序列。一开始，这个序列是1, 2, 3,... n - 1, n的一个排列。 对这个序列，可以进行如下的操作： 每次选择序列中k个连续的数字，然后用这k个数字中最小的数字替换这k个数字中的每个数字。 我们希望进行了若干次操作后，序列中的每个数字都相等。请你找出需要操作的最少次数。 思路因为是全排列吧，所以一定有数字1，那么第一次选择的k个内肯定包含有一个1，那么剩下k-1个就都变成了1，同理，一直操作即可。那么n个数，有一个1了，还有n-1个需要变成1，每次最多可以让k-1个变成1，所以答案就是  #include<bits/stdc++.h> using ...

今天的每日一题比较简单。 题目描述齐齐和司机在玩单机游戏《红色警戒IV》，现在他们的游戏地图被划分成一个nm的方格地图。齐齐的基地在最上方的4行格内，司机的基地在最下方的4行格内。他们只有一种攻击方式：远程大炮，相关属性如下：1、 大炮可以打到地图的任意一个位置。2、 双方每次必须动用本方的一门大炮攻击，齐齐先手，双方交替进行攻击。3、 一方大炮只能攻击另一方大炮，不能攻击本方或强制攻击未获得视野的地区。4、 被一方大炮击中的另一方大炮会产生以攻击点为中心的33的波及区域，波及区域内如果有其他大炮则也会产生3*3的波及区域。5、 两方的基地相距很远，所以不存在攻打敌方大炮时波及到本方大炮的情况...

组合数学 卡特兰数+可重集排列数容易发现，一个右上走+一个右下走就等于一个往右走两步。考虑一下第一个点，不能走到y下面，对y坐标影响的只有右上和右下，那么我们把右上看成一个左括号，右下看成一个右括号，求合法括号方案数，那么其实方案数就是一个卡特兰数。那么这样的话，对于右上右下的已经处理好了，还差一个直接往右走的有i个，那么考虑这两部分结合，容易发现是一个可重集排列数，那么对于每个合法括号数里结合i个直接往右走的方案数有其中分子就是总的组成个数，右上右下总共有2(n-i)个，直接右走有i个,所以一共是2n-i个。那么最后答案就是  #include <bits/stdc++.h> u...

题意：有n个电影可以看，现在有一段持续时间为0到L，让这段时间内一直观看电影不存在空闲时间，每个电影有个持续播放的时间和电影的场次，以及每场的开始时间。一部电影只能进入观看一次，电影可以中途进入观看或者中途退出。问从0到L之间一直观看电影，最少要看几部电影。 思路：N只有20，容易想到状压转移的话，枚举i的每个二进制位，从剩余状态转移过来即可。如果dp[i]为time，那么意味着从1~i之间我们都是可以持续观看的，所以转移时候，我们找到当前要转移到的这个电影的一个开始场次≤time的位置，这里以为输入的电影场次的开始时间是单调的，可以通过二分得到。(注意一下这里的二分我们要的是≤的最后一个，可...

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 输入描述:第一行有一个...

思路：最后的答案一定是再两点之间一直徘徊着走。所以直接枚举，起始点一直往左走，然后再任意两点间徘徊。枚举起点一直往右走然后再任意两点间徘徊。考虑一下一种特殊的情况，就是我先往左走一个城市，然后一直往右走，或者先往右走一个城市，然后一直左走。为什么会有这样的走法？比如先往左走一下，在一直往右走，那么容易得到左走那一部分的路径走了两次。也就是说可能存在你右走要新去一个点的距离比这个大。所以宁愿走这个两倍的距离，虽然距离是两倍但走得相对于一直右走距离更短。那么往右走一下，在一直往走左也是同理。还有一种特殊情况。就是一直在起点左右两个城市一直来回徘徊。其实直观感觉上这样不是最优的，因为会下意识地认为走...

D. Carousel题意：n个数字围成一个环，现在要求对n个数进行染色。染色要求是，对于相邻的两个数，如果不同的话，要求颜色也要不一样。那么如果相邻两个数相同，颜色可以不同，也可以相同。思路：一、如果所有数字都一样的话，只需要染上同一种颜色即可。二、如果数字的个数有偶数个，那么只需要两种颜色，按照1 2 1 2...1 2 1 2这样染色即可。三、如果数字的个数有奇数个，去看遍历一下这个环，看是不是有相邻的数字是一样的，如果有，我们只需要对其中一组相邻的数字染上同一种颜色，对于剩下的继续按照1 2 1 2...1 2 1 2染色即可。其实这样等价是把奇数个数字变成了意义上的偶数个。(注意这是...

三维线性dpdp[i][0/1][0/1]表示到了第i位，当前位和下一位是不是烈焰的状态。第二维表示当前位置，第三维表示下一个位置。0表示不是，1表示是。为什么不需要多开一个维度表示上一位？ 容易发现dp[i]的上一位就是dp[i-1]的当前位。所以不需要。 容易得到转移方程如下： (上一位、当前位、下一位都是0)  （上一位是0，下一位是1或者上一位是1、下一位是0）  （上一位和下一位都是1）  (该位是1，上一位和下一位都不确定)    (该位、上一位、下一位都不确定)   #include<bits/stdc++.h> using namespace std; typede...

A 求导幂函数求导n-1次，就是n的阶乘 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; int main(){ ll ans=1; ll n;cin>>n; for(int i=1;i<=n;i++){ ans=ans*i%mod; } cout<<ans<<endl; return 0; }B 猜数如果n个数总和≥m，那么直接输出0。如果＜m，贪心即可，从0开始，每次加上(9-k) 直到总和≥m #include...

题意：给出n和m，要你构造出满足如下条件的n*n的矩阵， 1、矩阵内的元素A[i][j] = {0,1,2} 2、矩阵内的元素A[i][j] = A[j][i] 3、矩阵内的元素A[i][1]+A[i][2]+A[i][3]+...+A[i][n]=2 对于所有的 i 都成立 4、矩阵内的元素A[i][i]=0 对于所有的 i 都成立 问你有多少中构造方案，构造方案取模m。 思路：题中的要求，我们可以看出是n个点的邻接矩阵形式。每个点的度都是2，意味着图是一些环组成的，且不存在自环。根据数据范围，应该要求O(n)的复杂度，那么应该是个递推。那么我们考虑f[n]为n个点的方案数。考虑一下从n-1...

经典线段树问题。我们知道等差数列加上等差数列还是一个等差数列。所以我们线段树维护区间的总和，当前位置的值，和公差即可。对于求区间和，因为模数是根据输入的，我们发现模数只到了25，所以我们考虑计算出来mod=lcm(1,2,3,....25)这样的mod一定时1到25中任意一个数的倍数。那么我们输出的时候就可以保证输入的模数能够整除所求的区间和。 #include <cstdio> #include <algorithm> using namespace std; #define ll long long const int mod = 3 * 5 * 7 * 11 * ...

看着挺吓人的题面，但其实并不难就是个模拟题(阅读理解题)题意：现在两个人轮流玩游戏。两个人分别有一个长度为n的字符串，初始的血量都是m。每个字符串是每个人的技能连招，第i个字符位置，表示游戏进行到了第i秒。对于第一个人，第一个字符串如果连续三个字符是“ora” 就会对第二个人扣一滴血。对于第二个人第二个字符串如果连续四个字符是“muda” 就会对第一个人扣一滴血。两个人的大招一样。如果字符串是"zawaluduo",那么可以让对方血量清空，如果两个人同时放大招，第二个人速度更快，等于第一个人先挂现在让根据两个人的剩余血量的相对大小，输出不同的字符串即可。 思路也没啥思路，就是直接模拟过程即可。...