T1 [luogu2920 USACO08NOV]时间管理
题解：
直接贪心（排序递推），注意处理-1的情况
code:
//By Menteur_Hxy
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define M(a,b) memset(a,(b),sizeof(a))
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define C(i,a,b) for(register int i=(b);i>=(a);i--)
#define E(i,u) for(register int i=head[u];i;i=nex[i])
using namespace std;
inline LL rd() {
LL x=0,fla=1; char c=' ';
while(!isdigit(c)) {if(c=='-') fla=-fla; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*fla;
}
inline void out(LL x){
int a[25],wei=0;
if(x<0) putchar('-'),x=-x;
for(;x;x/=10) a[++wei]=x%10;
if(wei==0){ puts("0"); return;}
for(int j=wei;j>=1;--j) putchar('0'+a[j]);
putchar('
');
}
const int N=100010;
int n,s;
struct things{
int t,s;
bool operator < (const things x) {return s>x.s;}
}th[N];
int main() {
// freopen("manage.in","r",stdin);
// freopen("manage.out","w",stdout);
n=rd();
F(i,1,n) th[i].t=rd(),th[i].s=rd();
sort(th+1,th+1+n);
int ans=0x3f3f3f3f;
F(i,1,n) {
if(th[i].s>=ans) ans-=th[i].t;
else if(th[i].s<ans) ans=th[i].s-th[i].t;
}
if(ans<0) return out(-1),0;
return out(ans),0;
}
T2 [luogu2515 HAOI2010]软件安装
题解：
考虑给出图的性质，发现有三种图（可能同时出现）：
纯树，纯环，树的根是环
所以我们可以缩点跑树形dp
考试时dp写错40分（手写数据失败，居然还有分）
code:
//By Menteur_Hxy
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define M(a,b) memset(a,(b),sizeof(a))
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define C(i,a,b) for(register int i=(b);i>=(a);i--)
#define E(i,u) for(register int i=head[u];i;i=nxt[i])
using namespace std;
inline LL rd() {
LL x=0,fla=1; char c=' ';
while(!isdigit(c)) {if(c=='-') fla=-fla; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*fla;
}
inline void out(LL x){
int a[25],wei=0;
if(x<0) putchar('-'),x=-x;
for(;x;x/=10) a[++wei]=x%10;
if(wei==0){ puts("0"); return;}
for(int j=wei;j>=1;--j) putchar('0'+a[j]);
putchar('
');
}
const int N=110,M=510;
int n,m,ecnt;
int vis[N<<2],we[N<<2],va[N<<2],dp[N<<2][M];
int to[N<<2],nxt[N<<2],head[N<<2];
void add(int a,int b) {
nxt[++ecnt]=head[a]; to[ecnt]=b; head[a]=ecnt;
}
int top,sta[N<<2],vist[N<<2],del[N<<2],flag;
void dfs(int u) { //tarjan弱化版
if(flag) return ;
sta[++top]=u;vis[u]=vist[u]=1;
E(i,u) { int v=to[i];
if(vis[v]&&vist[v]==0) continue;
else if(!vist[v]) dfs(v);
else {
n++;add(0,n);//新点连向虚根
while(sta[top]!=v) {
del[sta[top]]=1;
we[n]+=we[sta[top]],va[n]+=va[sta[top]];
E(j,sta[top]) add(n,to[j]);
top--;
}
del[sta[top]]=1;
we[n]+=we[sta[top]],va[n]+=va[sta[top]];
E(j,sta[top]) add(n,to[j]);
top--;
flag=1;//一个部分只会有一个环
}
}
vist[u]=0;top--;
}
void print(int x) {
F(i,0,m) cout<<dp[x][i]<<" ";
cout<<endl;
}
void dfs2(int u) {
F(i,we[u],m) dp[u][i]=va[u];
E(i,u) {
int v=to[i]; if(del[v]) continue;
dfs2(v);
C(j,we[u],m) F(k,0,j-we[u])
//考试时就这两行dp写错直接40分
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
int main() {
// freopen("software.in","r",stdin);
// freopen("software.out","w",stdout);
n=rd(),m=rd();
F(i,1,n) we[i]=rd();
F(i,1,n) va[i]=rd();
F(i,1,n) add(rd(),i);
F(i,1,n) if(!vis[i]) flag=top=0,dfs(i);
dfs2(0);
int ans=0;
// cout<<endl;
// F(i,0,n) print(i);
F(i,0,m) if(dp[0][ans]<dp[0][i]) ans=i;
out(dp[0][ans]);
return 0;
}
/* 假*手造数据
11 12
1 2 4 7 6 2 3 3 1 1 1
2 4 6 8 10 7 4 1 2 4 5
3 1 2 3 4 0 6 7 11 9 10
*/
T3 [luogu4198] 楼房重建
题解：
分析题目发现是要求斜率严格上升的数据个数
那么我们用线段树对斜率实现分治
我们在线段树中记录两个值：最大值(ma[cur])和严格上升序列长度(sum[cur])
由于一开始所有楼房为0所以只需update和pushup操作（答案为sum[1]）
update和pushup(ma[cur])好说，关键是对sum[cur]的pushup操作
我们将x处的斜率值修改，那么显然x左边的sum值不变直接加上
对于x右边的所有区间，我们判断其中的左区间ma值是否大于x
若大于，那么去统计右区间的答案
若小于，那么就用右区间的值+左区间统计出的答案
Q：为什么直接加上右区间的值？
A：根据性质我们知道右区间(cur<<1|1)统计在答案中的值(sum[cur]-sum[cur<<1])一定比左区间的大，所以直接加上
Q：为什么右区间的值是（sum[cur]-sum[cur<<1]）而不是（sum[cur<<1|1]）
A：因为sum[cur<<1|1]仅仅表示在右区间中的单调序列长度，其中统计到的斜率值不一定比左区间的大，所以统计到（sum[cur]）中的右区间斜率值<=（sum[cur<<1|1]）
eg: (1,2,3)(2,3,4)->(1,2,3,4) 右区间贡献：1
考试时n^2暴力QAQ
code:
//By Menteur_Hxy
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define M(a,b) memset(a,(b),sizeof(a))
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define C(i,a,b) for(register int i=(b);i>=(a);i--)
#define E(i,u) for(register int i=head[u];i;i=nex[i])
using namespace std;
inline LL rd() {
LL x=0,fla=1; char c=' ';
while(!isdigit(c)) {if(c=='-') fla=-fla; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*fla;
}
inline void out(LL x){
int a[25],wei=0;
if(x<0) putchar('-'),x=-x;
for(;x;x/=10) a[++wei]=x%10;
if(wei==0){ puts("0"); return;}
for(int j=wei;j>=1;--j) putchar('0'+a[j]);
putchar('
');
}
const int N=200010;
int n,m;
int sum[N<<1];
double ma[N<<1];
inline void pushup1(int cur) {
ma[cur]=max(ma[cur<<1],ma[cur<<1|1]);
}
inline int pushup2(int cur,int l,int r,double x) {
if(ma[cur]<=x) return 0;
if(l==r) return ma[cur]>x;
int mid=(l+r)>>1;
if(ma[cur<<1]<=x) return pushup2(cur<<1|1,mid+1,r,x);
else return pushup2(cur<<1,l,mid,x)+sum[cur]-sum[cur<<1];
}
inline void update(int cur,int l,int r,int id,double x) {
if(l==r) {
sum[cur]=1;
ma[cur]=x;
return ;
}
int mid=(l+r)>>1;
if(id<=mid) update(cur<<1,l,mid,id,x);
else update(cur<<1|1,mid+1,r,id,x);
pushup1(cur);
sum[cur]=sum[cur<<1]+pushup2(cur<<1|1,mid+1,r,ma[cur<<1]);
}
int main() {
n=rd(),m=rd();
F(i,1,m) {
int x=rd(),y=rd();
double k=(double)y/(double)x;
update(1,1,n,x,k);
printf("%d
",sum[1]);
}
return 0;
}