找工程去哪个网站,网站制作公司兴田德润简介,网站优化培训,衡阳 网络 网站A: http://acm.hust.edu.cn/vjudge/contest/view.action?cid83690#problem/A 题意#xff1a;N*M的格子#xff0c;从左上走到右下#xff0c;要求在每个点的权值必须大于0#xff0c;问起始的时候必须有多少能量 思路#xff1a;二分答案 #includeiostream
#i… A: http://acm.hust.edu.cn/vjudge/contest/view.action?cid83690#problem/A 题意N*M的格子从左上走到右下要求在每个点的权值必须大于0问起始的时候必须有多少能量 思路二分答案 #includeiostream
#includecstdio
#includestring
#includecstring
#includevector #includecmath #includequeue #includestack #includemap #includeset #includealgorithm using namespace std; typedef long long LL; const int maxn510; const int maxm1010; const int MOD1e97; const int INF0x3f3f3f3f; int N,M; int a[maxn][maxn]; int dp[maxn][maxn]; bool can(int x){ for(int i0;iN;i){ for(int j0;jM;j){ dp[i][j]-INF; } } dp[1][1]x; if(dp[1][1]0)return false; for(int i1;iN;i){ for(int j1;jM;j){ if(i1j1)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 i1;iN;i){ for(int j1;jM;j){ scanf(%d,a[i][j]); } } int l0,rINF; while(lr){ int mid(lr)1; if(can(mid))rmid; else lmid1; } printf(%d\n,r); } return 0; } D: http://acm.hust.edu.cn/vjudge/contest/view.action?cid83690#problem/D 题意N个人两两之间比赛然后告诉你每个人赢了多少场但里面存在错误问最小修改多少分能符合常理 思路每次枚举分数最高的然后把他输得分配下去更新答案 #includeiostream
#includecstdio
#includestring
#includecstring
#includevector #includecmath #includequeue #includestack #includemap #includeset #includealgorithm using namespace std; typedef long long LL; const int maxn100010; const int maxm1010; const int MOD1e97; const int INF0x3f3f3f3f; int N; int a[maxn]; int main(){ int T; scanf(%d,T); while(T--){ scanf(%d,N); int sum0; for(int i1;iN;i){ scanf(%d,a[i]); } int ans0; for(int iN;i1;i--){ sort(a1,a1i); if(a[i]i){ ansa[i]-i1; a[i]i-1; } int chai-a[i]-1; for(int ji-1;ji-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 。 #includecstdio
#includealgorithm
#includeiostream
using namespace std; int main(){ int s[51],p[51]; int t,i,n,res; for(cint;t--;){ cinn; for(i0,res0;in;i){ cins[i]; p[i]i?p[i-1]i:0; } sort(s,sn); for(i0;in;i){ s[i]i?s[i-1]s[i]:s[i]; if(p[i]s[i]) resp[i]-s[i],s[i]p[i]; } coutress[n-1]-p[n-1]endl; } return 0; } H: http://acm.hust.edu.cn/vjudge/contest/view.action?cid83690#problem/H 题意找有多少个字串包含最大值和最小值找有多少个子序列包含最大值最小值 思路对于第一个可以预处理出里每个位置最近的最大值和最小值然后枚举开头。对于第二问设最大值的个数为cnt1最小值的个数为cnt2那么答案就是2N−2N−cnt1−2N−cnt22N−cnt1−cnt2 #includeiostream
#includecstdio
#includestring
#includecstring
#includevector #includecmath #includequeue #includestack #includemap #includeset #includealgorithm using namespace std; typedef long long LL; const int maxn100010; const int maxm1010; const int MOD1e97; const int INF0x3f3f3f3f; int N; int a[maxn]; LL f[maxn]; int pos[maxn][2]; void solve(){ int minvINF,maxv-INF; int cnt10,cnt20; for(int i1;iN;i){ if(a[i]minv){ minva[i]; cnt11; } else if(a[i]minv){ cnt1; } if(a[i]maxv){ maxva[i]; cnt21; } else if(a[i]maxv){ cnt2; } } LL ans10,ans20; if(maxvminv){ ans1(1LL*(N1)*N/2)%MOD; ans2f[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; ans10; for(int iN;i1;i--){ if(a[i]minv)pos1i; if(a[i]maxv)pos2i; pos[i][0]pos1,pos[i][1]pos2; } for(int i1;iN;i){ if(pos[i][0]!-1pos[i][1]!-1){ int xmax(pos[i][0],pos[i][1]); ans1N-(x-1); if(ans1MOD)ans1-MOD; } } printf(%lld %lld\n,ans1,(ans2MOD)%MOD); } int main(){ f[0]1; for(int i1;imaxn;i){ f[i]f[i-1]*2%MOD; } int T; scanf(%d,T); while(T--){ scanf(%d,N); for(int i1;iN;i){ scanf(%d,a[i]); } solve(); } return 0; } I: http://acm.hust.edu.cn/vjudge/contest/view.action?cid83690#problem/I 题意每条龙都有一个生存周期也会有一个父亲问每条龙存在的时候最多跟他的子孙隔多少代 思路因为要查询他的子孙所以首先对每个节点求出dfs序隔多少代其实就是树中深度差多少然后按照d死亡时间排序离线处理对于出生时间h小于d的都加进去然后查询具体看代码 #includeiostream
#includecstdio
#includestring
#includecstring
#includevector #includecmath #includequeue #includestack #includemap #includeset #includealgorithm using namespace std; typedef long long LL; const int maxn100010; const int maxm1010; const int MOD1e97; const int INF0x3f3f3f3f; 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; vectorint G[maxn]; struct IntervalTree{ int maxv[maxn2]; void build(int o,int l,int r){ maxv[o]0; if(lr){ return ; } int mid(lr)1; build(o1,l,mid); build(o1|1,mid1,r); } void update(int o,int l,int r,int x,int val){ if(lr){ maxv[o]val; return ; } int mid(lr)1; if(xmid)update(o1,l,mid,x,val); else update(o1|1,mid1,r,x,val); pushup(o); } void pushup(int o){ maxv[o]max(maxv[o1],maxv[o1|1]); } int query(int o,int l,int r,int q1,int q2){ if(q1lrq2){ return maxv[o]; } int ans0; int mid(lr)1; if(q1mid)ansmax(ans,query(o1,l,mid,q1,q2)); if(q2mid)ansmax(ans,query(o1|1,mid1,r,q1,q2)); return ans; } }tree; void dfs(int u,int depth){ dep[u]depth; num[u]1; dfn[u]dfs_clock; int lenG[u].size(); for(int i0;ilen;i){ int vG[u][i]; dfs(v,depth1); num[u]num[v]; } } bool cmp(node A,node B){ return A.hB.h; } bool cmp1(node A,node B){ return A.dB.d; } int ans[maxn]; int main(){freopen(in.txt,r,stdin); int T; scanf(%d,T); while(T--){ scanf(%d,N); for(int i0;iN;i){ G[i].clear(); } for(int i0;iN;i){ scanf(%d%d%d,a[i].p,a[i].h,a[i].d); a[i].idb[i].idi; b[i].pa[i].p; b[i].ha[i].h; b[i].da[i].d; if(a[i].p!-1)G[a[i].p].push_back(i); } dfs_clock0; dfs(0,0); sort(a,aN,cmp); sort(b,bN,cmp1); tree.build(1,1,N); int j0; for(int i0;iN;i){ while(jNa[j].hb[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 i0;iN;i){ printf(%d,ans[i]); if(iN-1)printf(\n); else printf( ); } } return 0; }转载于:https://www.cnblogs.com/13224ACMer/p/4744350.html
