题目 思路 题意： 给n个矩形，求它们重叠后的周长 题解： 用线段树的扫描线从下到上扫一遍，与面积并思想有些相似，下面重边的处理相似，但是周长的并需要求的是竖边的个数然后乘以高度，而面积并求的是底边的长乘以高度，这里我们用了区间合并时的l和r 结构体kk中，l表示当前节点区间左侧是否有竖边，r表示右侧是否有竖边，sum表示目前加进多少竖边，len表示底边长 标程： #include<algorithm>  #include<iostream>  #include<cstring>  #include<cstdio>  #include<cm...

我其实并没有省选的资格，我就是去打酱油的，感受一下省选的形式和膜拜一下大佬。  我连省选算法都几乎没学过，确切的说，是老师没教过，我大部分都自学过，但都不会，也都没写过程序，模板都没打过  时间：3.18——3.21 day1： 早上八点多从一中出发，中午到衢州二中。中途大概四个小时。刚开始无聊，找人聊天，后来ZJH推荐我下个八分音符玩玩，结果是声控的，车里比较嘈杂，玩不好，就下了个弓箭手大作战，我周围的三个都没带手机和笔记本，就用我的手机轮流玩，玩得都挺不错的。  到达后，领了准考证、笔记本、笔、袋子、饭票等东西，然后去吃饭。已经第三次来了，并不感到陌生。然后去宾馆，放了一下行李，再休息一下...

题目 题意： 所有士兵都在独木桥上。每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。问要用多少时间才能使所有士兵通过独木桥。 题解： 这题初看一点思路都没有，直接想到的是n^2模拟，但事实上很简单。  相遇其实相当于就是穿过对方，不用考虑对方的存在，每个士兵都是独立的，自己管自己走就行 标程： #include<bits/stdc++.h> using namespace std; int l,n,i,x,k,ma; int main(){ cin...

题目 题意： 有一些同样长的小木棍，把这些木棍随意砍成几段，直到每段的长都不超过50。输入切割后的每段木棍长度，求原始木棍的最小可能长度。 题解： 搜索，加上一些剪枝就行，详见标程 标程： #include<bits/stdc++.h> using namespace std; int n,i,sum,mx,x,a[65],use[65],cnt; int cmp(int x,int y){ return x>y; } void dfs(int ans,int s,int g,int now){//ans为当前还原的木棍长度 //s为已还原的木棍个数，g为每根木棍目标长度，n...

很好的一篇博客  这是我的代码 #include<bits/stdc++.h> using namespace std; const int N=4000003; const double pi=acos(-1.0); #define C Complex int r[N],n,m,i,lim=1,l; struct C{ double x,y; C(double xx=0,double yy=0){x=xx;y=yy;} }a[N],b[N]; C operator +(C a,C b){return C(a.x+b.x,a.y+b.y);} C operator -(C a,C ...

题目 题解： f[i][j][t][p]表示当前是p在走，走到(i,j)这格两人魔瓶内的魔液的差的绝对值为t的方案数  初值：f[i][j][x][0]=1，x为当前这个的魔液数量  状态转移方程：  f[i][j][t][0]+=f[i-1][j][(t-x+k)%k][1]+f[i][j-1][(t-x+k)%k][1]  f[i][j][t][1]+=f[i-1][j][(t+x)%k][0]+f[i][j-1][(t+x)%k][0] 标程： #include<bits/stdc++.h> using namespace std; const int M=100000000...

题目 题解： 贪心。因为每个点都要被覆盖，所以每次取最深的一个点k，取t为k的爷爷，然后覆盖所有与t距离为1、2的点 标程： #include<bits/stdc++.h> using namespace std; int n,i,j,k,mx,p,t,fa[1003],x,dep[1003],h,v[1003],tt; vector<int>a[1003]; int main(){ cin>>n; fa[1]=1; for (i=2;i<=n;i++) scanf("%d",&x),fa[i]=x,dep[i]=dep[x...

题目 题解： 易证：在某一时刻，关的路灯一定是连续的。  f[i][j][t]表示已经关了i….j的路灯，当前在i或j的最小功耗(t=0表示在i，t=1表示在j)  初始化：除了f[k][k][0,1]=0外，其他所有f[i][i][t]=inf  状态转移方程：  t=s[n]-s[j]+s[i];  f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*t,f[i+1][j][1]+(a[j]-a[i])*t)  t=s[n]-s[j-1]+s[i-1];  f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*t,f[i][j-1]...

题目 题解： 首先要知道的是高次方程无求根公式，所以解这个方程没有公式，套公式只能过30%的数据 一种方法是枚举1到m的正整数，判断行不行。 若用高精度则只能能拿50分，那如何优化呢？取模！ 设     f   (   x   )   =    a   0    +    a   1    ∗   x   +    a   2    ∗    x   2    +   .   .   +    a   n    ∗    x   n     f(x)=a_0+a_1*x+a_2*x^2+..+a_n*x^n   f(x)=a0​+a1​∗x+a2​∗x2+..+an​∗xn 若     f  ...

题目 学习博客 题解： 无向图双联通分量 详见注释 标程： #include<bits/stdc++.h> using namespace std; #define M(a) memset(a,0,sizeof(a)) #define v e[i].to typedef long long ll; const int N=503; struct kk{ int to,ne; }e[N*2];//双向建边，两倍 int tot,n,m,T,cnt,num,low[N],dfn[N],ans1,vis[N],cut[N],head[N],Case,x,y,tim,i; ll ans2;...

题目 题解： 与普通线段树基本相同，要注意的是乘的运算级别比加高，所以在做加法是不用管乘法，在做乘法时要管加法 标程： #include<bits/stdc++.h> using namespace std; #define update tr[t].su=tr[t<<1].su+tr[t<<1|1].su;if (tr[t].su>=M) tr[t].su-=M; //每个子程序最后都要写这句，更新tr[t].su typedef long long ll; const int N=100003; struct kk{ ll mu,su,ad; //...

题目  题解 标程： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50003; struct kk{ int x,id; }a[N]; ll ans,mn; int n,i,vis[N]; bool cmp(kk x,kk y){ return x.x<y.x; } ll solve(int k){ ll Min=a[k].x,sum=a[k].x; int p=a[k].id,cnt=0; vis[k]=1; while (p!=k){ sum+=a[p].x;...

题目 题解： f[i][j]表示用了前i个垃圾，垫高j的高度后，还能存活的时间（注意：不是总共能存活的时间）  初始化：f[0][0]=10，其他都是负无穷  状态转移方程：  1.吃垃圾 f[i][j]=max(f[i][j],f[i-1][j]-a[i].T+a[i-1].T+a[i].F)  2.垃圾垫脚 f[i][j]=max(f[i][j],f[i-1][j-a[i].H]-a[i].T+a[i-1].T)  但在转移前要判断是否可行。  注意：要先根据时间来排序 标程： #include<bits/stdc++.h> using namespace std; struc...

题目 题解： f[t][j]表示i连接j个用户的费用（可能是负数）  初始化：f[i][0]=0，其他为负无穷  状态转移方程：  1.t为用户 f[t][1]=mon[t-n+m]  2.t不为用户 f[t][j]=max(f[t][j],f[t][j-k]+f[e[i].to][k]-e[i].w)  e[i].to为连接的那个点，e[i].w为连接的费用 标程： #include<bits/stdc++.h> using namespace std; struct kk{ int to,ne,w; }e[3003]; int tot,n,m,i,k,x,y,f[3003][3...