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可以…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
如何配置一个sql server使得其它用户可以通过excel odbc获取数据
要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据,你需要完成以下配置步骤: ✅ 一、在 SQL Server 端配置(服务器设置) 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到:SQL Server 网络配…...
计算机系统结构复习-名词解释2
1.定向:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方,那么就可以避免停顿。 2.多级存储层次:由若干个采用不同实现技术的存储…...
从数据报表到决策大脑:AI重构电商决策链条
在传统电商运营中,决策链条往往止步于“数据报表层”:BI工具整合历史数据,生成滞后一周甚至更久的销售分析,运营团队凭经验预判需求。当爆款突然断货、促销库存积压时,企业才惊觉标准化BI的决策时差正成为增长瓶颈。 一…...
解密鸿蒙系统的隐私护城河:从权限动态管控到生物数据加密的全链路防护
摘要 本文以健康管理应用为例,展示鸿蒙系统如何通过细粒度权限控制、动态权限授予、数据隔离和加密存储四大核心机制,实现复杂场景下的用户隐私保护。我们将通过完整的权限请求流程和敏感数据处理代码,演示鸿蒙系统如何平衡功能需求与隐私安…...
SDU棋界精灵——硬件程序ESP32实现opus编码
一、 音频处理框架 该项目基于Espressif的音频处理框架构建,核心组件包括 ESP-ADF 和 ESP-SR,以下是完整的音频处理框架实现细节: 1.核心组件 (1) 音频前端处理 (AFE - Audio Front-End) main/components/audio_pipeline/afe_processor.c功能: 声学回声…...
leetcode 386. 字典序排数 中等
给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。 示例 1: 输入:n 13 输出:[1,10,11,12,13,2,3,4,5,6,7,8,9]示例 2: 输入:n 2…...
