数组中元素互不相同的判断(暴力以及Trie 优化)

news/2024/11/27 22:55:58/

题目:

代码(暴力)

o(n^4)

// 循环暴力 
#include<bits/stdc++.h>
using namespace std;const int N = 2e3+50;
int a[N][N];int main() {int n, m;cin >> m >> n;for(int i = 1; i <= m; i ++) {for(int j = 1; j <= n; j ++) {cin >> a[i][j];}}for(int i = 1; i <= m; i ++) {for(int j = 1; j <= n; j ++) {// 与(i,j) 同行比较for(int k = j+1; k<=n; k ++) {if(a[i][j]==a[i][k]) {puts("no");return 0;}} // i+1行 后面的for(int k = i+1; k<=m; k ++) {for(int p = 1; p<=n; p ++) {if(a[i][j]==a[k][p]) {puts("no");return 0;}}}}}puts("yes");return 0;
}

代码2(Trie树数据结构优化)

Trie树存起来,数值记数与路径.o(n^2)

#include<bits/stdc++.h>
using namespace std;const int M = 1e3, N = 1e3;
const int MAXN = M*N*30;int son[MAXN][2], idx; // 0 1 二进制编码
int cnt[MAXN];void insert(int x) {int p = 0;for(int i = 30; i >= 0; i --) {int &s = son[p][x>>i&1];if(!s) s = ++idx; p = s;}cnt[p]++;
}int main() {int m, n;cin >> m >> n;for(int i = 1; i <= m*n; i ++) {int x; cin >> x;insert(x);}for(int i = 1; i <= idx; i ++) {if(cnt[i]>1) {puts("no");return 0;}}puts("yes");return 0;
}


http://www.ppmy.cn/news/1550458.html

相关文章

【大语言模型】ACL2024论文-20 SCIMON:面向新颖性的科学启示机器优化

【大语言模型】ACL2024论文-20 SCIMON&#xff1a;面向新颖性的科学启示机器优化 目录 文章目录 【大语言模型】ACL2024论文-20 SCIMON&#xff1a;面向新颖性的科学启示机器优化目录摘要研究背景问题与挑战如何解决创新点算法模型实验效果推荐阅读指数&#xff1a;★★★★☆ …

(已解决)wps无法加载此加载项程序mathpage.wll

今天&#xff0c;在安装Mathtype的时候遇到了点问题&#xff0c;如图所示 尝试了网上的方法&#xff0c;将C:\Users\Liai_\AppData\Roaming\Microsoft\Word\STARTUP路径中的替换为32位的Mathtype加载项。但此时&#xff0c;word又出现了问题 后来知道了&#xff0c;这是因为64位…

2024“龙信杯“电子数据取证竞赛-服务器取证题目Writeup

服务器检材-分析 前置 提示&#xff1a;该服务器做了登录密码校验配置&#xff0c;如果没有拿到服务器的密码而直接仿真服务器&#xff0c;输入密码进入系统后&#xff0c;服务器会将部分数据给自动删除 前提&#xff1a;无 因为我们仿真进入服务器会自动删除文件&#xff0…

Spring Boot英语知识网站:开发与优化

5系统详细实现 5.1 管理员模块的实现 5.1.1 用户信息管理 英语知识应用网站的系统管理员可以对用户信息添加修改删除以及查询操作。具体界面的展示如图5.1所示。 图5.1 用户信息管理界面 5.1.2 在线学习管理 系统管理员可以对在线学习信息进行添加&#xff0c;修改&#xff0…

componentReceivePropsreact class生命周期

componentReceiveProps并不是有props的变化触发&#xff0c;而是由父组件的更新触发的 父组件导致组件重新渲染&#xff0c;即使props没有更改&#xff0c;也会调用componentReceiveProps这个方法&#xff1b;如果只想处理更改&#xff0c;确保当前值与变更值比较--官方 …

【5】STM32·FreeRTOS·临界段保护与调度器挂起

目录 一、临界段代码保护简介 二、临界段代码保护函数介绍 2.1、调用示例 2.2、内部实现 三、任务调度器的挂起和恢复 3.1、调用示例 3.2、内部实现 一、临界段代码保护简介 什么是临界段&#xff1a;临界段代码也叫做临界区&#xff0c;是指那些必须完整运行&#xff…

大连环保公益管理系统|Java|SSM|Vue| 前后端分离

【重要①】前后端源码万字文档部署文档 【重要②】正版源码有问题包售后 【包含内容】 【一】项目提供非常完整的源码注释 【二】相关技术栈文档 【三】源码讲解视频 【其它服务】 【一】可以提供远程部署安装&#xff0c;包扩环境 【…

哈希表理解与底层模拟实现

内容摘要 本文内容包括红黑树和哈希表的性能比较逻辑分析及实现、哈希表的概念、哈希表映射关系建立的最常用的两种方法直接地址法和除留余数法介绍、介绍了哈希冲突的原因以及解决解决哈希冲突的方法、负载因子的概念、哈希表的扩容、开散列实现哈希表的思路及代码实现、闭散列…