Educational Codeforces Round 153 (Rated for Div. 2)
A.我直接构造((())))和()()()这种了,因为这两种都很简便,只有()和)(
连续字符,且只有这两种可能碰到,py写很简便,因为我忘了c++的find函数空等于啥了
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():s=I()n=len(s)a=""b=""for i in range(1,n+1):a+="()"for i in range(1,n+1):b+="("for i in range(1,n+1):b+=")"if s not in a:print("YES")print(a)return if s not in b:print("YES")print(b)return print("NO")if __name__ == '__main__':for _ in range(II()):solve()
B.我还没看懂题...
C.博弈论题,emmm感觉很典没啥好说的
因为没法操作就获胜
所以当前点能走到任何一个必胜态,那么当前点就是必败态
下面注释的就是没优化过的记忆化搜索
可以观察到优化,找到前面的位置且数比当前数小,存在一个数的状态是必胜态,那么当前就是必败态
然后我脑子可能wa了,用树状数组维护了,
if(tr0.q(a[i]-1)!=tr1.q(a[i]-1)) f[i]=0;就是说前面比当前数小的个数和他们有几个是必败态的
如果相等就说明全是必败态,那么当前就是必胜态
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N];
class BitTree {public:vector<int> tree;int n;BitTree(int _n) : n(_n) {tree.resize(n+1);fill(tree.begin(),tree.end(),0);//for(int i=0;i<=n;i++) tree[i]=0;}inline int lowbit(int x) { return x&-x; }inline void Modify(int x,int v) {for(;x<=n;x+=lowbit(x)) tree[x]+=v;}inline int q(int x) {int ret=0;if(x<=0) return 0;for(;x;x-=lowbit(x)) ret+=tree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}
};
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];vector<int> f(n+1,-1);vector<int> st;int mx=0x3f3f3f3f;BitTree tr0(n),tr1(n);for(int i=1;i<=n;i++){if(mx>a[i]) f[i]=0,mx=a[i];}// function<int(int)> dfs=[&](int x){// if(f[x]!=-1) return f[x];// f[x]=1;// for(int i=x-1;i>=1;i--)//左边有一个1就寄// {// if(a[i]<a[x])// {// f[x]&=(dfs(i)^1);// }// }// return f[x];// };int res=0;f[1]=0;for(int i=1;i<=n;i++){if(f[i]==-1){f[i]=1;if(tr0.q(a[i]-1)!=tr1.q(a[i]-1)) f[i]=0;}if(f[i]==0)tr0.Modify(a[i],1);tr1.Modify(a[i],1);}for(int i=1;i<=n;i++){if(f[i]==1){res++;// cout<<i<<"\n";}}cout<<res<<"\n";
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}
D.
cnt0=0的个数
cnt1=1的个数
首先00和11的个数我们是知道的因为00和11无论顺序怎么样都是 cnt0*(cnt0-1)/2和cnt1*(cnt1-1)/2
又因为01=10,所以最好01和10的个数就是(n-11-00)/2的个数了
然后问题就变成了前i个位置,当前位置填1,且目前01个数是k的最小次数的方程了
当前如果当前填1了,那么难点在怎么知道增加了几个01个数呢
这里有个比较巧妙的思路
由于第i位填1了,已经填了i个,所以增加了i-1个(01和11)因为前面不管填0还是1,01和11的总和是不变的,稳定增加i-1个,且最后答案的11+01的总和也是固定的
所以可以把方程变成
前i个位置,当前位置填1,且目前01+11的个数是k的最小次数的方程了
f[i][k]=f[i-1][k-j](j+i<=k)+(s[i]=='0')
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N];void solve(){string s;cin>>s;n=s.size();int c1=count(s.begin(),s.end(),'1'),c0=n-c1;int need=c1*(c1-1)/2+(n*(n-1)/2-c1*(c1-1)/2-c0*(c0-1)/2)/2;//11个数+01个数vector<vector<int>> f(c1+1,vector<int>(need+1,0x3f3f3f3f));f[0][0]=0;for(int i=0;i<n;i++){for(int j=min(c1-1,i);j>=0;j--){for(int k=0;k+i<=need;k++){f[j+1][k+i]=min(f[j+1][k+i],f[j][k]+(s[i]=='0'));}}}cout<<f[c1][need]<<"\n";
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;// cin>>t;while(t--) solve();
}
E:
直接01bfs搜全部点即可,枚举中点
#include<bits/stdc++.h>
using namespace std;
const int N = 60010,mod=99824435;
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N];
int id[N];
vector<int> g[N];
int dist[676][N];
void solve(){string s;cin>>s;n=s.size();s="?"+s;for(int i=1;i<n;i++){id[i]=(s[i]-'a')*26+s[i+1]-'a';g[id[i]+n+1].push_back(i);g[i].push_back(id[i]+n+1);}for(int i=2;i<n;i++)g[i].push_back(i-1),g[i-1].push_back(i);auto bfs=[&](int x){for(int i=1;i<=n+676;i++)dist[x][i]=1e9;deque<int> q;dist[x][x+n+1]=0;q.push_back(x+n+1);while(q.size()){int y=q.front();q.pop_front();for(auto z:g[y]){if((z>n||y>n)&&dist[x][z]>dist[x][y]+1){dist[x][z]=dist[x][y]+1;q.push_front(z);}if(dist[x][z]>dist[x][y]+2){dist[x][z]=dist[x][y]+2;q.push_back(z);}}}};for(int i=0;i<=675;i++)bfs(i);cin>>m;while(m--){int s,t;cin>>s>>t;int tmp=1e9;for(int j=0;j<=675;j++)tmp=min(tmp,dist[j][s]+dist[j][t]);cout<<min(min(abs(t-s),(id[s]==id[t]?1:1145141919)),tmp/2)<<"\n";}
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;// cin>>t;while(t--) solve();
}
相关文章:
Educational Codeforces Round 153 (Rated for Div. 2)
A.我直接构造((())))和()()()这种了,因为这两种都很简便,只有()和…...

