Winter Camp I (中）

G题：Red and Black 代码： #include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;int w,h,num;char a[30][30];int di

barry_cxg

185人浏览 · 2019-01-27 20:01:27

barry_cxg · 2019-01-27 20:01:27 发布

G题：Red and Black

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int w,h,num;
char a[30][30];
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,1,-1};//定义向右，向左，向上，向下的坐标
void DFS(int x,int y)
{
    a[x][y]='#';//因为把起点已经算进去了，所以为防止之后再多算起点，把起点变成#
    num++;
    int xx,yy;
    for(int k=0;k<4;k++)
    {
        xx=x+dirx[k];
        yy=y+diry[k];
        if(a[xx][yy]=='.'&&xx>=0&&xx<h&&yy>=0&&yy<w)
        {
            DFS(xx,yy);
        }
    }
}
int main()
{
    int i,j,di,dj;
    while(scanf("%d%d",&w,&h)!=EOF)
    {
        getchar();
        if(w==0&&h==0)
            break;
        for(i=0;i<h;i++)
        {
            for(j=0;j<w;j++)
            {
                scanf("%c",&a[i][j]);
                if(a[i][j]=='@')
                {
                    di=i;
                    dj=j;
                }
            }
            getchar();
        }
        num=0;
        DFS(di,dj);
        printf("%d\n",num);
    }
    return 0;
}

本题是常规的BFS和DFS问题，因为之前DFS用的比较熟悉了（I、H用的都是深度优DFS先算法），所以就DFS，有个博主写的这个题的多解之后可以下去学习参考。

https://blog.csdn.net/hurmishine/article/details/50927317

