HNFMS一个初二蒟蒻OIerの实验室

2019年10月3日测试解题报告

T1 高中运动会(match)

[问题描述]

梦幻城市每年为全市高中生兴办一次运动大会。为促进各校同学之间的交流,采用特别
的分队方式: 每一个学校的同学, 必须被均匀分散到各队, 使得每一队中该校的人数皆相同。
为增加比赛的竞争性,希望分成越多队越好。你的任务是由各校的人数,决定最多可分成的
队数。

[输入格式]

输入第一行为一个正整数 N,代表学校的个数。接下来有 N 行,每行为一个正整数,分
别代表这 N 个学校的人数。

[输出格式]

输出仅一个数,即最多可分成的队数。

样例输入

3
12 16 20

[样例输出 1]

4

算法分析

每一个学校的同学, 必须被均匀分散到各队, 使得每一队中该校的人数皆相同。

由这句话就可以看出,不过是求一个gcd嘛!于是乎直接STL过!

代码

#include<bits/stdc++.h>
#define ini(...) scanf("%d",__VA_ARGS__)
#define oui(...) printf("%d",__VA_ARGS__)
#define in(...) scanf(__VA_ARGS__)
#define ou(...) printf(__VA_ARGS__)
#define F(i,a,b) for(int (i)=(a);(i)<=(b);(i)=-~(i))
#define DF(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fin(...) freopen(__VA_ARGS__,"r",stdin)
#define fout(...) freopen(__VA_ARGS__,"w",stdout)
int n,gcd,temp;

int main()
{
    fin("match.in");
    fout("match.out");
    ini(&n);
    F(i,1,n)
    {
        ini(&temp);
        gcd=(i==1?temp:std::__gcd(gcd,temp));
    }
    oui(gcd);ou("\n");
    return 0;
}

T2 订货( orders )

[问题描述]

某商店经理已将所有的货物按它们的标号的字母顺序进行了分类。所有的标号首字母相同的货物被存储在同一仓库中,该仓库也用该字母进行标记。在某天中,经理接到并登记了许多订货单,每张订货单仅需一种货物。经理按照登记的顺序处理了这些要求。
你已知道了该天经理所需处理的所有订货单,但你不知道它们的登记顺序。计算出所有可能的访问仓库的方法,来为经理解决该天所有的订货要求。

[输入格式]

输入仅有一行,包含所有所需货物的标号(一个随机的顺序)。每一种货物是用它标号的首字母来表示的,只使用英文小写字母。

[输出格式]

输出要包含经理访问仓库的所有可能顺序。每个仓库由一个英文小写字母来代表所存货物标号的首字母。每一种仓库访问顺序写在输出文件中单独的一行上,并且所有行上的这些访问顺序要按字母顺序先后列出。输出不会超过2MB。

[样例输入]

bbjd

[样例输出]

bbdj
bbjd
bdbj
bdjb
bjbd
bjdb
dbbj
dbjb
djbb
jbbd
jbdb
jdbb

算法分析

简化一下题目,随机给你一个200以内的字符串,让从“从小到大”开始,输出所有全排列,于是乎,首先sort大法,然后next_permutation,轻松搞定~

代码

#include<bits/stdc++.h>
#define ini(...) scanf("%d",__VA_ARGS__)
#define oui(...) printf("%d",__VA_ARGS__)
#define in(...) scanf(__VA_ARGS__)
#define ou(...) printf(__VA_ARGS__)
#define F(i,a,b) for(int (i)=(a);(i)<=(b);(i)=-~(i))
#define DF(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fin(...) freopen(__VA_ARGS__,"r",stdin)
#define fout(...) freopen(__VA_ARGS__,"w",stdout)
using namespace std;
char ch[201],bak1[201];
int flag=1;

int main()
{
    fin("orders.in");
    fout("orders.out");
    in("%s",&ch);
    int len=strlen(ch);
    sort(ch,ch+len);
    while(1)
    {
        if(flag!=1)
        {
            next_permutation(ch,ch+len);
            if(strcmp(ch,bak1)==0)break;
        }
        else
        {
            memcpy(bak1,ch,sizeof(ch));
        }
        ou("%s\n",ch);
        flag=0;
    }
    return 0;
}

T3 黑白影像 ( blackandwhite )

[问题描述]

