USACO Dec 月赛 青铜组 解题报告

Start


哇!第一回参加usaco月赛,AK2333,让我们来看看这些坑爹的题目,是怎么让我做出来的

T1 Blocked Billboard


题目大意: 有辆车挡住了两个广告牌子(两个牌子不相交),问你还能看到多少个单位的牌子 输入规范: 第一行有四个数分别是 x1,y1,x2,y2 x1,y1表示第一个广告牌的左上角 x2,y2表示第一个广告牌的右下角 第二行也有四个数,表示的二个广告牌的坐标 第三行还是有四个数,表示卡车的坐标 输出规范: 输出一个数,表示你能看到多少 数据范围: 每个坐标>=-1000,<=1000
样例输入:
1 2 3 5
6 0 10 4
2 1 8 3
样例输出:
17
这道题有两种做法,博主选的是比较简单的一种,我们直接用数组模拟,因为有负数,我们需要往每个数上1100就行,剩下的模拟 代码:
/*
 * ID:woshiluo
 * LANG:C++
 * TASK:billboard
 * */
#include <cstdio>
#include <algorithm>
using namespace std;
int x[7],y[7],cnt;//x[] x坐标 y[] y坐标 cnt 可以看见的数目
int a[2100][2100];
int main(){
    freopen("billboard.in","r",stdin);
    freopen("billboard.out","w",stdout);
//读入
    scanf("%d%d%d%d",&x[1],&y[1],&x[2],&y[2]);
    scanf("%d%d%d%d",&x[3],&y[3],&x[4],&y[4]);
    scanf("%d%d%d%d",&x[5],&y[5],&x[6],&y[6]);
    for(int i=1;i<=6;i++){x[i]+=1100;y[i]+=1100;}//将负数变为正数
//填入广告牌子1
    for(int i=x[1];i<x[2];i++){
        for(int j=y[1];j<y[2];j++){
            a[i][j]=1;
        }
    }
//填入广告牌子2
    for(int i=x[3];i<x[4];i++){
        for(int j=y[3];j<y[4];j++){
            a[i][j]=1;
        }
    }
//填入卡车
    for(int i=x[5];i<x[6];i++){
        for(int j=y[5];j<y[6];j++){
            a[i][j]=2;
        }
    }
// 排序100找到最大的左上短点与右下端点
    sort(x+1,x+7);
    sort(y+1,y+7);
// 查找可以看到的
    for(int i=x[1];i<x[6];i++){
        for(int j=y[1];j<y[6];j++){
            if(a[i][j]==1) cnt++;
        }
    }
// 输出
    printf("%d",cnt);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2 The Bovine Shuffle


题目大意: 告诉你一些七位数字的“洗牌”方案以及洗过三次牌之后的的顺序,求排序前的顺序 输入标准: 第一行,一个数 n ,表示共有多少个牌 第二行,n个数,表示第i个数会被放到Xi上,也就是洗牌方案 第三行,n个数,表示洗过三次牌之后的顺序 输出标准: 5行,一行一个号码,表示排序前的顺序 数据范围: 1<=n<=100
样例输入:
5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555
样例输出:
1234567
5555555
2222222
3333333
4444444
这道题也就是反着求,也就是说,我们需要找到它反着时的替换方法
for(int i=1;i<=n;i++){
    b[xp[i]]=i;
}
代码:
/*
 * ID:woshiluo
 * LANG:C++
 * TASK:shuffle
 * */
#include <cstdio>
using namespace std;
int n;
int xp[110],a[110],b[110],c[110];
// xp洗牌方案 a 号码顺序 b 逆序方案 c 临时顺序
int main(){
    freopen("shuffle.in","r",stdin);
    freopen("shuffle.out","w",stdout);
// 读入
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&xp[i]);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
// 求逆序方案
    for(int i=1;i<=n;i++){
        b[xp[i]]=i;
    }
// 开始洗牌
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n;j++){
            c[b[j]]=a[j];// 将号码安逆序顺序放入c数组
        }
        for(int j=1;j<=n;j++){
            a[j]=c[j];c[j]=0;// 转移至a数组,c数组清0
        }
    }
