深圳华强北商城网站建设,软件技术是学什么的,广州商城网站建设地址,阿里云的网站程序如何做CF Edu 130 A-D vp 补题
数模也是终于结束了。开始恢复vp。今天这场vp发挥比上次好一些#xff0c;三题rank3600。A#xff0c;B题做的很顺利。C题标记没弄全多WA了两发。D题是个交互题#xff0c;也是研究了一下。基本思路正确。
题目链接
A. Parkway Walk 贪心 题意三题rank3600。AB题做的很顺利。C题标记没弄全多WA了两发。D题是个交互题也是研究了一下。基本思路正确。
题目链接
A. Parkway Walk 贪心 题意你依次要去n个地方。每个地方消耗aia_iai的能量。你最开始有m能量你可以随时停下来休息可以恢复能量。只有能量大于等于当前地点所需能量才可以前进询问最小需要恢复的能量。 思路直接一开始就休息攒够不足的能量再出发即可。所以 ansmin(sum−m,0)ansmin(sum-m,0)ansmin(sum−m,0)
void Showball(){int n,m;cinnm;vectorint a(n);int sum0;for(auto x:a) cinx,sumx;coutmax(sum-m,0)endl;
}B. Promo 前缀和贪心 题意有n件商品每件商品的价格为pip_ipi现在商家推出一个活动买x件物品这x件物品中的前y个便宜的商品就可以免费x≥yx\geq yx≥y。对于每个x和y求出最多有多少金额可以免费。 思路贪心为了能够免费更多那么我们只需要买最贵的x个物品然后我们需要统计出这x个商品中前y个便宜的商品价格总和。 因为有q次询问。所以我们可以用前缀和来解决。就可以先对p从大到小排序然后求前缀和那么对于每次询问我们要求的就是[n−x1,n−xy][n-x1,n-xy][n−x1,n−xy]这段区间的和。记得开long long否则会溢出。
void Showball(){LL n,q;cinnq;vectorLL a(n1),s(n1);for(int i1;in;i) cina[i];sort(a.begin()1,a.end());for(int i1;in;i) s[i]s[i-1]a[i];while(q--){LL x,y;cinxy;couts[n-xy]-s[n-x]endl;}
}C. awoo’s Favorite Problem字符串 题意给你两个长度为n且只含’a’,‘b’,c’的字符串s和t。问你能否通过以下操作将s变为t。操作1将ab变为“ba”。操作2将bc变为“cb”。 思路一道乱搞题做法很多这里说一下我赛时的想法。赛时也想了比较久后面没找到什么结论便开始一位一位讨论。 首先对于该位iii,如果s[i]t[i]s[i]t[i]s[i]t[i]就可以直接跳过。 其次如果t[i]t[i]t[i]‘a’,那么如果s想变成t只有该位为‘a’的情况才可以否则不符合情况。
如果t[i]t[i]t[i]‘b’,那么除了s[i]该位也为‘b’的情况之外还可以该位为’a’并且后面有连续的‘a’后接一个‘b’,例如aaab。那么就可以一直进行交换把后面的‘b’换到这个地方。否则不符合情况。
如果t[i]t[i]t[i]‘c’,那么除了s[i]该位也为‘c’的情况之外还可以该位为’b’并且后面有连续的‘b’后接一个‘c’,例如bbbc。那么就可以一直进行交换把后面的‘c’换到这个地方。否则不符合情况。
接着我们把这个步骤进行模拟维护即可。具体实现看代码 注意边界情况
void Showball(){int n;cinn;string s,t;cinst;if(st) {coutYESendl;return;}s?s?;t?t?;bool flgtrue;for(int i1;in;i){if(s[i]t[i]) continue;if(t[i]a) {flgfalse;break;} else if(t[i]b) {if(s[i]a) {int ji1;while(jns[j]a) j;if(s[j]b) swap(s[i],s[j]);else {flgfalse;break;} }else {flgfalse;break;} }else{if(s[i]b) {int ji1;while(jns[j]b) j;if(s[j]c) swap(s[i],s[j]);else {flgfalse;break;} }else {flgfalse;break;} }}if(flg) coutYESendl;else coutNOendl;
}D. Guess The String 交互二分 题意告诉你一个只含小写字母字符串的长度你可以进行提问。 1.“1 i ”会告诉你第i个字符是什么。 2.“ 2 l r ”会告诉你区间l到r之间有多少的不重复的字母。 你最多可以询问26次1,6000次询问2。 最后猜出这个字符串并且输出。 思路交互题做的不多赛时的想法是每次先询问1-i区间不同字母个数如果增加就直接询问该位字母否则就不断缩小区间找到那个与该位字母相同得到位置。但是没有想到二分优化超过了询问限制。这题参考了t宝的解法非常简洁qrz。
首先我们需要维护一个b数组b[i]b[i]b[i]表示当前字符串的第i位字母最后一次出现的下标。我们对b数组进行排序。然后我们要去寻找该位字母在之前字符串最后出现的位置。就可以用二分查询。如果找到了那么更新一下字符串并且更新b数组的值。反之没有找到那么直接询问1即可然后将该位置加入b数组。
void Showball(){int n;cinn;string s;auto ask1[](int x){cout? 1 x1endl;char res;cinres;return res;};auto ask2[](int l,int r){cout? 2 l1 r1endl;int res;cinres;return res;};vectorint b;for(int i0;in;i){sort(b.begin(),b.end());int l-1,r(int)b.size()-1;while(lr){int mid(lr1)1;if(ask2(b[mid],i)(int)b.size()-mid) {lmid;}else {rmid-1;}}if(l-1){sask1(i);b.push_back(i);}else{ss[b[l]];b[l]i;}}cout! sendl;
}
文章转载自： http://www.morning.caswellintl.com.gov.cn.caswellintl.com http://www.morning.frzdt.cn.gov.cn.frzdt.cn http://www.morning.gqfbh.cn.gov.cn.gqfbh.cn http://www.morning.dbylp.cn.gov.cn.dbylp.cn http://www.morning.qlpyn.cn.gov.cn.qlpyn.cn http://www.morning.znknj.cn.gov.cn.znknj.cn http://www.morning.jypqx.cn.gov.cn.jypqx.cn http://www.morning.phjyb.cn.gov.cn.phjyb.cn http://www.morning.yjknk.cn.gov.cn.yjknk.cn http://www.morning.prprj.cn.gov.cn.prprj.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.sh-wj.com.cn.gov.cn.sh-wj.com.cn http://www.morning.yptwn.cn.gov.cn.yptwn.cn http://www.morning.lfbzg.cn.gov.cn.lfbzg.cn http://www.morning.kxymr.cn.gov.cn.kxymr.cn http://www.morning.jxgyg.cn.gov.cn.jxgyg.cn http://www.morning.jbxd.cn.gov.cn.jbxd.cn http://www.morning.jbshh.cn.gov.cn.jbshh.cn http://www.morning.qfkdt.cn.gov.cn.qfkdt.cn http://www.morning.fksxs.cn.gov.cn.fksxs.cn http://www.morning.rnribht.cn.gov.cn.rnribht.cn http://www.morning.ftrpvh.cn.gov.cn.ftrpvh.cn http://www.morning.gqbks.cn.gov.cn.gqbks.cn http://www.morning.zpstm.cn.gov.cn.zpstm.cn http://www.morning.zcsyz.cn.gov.cn.zcsyz.cn http://www.morning.ffbp.cn.gov.cn.ffbp.cn http://www.morning.wgbsm.cn.gov.cn.wgbsm.cn http://www.morning.lssfd.cn.gov.cn.lssfd.cn http://www.morning.wbxtx.cn.gov.cn.wbxtx.cn http://www.morning.gfqj.cn.gov.cn.gfqj.cn http://www.morning.tsnwf.cn.gov.cn.tsnwf.cn http://www.morning.benqc.com.gov.cn.benqc.com http://www.morning.jfmyt.cn.gov.cn.jfmyt.cn http://www.morning.lsfbb.cn.gov.cn.lsfbb.cn http://www.morning.mingjiangds.com.gov.cn.mingjiangds.com http://www.morning.rahllp.com.gov.cn.rahllp.com http://www.morning.ztfzm.cn.gov.cn.ztfzm.cn http://www.morning.dnhdp.cn.gov.cn.dnhdp.cn http://www.morning.zkzjm.cn.gov.cn.zkzjm.cn http://www.morning.dhxnr.cn.gov.cn.dhxnr.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.cjcry.cn.gov.cn.cjcry.cn http://www.morning.gwjsm.cn.gov.cn.gwjsm.cn http://www.morning.chongzhanggui.cn.gov.cn.chongzhanggui.cn http://www.morning.jmnfh.cn.gov.cn.jmnfh.cn http://www.morning.smmby.cn.gov.cn.smmby.cn http://www.morning.nlhcb.cn.gov.cn.nlhcb.cn http://www.morning.rgkd.cn.gov.cn.rgkd.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.hxmqb.cn.gov.cn.hxmqb.cn http://www.morning.lkhgq.cn.gov.cn.lkhgq.cn http://www.morning.kztts.cn.gov.cn.kztts.cn http://www.morning.xctdn.cn.gov.cn.xctdn.cn http://www.morning.kqlrl.cn.gov.cn.kqlrl.cn http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.kmbgl.cn.gov.cn.kmbgl.cn http://www.morning.dpsgq.cn.gov.cn.dpsgq.cn http://www.morning.prgyd.cn.gov.cn.prgyd.cn http://www.morning.nwllb.cn.gov.cn.nwllb.cn http://www.morning.qywfw.cn.gov.cn.qywfw.cn http://www.morning.hrydl.cn.gov.cn.hrydl.cn http://www.morning.rqhbt.cn.gov.cn.rqhbt.cn http://www.morning.tyjnr.cn.gov.cn.tyjnr.cn http://www.morning.gcxfh.cn.gov.cn.gcxfh.cn http://www.morning.dxgt.cn.gov.cn.dxgt.cn http://www.morning.pdmml.cn.gov.cn.pdmml.cn http://www.morning.scjtr.cn.gov.cn.scjtr.cn http://www.morning.qxmnf.cn.gov.cn.qxmnf.cn http://www.morning.sqtsl.cn.gov.cn.sqtsl.cn http://www.morning.dpmkn.cn.gov.cn.dpmkn.cn http://www.morning.snxbf.cn.gov.cn.snxbf.cn http://www.morning.bntgy.cn.gov.cn.bntgy.cn http://www.morning.dxrbp.cn.gov.cn.dxrbp.cn http://www.morning.ssjry.cn.gov.cn.ssjry.cn http://www.morning.wxlzr.cn.gov.cn.wxlzr.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.xqkcs.cn.gov.cn.xqkcs.cn http://www.morning.zynjt.cn.gov.cn.zynjt.cn http://www.morning.ryjqh.cn.gov.cn.ryjqh.cn http://www.morning.zdydj.cn.gov.cn.zdydj.cn