一张黑白影像可以以一个二维阵列表示,将阵列的每个元素以一个位元表示其颜色,1代表黑色,0代表白色。然而在大多数情况下,我们发现一张黑白影像中,相同的颜色通常会位在相邻的位置;因此我们可以利用四分树(quadtree)的表示法来记录一张黑白影像,以得到比二维阵列较节省记忆的表示法。
四分树的表示法就是将目前欲表示的黑白影像区域,以十字形方式分割为四份,分别为东北方、西北方、西南方及东南方四个子区域。以图一为例,当把整张大小为16×16的图分割为四份时,东北方的恰好为一整块的黑色,我们可以一个黑色的节点(图二中的1号节点)表示这整个4×4的黑色区域。而西北方的4×4区域并非由同一色所组成,因此必须再进行分割;当我们以相同的方式同样地分割西北方的4×4区域,可得到图二中第3、4、5号节点以及再下一层的9、10、11、12号节点。图二中,黑色的节点表示黑色的像素,白色的节点表示白色的像素,圆圈表示内部节点。

(左:图一 右:图二)

当我们得到图二的四分树表示法后,可使用b,w,g三个符号分别代表黑色节点,白色节点及内部节点,依照深先(depth-first)表示法将四分树符号输出(依pre-order顺序输出)。因此,图二的四分树可表示成

g b g w w w g w b b w w g w w g w w b b b

请写一个程序,将每张黑白影像的四分树表示法,利用b,w,g三个符号以深先表示法的结果列出。

[输入格式]

第一行为一个整数n,代表一张正方形黑白影像的宽度及高度。

接下来的n行代表影像中每一行的内容:0表示一个白色像素,1表示一个黑色像素。

[输出格式]

对每一个输入的黑白影像,将其四分树表示法以b,w,g三个符号,依深先表示法顺序列出(每个输出符号之间有一个空格隔开)。

[样例输入1]

4
0000
0100
0011
0011

[样例输出1]

g w g w w w b w b

算法分析

首先判断全图是b/w/g,若是b/w直接输出,若是g则划分四块,分块递归,递归后不断判断b/w/g,判断完输出,直到扫完为止。

解释下样例吧。

首先,全图应为g。然后扫东北,全白,得w西北方向为g,进入递归,西北块的东北西北西南均为白,得w w w东南为黑,得b,递归返回。又得全图西南全白,得w全图东南为全黑,得b,至此,整张图表示为g w g w w w b w b

代码

#include<bits/stdc++.h>
#define ini(...) scanf("%d",__VA_ARGS__)
#define oui(...) printf("%d",__VA_ARGS__)
#define in(...) scanf(__VA_ARGS__)
#define ou(...) printf(__VA_ARGS__)
#define F(i,a,b) for(int (i)=(a);(i)<=(b);(i)=-~(i))
#define DF(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fin(...) freopen(__VA_ARGS__,"r",stdin)
#define fout(...) freopen(__VA_ARGS__,"w",stdout)
using namespace std;
int __map[1025][1025];
int n;

char check(int x,int y,int l,int r)
{
    bool white=false,black=false;
    F(i,x,y)
    {
        F(j,l,r)
        {
            if(__map[i][j]==1)
                black=true;
            else white=true;
            if(black&&white)goto bk;
        }
    }
    bk:
        if(white&&black)return 'g';
        else if(white)return 'w';
        else return 'b';        
}

int dfs(int x,int y,int l,int r)
{
    //第一象限 
    char temp=check(x,(y+x)>>1,((l+r)>>1)+1,r);
    if(temp=='g')
    {
        ou("g ");
        dfs(x,(y+x)>>1,((l+r)>>1)+1,r);
    }
    else ou("%c ",temp);
    
    //第二象限 
    temp=check(x,(y+x)>>1,l,(r+l)>>1);
    if(temp=='g')
    {
        ou("g ");
        dfs(x,(y+x)>>1,l,(r+l)>>1);
    }
    else ou("%c ",temp);
    
    //第三象限
    temp=check(((y+x)>>1)+1,y,l,(r+l)>>1);
    if(temp=='g')
    {
        ou("g ");
        dfs(((y+x)>>1)+1,y,l,(r+l)>>1);
    }
    else ou("%c ",temp); 
    
    //第四象限
    temp=check(((y+x)>>1)+1,y,((r+l)>>1)+1,r);
    if(temp=='g')
    {
        ou("g ");
        dfs(((y+x)>>1)+1,y,((r+l)>>1)+1,r);
    }
    else ou("%c ",temp); 
}

