Waterfall

0x01 思路：首先想到的便是暴力+前缀和，O(n^2)1≤n≤100000显然过不去 就想了想二分 但突然想到，这不就是一个尺取法吗？ 尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。 但虽然说了这么多，我还是写的二分( 对于每一个点 p ，二分最大的点 q，使p到q的和小于等于t ​ t 会不会越界？不会，因为二分后 r = p - 1 ，r-p+1 的值为 0。 0x02 代码尺取法： 1234567891011121314151617181920212223242526#include<bits/stdc++.h>#define ll long longusin ...

题目链接十分简单的一道题，但也有一些使人崩溃小小的坑点，数据太弱，线段树什么的都不需要！ 但是！存在比赛跨年举办所以我们要对数据进行一定的处理！具体的就去看代码吧 code12345678910111213141516171819202122232425262728#include <math.h>#include <stdio.h>#define max(a,b) (a>b)?(a):(b)int n,f[566],a,b,c,d,maxn;int k[13]={0,0,31,59,90,120,151,181,212,243,273,304,334};int main()//QAQ{ // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); scanf("%d",&n); while(n--)  ...

要不再看看题？先明确题意，一等奖最少 $min1$ 人，最多 $max1$ 人二等奖最多 $min2$ 人，最少 $max2$ 人三等奖最多 $min3$ 人，最少 $max3$ 人只要参加，必定得奖当有多个奖项分配方案时，取一等奖最多的若一等奖数量相同，取二等奖最多的若二等奖数量相同，取三等奖最多的 思路：首先判断一等奖能否取 $max1$ 个若不能则二等奖三等奖个数均取最小值，剩下的人数就是一等奖在满足其他条件下的最多人数若能则判断二等奖能否取 $max2$ 个与上面基本相同 code:这么简单的题还要代码吗？12345678910111213141516171819202122232425262728#include <iostream>#include <cmath>#include <cstdio>using namespace std;int n,a[4],b[4];int ans;int main(){ cin>>n; for(int i=1;i<=3;i++) cin>>a ...

简单的二分图一：什么是二分图？二分图是神魔？可以二分查找吗 就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。——百度百科 二：为什么他是二分图？你说是就是？ 我们可以看出，由于子集中每个顶点之间都没有路径，故任选包含两个子集中元素的连通图合法 三：具体做法不愿看我哔哔的直接去看代码从上图可以看出，当顶点数量为偶数时，路径最多 n^2/4 条从上图可以看出，当顶点数量为奇数时，路径最多 n/2*(n/2+1) 条 再通过一个简单的枚举输出，便AC了 四：代码你们最期待的代码12345678910111213141516int main(){ cin>>n; if(n%2==0) { cout<<n*n/4<<endl; } else { cout<<(n/2)*(n/2+1)<<endl; } for(int i=1;i<=n/2;i++) for(int l= ...

图论模板0x00 最短路0x01 floyd123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>#include <cstdio>#include <cmath>using namespace std;void read(long long &a){ a=0; bool k=false; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') k=true; c=getchar(); } while(c>='0'&&c<='9') a*=10,a+=c-'0', c=getchar(); if(k)a=-a;} ...

0x01 引入两道例题相信大家首先想到的便是朴素的暴力，但T1 查询O(n^3) 与T2 修改O(mn) 的数据让人头疼。之后想到的便是前缀和维护，但无奈修改的操作提高了复杂度于是便引入了线段树树状数组！ 0x02 定义 树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。——某度百科 0x03 原理介绍一个操作：lowbit。作用是获得一个数二进制下最低位的1所代表的数值代码实现inline int lowbit(int a){return a&-a;}作用：实现一个如下图的数据结构于是，操作一个节点时只需要操作与他有上下级关系的节点就OK啦 另外 ...