当前位置: 首页 > 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...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践

在电商行业蓬勃发展的当下&#xff0c;多平台运营已成为众多商家的必然选择。然而&#xff0c;不同电商平台在商品数据接口方面存在差异&#xff0c;导致商家在跨平台运营时面临诸多挑战&#xff0c;如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...