AtCoder ABC197

news/2024/2/24 7:35:04/文章来源:https://blog.csdn.net/acrux1985/article/details/135636443

本期难度适中,比起前几期的FFT和网络流要容易一些,但是需要仔细思考

C - ORXOR

n=20,可以暴力
把数中间的隔板进行状态压缩枚举

# -*- 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 check(arr_list):ret = 0for arr in arr_list:temp = 0for x in arr:temp |= xret ^= tempreturn retdef main():items = sys.version.split()fp = open("in.txt") if items[0] == "3.10.6" else sys.stdinn = int(fp.readline())a = list(map(int, fp.readline().split()))ans = 1 << 60for mask in range(1 << n):b = []temp = []for i in range(n):temp.append(a[i])if (mask >> i) & 1:b.append(temp)temp = []if len(temp) > 0:b.append(temp)ans = min(ans, check(b))print(ans)if __name__ == "__main__":main()

D - Opposite

将坐标为 x , y x,y x,y的点逆时针旋转 θ \theta θ公式
[ x 1 y 1 ] = [ c o s θ − s i n θ s i n θ c o s θ ] [ x 0 y 0 ] \begin {bmatrix} x_1 \\ y_1 \end{bmatrix} = \begin {bmatrix} cos\theta &-sin\theta \\ sin\theta & cos\theta \end{bmatrix} \begin {bmatrix} x_0 \\ y_0 \end{bmatrix} [x1y1]=[cosθsinθsinθcosθ][x0y0]
其实就是欧拉公式在xy坐标系下的变形

#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;int n;int main() {//freopen("in.txt", "r", stdin);scanf("%d", &n);int x0, y0, xn, yn;scanf("%d%d%d%d", &x0, &y0, &xn, &yn);ld dx0, dy0, dxn, dyn;dx0 = x0, dy0 = y0, dxn = xn, dyn = yn;ld cx = (dx0 + dxn) / 2, cy = (dy0 + dyn) / 2;ld x = dx0 - cx, y = dy0 - cy;ld sinx = sin(2.0 * pi / n), cosx = cos(2.0 * pi / n);ld nx = x * cosx - y * sinx + cx, ny = x * sinx + y * cosx + cy;printf("%.8Lf %.8Lf\n", nx, ny);return 0;
}

E - Traveler

因为按照颜色顺序,每次必须取完每种颜色最小值与最大值 [ L , R ] [L,R] [L,R]之间的所有点,从 L L L或者 R R R进入下一种颜色
显然是个两端点dp的模型
设dp[i][0]是第i种颜色取完之后从L出去(最后一个点是L)的cost最小值,dp[i][1]是从R出去的最小值

#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<ll> vi;
const ll inf = ll(1e15);
const ld pi = 3.1415926535897932384626;int n;
vi balls[200020];
ll dp[200020][2];int main() {//freopen("in.txt", "r", stdin);scanf("%d", &n);for (int i = 0; i < n; ++i) {int x, c;scanf("%d%d", &x, &c);balls[c].push_back(x);}for (int i = 0; i <= n; ++i) {sort(balls[i].begin(), balls[i].end());}dp[0][0] = dp[0][1] = 0;balls[0] = { 0 };vi last = balls[0];for (int i = 1; i <= n; ++i) {if (balls[i].size() == 0) {dp[i][0] = dp[i - 1][0], dp[i][1] = dp[i - 1][1];}else {int m = balls[i].size(), lm = last.size();ll l0 = last[0], r0 = last[lm - 1], l1 = balls[i][0], r1 = balls[i][m - 1];dp[i][0] = min(abs(l0 - r1) + dp[i - 1][0], abs(r0 - r1) + dp[i - 1][1]) + r1 - l1;dp[i][1] = min(abs(l0 - l1) + dp[i - 1][0], abs(r0 - l1) + dp[i - 1][1]) + r1 - l1;last = balls[i];}}ll ans = min(abs(last[0]) + dp[n][0], abs(last[last.size() - 1]) + dp[n][1]);printf("%lld\n", ans);return 0;
}

F - Construct a Palindrome

把问题改成两边同时出发汇合。由于两边是从 ( 1 , n ) (1,n) (1,n)出发的,设当前的状态为 ( i , j ) (i,j) (i,j),从状态 ( i 0 , j 0 ) (i_0,j_0) (i0,j0)转移到 ( i 1 , j 1 ) (i_1,j_1) (i1,j1)需要满足边 i 0 i 1 i_0i_1 i0i1和边 j 0 j 1 j_0j_1 j0j1是相同字母。求到 ( t , t ) (t,t) (t,t)或者 ( s , t ) (s,t) (s,t)有边的最短路径。修改普通的bfs算法,在转移状态入队列的时候枚举字母即可。

