算法笔记_第八章

2020-02-13

第八章上机训练

8(上机)

8.1

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1103
vector<int> K,ans,temp;
int n,k,p,maxsum=-1;

void DFS(int index,int nowk,int sum,int Ksum)
{
    if(sum==n&&nowk==k){
        if(Ksum>maxsum){
            ans=temp;
            maxsum=Ksum;
        }
        return;
    }
    if(sum>n||nowk>k) return;
    if(index-1>=0){
        temp.push_back(index);
        DFS(index,nowk+1,sum+K[index],Ksum+index);
        temp.pop_back();
        DFS(index-1,nowk,sum,Ksum);
    }
}

int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(int i=0;pow(1.0*i,p)<=n;i++){
        K.push_back(pow(1.0*i,p));
    }
    DFS(K.size()-1,0,0,0);
    if(maxsum==-1) printf("Impossible\n");
    else{
        printf("%d = %d^%d",n,ans[0],p);
        for(int i=1;i<ans.size();i++){
            printf(" + %d^%d",ans[i],p);
        }
    }
    return 0;
}

8.2

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1091
int m,n,L,t;
int X[6]={0,0,0,0,1,-1};
int Y[6]={0,0,1,-1,0,0};
int Z[6]={1,-1,0,0,0,0};
struct Node
{
    int x,y,z;
}node;
int pixel[1290][130][65];
bool inq[1290][130][65]={false};

bool judge(int x,int y,int z)
{
    if(x>=n||x<0||y>=m||y<0||z>=L||z<0) return false;
    if(pixel[x][y][z]==0||inq[x][y][z]==true) return false;
    return true;
}

int BFS(int x,int y,int z)
{
    int volume=0;
    queue<Node> Q;
    node.x=x,node.y=y,node.z=z;
    Q.push(node);
    inq[x][y][z]=true;
    while(!Q.empty()){
        Node top=Q.front();
        Q.pop();
        volume++;
        for(int i=0;i<6;i++){
            int newx=top.x+X[i];
            int newy=top.y+Y[i];
            int newz=top.z+Z[i];
            if(judge(newx,newy,newz)){
                node.x=newx,node.y=newy,node.z=newz;
                Q.push(node);
                inq[newx][newy][newz]=true;
            }
        }
    }
    if(volume>=t) return volume;
    else return 0;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&L,&t);
    for(int z=0;z<L;z++){
        for(int x=0;x<n;x++){
            for(int y=0;y<m;y++){
                scanf("%d",&pixel[x][y][z]);
            }
        }
    }
    int ans=0;
    for(int z=0;z<L;z++){
        for(int x=0;x<n;x++){
            for(int y=0;y<m;y++){
                if(pixel[x][y][z]==1&&inq[x][y][z]==false){
                    ans+=BFS(x,y,z);
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2020/02/13/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E7%AC%AC%E5%85%AB%E7%AB%A0/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！