当前位置: 首页 > news >正文

AC修炼计划(AtCoder Regular Contest 163)

传送门:AtCoder Regular Contest 163 - AtCoder

第一题我们只需要将字符串分成两段,如果存在前面一段比后面一段大就成立。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1000000007;
int n,k;
void icealsoheat(){cin>>n;string s;cin>>s;for(int i=1;i<n;i++){if(s.substr(0,i)<s.substr(i)){puts("Yes");return;}}puts("No");}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;cin>>_;while(_--){icealsoheat();}}

B - Favorite Game

第二题也比较基础,我们可以先把后面的数组排序,然后枚举每一段(每一段的长度为k,包含按顺序的k个数)

代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1000000007;
int n,k;
int b[1000005];
void icealsoheat(){int le,re;cin>>n>>k;cin>>le>>re;n-=2;int an=0;for(int i=1;i<=n;i++){cin>>b[i];if(b[i]>=le&&b[i]<=re)an++;}sort(b+1,b+1+n);if(an>=k){cout<<0;return;}int ans=0x3f3f3f3f3f3f3f3f;for(int i=1;i<=n-k+1;i++){int xx=0;if(le>b[i])xx+=abs(le-b[i]);if(re<b[i+k-1])xx+=abs(re-b[i+k-1]);ans=min(ans,xx);}cout<<ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}}

C - Harmonic Mean

这题想到了裂项相消公式,但是没有想到给他们分开。

当存在n=t*(t+1)的时候,我们不能直接用数列(2,6,12,20.。。。。(n-1)*n,n)

而是把后n-1项看成一部分,使后n-1项的和等于1,然后把每一个项数*2,此时的后n-1项的总和为1/2,这时候我们只需要再放入一个2即可

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,k;
map<int,int>hh;
void yu(){for(int i=1;i<=500;i++){hh[i*(i+1)]=1;}
}
void icealsoheat(){cin>>n;if(n==2)cout<<"No\n";else{cout<<"Yes\n";if(n==1)cout<<"1\n";else if(n==3)cout<<"2 3 6\n";else{vector<int>ans;if(hh[n]){n--;for(int i=1;i<n;i++){ans.push_back(2ll*i*(i+1ll));}ans.push_back(2ll*n);cout<<"2 ";for(auto i:ans){cout<<i<<" ";}}else{for(int i=1;i<n;i++){cout<<i*(i+1)<<" ";}cout<<n;}cout<<"\n";}}}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;yu();cin>>_;while(_--){icealsoheat();}
}

D - Sum of SCC

好厉害的题,开拓了我的视野。不看题解我是真想不到竟然还能这么dp。

我们可以知道,统计SSG(强连通分量)是很难统计的。竞赛图有一个性质:当我们把强连通分量缩点之后,拉直,整个竞赛图会变成一条很长的链,并且,长的链上的任何两个点之间都有一个链(很抽象又很神奇的想法)。既然变成了一个长长的链,那么其实我们可以通过在长链上某点进行一刀切,使其分成左右两个集合,分别是集合A与集合B,同时,我们定义集合A的所有点都与集合B的相连。且集合A的数字较小,集合B的数字较大。

我们用三维dp i,j,k来进行动态规划。i表示我们只有前i个点儿的状态,j表示A集合中有j个点儿,k表示有k条小数向大数连的边。

我们每次塞进去第i个点儿,有两种情况:

1.将该点儿塞入集合A中,那么该点儿可以从集合A中选择p个点使这p个点儿指向该点儿。

dp[i+1][j+1][k+p]+=dp[i][j][k]*c[j][p]

2.将该点儿塞入集合B中,那么A点都会指向该点儿,同时我们可以选取B集合中p个点儿,使其指向该点儿。

dp[i+1][j][j+k+p]+=dp[i][j][k]*c[i-j][p]

