首页 > 其他分享 >USACO 测试赛2

USACO 测试赛2

时间:2023-01-15 17:33:19浏览次数:51  
标签:cnt John int 样例 USACO 测试 Farmer 奶牛

USACO测试赛2

D2ege. 奶牛唱歌

问题描述

一个鲜为人知的事实是,奶牛拥有自己的文字:「牛文」。牛文由 26 个字母 'a' 到 'z' 组成,但是当奶牛说牛文时,可能与我们所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同,她会按某种特定的顺序排列字母。

为了打发时间,奶牛 Bessie 在反复哼唱牛文字母歌,而 Farmer John 好奇她唱了多少遍。

给定一个小写字母组成的字符串,为 Farmer John 听到 Bessie 唱的字母,计算 Bessie 至少唱了几遍完整的牛文字母歌,使得 Farmer John 能够听到给定的字符串。Farmer John 并不始终注意 Bessie 所唱的内容,所以他可能会漏听 Bessie 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。

输入格式

输入的第一行包含 26 个小写字母 'a' 到 'z' 的牛文字母表顺序。下一行包含一个小写字母组成的字符串,为 Farmer John 听到 Bessie 唱的字母。字符串的长度不小于 1 且不大于 1000。

输出格式

输出 Bessie 所唱的完整的牛文字母歌的最小次数。

输入样例

abcdefghijklmnopqrstuvwxyz
mood

输出样例

3

样例说明

在这个样例中,牛文字母表与日常的字母表的排列一致。

Bessie 至少唱了三遍牛文字母歌。有可能 Bessie 只唱了三遍牛文字母歌,而 Farmer John 听到了以下被标记为大写的字母。
abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz

测试点性质

测试点 2-5 中,牛文字母表与日常的字母表相同。
测试点 6-10 没有额外限制。

题解

判断字母顺序即可。

#include <bits/stdc++.h>
using namespace std;

int vhash[200];

int main()
{
    freopen("herd.in" , "r" , stdin);
    freopen("herd.out" , "w" , stdout);

    string dct;
    string res;
    cin >> dct >> res;

    for(int i = 0 ; i < dct.length() ; i ++)
        vhash[dct[i]] = i + 1;
    
    int cnt = 1 , pre = -1;

    for(int i = 0 ; i < res.length() ; i ++)
    {
        if(vhash[res[i]] > pre)
            pre = vhash[res[i]]; 
        else
            cnt ++ , pre = vhash[res[i]];
    }

    cout << cnt << endl;
    return 0;
}

D5b69. 照片分组

问题描述

Farmer John 正再一次尝试给他的 N 头奶牛拍照(2≤N≤1000)。

每头奶牛有一个范围在 1…100 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思:他希望将所有的奶牛分为不相交的若干组(换句话说,将每头奶牛分到恰好一组中)并将这些组排成一行,使得第一组的奶牛的品种编号之和为偶数,第二组的编号之和为奇数,以此类推,奇偶交替。

Farmer John 可以分成的最大组数是多少?

输入格式

输入的第一行包含 N。下一行包含 N 个空格分隔的整数,为 N 头奶牛的品种编号。

输出格式

输出 Farmer John 的照片中的最大组数。可以证明,至少存在一种符合要求的分组方案。

输入样例

7
1 3 5 7 9 11 13

输出样例

3

样例说明

在这个样例中,以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组,5、7 和 9 分在第二组,11 和 13 分在第三组。

输入样例

7
11 2 17 13 1 15 3

输出样例

5

样例说明

在这个样例中,以下是一种分成最大组数五组的方案。将 2 分在第一组,11 分在第二组,13 和 1 分在第三组,15 分在第四组,17 和 3 分在第五组。

题解

奇数 + 奇数 = 偶数
偶数 + 偶数 = 偶数

所以只要使得奇数偶数的数量相近,然后再构成奇数和偶数即可。


#include <bits/stdc++.h>
using namespace std;

int cnt_a , cnt_b;

int main()
{
    // freopen("group.in" , "r" , stdin);
    // freopen("group.out" , "w" , stdout);

    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i ++)   
    {
        int tmp;
        cin >> tmp;
        if(tmp % 2 == 0)
            cnt_a ++;
        else 
            cnt_b ++;
    }

    while(cnt_b > cnt_a)
    {
        cnt_b -= 2;
        cnt_a ++;
    }

    if(cnt_a == cnt_b)
        cout << cnt_a + cnt_b;
    else
        cout << cnt_b * 2 + 1;

    return 0;
}

Dg9s3. 牛舍安排

问题描述

Farmer John 有 N 头奶牛(1≤N≤20),高度为 a1…aN。他的牛栏有 N 个牛棚,高度限制分别为 b1…bN(例如,如果 b5=17,那么一头高度不超过 17 的奶牛可以住在牛棚 5 里)。Farmer John 有多少种不同的方式安排他的奶牛,使得每头奶牛均住在不同的牛棚里,并且使得每个牛棚的高度限制均得到满足?