J 题：Nightmare

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
char mapp[16][16];
int vis[16][16];
int dirx[4]={-1,0,1,0};
int diry[4]={0,-1,0,1};
int n,m,f_x,f_y;//n行m列,f_x,f_y为出口的横纵坐标
struct maze//坐标结构体存储总时间和炸弹倒计时
{
    int x,y;
    int to_time,now_time;
};
bool judge(int x,int y)//判断越界
{
    if(x>=n||x<0||y>=m||y<0)
        return false;
    if(mapp[x][y]=='0')
        return false;
    return true;
}
int BFS(int x,int y)
{
    queue<maze> q;
    maze a,b;
    memset(vis,0,sizeof(vis));
    vis[x][y]=6;//记录之前到达某点的剩余时间
    a.x=x;
    a.y=y;
    a.to_time=0;
    a.now_time=6;
    q.push(a);
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        if(a.x==f_x&&a.y==f_y)
            return a.to_time;
        for(int i=0;i<4;i++)
        {
            b.x=a.x+dirx[i];
            b.y=a.y+diry[i];
            if(judge(b.x,b.y))
            {
                if(mapp[b.x][b.y]=='4')//如果到了重置时间
                {
                    if(a.now_time==1)
                        continue;
                    else
                    {
                        b.now_time=6;
                        b.to_time=a.to_time+1;
                    }
                    if(b.now_time==0||b.now_time<=vis[b.x][b.y])// 判断后到达的此点剩余时间是否 大于 之前到达这个点剩余时间
                        continue;
                    else//更新时间
                    {
                        vis[b.x][b.y]=b.now_time;
                        q.push(b);
                    }
                }
                else
                {
                    b.now_time=a.now_time-1;
                    b.to_time=a.to_time+1;
                    if(b.now_time==0||b.now_time<=vis[b.x][b.y])// 判断后到达的此点剩余时间是否 大于 之前到达这个点剩余时间
                        continue;
                    else//更新时间
                    {
                        vis[b.x][b.y]=b.now_time;
                        q.push(b);
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    int s_x,s_y;//入口横纵坐标
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        getchar();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%c",&mapp[i][j]);//输入坐标，但要注意要把空格和回车吞掉。
                getchar();
                if(mapp[i][j]=='2')//输入时记录起点坐标
                {
                    s_x=i;
                    s_y=j;
                }
                if(mapp[i][j]=='3')//输出时记录终点坐标
                {
                    f_x=i;
                    f_y=j;
                }
            }
        }
        cout<<BFS(s_x,s_y)<<endl;
    }
    return 0;
}

本题是一道运用BFS算法的题，与之前用的DFS算法不同，在写BFS的过程中，我们是用队列把每一次生成的新的步骤数组入队，然后再检测是否队空不空继续搜索，直到出现目标或者没有返回-1，和DFS通过递归进行搜索找到终点的方式不同。

简单翻译一下这个题意：

以下是一些规则:

1.我们可以假设迷宫是2个数组。

2. 伊格内修斯每分钟只能走到最近的一个地区，他不应该走出边境，当然他也不能在墙上走。

3.如果伊格内修斯在爆炸时间变为0时到达出口，他就无法走出迷宫。

4. 如果伊格内修斯在爆炸时间变为0时到达装有炸弹静止装置的区域，他就不能使用该装置复位炸弹。

5. 一个炸弹重置设备可以用多少次就用多少次，如果需要的话，伊格内修斯可以用多少次就能到达迷宫中的任何地方。

6. 爆炸时间复位时间可以忽略，也就是说，如果Ignatius到达一个含有炸弹静止装置的区域，且爆炸时间大于0，则爆炸时间复位为6。

输入包含几个测试用例。输入的第一行是单个整数T，它是测试用例的数量。接下来是T测试用例。

每个测试用例以两个整数N和M(1<=N,Mm=8)开始，这两个整数表示迷宫的大小。然后N行，每一行包含M个整数。该数组指示迷宫的布局。

迷宫中有5个整数表示不同类型的面积:

0:这是一堵墙，伊格那丢不应该在上面走。

1这个地方什么都没有，伊格那丢可以在上面走。

2:伊格那丢的起始位置，伊格那丢开始从这个位置逃跑。

3:迷宫的出口，伊格那丢的目标位置。

4:该区域有一个炸弹复位设备，Ignatius可以步行到这些区域来延迟爆炸时间。

分析：

NightMare 就是在一个地宫中从入口到出口，2为入口，3为出口，0为墙，1为路。

当从入口离开，地宫倒计时6秒坍塌，地图中有一些装置可以重置坍塌时间，（不是坍塌时间晚6秒，而是重新更新到6秒，继续倒计时）

最终输出到出口时，花费的总时间。

有几点：

①当你踏上出口时，倒计时刚好归0，则无法出去。同理，倒计时归0时，到达重置时间点也是不可以的。

②如果出不去输出-1.

③重置时间装置可以重复触发。

这道题目关键就在于它的VIS数组，因为里面的路可以多次访问，不能走一次都归0。

当碰到重置时间装置，使vis数组全为0，也是行不通的，因为队列里有一些其他的点的访问会影响到。

仔细，想想，什么时候不需要再次走这条路了呢？

当然是当你到达这个点时，和之前到达此点所剩余时间比较，

如果你后到达这个点剩余时间小于之前到达这个点剩余时间，那就不需要走这条路了。

剩余时间，当然是地宫坍塌的时间，如此设置vis数组，bfs就可以过了。

L 题：Sticks

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,maxx,sum,arr[85];
bool ipos,vis[85];
bool cmp(int a,int b)//由大到小排序
{
    return a>b;
}
void DFS(int res,int js)
{
    if(ipos==1)// 找到答案，返回
        return;
    if(js==n)//如果所有都被选择 ispos置1，表示找到
    {
        ipos=1;
        return;
    }
    if(res==0&&js<n)// 如果res=0 且并非所有都被选择，则继续广度搜索
        DFS(maxx,js);
    for(int i=0;i<n;i++)
    {
        if(!ipos&&!vis[i]&&arr[i]<=res)
        {
            vis[i]=1;
            DFS(res-arr[i],js+1);
            vis[i]=0;
            if(res==arr[i])// 第一种剪枝，这个去掉 +40MS
                return;
            if(res==maxx)//第二种剪枝，这个去掉，TLE。
                return;
            while(arr[i]==arr[i+1])// 第三种剪枝，这个剪枝去掉了，+100MS
                i++;
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
            sum+=arr[i];
        }
        sort(arr,arr+n,cmp);
        maxx=arr[0];
        if(maxx>sum-maxx)// 剪枝：如果最长的长度大于剩余所有长度和，则答案就是他们的和.
        {
            printf("%d\n",sum);
            continue;
        }
        ipos=0;
        while(!ipos)
        {
            while(sum%maxx!=0)// 剪枝:如果所有长度总和对目标长度取模不为0，则目标长度一定不是答案，
                maxx++;
            memset(vis,0,sizeof(vis));
            DFS(maxx,0);
            if(ipos)
                break;
            maxx++;
        }
        printf("%d\n",maxx);
    }
    return 0;
}

本题是深度搜索与剪枝结合的题，如果不做剪枝处理，则会出现超时问题，下面有几点说明

dfs函数中那三个if里的剪枝：

第一条剪枝：

如果你剩余的长度和当前长度相等，就没有必要搜索，也就是说当你剩余长度为3，接着搜索3，发现不符合，就不需要搜索剩下能构成3的（比如2+1,1+1+1等）

第二条剪枝：（重要的）

意思是如果剩余的长度等于绳子总长度，而当前不符合，就不需要接着搜索。

也就是说，接下来搜索的长度就是绳子目标长度，而你当前长度根本用不上，那就肯定不符合了。

例子：假设要搜索目标长度为 7 ：绳长有 7 6 3 2 2.

假设第一个7 搜索完，接下来搜索6 发现6没有1来配对，程序会接下来搜索 3 2 2，但很明显根本不需要搜索后面的，前面有一个用不上，后面就不需要再搜索了。

第三条剪枝：

如果当前长度的不满足，那么相同长度的就不需要再次去搜索

2.主函数中有sum%maxx!=0这个语句，理解为当我们所设定棍子折断前最小长度无论是多少，sum都是这些棍子折断前长度的倍数，所以取这些搜索。

3.深度搜索搜索到目标的判定条件：

if(!ipos&&!vis[i]&&arr[i]<=res)

{

vis[i]=1;

DFS(res-arr[i],js+1);

vis[i]=0;

正如代码写的，一个棒子无论被怎样折断，其假设的总长res(第一次是Maxx)-arr[i]肯定在其他小棒中能找到这样的长度，如果这样的小棒又被分成了几份，一定能找到它的子份再进行分解，直到res变为0，则表示这个分支搜索成功，则对下一个分支进行搜索,即DFS（maxx,js）。Vis[i]表示你再进去搜索前标记为1，如果成功找到，标记1则会让其他搜索避开，减少重复搜索，如果没有找到，则再变回0，让其他分支去搜索这个路径。

B题： Moving Tables

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,s,t,coun[500];
int main()
{
    int T,k;
    cin>>T;
    while(T--)
    {
        scanf("%d",&N);
        memset(coun,0,sizeof(coun));
        for(int i=0;i<N;i++)
        {
            scanf("%d%d",&s,&t);
            if(s>t)//为保证是从小房间号起，可以将大的起点和小点终点交换一下
            {
                k=s;
                s=t;
                t=k;
            }
            if(s%2==0)//对于终点和起点的要求为了保证在路途中把所有的房间号全部找全，所以要求起点为奇数
                s-=1;//不为奇数的要-1
            if(t%2==1)//要求终点为偶数，不为偶数的，终点要加1
                t+=1;
            for(int i=s;i<=t;i++)
               coun[i]+=10;
        }
        printf("%d\n",*max_element(coun,coun+500));
    }
    return 0;
}

本题是按照固定规则寻找最优路径的一道题，属于贪心算法的范畴

思路：若移动多个桌子时，所需要经过的走廊没有重合处，即可以同时移动。若有一段走廊有m个桌子都要经过，一次只能经过一个桌子，则需要m*10的时间移动桌子。设一个数组，下标值即为房间号。桌子经过房间时，该房间号为下标对应的数组值即加10。最后找到最大的数组值，即为移动完桌子需要的最短时间。

利用每次移动时，用数组下标代表房间号，每经过一个房间，对应数组加10，之后若遇到途径该房间或从该房间开始或结束，则会累加计时，达到模拟题中说的一个走廊每次过一个桌子的过程。如果没有重合，则每个数组内容只加10，最后找数组里最大的数，即为所花费的最小时间，模拟了不重合时同时搬桌子的过程

E题： Parencodings

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,s[100];
int countt;
bool flag;
int main()
{
    int t,p,num;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        memset(s,0,sizeof(s));//初始化，假设全部都是左括号,0表示
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p);
            s[p+i]=1;//右括号用1表示
        }
        for(int i=1;i<=2*n;i++)
        {
            if(s[i]==1)
            {
                if(s[i-1]==0)
                {
                    printf("1");
                    if(i!=2*n)
                        printf(" ");
                }
                else
                {
                    flag=1;
                    countt=1;
                    int j=i-1;
                    num=0;
                    while(flag)
                    {
                        if(s[j]==1)
                        {
                            countt++;
                            j--;
                        }
                        else
                        {
                            if(countt)
                            {
                                countt--;
                                j--;
                                num+=1;
                            }
                            if(countt==0)
                                flag=0;
                        }
                    }
                    printf("%d",num);
                    if(i!=2*n)
                        printf(" ");
                }
            }
        }
        printf("\n");
    }
    return 0;
}

