东华进阶oj41-50

2023-10-24 15:20
文章标签 进阶 50 东华 oj41

本文主要是介绍东华进阶oj41-50，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
41 盾神与条状项链
作者: Turbo 时间限制: 1S 章节: 模拟
问题描述 :
　　有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。
　　“哇这么恶心的项链你也做得出来！！！”
　　盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。
　　“这个嘛首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧”土方一下子说出了m个修改步骤。
　　盾神觉得这个用人工做太麻烦了，于是交给了你。
输入说明 :
　　第一行两个数，分别为n，m。
　　第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。
　　接下来m行，为以下形式之一：
　　ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。
　　DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。
　　输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。

表示颜色的数字不超过105的正数，1<=n<=104，1<=m<=10^4。
输出说明 :
　　第一行为一个数len，为做完所有操作后，项链的长度。
　　第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>//链表操作
typedef struct nod
{int data;struct nod *next;
}node;
int n,m,len;void init(node *&head)
{node *p,*r;head=(node*)malloc(sizeof(node));head->next=NULL;r=head;len=n;for(int i=0;i<n;++i){p=(node*)malloc(sizeof(node));scanf("%d",&(p->data));p->next=NULL;r->next=p;r=p;}
}
void add(node *head,int p,int q)
{node *pre=head,*t;while(pre->next->data!=p && pre->next)pre=pre->next;//找到pt=(node *)malloc(sizeof(node));t->data=q;t->next=pre->next;pre->next=t;len++;
}
void del(node *head,int p)
{node *pre=head,*t;while(pre->next->data!=p)pre=pre->next;t=pre->next;//肯定能找到 所以不用担心找不到pre->next=pre->next->next;free(t);len--;
}
int main()
{node *head;		//怎能无表头呢scanf("%d %d",&n,&m);init(head);while(m--){char str[100];int p,q;scanf("%s",str);if(strcmp(str,"ADD")==0){scanf(" %d %d",&p,&q);add(head,p,q);}if(strcmp(str,"DEL")==0){scanf(" %d",&p);del(head,p);}}printf("%d\n",len);while(head->next){printf("%d ",head->next->data);head=head->next;}return 0;
}

42 Cutting Chains
作者: Turbo 时间限制: 1S 章节: 深度优先搜索
问题描述 :
　　什么！Anna Locke最近买了几个链环，并且其中的一些链环连接到了一起。
　　Anna想要把这些链环拼组成连续的一段链。她把这些链环带到一个珠宝商那里，珠宝商告诉她合并这些链环的费用取决于必须打开和关上的环的数目。为了最小化这个费用，她小心地计算为了合并成一个单独的序列所需要打开的最小的环的数目。这个比她想象中更困难。请你为她解决这个问题。
输入说明 :
　　输入包含多组关于链环集合的描述，对于每一组。每个链环集合由一行用一个或多个空格隔开的数字表示。
每个描述由一个n开始，表示链环集合中环的数量。我们把这些环编号为1,2,…,n。
紧接着n后面的整数描述了哪些环连接在一起。每个连接由一对整数i，j（1<=i,j<=n并且i≠j）来描述，代表环i和环j连接，即一个穿过另一个。每个链环集合用一对-1 -1表示结束（-1 -1 不用进行计算）
　　输入用n=0表示结束，并且n=0不用进行计算
1<=n<=15
输出说明 :
　　对于每一个输入的链环集合，输出一行形如
　　Set N: Minimum links to open is M
　　N是测试数据的组号，M是最小需要打开然后关闭的次数来使所有环组成一条单独的链。
　　1<=i,j<=n并且i≠j

