A: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83690#problem/A
题意：N*M的格子，从左上走到右下，要求在每个点的权值必须大于0，问起始的时候必须有多少能量
思路：二分答案
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=510;
const int maxm=1010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int N,M;
int a[maxn][maxn];
int dp[maxn][maxn];
bool can(int x){
for(int i=0;i<=N;i++){
for(int j=0;j<=M;j++){
dp[i][j]=-INF;
}
}
dp[1][1]=x;
if(dp[1][1]<=0)return false;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
if(i==1&&j==1)continue;
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
if(dp[i][j]<=0)dp[i][j]=-INF;
}
}
return dp[N][M]>=0;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
scanf("%d",&a[i][j]);
}
}
int l=0,r=INF;
while(l<r){
int mid=(l+r)>>1;
if(can(mid))r=mid;
else l=mid+1;
}
printf("%d\n",r);
}
return 0;
}D: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83690#problem/D
题意：N个人，两两之间比赛，然后告诉你每个人赢了多少场，但里面存在错误，问最小修改多少分，能符合常理
思路：每次枚举分数最高的，然后把他输得分配下去，更新答案
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
const int maxm=1010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int N;
int a[maxn];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
int sum=0;
for(int i=1;i<=N;i++){
scanf("%d",&a[i]);
}
int ans=0;
for(int i=N;i>=1;i--){
sort(a+1,a+1+i);
if(a[i]>=i){
ans+=a[i]-i+1;
a[i]=i-1;
}
int cha=i-a[i]-1;
for(int j=i-1;j>=i-cha;j--){
a[j]--;
if(a[j]<0){
ans++;
a[j]=0;
}
}
}
printf("%d\n",ans);
}
return 0;
}前1个人，至少0场胜利，他可能全部败给后面的人，也可能赢了后面某几个人。
前2个人，至少要有1场胜利，他们之间必须有一人获胜，如果不够，就需要补足。如果大于1，表示他们之中有人赢了后面某几人。
前3个人，至少要有3场胜利 ………………
前4个人，至少要有6场胜利 ………………
等等…………
前n个人（即所有的人）时，至少要有n(n-1)/2场胜利，不够则补足。但如果大于n(n-1)/2，就表示胜利场数超了，此时需要将胜利场数更改回n(n-1)/2 。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int s[51],p[51];
int t,i,n,res;
for(cin>>t;t--;){
cin>>n;
for(i=0,res=0;i<n;i++){
cin>>s[i];
p[i]=i?p[i-1]+i:0;
}
sort(s,s+n);
for(i=0;i<n;i++){
s[i]=i?s[i-1]+s[i]:s[i];
if(p[i]>=s[i])
res+=p[i]-s[i],s[i]=p[i];
}
cout<<res+s[n-1]-p[n-1]<<endl;
}
return 0;
} H: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83690#problem/H
题意：找有多少个字串包含最大值和最小值，找有多少个子序列包含最大值最小值
思路：对于第一个，可以预处理出里每个位置最近的最大值和最小值，然后枚举开头。对于第二问设最大值的个数为cnt1，最小值的个数为cnt2，那么答案就是2N−2N−cnt1−2N−cnt2+2N−cnt1−cnt2
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
const int maxm=1010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int N;
int a[maxn];
LL f[maxn];
int pos[maxn][2];
void solve(){
int minv=INF,maxv=-INF;
int cnt1=0,cnt2=0;
for(int i=1;i<=N;i++){
if(a[i]<minv){
minv=a[i];
cnt1=1;
} else if(a[i]==minv){
cnt1++;
}
if(a[i]>maxv){
maxv=a[i];
cnt2=1;
} else if(a[i]==maxv){
cnt2++;
}
}
LL ans1=0,ans2=0;
if(maxv==minv){
ans1=(1LL*(N+1)*N/2)%MOD;
ans2=f[N]-1;
printf("%lld %lld\n",ans1,ans2);
return;
}
ans2=(f[N]-f[N-cnt1]-f[N-cnt2]+f[N-cnt1-cnt2])%MOD;
int pos1=-1,pos2=-1;
ans1=0;
for(int i=N;i>=1;i--){
if(a[i]==minv)pos1=i;
if(a[i]==maxv)pos2=i;
pos[i][0]=pos1,pos[i][1]=pos2;
}
for(int i=1;i<=N;i++){
if(pos[i][0]!=-1&&pos[i][1]!=-1){
int x=max(pos[i][0],pos[i][1]);
ans1+=N-(x-1);
if(ans1>=MOD)ans1-=MOD;
}
}
printf("%lld %lld\n",ans1,(ans2+MOD)%MOD);
}
int main(){
f[0]=1;
for(int i=1;i<maxn;i++){
f[i]=f[i-1]*2%MOD;
}
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d",&a[i]);
}
solve();
}
return 0;
}I: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83690#problem/I
题意：每条龙都有一个生存周期，也会有一个父亲，问每条龙存在的时候，最多跟他的子孙隔多少代
思路：因为要查询他的子孙，所以首先对每个节点求出dfs序，隔多少代其实就是树中深度差多少，然后按照d（死亡时间）排序，离线处理，对于出生时间h小于d的都加进去，然后查询，具体看代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
const int maxm=1010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
struct node{
int h,d,p,id;
node(){}
node(int _p,int _h,int _d,int _id):p(_p),h(_h),d(_d),id(_id){}
}a[maxn],b[maxn];
int dfn[maxn],dep[maxn],num[maxn];
int dfs_clock;
int N;
vector<int> G[maxn];
struct IntervalTree{
int maxv[maxn<<2];
void build(int o,int l,int r){
maxv[o]=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
}
void update(int o,int l,int r,int x,int val){
if(l==r){
maxv[o]=val;
return ;
}
int mid=(l+r)>>1;
if(x<=mid)update(o<<1,l,mid,x,val);
else update(o<<1|1,mid+1,r,x,val);
pushup(o);
}
void pushup(int o){
maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}
int query(int o,int l,int r,int q1,int q2){
if(q1<=l&&r<=q2){
return maxv[o];
}
int ans=0;
int mid=(l+r)>>1;
if(q1<=mid)ans=max(ans,query(o<<1,l,mid,q1,q2));
if(q2>mid)ans=max(ans,query(o<<1|1,mid+1,r,q1,q2));
return ans;
}
}tree;
void dfs(int u,int depth){
dep[u]=depth;
num[u]=1;
dfn[u]=++dfs_clock;
int len=G[u].size();
for(int i=0;i<len;i++){
int v=G[u][i];
dfs(v,depth+1);
num[u]+=num[v];
}
}
bool cmp(node A,node B){
return A.h<B.h;
}
bool cmp1(node A,node B){
return A.d<B.d;
}
int ans[maxn];
int main(){freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=0;i<=N;i++){
G[i].clear();
}
for(int i=0;i<N;i++){
scanf("%d%d%d",&a[i].p,&a[i].h,&a[i].d);
a[i].id=b[i].id=i;
b[i].p=a[i].p;
b[i].h=a[i].h;
b[i].d=a[i].d;
if(a[i].p!=-1)G[a[i].p].push_back(i);
}
dfs_clock=0;
dfs(0,0);
sort(a,a+N,cmp);
sort(b,b+N,cmp1);
tree.build(1,1,N);
int j=0;
for(int i=0;i<N;i++){
while(j<N&&a[j].h<=b[i].d){
tree.update(1,1,N,dfn[a[j].id],dep[a[j].id]);
j++;
}
ans[b[i].id]=tree.query(1,1,N,dfn[b[i].id],dfn[b[i].id]+num[b[i].id]-1)-dep[b[i].id];
}
for(int i=0;i<N;i++){
printf("%d",ans[i]);
if(i==N-1)printf("\n");
else printf(" ");
}
}
return 0;
}