int main()
{
    fin("blackandwhite.in");
    fout("blackandwhite.out");
    ini(&n);
    F(i,1,n)
    {
        F(j,1,n)
        {
            in("%1d",&__map[i][j]);
        }
    }
    char temp1=check(1,n,1,n);
    if(temp1=='g')
    {
        ou("g ");
        dfs(1,n,1,n);
    }
    else ou("%c ",temp1);
    ou("\n");
    return 0;
}

T4 银河帝国旅行社( galaxy )

[问题描述]

很久很久以前,银河系有一个科技极度发达的帝国存在,这个帝国有着许许多多的星球所组成,这些星球之间有主从关系,除了帝国首者之外,其他的星球均从属于自己专属的主星。

由于银河是相当的浩瀚,主要的旅行方式是空间跳跃,不管这两个星球有多远,只要花一小时就抵达目的地。为了维护帝国间的和平与安定,帝国当局是严格的管制空间跳跃的使用,只允许主星到从属星以及从属星到主星之间的空间跳跃。假定银河帝国中,只有一个帝国首都,首都本身也是一个星球,每个星球只有一个专属的主星,但一个星球可以有许多从属星。并且不会发生循环从属的关系,即不会发生如下情况:S1是S2的主星,S2是S3的主星,……,Sn-1是Sn的主星,Sn是S1的主星。

以图为例,1号星与2号星为0号星(也就是帝国首都)的从属星,3号星是1号星从属星,4号星是2号星的从属星。在这个例子中,从3号星到2号星作星际旅行需要3小时:3号星——1号星,1号星——0号星,0号星——2号星。而在这个星系中作星际旅行,最多需要花4小时,也就是从3号星旅行到4号星。
现在你的任务是估计银河帝国之中,任意选两个星球作为起点与终点进行空间跳跃旅行,最多需要花多少时间?(以图为例,答案是4个小时)

[输入格式]

第一行将有一个数字n,代表银河帝国中有n个星球。

紧接下来会有n行,接下来的每行依序都代表了一个星球的从属星名单。为了简化输入的复杂度,将由0到n-1的数字来替代星球名称,0就是帝国首都,而且只有数字小的才可以当数字大的主星。每行的格式:“从属星1 从属星2 … -1”,最后的-1代表从属星名单结束。如果是单一一行的-1,代表该星球没有从属星。

[输出格式]

输出一行,包含一个数字,即任选两星球,最多需花多少小时才能由藉由空间跳跃从起点抵达目的地。

[样例输入1]

5
1 2 -1        //首都(0号星)的从属星是1号星与2号星
3 -1            //1号星的从属星是3号星
4 -1            //2号星的从属星是4号星
-1              //3号星没有从属星
-1              //4号星没有从属星

[样例输出1]

4

算法分析

代码

#include<bits/stdc++.h>
#define ini(...) scanf("%d",__VA_ARGS__)
#define oui(...) printf("%d",__VA_ARGS__)
#define in(...) scanf(__VA_ARGS__)
#define ou(...) printf(__VA_ARGS__)
#define F(i,a,b) for(int (i)=(a);(i)<=(b);(i)=-~(i))
#define DF(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fin(...) freopen(__VA_ARGS__,"r",stdin)
#define fout(...) freopen(__VA_ARGS__,"w",stdout)
std::vector<int> a[50001];
int n,x,s[50001],mx,random,xlong;
bool lock[50001];

void dfs(int l){
    F(i,0,a[l].size()-1)
        if(!lock[a[l][i]]){
            lock[a[l][i]]=1;
            s[a[l][i]]=s[l]+1;
            dfs(a[l][i]);
        }
}

int calc(int v){
    memset(lock,0,sizeof(lock));
    s[v]=mx=0;
    dfs(v);
    F(i,0,n-1)
        mx=std::max(mx,s[i]);
    F(i,0,n-1)
        if(s[i]==mx)
            return i;
}

int main()
{
    fin("galaxy.in");
    fout("galaxy.out");
    ini(&n);
    F(i,0,n-1)
    {
        while(ini(&x)!=EOF){
            if(x<0) break;
            a[x].push_back(i);
            a[i].push_back(x);
        }
    }
    random=calc(0);
    xlong=calc(random);
    oui(mx);ou("\n");
    return 0;
}

标签: 解题报告

Title - Artist
0:00