#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
int n,num,maxn=20,edge[20][20],vis[20];
int branch(int x)//分支数目
{for(int i=0;i<n;++i){if(x&(1<<i))continue;int cnt=0;for(int j=0;j<n;++j){if(x&(1<<j))continue;//已经打开的环if(edge[i][j])++cnt;//若其与其他环相连+1}if(cnt>2)return 1;//大于0 结束}return 0;
}
int dfs(int s,int now,int pre)
{//now是当前环 pre是上一个vis[now]=1;for(int i=0;i<n;++i){if((s&(1<<i)) || !edge[now][i] || i==pre)continue;//如果已经打开或者遇见自己就跳过if(vis[i]||dfs(s,i,now))return 1;}return 0;
}
int circle(int x)
{for(int i=0;i<n;++i){if(x&(1<<i)||vis[i])continue;++num;if(dfs(x,i,-1))return 1;}return 0;
}
int cal(int x)
{//计算要打开的环的数量return x==0?0:cal(x/2)+(x&1);
}
int solve()
{int ans=n-1;//最多打开的数目for(int i=0;i<(1<<n);++i){memset(vis,0,sizeof(vis));num=0;if(branch(i)||circle(i))continue;//若有环或者分支大于2//int temp=cal(i);if(cal(i)>=num-1)ans=min(ans,cal(i));//如果能够连起来，就更新ans}return ans;
}
int main()
{int cou=0;while(scanf("%d",&n) && n){memset(edge,0,sizeof(edge));int x,y;while(scanf("%d %d",&x,&y) && x+y>0){edge[x-1][y-1]=1;edge[y-1][x-1]=1;}printf("Set %d: Minimum links to open is %d\n", ++cou, solve());}return 0;
}

43 最少操作数
作者: Turbo 时间限制: 1S 章节: 基本练习（数组）
问题描述 :
　　数组A中共有n个元素，初始全为0。你可以对数组进行两种操作：1、将数组中的一个元素加1；2、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。
输入说明 :
　　第一行一个正整数n表示数组中元素的个数
　　第二行n个正整数表示目标状态B中的元素
　　n<=50，B[i]<=1000
输出说明 :
　　输出一行表示最少操作数

#include<iostream>
int a[55],n;//逆向考虑 如果是奇数就-1，方便除2呀，如果全是偶数/2
__int64 ans=0;
int judge()//判断是否全是0
{for(int i=0;i<n;++i)if(a[i]!=0)return 0;return 1;
}
int main()
{std::cin>>n;for(int i=0;i<n;++i)std::cin>>a[i];while(1){for(int i=0;i<n;++i)//是奇数就-1if(a[i]&1){a[i]--;ans++;}if(judge())break;for(int i=0;i<n;++i)a[i]/=2;ans++;}std::cout<<ans<<std::endl;return 0;
}

在这里插入图片描述

#include<stdio.h>
void printX(int b)
{if(b!=0){printf("x");if(b!=1)printf("^%d",b);}
}
int main()
{int n,b;scanf("%d %d",&n,&b);if(b<0)printf("-");if(b!=1 && b!=-1)printf("%d",b>0?b:-b);printX(n);while(--n>=0){scanf("%d",&b);if(b==0)continue;printf(b>0?"+":"-");if(n!=0 && b!=1 && b!=-1)printf("%d",b>0?b:-b);printX(n);}if(b!=0)printf("%d",b>0?b:-b);return 0;
}

在这里插入图片描述

#include<stdio.h>
int main()//和最大子序列，思路是动态规划，我们尽量使用连续的序列，因为
{//连续的才能遇见更好的（更大的数），那么假设dp[i-1]是i-1及其之前连续的和long long int n,temp,max;//有可能a[i-1]是负的，但是没关系，只要加上a[i-1]后dp[i-1]还是正的while(scanf("%lld",&n)!=EOF){//那么它这个状态就是一个略好的，我们到最后比较哪个dp[i]最大scanf("%lld",&max);long long int sum=max;//就是我们想要的结果，结果可能很大 要使用long int 刚刚就wa了for(int i=1;i<n;++i){scanf("%lld",&temp);if(sum>=0)sum+=temp;//sum就是之前i-1个的状态，若他是正的或者0，则可以尽量和后面连续else sum=temp;//若实在没办法。就只能从新加和if(max<sum)max=sum;}printf("%lld\n",max);}return 0;
}

在这里插入图片描述

#include<stdio.h>
#define min(a,b) (a<b?a:b)//dfs+动态规划
int n,k,max=-1,ans[20],v[20];
void calculate()//计算当前组合得到的最大值
{int dp[300]={0},i=0;//dp[i]是表示i面值 最少需要多少张while(dp[i]<=n)//当张数还不满{++i;dp[i]=99999;for(int j=0;j<k && i>=v[j];++j)dp[i]=min(dp[i],dp[i-v[j]]+1);}//当无法连续时候才跳出循环 所以是i-1是答案if(i-1>max){max=i-1;for(int i=0;i<k;++i) ans[i]=v[i];}
}
void DFS(int deep)//搜索可能有的组合
{if(deep==k-1)//这题很严格 一开始出口是k 就TLE了{calculate();return;}for(int i=v[deep]+1;i<v[deep]*n+2;++i)//假设 前面是3 则 下一个设计最大是3*n+1 不然断了{v[deep+1]=i;DFS(deep+1);}
}
int main()
{scanf("%d %d",&n,&k);v[0]=1;//第一张肯定是1DFS(0);for(int i=0;i<k;++i)printf(i==0?"%d":" %d",ans[i]);printf("\nMAX=%d\n",max);return 0;
}

在这里插入图片描述

#include<stdio.h>
#include<string.h>
int convert(int x)
{int sum=0;while(x){sum+=x%10;x/=10;}return sum<10?sum:convert(sum);
}
int main()//好久没见过这种水题了，开心
{char str[2020];int n,code[6];scanf("%d ",&n);while(n--){gets(str);int len=strlen(str),y=0;memset(code,0,sizeof(code));for(int i=0;i<len;i++){code[y]+=str[i];y=(y+1)%6;}for(int i=0;i<6;++i)printf("%d",convert(code[i]));printf("\n");}return 0;
}

48 小计算器
作者: Turbo 时间限制: 1S 章节: 模拟
问题描述 :
模拟程序型计算器，依次输入指令，可能包含的指令有

数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
输出指令：‘EQUAL’，以当前进制输出结果
重置指令：‘CLEAR’，清除当前数字
指令按照以下规则给出：
数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
进制转换指令可能出现在任何地方

运算过程中中间变量均为非负整数，且小于2^63。
以大写的’A’'Z’表示1035
输入说明 :
第1行：1个n，表示指令数量
第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出说明 :
依次给出每一次’EQUAL’得到的结果

#include<stdio.h>
#include<string.h>//感觉使用运算时候都转成10进制比较好办
__int64 convert10(char s[],__int64 b)//b进制下的s换成10进制的
{__int64 sum=0,temp=1,num;int len=strlen(s)-1;while(len>=0){if(s[len]>='A')num=10+s[len]-'A';else num=s[len]-'0';sum+=num*temp;temp=temp*b;len--;}return sum;
}
void convert(__int64 x, __int64 b)//把10进制的x转换成b进制，除留余数法
{//输出if(b==10){printf("%I64d\n",x);return;}int sta[5000],pos=-1;do{sta[++pos]=x%b;x/=b;}while(x);//有效的解决了0的输出问题while(pos!=-1){if(sta[pos]<10)printf("%d",sta[pos]);else printf("%c",sta[pos]-10+'A');pos--;}printf("\n");
}
__int64 cal(__int64 a,__int64 b,__int64 flag)
{if(flag==1)return a+b;else if(flag==2) return a-b;else if(flag==3) return a*b;else if(flag==4) return a/b;else if(flag==5) return a%b;
}
int main()
{char str[2020],s1[2020];__int64 n,temp,sum,k=10,flag=1;//flag表示+-...scanf("%I64d",&n);getchar();while(n--){scanf("%s",str);getchar();if(strcmp(str,"CLEAR")==0){sum=0;//每次clear之后进制不变flag=1;//初始的时候是+ 它不香吗}if(str[0]=='N' && str[1]=='U' && str[2]=='M'){scanf("%s",s1);getchar();temp=convert10(s1,k);sum=cal(sum,temp,flag);}if(strcmp(str,"ADD")==0)flag=1;if(strcmp(str,"SUB")==0)flag=2;if(strcmp(str,"MUL")==0)flag=3;if(strcmp(str,"DIV")==0)flag=4;if(strcmp(str,"MOD")==0)flag=5;if(str[0]=='C'&&str[1]=='H'&&str[2]=='A'){scanf("%I64d",&k);getchar();}if(strcmp(str,"EQUAL")==0)convert(sum,k);}return 0;
}

49 合根植物
作者: Turbo 时间限制: 1S 章节: 深度优先搜索
问题描述 :
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体(也就是说，成为一株合根植物了）。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入说明 :
　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
　　接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
　　接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。
　　比如：5 * 4 的小格子，编号：

	1   2   3   45   6   7   89   10  11  1213  14  15  1617  18  19  20

比如输入：
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
其合根情况如下：

因此总共有5株合根植物。

#include<stdio.h>
int tree[1000001],m,n,k,a,b,x,y;//克鲁斯卡尔算法
int getroot(int a)
{while(tree[a]!=a)a=tree[a];return a;
}
int main()
{for(int i=0;i<1000001;++i)tree[i]=i;scanf("%d %d %d",&m,&n,&k);for(int i=0;i<k;++i){scanf("%d %d",&a,&b);x=getroot(a);y=getroot(b);if(x!=y)tree[x]=y;}int ans=0;for(int i=1;i<=m*n;++i){if(tree[i]==i)ans++;}printf("%d\n",ans);return 0;
}

在这里插入图片描述

#include<iostream>
#include<algorithm>//深搜
int n,m,e[110][110],ans=10000;
int room[110][110];//room[i][0]表示第i个room里有多少人
void dfs(int deep,int num)//num是有几个屋子，deep表示第几人
{if(num>=ans)return;//剪枝if(deep==n+1)//第n+1个人，即是n个都安排完了{ans=std::min(ans,num);return;}for(int i=1,j;i<=num;++i){for(j=1;j<=room[i][0];++j){if(e[deep][ room[i][j] ]==1)break;}if(j>room[i][0])//若都不认识，进房子{room[i][0]++;room[i][j]=deep;dfs(deep+1,num);room[i][0]--;}}//再开一间num++;room[num][0]++;room[num][ room[num][0] ]=deep;dfs(deep+1,num);room[num][0]--;//回溯
}
int main()
{std::cin>>n>>m;;for(int i=0;i<m;++i){int a,b;std::cin>>a>>b;;e[a][b]=e[b][a]=1;}dfs(0,0);std::cout<<ans<<std::endl;return 0;
}

这篇关于东华进阶oj41-50的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/276049。

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
[MySQL表的增删改查-进阶]

[MySQL表的增删改查-进阶]

🌈个人主页：努力学编程’ ⛅个人推荐： c语言从初阶到进阶 JavaEE详解 数据结构 ⚡学好数据结构，刷题刻不容缓：点击一起刷题 🌙心灵鸡汤：总有人要赢，为什么不能是我呢 💻💻💻数据库约束 🔭🔭🔭约束类型 not null: 指示某列不能存储 NULL 值unique: 保证某列的每行必须有唯一的值default: 规定没有给列赋值时的默认值.primary key:
阅读更多...
【Linux 从基础到进阶】Ansible自动化运维工具使用

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具，采用无代理架构（agentless），基于 SSH 连接进行管理，具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用，旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念
阅读更多...
Flutter 进阶：绘制加载动画

Flutter 进阶：绘制加载动画

绘制加载动画：由小圆组成的大圆 1. 定义 LoadingScreen 类2. 实现 _LoadingScreenState 类3. 定义 LoadingPainter 类4. 总结 实现加载动画 我们需要定义两个类：LoadingScreen 和 LoadingPainter。LoadingScreen 负责控制动画的状态，而 LoadingPainter 则负责绘制动画。
阅读更多...
从0到1，AI我来了- （7）AI应用-ComfyUI-II（进阶）

从0到1，AI我来了- （7）AI应用-ComfyUI-II（进阶）

上篇comfyUI 入门 ，了解了TA是个啥，这篇，我们通过ComfyUI 及其相关Lora 模型，生成一些更惊艳的图片。这篇主要了解这些内容：         1、哪里获取模型？         2、实践如何画一个美女？         3、附录：               1）相关SD(稳定扩散模型的组成部分）               2）模型放置目录（重要）
阅读更多...
java学习，进阶，提升

java学习，进阶，提升

http://how2j.cn/k/hutool/hutool-brief/1930.html?p=73689
阅读更多...
【408DS算法题】039进阶-判断图中路径是否存在

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G，设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断，有两种做法：（本文的实现均基于邻接矩阵存储方式的图） 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历，遍历过程中遇到结点i就表示存在路径start->i，故只需判断每个结点i是否就是stop
阅读更多...
【附答案】C/C++ 最常见50道面试题

【附答案】C/C++ 最常见50道面试题

文章目录 面试题 1：深入探讨变量的声明与定义的区别面试题 2：编写比较“零值”的`if`语句面试题 3：深入理解`sizeof`与`strlen`的差异面试题 4：解析C与C++中`static`关键字的不同用途面试题 5：比较C语言的`malloc`与C++的`new`面试题 6：实现一个“标准”的`MIN`宏面试题 7：指针是否可以是`volatile`面试题 8：探讨`a`和`&a`
阅读更多...
day-50 求出最长好子序列 I

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾，且有不超过 h 个下标满足条件的最长好子序列的长度（0<=h<=k），二维数组dp初始值全为1 解题过程 状态转换方程： 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2