0823模拟赛-白红宇

0823模拟赛

阅读量：7296 次

发布时间：2019-06-30

本文共 4751 字，大约阅读时间需要 15 分钟。

由于3道题都做对了，我就懒得写题解了。

一、搭桥

题目描述 Description

有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。

输入描述 Input Description

在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。

输出描述 Output Description

在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。

样例输入 Sample Input

样例1

3 5

#...#

..#..

#...#

样例2

3 5

##...

.....

....#

样例3

3 5

#.###

#.#.#

###.#

样例4:

3 5

#.#..

.....

....#

样例输出 Sample Output

样例1

4 4

样例2

0 0

样例3

0 0

样例4

1 1

AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                using namespace std;#define N 100010#define M 60#define ll long long#define xx first#define yy secondtypedef pair
                 
                   diy;inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline const bool in(){ for(register char ch=getchar();;ch=getchar()) if(ch=='#'||ch=='.') return ch=='#';}const int dx[]={ 0,0,1,1,-1,-1,1,-1};const int dy[]={ 1,-1,1,-1,1,-1,0,0};bool mp[M][M];int fa[N],mark[M][M];int ans,sum,n,m,cnt;struct node{ int x,y,v; bool operator < (const node &a) const{ return v
                  
                   n||y2<1||y2>m||!mark[x2][y2]) return 1; if(mark[x1][y1]==mark[x2][y2]) return 0; e[++cnt].x=mark[x1][y1]; e[cnt].y=mark[x2][y2]; e[cnt].v=v-1; return 1;}void build(int x,int y){ for(int i=x+1;i<=n;i++){ if(!insert(x,y,i,y,i-x)||!insert(x,y,i,y+1,i-x)||!insert(x,y,i,y-1,i-x)){ break; } } for(int i=x-1;i;i--){ if(!insert(x,y,i,y,x-i)||!insert(x,y,i,y+1,x-i)||!insert(x,y,i,y-1,x-i)){ break; } } for(int i=y+1;i<=m;i++){ if(!insert(x,y,x,i,i-y)||!insert(x,y,x+1,i,i-y)||!insert(x,y,x-1,i,i-y)){ break; } } for(int i=y-1;i;i--){ if(!insert(x,y,x,i,y-i)||!insert(x,y,x+1,i,y-i)||!insert(x,y,x-1,i,y-i)){ break; } }}void work2(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]){ build(i,j); } } } sort(e+1,e+cnt+1); for(int i=1;i<=ans;i++) fa[i]=i; ans=0;sum=0; for(int i=1,fx,fy;i<=cnt;i++){ fx=find(e[i].x); fy=find(e[i].y); if(fx!=fy){ fa[fy]=fx; ans++; sum+=e[i].v; } } printf("%d %d\n",ans,sum);}int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ mp[i][j]=in(); } } work1(); work2(); return 0;}

二、产生数

题目描述 Description

　　给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。

　　规则：

　　　一位数可变换成另一个一位数：

　　　规则的右部不能为零。

　　例如：n=234。有规则（k＝2）：

　　　　2－> 5

　　　　3－> 6

　　上面的整数 234 经过变换后可能产生出的整数为（包括原数）:

　　　234

　　　534

　　　264

　　　564

　　共 4 种不同的产生数

问题：

　　给出一个整数 n 和 k 个规则。

求出：

　　经过任意次的变换（0次或多次），能产生出多少个不同整数。

　　仅要求输出个数。

输入描述 Input Description

键盘输人，格式为：

　　n k

　　x1 y1

　　x2 y2

　　... ...

　　xn yn

输出描述 Output Description

屏幕输出，格式为：

　　一个整数（满足条件的个数）

样例输入 Sample Input

　　 234 2

　　2 5

　　3 6

样例输出 Sample Output

AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                using namespace std;#define N 10010#define M 60#define ll long long#define xx first#define yy secondtypedef pair
                 
                   diy;inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int num[M],a[M][M];char s[N];int f[N],p;void deal(int x){ for(int j=1;j<=p;j++){ f[j]*=x; } for(int j=1;j<=p<<1;j++){ if(f[j]>9){ f[j+1]+=f[j]/10; f[j]%=10; } } while(f[p+1]) p++;}int main(){ //freopen("sh.txt","r",stdin); int i,j,k,x,y; scanf("%s %d",s,&k); while(k--) scanf("%d%d",&x,&y),a[x][y]=1; for(k=0;k<10;k++){ for(i=0;i<=10;i++){ for(j=0;j<10;j++){ if(i!=j&&i!=k&&j!=k){ if(a[i][k]&&a[k][j]){ a[i][j]=1; } } } } } for(i=0;i<10;i++){ for(j=0;j<10;j++){ num[i]+=a[i][j]; } } f[1]=1;p=1; //ll sum=1; //for(i=0;i

三、装箱问题

题目描述 Description

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述 Input Description

一个整数v，表示箱子容量

一个整数n，表示有n个物品

接下来n个整数，分别表示这n 个物品的各自体积

输出描述 Output Description

一个整数，表示箱子剩余空间。

样例输入 Sample Input

样例输出 Sample Output

AC代码：

#include
     
      #include
      
       using namespace std;#define N 100020int n,m,c[N],f[N];int main(){    scanf("%d%d",&m,&n);    for(int i=1;i<=n;i++) scanf("%d",&c[i]);    for(int i=1;i<=n;i++){        for(int j=m;j>=c[i];j--){            f[j]=max(f[j],f[j-c[i]]+c[i]);        }    }    printf("%d\n",m-f[m]);    return 0;}

转载于:https://www.cnblogs.com/shenben/p/5798512.html

你可能感兴趣的文章

软件测试2019：第五次作业—— 安全测试（含安全测试工具实验）

查看>>

SSM框架搭建总结（2）

查看>>