分布式 | 如何搭建 DBLE 的 JVM 指标监控系统
本篇文章采用 Docker 方式搭建 Grafana Prometheus 实现对 DBLE 的 JVM 相关指标的监控系统。 作者:文韵涵 爱可生 DBLE 团队开发成员,主要负责 DBLE 需求开发,故障排查和社区问题解答。 本文来源:原创投稿 爱可生开源社区出品&a…...

下线40万辆,欧拉汽车推出2023款好猫尊荣型和GT木兰版
欧拉汽车是中国新能源汽车制造商,成立于2018年。截至目前,已经下线了40万辆整车,可见其在市场的影响力和生产实力。为了庆祝这一里程碑,欧拉汽车推出了品牌书《欧拉将爱进行到底》,在其中讲述了欧拉汽车的发展历程和未…...

【Python】使用python解析someip报文,以someip格式打印报文
文章目录 1.安装scapy库2.解析someip格式报文3.示例 1.安装scapy库 使用 pip 安装 scapy 第三方库,打开 cmd,输入以下命令: pip install scapy出现如图所示,表示安装成功: 2.解析someip格式报文 要解析someip格式报…...

C#与西门子PLC1500的ModbusTcp服务器通信2--ModbusTcp协议
Modbus TCP是近年来越来越流行的工业控制系统通信协议之一,与其他通信协议相比,Modbus TCP通信速度快、可靠性高、兼容性强、适用于模拟或数字量信号的传输,阅读本文前你必须比较熟悉Modbus协议,了解tcp网络。 一、什么是Modbus …...

SpringBoot + MyBatis-Plus构建树形结构的几种方式
1. 树形结构 树形结构,是指:数据元素之间的关系像一颗树的数据结构。由树根延伸出多个树杈 它具有以下特点: 每个节点都只有有限个子节点或无子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点&a…...

linux vscode 下开发
linux vscode 下开发 javajdk插件查看调用层次 java jdk 各种JAVA JDK的镜像分发 编程宝库 - 技术改变世界 jdk 镜像 ubuntu22.04 安装 # Linux x64 64位 jdk-8u351-linux-x64.tar.gztar -zxf jdk-8u351-linux-x64.tar.gz mv jdk1.8.0_351 jdk8/ vim ~/.pr…...