这题是一道括号匹配题，难点在于入手的时候如何重新构建s字符串。我的思路是我们可以由P数组先求出S数组，再由S数组找出W数组会更容易些。至于怎么由P数组找出S呢，我们用0和1分别表示左括号和右括号，先把S数组初始化为0（即初始化为只包含左括号），那么对于每一个输入的Pi，由定义我们知道，这是第i个右括号，同时我们还知道，这个右括号前面有Pi个左括号，这时我们就可以对S[ Pi+i ]赋值为1，即该点为右括号。有了S数组，找W数组就是根据当前数组的数值和前一个数组的数值来判断括号个数，若前一个为左括号，则直接直接输出为1，否则先记录下右括号个数，再往前倒推找左括号，直到找到相应的左括号为止就行

K题： Defragment

代码：

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int N;
    int K;
    int move_cnt = 0;
    cin >> N >> K;

    int * clusters = new int[N + 1];
    for (int i = 0; i <= N; ++i) {
        clusters[i] = 0;
    }
    int sum = 0;
    for (int i = 0; i < K; ++i) {
        int n;
        cin >> n;
        for (int j = 1; j <= n; ++j) {
            int a;
            cin >> a;
            clusters[a] = ++sum;
        }
    }
    for (int i = 1; i <= N; ++i) {
        if (clusters[i] == 0 || clusters[i] == i) {
            continue;
        }
        stack<int> s;
        int next = clusters[i];
        s.push(i);
        bool isCircle = false;
        while (true) {
            if (clusters[next] == i) {
                isCircle = true;
                break;
            } else if (clusters[next] == 0) {
                break;
            }
            s.push(next);
            next = clusters[next];
        }
        if (isCircle == true) {
            int j = N;
            while (clusters[j] != 0) {
                --j;
                continue;
            }
            cout << next << " " << j << endl;
            clusters[j] = clusters[next];
            int t;
            while (!s.empty()) {
                t = s.top();
                cout << t << " " << next << endl;
                clusters[next] = clusters[t];
                next = t;
                s.pop();
                ++move_cnt;
            }
            clusters[next] = clusters[j];
            clusters[j] = 0;
            cout << j << " " << next << endl;
        } else {
            int t;
            while (!s.empty()) {
                t = s.top();
                cout << t << " " << next << endl;
                clusters[next] = clusters[t];
                next = t;
                s.pop();
                ++move_cnt;
            }
            clusters[next] = 0;
        }
    }
    if (move_cnt == 0) {
        cout << "No optimization needed" << endl;
    }
    return 0;
}

光是看题都让人看得绝望

附上博客网址，慢慢消化：

https://www.cnblogs.com/dengeven/p/3230223.html