?

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; }

轉載于:https://www.cnblogs.com/13224ACMer/p/4744350.html

總結

以上是生活随笔為你收集整理的2015暑假训练（UVALive 5983 - 5992）线段树离线处理+dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。