Codeforces 903 div3 A-F

A

题目分析

数据范围很小,暴力枚举即可,然后给字符串x的长度设置一个上限,我设了50,因为n*m<25,多一倍够用了

C++代码

#include<iostream>
using namespace std;
void solve(){int n,m;string x,s;cin>>n>>m>>x>>s;int cnt=0;while(x.size()<50){for(int i=0;i<x.size();i++)if(x[i]==s[0]&&x.size()-i>=m){if(x.substr(i,m)==s){cout<<cnt<<endl;return;}}cnt++;x+=x;}cout<<-1<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

B

题目分析

找三个数中的最小数,然后判断其他两个数是否是他的倍数,如果不是,直接输出no

否则直接判断要切多少次,次数大于三就不可以

C++代码

#include<iostream>
using namespace std;
int main(){int t;cin>>t;while(t--){int a,b,c;cin>>a>>b>>c;int minn=min(min(a,b),c);if(a%minn||b%minn||c%minn)puts("NO");else{int cnt=a/minn-1+b/minn-1+c/minn-1;if(cnt>3)puts("NO");else puts("YES");}}return 0;
}

题目分析

 旋转90度与原来相同,可以发现,旋转的过程中,每个数都与另外三个数相关联,如图(i,j)

与他相关联的三个位置也标出来了,直接把四个字母都变成其中最大的一个字母就可以了,然后操作数直接加上它们与最大的字母的差距

C++代码

#include<iostream>
using namespace std;
const int N=1010;
char g[N][N];
char rev[N][N];
int n;
void solve(){cin>>n;for(int i=1;i<=n;i++)scanf("%s",g[i]+1);int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){char &v1=g[i][j],&v2=g[j][n-i+1],&v3=g[n-i+1][n-j+1],&v4=g[n-j+1][i];int maxx=max(max(v1,v2),max(v3,v4));cnt+=maxx-v1;}cout<<cnt<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

D

题目分析

每次找a[i]、a[j]、x,使得a[i]=a[i]/x,a[j]=a[j]*x

由此可见,相当于将a[i]的一个因数分给a[j]

每个数是由若干个质数的乘积组成,所以可以对每个a[i]分解质因数,然后判断每个质数出现的次数是否是n的倍数,如果是,则可以让所有数相等,否则不能

拿样例举例:

100=(2^2)*(5^2)

2=(2^1)

50=(2^1)*(5^2)

10=(2^1)*(5^1)

1无法分解质因数,不过不影响

可以发现,2一共有5次幂,5也一共有5次幂,都是n=5的倍数,每个数只需得到一个2一个5即可,即每个数都可以变成10

C++代码

#include<iostream>
#include<map>
using namespace std;
const int N=10010;
int a[N];
int n;
void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];map<int,int> cnt;for(int i=1;i<=n;i++){int s=a[i];for(int j=2;j<=s/j;j++){//分解质因数if(s%j==0){while(s%j==0){cnt[j]++;//j的次数+1s/=j;}}}if(s>1)cnt[s]++;}for(auto t:cnt){if(t.second%n!=0){puts("No");return;}}puts("Yes");
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

题目分析

dp[i]:从n到i最少需要删除几个数才可以变成优美序列

从后往前做一遍DP,每次遍历到一个数,有两种情况:

1、不选择该数开头的一串序列

dp[i]=dp[i+1]+1

2、选择该数开头的一串序列,即下标为i~i+a[i]的数都不能删

dp[i]=min(dp[i],dp[i+a[i]+1])

记得初始化

dp[n]=1;//只有一个数的时候只能删掉,因为a[i]至少为1,后面最少要跟着一个数

dp[n+1]=0;

C++代码

#include<iostream>
using namespace std;
const int N=200010;
int dp[N],a[N];
int n;
void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//dp[i]表示从n~i最少删除几个数 dp[n+1]=0; dp[n]=1;//最后一个数不可能选,因为它后面没有数了 for(int i=n;i>=1;i--){//不选以a[i]为起点的一串数字,就要删掉a[i]dp[i]=dp[i+1]+1;//选以a[i]为起点的一串数字,前提是i+a[i]要小于等于nif(i+a[i]<=n)dp[i]=min(dp[i],dp[i+a[i]+1]); }cout<<dp[1]<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

题目分析

换根DP

设置一个数组f[N][2]

f[i][0]:以i为根节点到任意一个被标记的点的最大距离

f[i][1]:以i为根节点到任意一个被标记的点的次大距离

dfs1(u,fa)函数由子节点更新父节点的信息

假设j是u的儿子节点,状态转移方程为:

1、f[j][0]+1>=f[u][0]:f[u][1]=f[u][0],f[u][0]=f[j][0]+1

2、f[j][0]+1>f[u][1]:f[u][1]=f[j][0]+1

dfs2(u,fa)函数由父节点更新子节点的信息

1、f[fa][0]不是由f[u][0]更新来的,则用f[fa][0]更新u:

      f[fa][0]+1>=f[u][0]:f[u][1]=f[u][0],f[u][0]=f[fa][0]+1

      f[fa][0]+1>f[u][1]:f[u][1]=f[fa][0]+1

2、f[fa][0]是由f[u][0]更新来的,则用f[fa][1]更新u:

      f[fa][1]+1>=f[u][0]:f[u][1]=f[u][0],f[u][0]=f[fa][1]+1

      f[fa][1]+1>f[u][1]:f[u][1]=f[fa][1]+1

两次dfs传入的第一个参数必须相同(1~n中的任何一个数),不然会打乱父子关系

C++代码

#include<iostream>
using namespace std;
const int N=200010,M=N*2,INF=0x3f3f3f3f;
int h[N],e[M],ne[M],idx;
int f[N][2];//f[u][0]存储以节点u为根节点的到其他点的最大值,f[u][1]存储次大值 
int n,k,ans;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int fa){//子节点更新父节点 //由于初始化f为负无穷(被标记的点除外)//所以此时求到的最大和次大的距离就是到每个标记的点的距离for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa)continue;dfs1(j,u);if(f[j][0]+1>=f[u][0])f[u][1]=f[u][0],f[u][0]=f[j][0]+1;else if(f[j][0]+1>f[u][1])f[u][1]=f[j][0]+1;}
}
void dfs2(int u,int fa){//父节点更新子节点 if(fa!=-1){int t=f[fa][0]+1;//t为父节点的最大值+1 //如果父节点的最大值刚好就是由u过来的,则t更新为次大值+1 if(f[fa][0]==f[u][0]+1)t=f[fa][1]+1;//父节点信息更新字节点信息if(t>=f[u][0])f[u][1]=f[u][0],f[u][0]=t;else if(t>f[u][1])f[u][1]=t;}//更新u的所有儿子for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa)continue;dfs2(j,u);}ans=min(ans,f[u][0]);
}
void solve(){cin>>n>>k;idx=0,ans=INF;for(int i=1;i<=n;i++)f[i][0]=f[i][1]=-INF,h[i]=-1;for(int i=1;i<=k;i++){int x;cin>>x;f[x][0]=f[x][1]=0;}for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}//注意:dfs1和dfs2中的参数必须相同,不能上面传1下面传2,不然两次dfs的父子关系就不一样dfs1(1,-1);
//	for(int i=1;i<=n;i++)
//		cout<<"i="<<i<<" "<<f[i][0]<<" "<<f[i][1]<<endl;dfs2(1,-1);
//	for(int i=1;i<=n;i++)
//		cout<<"i="<<i<<" "<<f[i][0]<<" "<<f[i][1]<<endl;cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3268401.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

基于RS485的Modbus协议

RS485&#xff1a;用来传输数据&#xff0c;RS485是一种差分传输的串行通信标准&#xff0c;以其强大的抗干扰能力、长距离传输和多点通信能力&#xff0c;在工业控制领域得到广泛应用。RS485使用一对差分信号线&#xff08;A和B&#xff09;来传输数据&#xff0c;差分信号能有…

eclipse ui bug

eclipse ui bug界面缺陷&#xff0c;可能项目过多&#xff0c;特别maven项目过多&#xff0c;下载&#xff0c;自动编译&#xff0c;加载更新界面异常 所有窗口死活Restore不回去了 1&#xff09;尝试创建项目&#xff0c;还原界面&#xff0c;失败 2&#xff09;关闭所有窗口&…

Django学习(二)

get请求 练习&#xff1a; views.py def test_method(request):if request.method GET:print(request.GET)# 如果链接中没有参数a会报错print(request.GET[a])# 使用这个方法&#xff0c;当查询不到参数时&#xff0c;不会报错而是返回你设置的值print(request.GET.get(c,n…

winrar安装好后,鼠标右键没有弹出解压的选项

本来安装挺好的&#xff0c;可以正常使用&#xff0c;有天我把winrar相关的文件挪了个位置&#xff0c;就不能正常使用了。 然后我去应用里面找&#xff0c;找到应用标识了&#xff0c;但是找不到对应的文件夹&#xff08;因为我挪到另外一个文件夹里了&#xff09;。 于是我找…

语言转文字

因为工作原因需要将语音转化为文字&#xff0c;经常搜索终于找到一个免费的好用工具&#xff0c;记录下使用方法 安装Whisper 搜索Colaboratory 右上方链接服务 执行 !pip install githttps://github.com/openai/whisper.git !sudo apt update && sudo apt install f…

Android 软键盘挡住输入框

Android原生输入法软键盘挡住输入框,网上各种解法,但不起效。 输入框都是被挡住了,第二张图的小点,实际就是输入法的光标。 解法: packages\inputmethods\LatinIME\java\res\values-land config.xml <!-- <fraction name="config_min_keyboard_height"&g…

pikachu靶场之目录遍历、敏感信息泄露

一、目录遍历 漏洞概述 在web功能设计中,很多时候我们会要将需要访问的文件定义成变量&#xff0c;从而让前端的功能便的更加灵活。 当用户发起一个前端的请求时&#xff0c;便会将请求的这个文件的值(比如文件名称)传递到后台&#xff0c;后台再执行其对应的文件。 在这个过…

如何评价估计量的好坏

目录 三大方法 概念 无偏性 如何计算估计量的无偏性&#xff1f; 步骤 有效性 有效性在不同类型的数据分析中如何评估&#xff1f; 步骤 一致性 一致性原则在实际应用中的挑战有哪些&#xff1f; 挑战 在大样本情况下&#xff0c;如何准确测量估计量的一致性&#xf…

AcWing-差分矩阵

insert函数影响范围&#xff0c;在b差分数组这样操作影响到是a里面的&#xff0c;所以下图的矩阵表示的是a数组 b[x1][y1]c;会导致a里面仅绿色范围的a[i][j]c b[x1][y21]-c;会导致a里面仅黄色范围的a[i][j]-c b[x21][y1]-c;会导致a里面仅蓝色范围的a[i][j]-c b[x21][y21]c;会导…

SQL Server 设置端口号:详细步骤与注意事项

目录 一、了解SQL Server端口号的基础知识 1.1 默认端口号 1.2 静态端口与动态端口 二、使用SQL Server配置管理器设置端口号 2.1 打开SQL Server配置管理器 2.2 定位到SQL Server网络配置 2.3 修改TCP/IP属性 2.4 重启SQL Server服务 三、注意事项 3.1 防火墙设置 3…

数据结构与算法-归并排序

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; 文章目录 引言一、归并排…

MySQL笔记3——高级数据查询语句DQL

多表联查 多表联查可以通过连接运算实现&#xff0c;即将多张表通过主外键关系关联在一起进行查询。下图提供了多表联查 时用到的数据库表之间的关系。 等值查询和非等值查询 非等值查询&#xff1a;SELECT * FROM 表1&#xff0c;表2 等值查询&#xff1a;SELECT * FROM 表…

Oracle对比两表数据的不一致

MINUS 基本语法如下 [SQL 语句 1] MINUS [SQL 语句 2];举个例子&#xff1a; select 1 from dual minus select 2 from dual--运行结果 1-------------------------------- select 2 from dual minus select 1 from dual--运行结果 2所以&#xff0c;如果想找所有不一致的&a…

Codeforces Round 962 (Div. 3)

链接 C题&#xff1a; 思路&#xff1a; 直接暴力求每个字母的前缀和&#xff0c;对于区间l&#xff0c;r的最小操作就是区间不同数的一半&#xff0c;因为可以把一个数变成另一个不一样的数&#xff0c;一下抵消两个。 #include<bits/stdc.h> using namespace std; //…

苹果CMS V10萌芽采集插件Pro v10.7.3

苹果CMS V10萌芽采集插件Pro v10.7.3 插件下载:萌芽采集插件Pro v10.7.3.zip 使用说明: 将addons文件和static文件放到你苹果cms程序的根目录并覆盖&#xff0c; 在登录后台在应用-应用市场启用。http://你的域名/admin.php/admin/mycj/union.html

等保测评练习卷19

等级保护初级测评师试题19 姓名&#xff1a; 成绩&#xff1a; 判断题&#xff08;10110分&#xff09; 1.为了有效处理等级保护对象运行过程中可能发生的重大安全事件&#xff0c;需要在统一的框架下制定针对不同安全事件的应急预…

FPGA开发——呼吸灯的设计

一、原理 呼吸灯的原理主要基于‌PWM&#xff08;脉冲宽度调制&#xff09;技术&#xff0c;通过控制LED灯的占空比来实现亮度的逐渐变化。这种技术通过调整PWM信号的占空比&#xff0c;即高电平在一个周期内所占的比例&#xff0c;来控制LED灯的亮度。当占空比从0%逐渐变化到1…

java计算机毕设课设—记账管理系统(附源码和安装视频)

这是什么系统&#xff1f; java计算机毕设课设—记账管理系统&#xff08;附源码和安装视频&#xff09; 记账管理系统主要用于财务人员可以从账务中判断公司的发展方向。对个人和家庭而言&#xff0c;通过记账可以制定日后的 消费计划&#xff0c;这样才能为理财划出清晰合理…

C++初学者指南-6.函数对象--lambdas(基础)

C初学者指南-6.函数对象–lambdas(基础) 文章目录 C初学者指南-6.函数对象--lambdas(基础)提醒:函数类和对象Lambdas变量捕获保存闭包通用Lambdas (C14)广义捕获 (C14)相关内容 幻灯片 提醒:函数类和对象 类至少提供一个operator () (…) {…} 函数能像一个函数一样被调用可以…

Nginx制作下载站点

使用nginx制作一个类似nginx官网的下载站点 如何制作一个下载站点,首先需要ngx_http_autoindex_module模块 该模块处理以斜杠(“/”)结尾的请求&#xff0c;并生成目录列表。 nginx编译的时候会自动加载该模块&#xff0c;但是该模块默认是关闭的&#xff0c;需要使用下来指令…