输入格式

输入的第一行包含 N。

第二行包含 N 个空格分隔的整数 a1,a2,…,aN。

第三行包含 N 个空格分隔的整数 b1,b2,…,bN。所有的高度和高度限制均在范围
内。

输出格式

输出 Farmer John 可以将每头奶牛安排到不同的牛棚里,使得每个牛棚的高度限制均得到满足的方法数。注意输出的数量可能需要使用 64 位整数型,例如 C++ 中的 long long。

输入样例

4
1 2 3 4
2 4 3 4

输出样例

8

样例说明

在这个例子中,我们不能将第三头奶牛安排到第一个牛棚里,因为 3=a3>b1=2。类似地,我们不能将第四头奶牛安排到第一或第三个牛棚里。一种符合高度限制的安排方式为将奶牛 1 安排到牛棚 1,奶牛 2 安排到牛棚 2,奶牛 3 安排到牛棚 3,奶牛 4 安排到牛棚 4。

测试点性质

测试点 1-5 满足 N≤8。
测试点 6-12 没有额外限制。

题解

排列组合。
记录合法的数量,再排除不合法的数量(用排序可以降低复杂度)。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 30;

int a[MAXN];
int b[MAXN];

int n , ans = 1;

signed main()
{
    freopen("stalling.in" , "r" , stdin);
    freopen("stalling.out" , "w" , stdout);

    cin >> n;
    for(int i = 1 ; i <= n ; i ++)  
        cin >> a[i];
    for(int i = 1 ; i <= n ; i ++)
        cin >> b[i];

    sort(a + 1 , a + 1 + n);

    for(int i = n ; i >= 1 ; i --)
    {
        int cnt = 0;

        for(int j = 1 ; j <= n ; j ++)
            if(b[j] >= a[i])
                cnt ++;
        
        cnt -= (n - i); //不合法排列数
        ans *= cnt;
    }

    cout << ans << endl;

    return 0;
}

标签:cnt,John,int,样例,USACO,测试,Farmer,奶牛
From: https://www.cnblogs.com/liziyu0714/p/17053803.html

相关文章

  • Spring Boot---(11)SpringBoot使用Junit单元测试
    摘要:本文详细的记录了SpringBoot如何结合Junit写测试用例,如何执行,打包执行,忽略执行等操作,SpringBoot内置了Junit测试组件,使用很方便,不用再单独引入其他测试组件。 演示环境......
  • python:一文带你搞懂AB测试
    学习目标目标知道什么是AB测试知道AB测试的步骤知道AB测试原理  让我们想象一下,在公司的某产品研发讨论会上……“这个功能要不要上?”“我觉得没问题,XX指标肯定能涨一大截......
  • 黑盒测试策略及测试范围和构架
     2.黑盒测试策略及测试范围和构架B/S架构的定义及原理80%的系统基本都是基于B/SB/S架构一种是C/S架构MVCmodelVview视图层C控制层前端主要是......
  • Postman实现UI自动化测试
    转载请注明出处❤️作者:测试蔡坨坨原文链接:caituotuo.top/1db4fa44.html你好,我是测试蔡坨坨。看到这篇文章的标题,是不是有小伙伴会感到惊讶呢?Postman不是做接口测试的......
  • Vulnhub之Driftingblues 1靶机测试过程
    Driftingblues1识别目标主机IP地址─(kali㉿kali)-[~/Vulnhub/Driftingblues1]└─$sudonetdiscover-ieth1-r192.168.56.0/24Currentlyscanning:Finished!......
  • DTOJ-2023-01-02-测试-题解
    (2023省选模拟Round#4)之前感冒了一阵子,错过了两场省选模拟,不过我不打算补(乐成绩:0+42+0(就是说T1写挂了)A题目链接题目大意小\(\omega\)最近学习了分治\(\text{......
  • 测试
    SpringBoot核心原理:自动配置2018-02-25 java4all ​​java4all​​摘要:本文通过断点追溯源码的方式,来逐步展示SpringBoot的核心功能实现原理:自动化配置;由于是分析源......
  • Gradle配置对数据库集成测试的方法
    Gradle管理Java项目,标准项目布局仅定义了一个测试目录( src/test ),如果将集成测试添加到与单元测试相同的目录中。这是一个糟糕的主意,因为集成测试通常比单元测试慢很......
  • NIST随机性测试套件下载,安装,实验
    参考博客NIST随机性测试美国国家标准与技术研究所提供的测试,一共包括16种测试手段,具体内容可参考此博客NIST下载与安装环境:Windows11下载:NIST官网链接点击downlo......
  • API接口自动化测试框架搭建之需求整理、详细设计和框架设计
    (API接口自动化测试框架搭建之需求整理、详细设计和框架设计)1需求整理1.1实现目的API接口自动化测试,主要针对http接口协议;便于回归测试;线上或线下巡检测试,结合持续......