AtCoder ABC198
本期F为群论题,很有难度。
C - Compass Walking
为了避免精度问题,采用二分推算。但是要小心结果为1的地方。
R 2 ∗ k 2 ≥ x 2 + y 2 R^2*k^2\geq x^2+y^2 R2∗k2≥x2+y2
# -*- coding: utf-8 -*-
# @time : 2023/6/2 13:30
# @file : atcoder.py
# @software : PyCharmimport bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)def main():items = sys.version.split()fp = open("in.txt") if items[0] == "3.10.6" else sys.stdinr, x, y = map(int, fp.readline().split())d = x ** 2 + y ** 2r = r ** 2# r^2 * k^2 >= d^2 (first k)lo, hi = 0, 100000001while lo < hi:mi = (lo + hi) >> 1if mi ** 2 * r >= d:hi = mielse:lo = mi + 1if hi == 1:if r != d:hi = 2print(hi)if __name__ == "__main__":main()
D - Send More Money
还不错的搜索题,硬做就好了。
一开始思路不好,半小时写了个搜索WA,
因为没有想到答案应该有long long类型。
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll inf = ll(1e15);
const ld pi = 3.1415926535897932384626;string sa, sb, sc;
int na, nb, nc, n;
bool vis[10];
int dig[256];
set<char> ss;
bool ac;
int ansa, ansb, ansc;void gene() {if (dig[sa[sa.size() - 1]] == 0 || dig[sb[sb.size() - 1]] == 0 || dig[sc[sc.size() - 1]] == 0){ac = 0;return;}for (int i = 0; i < sa.size(); ++ i) {char c = sa[sa.size() - 1 - i];ansa = ansa * 10 + dig[c];}for (int i = 0; i < sb.size(); ++ i) {char c = sb[sb.size() - 1 - i];ansb = ansb * 10 + dig[c];}for (int i = 0; i < sc.size(); ++ i) {char c = sc[sc.size() - 1 - i];ansc = ansc * 10 + dig[c];}
}void dfs(int pos, int row, int c) {if (pos == n) {if (c == 0) {ac = 1;gene();}return;}if (ac)return;if (row == 0) {int da = pos < na ? dig[sa[pos]] : 0;if (da == -1) {for (int i = 0; i < 10; ++i) {if (!vis[i]) {vis[i] = 1;dig[sa[pos]] = i;dfs(pos, row + 1, c + i);dig[sa[pos]] = -1;vis[i] = 0;}}}else {dfs(pos, row + 1, c + da);}}else if (row == 1) {int db = pos < nb ? dig[sb[pos]] : 0;if (db == -1) {for (int i = 0; i < 10; ++i) {if (!vis[i]) {vis[i] = 1;dig[sb[pos]] = i;dfs(pos, row + 1, c + i);dig[sb[pos]] = -1;vis[i] = 0;}}}else {dfs(pos, row + 1, c + db);}}else {int dc = pos < nc ? dig[sc[pos]] : 0;if (dc == -1) {int next_c = c / 10;dc = c % 10;if (!vis[dc]) {dig[sc[pos]] = dc;vis[dc] = 1;dfs(pos + 1, 0, next_c);vis[dc] = 0;dig[sc[pos]] = -1;}}else {int tc = c % 10, next_c = c / 10;if (tc == dc) {dfs(pos + 1, 0, next_c);}}}
}int main() {//freopen("in.txt", "r", stdin);cin >> sa >> sb >> sc;sa = string(sa.rbegin(), sa.rend());sb = string(sb.rbegin(), sb.rend());sc = string(sc.rbegin(), sc.rend());na = sa.length(), nb = sb.length(), nc = sc.length();n = max(max(na, nb), nc);memset(dig, 0xff, sizeof(dig));for (char x : sa)ss.insert(x);for (char x : sb)ss.insert(x);for (char x : sc)ss.insert(x);if (ss.size() > 10) {printf("UNSOLVABLE\n");return 0;}dfs(0, 0, 0);if (!ac) {printf("UNSOLVABLE\n");}else {printf("%d\n%d\n%d\n", ansa, ansb, ansc);}return 0;
}
后来看了题解,发现有简便的permutation做法。
p数组是每个字母代表的数字。
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll inf = ll(1e15);
const ld pi = 3.1415926535897932384626;string sa, sb, sc;
set<char> ss;int main() {//freopen("in.txt", "r", stdin);cin >> sa >> sb >> sc;for (char x : sa)ss.insert(x);for (char x : sb)ss.insert(x);for (char x : sc)ss.insert(x);if (ss.size() > 10) {printf("UNSOLVABLE\n");return 0;}vector<char> v(ss.begin(), ss.end());int mp[256] = { 0 };for (int i = 0; i < v.size(); ++i) {mp[v[i]] = i;}vi p;for (int i = 0; i < 10; ++i) p.push_back(i);do {bool ac = 1;ll a = 0, b = 0, c = 0;for (int i = 0; i < sa.size(); ++i) {a = a * 10 + p[mp[sa[i]]];if (i == 0 && p[mp[sa[i]]] == 0) ac = 0;}for (int i = 0; i < sb.size(); ++i) {b = b * 10 + p[mp[sb[i]]];if (i == 0 && p[mp[sb[i]]] == 0) ac = 0;}for (int i = 0; i < sc.size(); ++i) {c = c * 10 + p[mp[sc[i]]];if (i == 0 && p[mp[sc[i]]] == 0) ac = 0;}if (ac && a + b == c) {printf("%lld\n%lld\n%lld\n", a, b, c);return 0;}} while (next_permutation(p.begin(), p.end()));printf("UNSOLVABLE\n");return 0;
}
E - Unique Color
搜索
记录一个当前搜索到的颜色数量vis
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;int n;
int a[100020];
vi g[100020];
int vis[100020];
int ans = 0;
vi ansl;void dfs(int u, int fa) {if (vis[a[u]] == 0) {ansl.push_back(u);ans++;}vis[a[u]] ++;for (int v : g[u]) {if (v == fa) continue;dfs(v, u);}vis[a[u]] --;
}int main() {//freopen("in.txt", "r", stdin);scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}for (int i = 0; i < n - 1; ++i) {int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);//printf("%d\n", ans);sort(ansl.begin(), ansl.end());for (int x : ansl)printf("%d\n", x);return 0;
}
F - Cube
Polya定理,暂无
相关文章:
AtCoder ABC198
本期F为群论题,很有难度。 C - Compass Walking 为了避免精度问题,采用二分推算。但是要小心结果为1的地方。 R 2 ∗ k 2 ≥ x 2 y 2 R^2*k^2\geq x^2y^2 R2∗k2≥x2y2 # -*- coding: utf-8 -*- # time : 2023/6/2 13:30 # file : atcoder.…...
phpinfo和php -m 加载的php.ini不一致
目的: 将phpinfo在web中展示的php.ini和在命令行中展示的php.ini加载路径设置一致。 原本的php.ini加载路劲是: /usr/local/lib/php.ini 解决思路: (1)which php 查看服务器加载的php的位置,这里原来是&a…...
121.买卖股票的最佳时机 122.买卖股票的最佳时机II
121.买卖股票的最佳时机 122.买卖股票的最佳时机II 121.买卖股票的最佳时机 力扣题目链接(opens new window) 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一…...
Spring Boot整理-Spring Boot是什么?
Spring Boot 是一个开源的 Java 基础框架,它旨在简化基于 Spring 的应用开发。其核心特点在于“约定优于配置”的设计哲学,意味着它提供了一系列默认配置,从而帮助开发者更快地启动和运行新的 Spring 应用。Spring Boot 的主要特点包括: 自动配置:Spring Boot 可以根据项目…...
【pytorch】Pytorch 中的 grid 与 各种变换
Pytorch 中的 grid 与 各种变换 数学原理 **单应性(Homography) : 也就是透视变换。**单应性最初用来研究欧几里得几何中的透视和投影,而单应性一词,从词源学上来说,大致意思是“相似的绘图”。单应性的概念被引入来…...
【Linux】线程池实现
📗线程池实现(单例模式) 1️⃣线程池概念2️⃣线程池代码样例3️⃣部分问题与细节🔸类成员函数参数列表中隐含的this指针🔸单例模式🔸一个失误导致的bug 4️⃣调用线程池完成任务 1️⃣线程池概念 线程池是…...
使用Python批量上传本地maven库到nexus
背景:外包类项目开发时是调用的公司maven仓库进行开发,交付后需要将maven仓库转移到客户环境。 原理:1、打开idea运行源代码,将maven包下载到本地仓库, 2、下载包所在目录中执行脚本将本地仓库的maven包上传到客户nex…...
【Unity实战100例】Unity对Ini格式的配置文件管理和读写
目录 一.编写ini格式配置文件 二.读取解析ini文件 三.调用属性 INI 文件以文本形式存储,易于阅读和编辑。这种人可读的格式使得调整配置参数变得更加直观,不需要专门的工具。 INI 文件是一种轻量级的配置文件格式,不需要复杂的解析器或库。它的结构相对简单,适用于小到...
k8s存储卷和数据卷下
静态pv和pvc 运维负责pv:创建号持久化存储卷,申明好读写和挂载类型,以及可以提供的存储空间 Pvc开发做,要和开发沟通好,你期望的读写和挂载类型,以及存储空间 当我发布vc之后可以生成pv,还可以在…...
SQL Server 配置远程连接
Windows 安装好 SQL Server 的 SSMS,打开SSMS配置远程连接 找到 配置管理器 启用 TCP/IP 打开防火墙设置 新建入站规则 端口TCP - 特定本地端口 (1433)允许连接下一步名称完成 重启 SQL Server 服务...
vscode(visual studio code) 免密登陆服务器
1.生成密钥 首先,在本地,打开命令输入框: WinR–>弹出输入框,输入cmd,打开命令框。 然后,在命令框,输入 ssh-keygen -t rsa -C "love"按两次回车键,问你是否重写,选择…...
[redis] redis主从复制,哨兵模式和集群
一、redis的高可用 1.1 redis高可用的概念 在web服务器中,高可用是指服务器可以正常访问的时间,衡量的标准是在多长时间内可以提供正常服务(99.9%、99.99%、99.999%等等)。 高可用的计算公式是1-(宕机时间)/(宕机时…...
debian12部署Gitea服务
首先安装git、wget、sqlite,然后进行用户和组的相关设置 sudo apt install -y git wget sqlite3 新增一个git用户与一个git组 sudo adduser --system --group --disabled-password --shell /bin/bash --home /home/git --gecos Git Version Control git 给git用户设…...
js动态设置关键侦@keyframes
js动态设置关键侦keyframes 1.前置知识 关键侦keyframes规则通过在动画序列中定义关键侦的样式来控制CSS动画序列的中间步骤 keyframes slidein {from {transform: translateX(0%);}to {transform: translateX(100%);} } // from 等价于 0%;to 等价与 100% // 或…...
【WPF.NET开发】流文档
本文内容 什么是流文档?流文档类型创建流内容与流相关的类内容架构自定义文本 流文档旨在优化查看和可读性。 流文档根据运行时变量(例如,窗口大小、设备分辨率和可选的用户首选项)来动态调整和重新排列内容,而不是设…...
golang学习-结构体
1、定义 使用type 和struct 关键字来定义结构体,是值类型 格式如下: type 类型名 struct { 字段名 类型 字段名 类型 ... } 2、实例化 1、var 结构体实例 结构体类型 var p1 Person 2、使用new关键字 var p2 new(Person) 3、使用&对结构体…...
Python:enumerate() 函数
enumerate() 函数用于同时遍历索引和元素,常用于循环中。这个函数返回一个包含索引和元素的元组,可以通过解包的方式获取它们。 使用方法: enumerate(iterable, start0). iterable: 要遍历的可迭代对象。start: 索引起始值,默认…...
FPGA 移位运算与乘法
题目: 已知d为一个8位数,请在每个时钟周期分别输出该数乘1/3/7/8,并输出一个信号通知此时刻输入的d有效(d给出的信号的上升沿表示写入有效) 由题意可知: 复位信号高有效,低复位;在inpu_grant上升…...
网络安全B模块(笔记详解)- MYSQL信息收集
MYSQL信息收集 1.通过渗透机场景Kali中的渗透测试工具对服务器场景MySQL03进行服务信息扫描渗透测试(使用工具Nmap,使用必须要使用的参数),并将该操作显示结果中数据库版本信息作为Flag提交; Flag:MySQL 5.5.12 2.通过渗透机场景Kali中的渗透测试工具对服务器场景MySQL0…...
从JavaScript的角度上讲解一下xml
- XML(可扩展标记语言) XML(可扩展标记语言)是一种被设计用于存储和传输结构化数据的标记语言。它与HTML相似,但XML并没有预定义的标签,可以自定义标签及其属性。从JavaScript的角度来看,XML可以…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