//输出
    for(int j=1;j<=n;j++){
        printf("%d\n",a[j]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T3 Milk Measurement


题目大意: 我们知道奶牛产量每年的变化,求产量第一名变多少次,开始时每头产奶7单位 输入规范: 第一行,一个数,n 第二行到第n+1行,三个部分,第一个部分一个数,表示第几天,第二部分表示奶牛的名字,第三个部分表示产量的增加或减少 输出规范: 一个数,表示变了几次 数据范围: n<=100
样例输入:
4
7 Mildred +3
4 Elsie -1
9 Mildred -1
1 Bessie +2
样例输出:
3
这道题是模拟,需要注意一下日期的问题,具体,看代码 代码:
/*
 * ID:woshiluo
 * LANG:C++
 * TASK:measurement
 * */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,temp,cnt,day,joj,dcnt;
// cnt 变化总次数 day,joj,temp 读入用 dcnt 当前读入的是第多少个(多余的变量,在程序中可以用n替换)
int d[110][4],c[110];
// d[i][j] 模拟专用数组,表示奶牛j在i天生产多少 c[]临时排序用
char name[110];
// 读入用 名字
bool x[110],y;
// x[i] 表示第i天是否有变化 y 模拟用
int top[4];
// top[i] 模拟用,表示第i头奶牛当前最高
struct fu{
    int day,name,joj;
// day 第几天 name 名字 joj 加或减少的产量
}a[110];
//在程序中
//1=M
//2=E
//3=B
// MEB分别是三个奶牛名字的首字母
// 两个cmp,sort用
bool cmp(int x,int y){
    return x>y;
}
bool cmp2(fu x,fu y){
    return x.day<y.day;
}
int main(){
    freopen("measurement.in","r",stdin);
    freopen("measurement.out","w",stdout);
// 预处理,将d[]数组内所有设为7
    for(int i=0;i<110;i++){
        for(int j=0;j<4;j++){
            d[i][j]=7;
        }
    }
// 读入
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&day);
        scanf("%s",name);
// 判断名字
        if(name[0]=='M') temp=1;
        if(name[0]=='E') temp=2;
        if(name[0]=='B') temp=3;
        if(!x[day]){
            x[day]=true;// 如果这天没有出现过,就改为出现过
        }
        scanf("%d",&joj);
        dcnt++;
// 存入结构体
        a[dcnt].day=day;
        a[dcnt].joj=joj;
        a[dcnt].name=temp;
    }
// 根据输入,找出每天的状况
    for(int i=1;i<=dcnt;i++){
        for(int j=a[i].day;j<=109;j++){
            d[j][a[i].name]+=a[i].joj;
        }
    }
// 模拟
    for(int i=1;i<=109;i++){
        if(!x[i]) continue;// 如果没有出现过,那么肯定没有变化
        y=false;// 假设没有变化
// 找出最优
        c[1]=d[i][1];
        c[2]=d[i][2];
        c[3]=d[i][3];
        sort(c+1,c+4,cmp);
// 判断最优是谁
        for(int j=1;j<=3;j++){
            if(c[1]==d[i][j]){
                if(top[j]==0){
                    top[j]=1;// 如果是最优,但是上次不是,top[j]变成1,
                    y=true;// 确定有变化
                }
            }
            else {
                if(top[j]==1){// 如果上次是最优,这次不是,top[j]变为0,
                    top[j]=0;
                    y=true;//确定变化
                }
                else {top[j]=0;}
            }
        }
        if(y) cnt++;
    }
// 输出
    printf("%d",cnt);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

End


解题报告完毕,部分题目可能会有点复杂或者不必要的变量,欢迎支出, 哇AK的感觉真好,还有披萨吃2333 ]]>

《USACO Dec 月赛 青铜组 解题报告》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注