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

ABC 258 G Triangle(bitset 优化)

ABC 258 G Triangle(bitset 优化)

ABC 258 G Triangle

大意:给出一个邻接矩阵 ,用来记录两两元素间是否连接 , 计算其中三元环的数目。

思路:

不妨先想暴力解法

for(int i = 1 ; i <= n ; i ++){for(int j = i + 1 ; j <= n ; j ++){for(int k = j + 1 ; k <= n ; k ++){res += (a[i][j] && a[j][k] && a[k][i]);}}}

考虑 bitset 优化这个式子 , 可以仿照传递闭包的优化方式

优化成 if(a[i][j]) res += (a[i] & a[j]).count();

注意这样会重复计数 , 去重即可。

对于一个三元组 , 我们要求 第二维大于第一维 , 以 (1 , 2 , 3) 为例 , 会有 (1 , 2 , 3) (1 , 3 , 2) (2 , 3 , 1) 三种计数方式 , 也就是每个三元组重复记录了三次 , 除 3 即可。

时间复杂度  O ( n 3 w ) 时间复杂度~O(\frac{n^3}{w}) 时间复杂度 O(wn3)

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;bitset<N>bit[N];
int n , a[N][N];
string s;
signed main(){IOScin >> n;for(int i = 1 ; i <= n ; i ++){cin >> s;for(int j = 0 ; j < n ; j ++){if(s[j] == '0') a[i][j + 1] = 0;else a[i][j + 1] = bit[i][j + 1] = 1;}}int cnt = 0;for(int i = 1 ; i <= n ; i ++){for(int j = i + 1 ; j <= n ; j ++){if(a[i][j]) cnt += (bit[i] & bit[j]).count(); }}cout << cnt / 3 << "\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

相关文章:

ABC 258 G Triangle(bitset 优化)

ABC 258 G Triangle(bitset 优化) ABC 258 G Triangle 大意&#xff1a;给出一个邻接矩阵 &#xff0c;用来记录两两元素间是否连接 &#xff0c; 计算其中三元环的数目。 思路&#xff1a; 不妨先想暴力解法 for(int i 1 ; i < n ; i ){for(int j i 1 ; j < n ;…...

使用StreamLold写入 Starrocks报错:Caused by org

问题描述 使用StreamLoad写入Starrocks报错&#xff0c;报这个错误:Caused by: org.apache.http.ProtocolException: Content-Length header already present 代码案例 引入依赖 <!-- Starrocks使用StreamLoad发送Http请求 --><dependency><groupId>or…...

WX1860- ngbe-1.2.5 xdp程序在路由模式下,使用iperf工具测试数据包不转发,用jmeter可以

本地验证时重定向iperf包有出现calltrace错误&#xff0c;经推断&#xff0c;系统PAGE_SIZE<8k时可能出现&#xff08;getconf PAGE_SIZE指令可查看&#xff09;&#xff0c;按下图将ngbe_main.c的2350行ngbe_rx_bufsz改为ngbe_rx_pg_size可修复。其次&#xff0c;需要将加载…...

PHPStudy 安装tp8 php8.2.9 安装XDbug、redis扩展

一、PhpStudy升级PHP版本&#xff0c;安装PHP8.2操作步骤 1.1、官网下载最新的php版本 打开Windows版的官网下载&#xff0c;地址&#xff1a;https://windows.php.net/download/ 页面上有不同的PHP版本&#xff0c;这里我们下载的是64位nts版的PHP8.2.9。 1.2、解压下载的文…...

结构体指针和结构体数组指针

结构体指针和结构体数组指针是不同的类型。 结构体指针定义&#xff1a;Student *stu 结构体指针的步长是一个结构体的大小&#xff1b; 结构体数组指针定义&#xff1a;Student (*stu)[] 结构体数组指针的步长是整个结构体数组的大小。 例程&#xff1a; #include <stdio…...

libdrm全解析二十 —— 源码全解析(17)

接前一篇文章&#xff1a;libdrm全解析十九 —— 源码全解析&#xff08;16&#xff09; 本文参考以下博文&#xff1a; DRM 驱动程序开发&#xff08;VKMS&#xff09; 特此致谢&#xff01; 本文继续对include/drm/drm.h中实际功能宏定义进行讲解。 29. DRM_IOCTL_SET_MAS…...

基于docker搭建owncloud Harbor 构建镜像

环境介绍&#xff1a;ContenOS7.9 docker17.12.1-ce 使用mysql:5.7和 owncloud 镜像&#xff0c;构建一个个人网盘。 docker pull owncloud #拉取镜像 docker pull mysql5.7 创建容器 docker run --name owncloud-mysql -p 3306:3306 -e MYSQL\_ROOT\_PASSWORDroot …...

往Buildroot中增加Qt项目

前言 目的&#xff1a;应用开发时最初是没有和buildroot中一起编译时&#xff0c;后面应用程序写的差不多时&#xff0c;同事问我怎么把应用程序打包到文件系统中&#xff0c;然后发布时跟随文件系统一起发布&#xff0c;并且增加打包启动脚本。所以本文在已经可以单独编译的基…...

C#-Tolewer和ToUpper的使用

目录 简介: 好处:​ 过程: 总结&#xff1a; 简介: 字符串是不可变的&#xff0c;所以这些函数都不会直接改变字符串的内容&#xff0c;而是把修改后的字符串的值通过函数返回值的形式返回。 ToLower和ToUpper是字符串处理函数&#xff0c;用于将字符中的英文字母转换为小…...

RabbitMQ集群搭建和测试总结_亲测

RabbiMQ简介 RabbitMQ是用Erlang开发的&#xff0c;集群非常方便&#xff0c;因为Erlang天生就是一门分布式语言&#xff0c;但其本身并不支持负载均衡。 RabbitMQ模式 RabbitMQ模式大概分为以下三种: (1)单一模式。 (2)普通模式(默认的集群模式)。 (3)镜像模式(把需要的队列…...

SQLSTATE[IMSSP]: The active result for the query contains no fields.

我的是SQL server 报错场景&#xff0c;代码&#xff1a; $psendmx_sql"SET IDENTITY_INSERT PSENDMX ON;INSERT INTO psendmx (DJBH,MIBH,MXBH,SPDM,GG1DM,GG2DM,SL,SL_2,CKJ,ZK,DJ,DJ_1,JE,HH) VALUES {$mx_values};SET IDENTITY_INSERT PSENDMX OFF;"; $a$db_er…...

在Flutter应用内部实现分屏功能

前言 这一次被要求实现屏幕上同时展示两个页面&#xff0c;并且两个页面的逻辑&#xff0c;功能互不影响&#xff0c;通俗一点讲就是在Flutter内部实现一个类似于分屏的功能&#xff0c;这可难不倒我。 方法 要在 Flutter 中实现一个屏幕的上半部分和下半部分展示不同的页面…...

Docker常用操作命令(二)

Docker常用操作命令(二) 11、进入容器 docker exec -it 容器名称or容器ID /bin/bash [rootzch01 ~]# docker exec -it 973ff3caff19 /bin/bash 退出容器 root973ff3caff19:/# exit 12、查看容器中的进程 docker top 容器名称or容器ID [rootzch01 ~]# docker top 973ff3c…...

vue3 tailwindcss的使用

首先安装依赖&#xff1a; npm install -D tailwindcsslatest postcsslatest autoprefixerlatestnpm i -D unocss 然后vite.config.ts中 引入 import Unocss from unocss/viteexport default defineConfig({plugins: [Unocss(),],})终端执行&#xff1a; npx tailwindcss in…...

redis 基础篇(redis 理解)

目录 redis 特性介绍 redis 的一些特性&#xff08;优点&#xff09; 1. 在内存中存储数据 2. 可编程的 3. 可扩展 4. 持久化 5. 支持集群 6. 高可用 redis 的应用场景 数据库 作缓存 会话存储 作消息队列 redis 不适合做的事情 redis 介绍 redis 客户端形态 命…...

C++系列-函数重载

C系列-函数重载 函数重载函数重载的条件函数重载注意事项引用作为重载函数重载遇到默认参数 函数重载 函数名可以相同&#xff0c; 提高复用性 函数重载的条件 同一个作用域下函数名相同函数参数不同 – 参数个数不同 – 参数顺序不同 – 参数类型不同不可以使用返回值作为重…...

leetcode-23.合并k个升序链表-day17

...

Linux scp命令

scp 是 secure copy 的缩写, scp 是 linux 系统下基于 ssh 登陆进行安全的远程文件拷贝命令。 scp 是加密的&#xff0c;rcp 是不加密的&#xff0c;scp 是 rcp 的加强版。 scp [可选参数] file_source file_target 参数说明&#xff1a; -1&#xff1a; 强制scp命令使用协议ss…...

vue 简单实验 v-bind 变量与html属性绑定

1.代码 <script src"https://unpkg.com/vuenext" rel"external nofollow" ></script> <div id"bind-attribute"><span v-bind:title"message">鼠标悬停几秒钟查看此处动态绑定的提示信息&#xff01;</sp…...

114.(cesium篇)cesium去掉时间轴并用按钮控制运动

地图之家总目录(订阅之前必须详细了解该博客) 完整代码工程包下载,运行如有问题,可“私信”博主。效果如下所示: cesium去掉时间轴并用按钮控制运动 下面献上完整代码,代码重要位置会做相应解释 <html lang...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 &#xff08;1&#xff09;确定回溯算法函数的参数和返回值&#xff08;一般是void类型&#xff09; &#xff08;2&#xff09;因为是用递归实现的&#xff0c;所以我们要确定终止条件 &#xff08;3&#xff09;单层搜索逻辑 二…...

React父子组件通信:Props怎么用?如何从父组件向子组件传递数据?

系列回顾&#xff1a; 在上一篇《React核心概念&#xff1a;State是什么&#xff1f;》中&#xff0c;我们学习了如何使用useState让一个组件拥有自己的内部数据&#xff08;State&#xff09;&#xff0c;并通过一个计数器案例&#xff0c;实现了组件的自我更新。这很棒&#…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战

🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...