【工具】python代码编辑器--PyCharm下载安装和介绍
PyCharm是一种Python IDE(集成开发环境),由JetBrains打造。它带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试、语法高亮、项目管理、代码跳转、智能提示、自动完成、单元测试、版本控制等。此外,PyCharm还提供了一些高级功能,以用于支持Django框…...
SpringBoot第44讲:SpringBoot集成Redis - Redis分布式锁的实现之Jedis(setNXPX+Lua)
SpringBoot第44讲:SpringBoot集成Redis - Redis分布式锁的实现之Jedis(setNXPXLua) Redis实际使用场景最为常用的还有通过Redis实现分布式锁。本文是SpringBoot第44讲,主要介绍Redis实现分布式锁 文章目录 SpringBoot第44讲:SpringBoot集成Re…...

STM32F4X USART串口使用
STM32F4X USART串口使用 串口概念起始位波特率数据位停止位校验位串口间接线 STM32F4串口使用步骤GPIO引脚复用函数串口初始化函数串口例程 串口概念 串口是MCU与外部通信的重要通信接口,也是MCU在开发过程中的调试利器。串口通信有几个重要的参数,分别…...
python实现两个字符串比对差异点
一:代码实现 import difflib, re# 比较两个文本差异点 def compare_text_index(text1, text2):# 创建SequenceMatcher对象matcher = difflib.SequenceMatcher(a=text1, b=text2)# 获取差异报告diff_report = matcher.get_opcodes()# 检查差异报告中是否存在关键词错误for tag…...

SQLite数据库实现数据增删改查
当前文章介绍的设计的主要功能是利用 SQLite 数据库实现宠物投喂器上传数据的存储,并且支持数据的增删改查操作。其中,宠物投喂器上传的数据包括投喂间隔时间、水温、剩余重量等参数。 实现功能: 创建 SQLite 数据库表,用于存储宠…...

【Golang系统开发】搜索引擎(2) 压缩词典
写在前面 这篇文章我们就给出一系列的数据结构,使得词典能达到越来越高的压缩比。当然,和倒排索引记录表的大小相比,词典只占据了非常小的空间。那么为什么要对词典进行压缩呢? 这是因为决定信息检索系统的查询响应时间的一个重…...
clickhouse修改默认密码
1.明文密码 vim /etc/clickhouse-server/users.xml找到下面的语句,增加明文密码 <password>123456789</password> 2. sha256密码 # echo -n 123456789 | openssl dgst -sha256 (stdin) 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225 修改…...
基于java在线捐赠系统设计与实现
摘要 近年来,随着网络的快速发展,由于网络的开放性和便利性,具有广阔的发展前景。 本文设计并实现了医药捐赠系统。通过分析确定由两个不同的用户组成,每个用户具有不同的功能。它还可以帮助用户在线求助、申请项目、发表留言等&a…...

【前端】vscode javascript 代码片段失效问题解决
1. 文件--首选项--用户代码片段-vue.json : 添加 // { // // Place your global snippets here. Each snippet is defined under a snippet name and has a scope, prefix, body and // // description. Add comma separated ids of the languages where the snippet is app…...

AE-卡通人物解说动画视频的制作
目录 1.导入卡通人物图片和音频文件 2.新建合成 3.在卡通人物图片上添加效果和表达式 4.在音频文件上添加效果和表达式 5.将卡通人物中的 CC Split2 中分割1 表达式链接到滑块中 6.卡通人物根据音频文件自动匹配口型。 AE制作卡通人物解说视频,卡通人物口型根据…...
Linux 查看日志
在 Linux 中,内核日志使用 printk 函数进行输出。你可以通过以下方法查看 printk 的日志: 使用 dmesg 命令: dmesg 这个命令会显示内核环缓冲区中的日志消息,包括使用 printk 输出的消息。你可以通过滚动浏览输出来查看完整的日志…...

使用IO多路复用select完成TCP循环服务器接收客户端消息并打印
服务器 客户端 结果...

unity之Input.GetKeyDown与Input.GetKey区别
文章目录 Input.GetKeyDown与Input.GetKey区别 Input.GetKeyDown与Input.GetKey区别 Input.GetKey 和 Input.GetKeyDown 是 Unity 中用于检测按键状态的两个不同函数。它们之间的区别在于何时触发。 Input.GetKey(KeyCode key): 这个函数会在用户按住指定的键时触发࿰…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...

uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...