#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;int n, m;
vi g[1002][26];
int f[1002][1002];
bool w[1002][1002];int main() {//freopen("in.txt", "r", stdin);cin >> n >> m;for (int i = 0; i < m; ++i) {int u, v;char c;cin >> u >> v >> c;int p = c - 'a';g[u][p].push_back(v);g[v][p].push_back(u);w[u][v] = w[v][u] = 1;}memset(f, 0xff, sizeof(f));f[1][n] = 0;int ans = 1 << 30;queue<pii> qu;qu.push({ 1, n });while (!qu.empty()) {pii c = qu.front();qu.pop();int u0 = c.first, u1 = c.second;if (u0 == u1) {if (f[u0][u1] * 2 <= ans - 1)ans = f[u0][u1] * 2;}if (w[u0][u1]) {ans = min(ans, f[u0][u1] * 2 + 1);}for (int p = 0; p < 26; ++p) {for (int v0 : g[u0][p]) {for (int v1 : g[u1][p]) {if (f[v0][v1] == -1) {f[v0][v1] = f[u0][u1] + 1;qu.push({ v0, v1 });}}}}}if (ans > 200000) ans = -1;printf("%d\n", ans);return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【ONE·MySQL || 常见的基本函数】

总言 主要内容&#xff1a;介绍了MySQL中常用的基本函数。一些聚合函数、时间日期函数、字符串函数、数字函数等。       文章目录 总言1、聚合函数1.1、汇总1.2、COUNT()函数1.2.1、基本说明1.2.2、使用演示 1.3、SUM( )函数1.3.1、基本说明1.3.2、使用演示 1.4、AVG( )函…

java基础知识点系列——数据输入(五)

java基础知识点系列——数据输入&#xff08;五&#xff09; 数据输入概述 Scanner使用步骤 &#xff08;1&#xff09;导包 import java.util.Scanner&#xff08;2&#xff09;创建对象 Scanner sc new Scanner(System.in)&#xff08;3&#xff09;接收数据 int i sc…

PHP开发日志 ━━ php8.3安装与使用组件Xdebug

今天开头写点历史&#xff1a; 二十年前流行asp&#xff0c;当时用vb整合常用函数库写了一个dll给asp调用&#xff0c;并在此基础上开发一套仿windows界面的后台管理系统&#xff1b;后来asp逐渐没落&#xff0c;于是在十多年前转投php&#xff0c;不久后用php写了一套mvc框架&…

C++——map和set的基本使用

目录 一&#xff0c;关联式容器 二&#xff0c;键值对 三&#xff0c;set的使用 3.1 set介绍 3.2 set的插入和删除 3.3 set的pair 3.4 multiset 四&#xff0c;map的使用 4.1 map介绍 4.2 map实现简易字典 4.3 map实现统计次数 4.4 map的[] 五&#xff0c;使用map或…

TRB 2024论文分享:基于生成对抗网络和Transformer模型的交通事件检测混合模型

TRB&#xff08;Transportation Research Board&#xff0c;美国交通研究委员会&#xff0c;简称TRB&#xff09;会议是交通研究领域知名度最高学术会议之一&#xff0c;近年来的参会人数已经超过了2万名&#xff0c;是参与人数和国家最多的学术盛会。TRB会议几乎涵盖了交通领域…

【REST2SQL】07 GO 操作 Mysql 数据库

【REST2SQL】01RDB关系型数据库REST初设计 【REST2SQL】02 GO连接Oracle数据库 【REST2SQL】03 GO读取JSON文件 【REST2SQL】04 REST2SQL第一版Oracle版实现 【REST2SQL】05 GO 操作 达梦 数据库 【REST2SQL】06 GO 跨包接口重构代码 MySQL是一个关系型数据库管理系统&#xf…

系统性学习vue-vue核心

做了三年前端,但很多系统性的知识没有学习 还是从头系统学习一遍吧 课程是b站的Vue2.0Vue3.0课程 后续还会学习的如下,就重新开一篇了,不然太长,之后放链接 vue组件化编程 vue-cli 脚手架 vue中的ajax vue-router vuex element-ui vue3 老师推荐的vscode针对vue的插件: Vue 3…

在线项目实习|2024寒假项目实战火热报名中!

一、在线实习项目分类 二、在线实习项目流程 三、在线实习项目优惠及项目特色 1、师傅带练教学模式&#xff0c;手把手教你掌握 采用“师带徒”的教学模式&#xff0c;课程以“项目前置知识学习 师傅带练 项目实战”贯穿&#xff0c;强调动手实操&#xff0c;内容以代码落地为…

mp4文件全部转换为mp3

问题 今天突发奇想&#xff0c;想把mp4视频转换为mp3来收听&#xff0c;于是想到了ffmpeg工具 步骤 安装ffmpeg环境 要在 Windows 上配置 FFmpeg 环境&#xff0c;你可以按照以下步骤进行操作&#xff1a; 下载 FFmpeg&#xff1a; 首先&#xff0c;你需要下载 FFmpeg 的 W…

图像处理:孤立点的检测

图像处理-孤立点的检测 孤立点的检测在图像处理中通常涉及到检测图像中的突变或者边缘&#xff0c;而使用二阶导数是一种常见的方法。一阶导数可以帮助找到图像中的边缘&#xff0c;而二阶导数则有助于检测边缘上的峰值&#xff0c;这些峰值可能对应于孤立点或者特殊的图像结构…

如何在30秒内学会使用pprof分析Go

假设下面的代码是你要分析的 Go 代码&#xff1a; package mainimport ("fmt""sync""time" )// 模拟耗时操作 func hardWork(wg *sync.WaitGroup) {defer wg.Done()fmt.Printf("Start: %v\n", time.Now())// 模拟耗内存a : []string{…

[开发语言][c++]:Static关键字和全局变量

Static关键字和全局变量 1. 生命周期、作用域和初始化时机2. 全局变量3. Static 关键字3.1 面向过程3.1.1 静态全局变量3.1.2 静态局部变量&#xff08;单例中会使用&#xff09;3.1.3 静态函数 3.2 面向对象3.2.1 类内静态成员变量3.2.2 类内静态成员函数 Reference 写在前面&…

伪装目标检测模型论文阅读之:Zoom in and out

论文链接&#xff1a;https://arxiv.org/abs/2203.02688 代码;https://github.com/lartpang/zoomnet 1.摘要 最近提出的遮挡对象检测&#xff08;COD&#xff09;试图分割视觉上与其周围环境融合的对象&#xff0c;这在现实场景中是非常复杂和困难的。除了与它们的背景具有高…

C语言中关于指针的理解及用法

关于指针意思的参考&#xff1a;https://baike.baidu.com/item/%e6%8c%87%e9%92%88/2878304 指针 指针变量 地址 野指针 野指针就是指针指向的位置是不可知的&#xff08;随机的&#xff0c;不正确的&#xff0c;没有明确限制的&#xff09; 以下是导致野指针的原因 1.指针…

力扣每日一练(24-1-13)

如果用列表生成式&#xff0c;可以满足输出的型式&#xff0c;但是不满足题意&#xff1a; nums[:] [i for i in nums if i ! val]return len(nums) 题意要求是&#xff1a; 你需要原地修改数组&#xff0c;并且只使用O(1)的额外空间。这意味着我们不能创建新的列表&#xff…

【java八股文】之Spring系列篇

【java八股文】之JVM基础篇-CSDN博客 【java八股文】之MYSQL基础篇-CSDN博客 【java八股文】之Redis基础篇-CSDN博客 【java八股文】之Spring系列篇-CSDN博客 【java八股文】之分布式系列篇-CSDN博客 【java八股文】之多线程篇-CSDN博客 【java八股文】之JVM基础篇-CSDN博…

ES6(ECMAScript 6.0)

ES6 学习链接ES6什么是ES6&#xff1f;ECMAScript 和 JavaScript 的关系 ECMAScript各版本新增特性ES6 块级作用域 let 学习链接 ES6简介 ECMAScript简介及特性&#xff08;科普&#xff01;很详细&#xff01;&#xff01;&#xff01;&#xff01;&#xff09; 20分钟上手ES…

OpenHarmony基于HDF简单驱动开发实例

OpenHarmony基于HDF简单驱动开发实例 背景 OpenHarmony-3.0-LTS qemu_small_system_demo liteos_a qemu 添加配置 device/qemu/arm_virt/liteos_a/hdf_config/device_info/device_info.hcs device_info 新增&#xff1a; sample_host :: host {hostName "sample…

Docker 配置国内镜像源加速

1. 国内镜像源总览 名称路径中国官方镜像https://registry.docker-cn.com网易163镜像http://hub-mirror.c.163.com中科大镜像https://docker.mirrors.ustc.edu.cn阿里云镜像https://[xxx].mirror.aliyuncs.com 2. 阿里云镜像源 地址&#xff1a;https://cr.console.aliyun.c…

基于Java SSM框架实现医院管理系统项目【项目源码】计算机毕业设计

基于java的SSM框架实现医院管理系统演示 SSM框架 当今流行的“SSM组合框架”是Spring SpringMVC MyBatis的缩写&#xff0c;受到很多的追捧&#xff0c;“组合SSM框架”是强强联手、各司其职、协调互补的团队精神。web项目的框架&#xff0c;通常更简单的数据源。Spring属于…