代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int n,m;
int c[505][505];void init(int mx)
{for(int i=0;i<=mx;i++)for(int j=0;j<=i;j++) c[i][j]=j?(c[i-1][j-1]+c[i-1][j])%mod:1;
}void icealsoheat(){cin>>n>>m;vector dp(50,vector(50,vector<int>(1600,0)));dp[0][0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){for(int k=0;k<=i*(i-1)/2;k++){for(int p=0;p<=j;p++)(dp[i+1][j+1][k+p]+=dp[i][j][k]*c[j][p]%mod)%mod;for(int p=0;p<=i-j;p++)(dp[i+1][j][j+k+p]+=dp[i][j][k]*c[i-j][p]%mod)%mod;}}}int ans=0;for(int i=1;i<=n;i++){ans=(ans+dp[n][i][m])%mod;}cout<<ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;init(500);while(_--){icealsoheat();}}

相关文章:

AC修炼计划(AtCoder Regular Contest 163)

传送门&#xff1a;AtCoder Regular Contest 163 - AtCoder 第一题我们只需要将字符串分成两段&#xff0c;如果存在前面一段比后面一段大就成立。 #include<bits/stdc.h> #define int long long using namespace std; typedef long long ll; typedef pair<int,int&g…...

持续进化,快速转录,Faster-Whisper对视频进行双语字幕转录实践(Python3.10)

Faster-Whisper是Whisper开源后的第三方进化版本&#xff0c;它对原始的 Whisper 模型结构进行了改进和优化。这包括减少模型的层数、减少参数量、简化模型结构等&#xff0c;从而减少了计算量和内存消耗&#xff0c;提高了推理速度&#xff0c;与此同时&#xff0c;Faster-Whi…...

【设计模式】第24节:行为型模式之“模板方法模式”

一、简介 模板方法模式在一个方法中定义一个算法骨架&#xff0c;并将某些步骤推迟到子类中实现。模板方法模式可以让子类在不改变算法整体结构的情况下&#xff0c;重新定义算法中的某些步骤。 模板模式有两大作用&#xff1a;复用和扩展。其中&#xff0c;复用指的是&#…...

【考研数学】数学“背诵手册”(二)| 线代及概率论部分

文章目录 引言二、线代施密特正交化分块矩阵转置、逆、伴随之间的运算关于秩定义性质 三、概统常见分布的期望及方差 引言 这数一全部内容太多了&#xff0c;放在一篇文章里的话&#xff0c;要编辑就很困难&#xff0c;就把线代和概率放在这篇文章里吧。 二、线代 施密特正交…...

Android WMS——WindowState介绍(十三)

前面文章中的 addWindow 方法,首先获取了 DisplayContent,紧接着判断窗口的 type 类型并标记。然后获取 token 信息,且该信息是通过 DisplayContent 中的方法获取的。最后就是创建并保存 WindowState 信息。 一、简介 在窗口管理系统(Window Manager Service,WMS)中,Wi…...

C/C++网络编程基础知识超详细讲解第二部分(系统性学习day12)

懒大王感谢大家的关注和三连支持~ 目录 前言 一、UDP编程 UDP特点&#xff1a; UDP框架: UDP函数学习 发送端代码案例如下&#xff1a; 二、多路复用 前提讲述 select poll 三、图解如下 总结 前言 作者简介&#xff1a; 懒大王敲代码&#xff0c;…...

【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II

2哥 : 3妹&#xff0c;听说你昨天去面试了&#xff0c;怎么样啊&#xff1f; 3妹&#xff1a;嗨&#xff0c;别提了&#xff0c;让我回去等通知&#xff0c;估计是没有通知了&#xff0c; 还浪费我请了一天假。 2哥 : 你又请假了啊&#xff0c; 你是怎么跟你那个严厉的老板请假…...

window10 mysql8.0 修改端口port不生效

mysql的默认端口是3306&#xff0c;我想修改成3307。 查了一下资料&#xff0c;基本上都是说先进入C:\Program Files\MySQL\MySQL Server 8.0这个目录。 看看有没有my.ini&#xff0c;没有就新建。 我这里没有&#xff0c;就新建一个&#xff0c;然后修改port&#xff1a; […...

欧盟网络安全威胁:虚假与错误信息

如今&#xff0c;数字平台已是新闻媒体的主战地。社交网站、新闻媒体、甚至搜索引擎都是现在大多数人的信息来源。由于这些网站的运作方式是通过吸引人们来产生网站流量&#xff0c;这些抓人眼球的信息通常是推广广告&#xff0c;有些甚至没有经过审查。 国际现状 恶意攻击者现…...

