【原创】USACO 2020-2021赛季试题解析系列(1月晋级赛)

点击领取>>>信息学奥赛 NOI、NOIP、各区CSP-J/S初赛复赛试题&蓝桥杯、信息杯、智慧杯编程试卷& 海淀区科普节、程序设计大赛



第1题



题目解析:

模拟题,把Farm John听到的字符串遍历一遍,相邻两个字符如果在cowphabet中为逆序,就把答案累加1。

string cowphabet, heard;cin >> cowphabet >> heard;for (int i = 0; i < 26; i++) {
   c[cowphabet[i] - 'a'] = i;  //记录字母表顺序}for (int i = 1; i < heard.size(); i++) {    int x = c[heard[i] - 'a'];    int y = c[heard[i - 1] - 'a'];    if (x <= y) {  //当前字母小于等于上一字母顺序
       ans++;
   }
}


第2题



题目解析:

题目要求把N个数划分为若干组,每组数之和要按照偶数与奇数交替的方式排列,问最多能得到多少组数。首先统计奇数和偶数的个数,一个偶数或者两个奇数可以划分为一组偶数和,一个奇数可以划分为一组奇数和。因此咱们按照一个偶数一个奇数的方式分组,如果没有偶数了,那就用两个奇数替代偶数,最后如果多一个奇数,那么需要把这个奇数和最后一组奇数合并为偶数,然后再和前一组偶数合并,会减少一组。如果多余若干个偶数,直接合并到最后一组偶数中即可,不影响结果。

while (odd > 0 || even > 0) {
    // 分出一组偶数
   if (even > 0) {
       even--, ans++;
   } else if (odd >= 2) {
       odd -= 2, ans++;
   } else {        break;
   }        
   //第一组奇数
   if (odd > 0) {
       odd--, ans++;
   } else {        break;
   }
}if (odd == 1) ans--;


第3题


题目解析:

本题如果用全排列枚举只能得5个cases分数,20!次显然会超时。比较适合铜级选手的解法是采用排列组合完成,当然会状压DP的选手也可以用状压DP做。下面讲解下排列组合方案的思想,首先把两个数组排序,然后对于每个stall, 求出该位置可以放几种数,然后把每个位置的种数全部相乘即可。

 sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; i++) {     ans *= 每个stall上的种数; }




第1题



题目解析




第2题



题目解析:


第3题




题目解析:




第1题



题目解析:


第2题



题目解析:



第3题




题目解析:







第1题


限于篇幅,Platinum题目就不贴了

需要者可以扫描文末二维码,添加老师微信获取

题目解析:


第2题


题目解析:


第3题


题目解析:

微信公众号搜索: 北京小学学习资料     家长升学指南  关注公众号,获取最新资讯!   

图片 扫码添加“家长论坛”微信好友(微信号 16619908263

获取信息学奥赛 NOI、NOIP、各区CSP-J/S试题&蓝桥杯、智慧杯、 海淀区科普节真题
咨询信息学奥赛 NOI、NOIP、各区CSP-J/S试题&蓝桥杯、智慧杯、 海淀区科普节政策请拨打电话 16619908263 (同微信号)

已邀请:

要回复问题请先登录注册