LGP1080 [NOIP 2012 提高组] 国王游戏原题链接[NOIP 2012 提高组] 国王游戏分析真的是只按照左手进行排序吗我觉得不完全对……因为右手没有什么影响所以理论上是对的乘一下就行了。正解#includebits/stdc.h#defineintlonglongusingnamespacestd;structBigInt{vectorintd;BigInt(longlongx0){if(x0)d.push_back(0);else{while(x0){d.push_back(x%10);x/10;}}}voidtrim(){while(d.size()1d.back()0)d.pop_back();}BigIntoperator*(intx){longlongcar0;for(inti0;i(int)d.size();i){longlongcurd[i]*xcar;d[i]cur%10;carcur/10;}while(car){d.push_back(car%10);car/10;}trim();return*this;}BigIntoperator/(intx)const{BigInt res;res.d.resize(d.size());longlongrem0;for(inti(int)d.size()-1;i0;i--){longlongcurrem*10d[i];res.d[i]cur/x;remcur%x;}res.trim();returnres;}booloperator(constBigInttmp)const{if(d.size()!tmp.d.size())returnd.size()tmp.d.size();for(inti(int)d.size()-1;i0;--i){if(d[i]!tmp.d[i])returnd[i]tmp.d[i];}returnfalse;}booloperator(constBigIntother)const{returnother*this;}voidprint()const{for(inti(int)d.size()-1;i0;--i)coutd[i];cout\n;}};constintN1005;intn;structnode{inta,b;}inp[N];boolcmp(constnodetmp1,constnodetmp2){returntmp1.a*tmp1.btmp2.a*tmp2.b;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;intA,B;cinAB;for(inti1;in;i){cininp[i].ainp[i].b;}sort(inp1,inpn1,cmp);BigIntans(0);BigIntres(A);for(inti1;in;i){BigInt tmpres/inp[i].b;if(tmpans)anstmp;res*inp[i].a;}ans.print();return0;}LGP3743 小鸟的设备原题链接小鸟的设备分析感觉拿时间除一下贪一下做完了……好好细想一下……那不就是和吗就是说你直接做就行吗随机贺一篇……正解#includebits/stdc.husingnamespacestd;constintN100005;constdoubleeps1e-6;intn;doublep,a[N],b[N];boolcheck(doublex){doubletmpp*x;doublesum0;for(inti1;in;i){if(a[i]*xb[i])continue;sum(a[i]*x-b[i]);}if(sumtmp)returntrue;returnfalse;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnp;doublesum0;for(inti1;in;i){cina[i]b[i];suma[i];}if(sump){cout-1;return0;}doublel0,r10000000000;while(r-leps){doublemid(rl)/2.0;if(check(mid))lmid;elsermid;}coutl;}LGP1970 [NOIP 2013 提高组] 花匠原题链接[NOIP 2013 提高组] 花匠分析刻画一下条件就是m 2 \frac{m}{2}2m​峰或m 2 \frac{m}{2}2m​谷。这是真的……那么就是设d p i , 0 / 1 dp_{i,0/1}dpi,0/1​表示以i ii结尾第i ii个位置是峰/谷的最长长度。那么转移是贪心的就是说……每次找比当前位置大的第一个是对的吗我不这么认为……我觉得应该是……这应该是对的吧……那么需要什么数据结构来维护呢单调栈是干这个的吗对的对的。那是不是做完了也不既然你会发现这个地方你需要顾全当前的高度和剩下的长度所以每次直接从后面一个转移就做完了。当然虽然我们已经做到了O ( n ) O(n)O(n)但是正解#includebits/stdc.husingnamespacestd;constintN100005;intn,h[N],dp[N][2];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cinh[i];dp[i][0]dp[i][1]1;}for(inti2;in;i){dp[i][0]dp[i-1][0];dp[i][1]dp[i-1][1];if(h[i]h[i-1]){dp[i][0]max(dp[i][0],dp[i-1][1]1);}if(h[i]h[i-1]){dp[i][1]max(dp[i][1],dp[i-1][0]1);}}coutmax(dp[n][0],dp[n][1]);return0;}