006 Linux 进程的概念 | 获取进程的PID

前言 本文将会向您进程的概念&#xff0c;程序与进程的区别&#xff0c;如何获取进程的标识符-pid 文章重点 1.描述进程——PCB 进程与程序的区别 CPU对进程列表的处理 2.获取进程PID 描述进程-PCB 进程概念 课本概念&#xff1a;程序的一个执行实例或正在执行的程序 内核…...

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测 目录 时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 时序预测 …...

《异常检测——从经典算法到深度学习》23 TimesNet: 用于常规时间序列分析的时间二维变化模型

zz# 《异常检测——从经典算法到深度学习》 0 概论1 基于隔离森林的异常检测算法 2 基于LOF的异常检测算法3 基于One-Class SVM的异常检测算法4 基于高斯概率密度异常检测算法5 Opprentice——异常检测经典算法最终篇6 基于重构概率的 VAE 异常检测7 基于条件VAE异常检测8 Don…...

计算机网络(59)

1. OSI 的七层模型分别是&#xff1f;各自的功能是什么&#xff1f; 2. 为什么需要三次握手&#xff1f;两次不行&#xff1f; 3. 为什么需要四次挥手&#xff1f;三次不行&#xff1f; 4. TCP与UDP有哪些区别&#xff1f;各自应用场景&#xff1f; 5. HTTP1.0&#xff0c;1.1&…...

【CSS】CSS基础知识扫盲

1、 什么是CSS&#xff1f; CSS即层叠样式表 (Cascading Style Sheets). CSS 能够对网页中元素位置的排版进行像素级精确控制, 实现美化页面的效果. 能够做到页面的样式和结构分离 2、 CSS引入方式 CSS代码编写的时候有多种引入方式&#xff1a; 内部样式、外部样式、内联样…...

React中的状态管理

目录 前言 1. React中的状态管理 1.1 本地状态管理 1.2 全局状态管理 Redux React Context 2. React状态管理的优势 总结 前言 当谈到前端开发中的状态管理时&#xff0c;React是一个备受推崇的选择。React的状态管理机制被广泛应用于构建大型、复杂的应用程序&#xf…...

【优选算法系列】【专题九链表】第一节.链表常用技巧和操作总结(2. 两数相加)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、链表常用技巧和操作总结二、两数相加 2.1 题目描述 2.2 题目解析 2.2.1 算法原理 2.2.2 代码编写总结 前言 一、链表常…...

上线Spring boot-若依项目

基础环境 所有环境皆关闭防火墙与selinux 服务器功能主机IP主机名服务名称配置前端服务器192.168.231.177nginxnginx1C2G后端服务器代码打包192.168.231.178javajava、maven、nodejs4C8G数据库/缓存192.168.231.179dbmysql、redis2C4G Nginx #配置Nginxyum源 [rootnginx ~]…...

pinia简单使用

新命令-创建vue3项目 vue create 方式使用脚手架创建项目&#xff0c;vue cli处理&#xff0c; vue3后新的脚手架工具create-vue 使用npm init vuelatest 命令创建即可。 在pinia中&#xff0c;将使用的组合式函数识别为状态管理内容 自动将ref 识别为stste,computed 相当于 ge…...

数据库进阶教学——数据库故障恢复(日志文件)

目录 一、日志简介 二、日志文件操作 1、查看日志状态 2、开启日志功能 3、查看日志文件 4、查看当前日志 5、查看日志中的事件 6、删除日志文件 7、查看和修改日志文件有效期 8、查看日志文件详细信息 三、删除的数据库恢复 一、日志简介 日志是记录所有数据库表结…...

Leetcode 73 矩阵置0

class Solution {//1.用矩阵的第一行和第一列来标记该行或该列是否应该为0,但是这样的话忽视了第一行或第一列为0的情况//2.用标记row0和column0来标记第一行或第一列是否该为0public void setZeroes(int[][] matrix) {int n matrix.length;int m matrix[0].length;boolean r…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...