2021-01-25 cf #697 Div3 C题(超时,换思路减少复杂度)
2024-09-06 15:20:52
题目链接:https://codeforces.com/contest/1475/problem/C
题意要求:需组成的2对,男的序号不能重,女的序号不能重
比如这例
输入: |
行1--测试个数 行1` --男生个数p,女生个数q,成对数k 接下两行`--分别为这k对男女序号(上下为一对) |
1 |
输出: |
合法的组队对数 |
4 |
- (1,2) and (3,4);
- (1,3) and (2,2);
- (1,3) and (3,4);
- (2,2) and (3,4).
解析:
当时,题意明白的很快,但代码太暴力了,O(n^2)复杂度,而且n<=2e5,结果超时;
其实,这个不难想,每组寻找匹配的组时,只要分别去除了男女的重合序号,
但需注意的是:
- 每组寻找时,会把所有的选一遍,所以最后合法的组数需要/2;
- sum = sum + k - 男重 - 女重 + 1//最后+1是因为前面男重和女重都把自己减去了一遍,需要+1补齐;
上代码:
#include<iostream> using namespace std; typedef long long ll; const int N = 2e5 + 10; int main()
{
int t;
cin >> t;
while(t --)
{
int a1[N], b1[N];
int p, q, k, a[N], b[N]; for(int i = 0; i < N; i ++)//初始化
a1[i] = 0,b1[i] = 0; scanf("%d%d%d", &p , &q , &k);
for(int i = 0; i < k; i ++) scanf("%d", &a[i]), a1[a[i]] ++;
for(int i = 0; i < k; i ++) scanf("%d", &b[i]), b1[b[i]] ++; ll sum = 0;
for(int i = 0; i < k; i ++)
sum = sum + k - a1[a[i]] - b1[b[i]] + 1;
printf("%lld\n", sum/2);
}
return 0;
}
//相比而言,开始这个太傻了
// for(int i = 0; i < cou-1; i ++)
// for(int j = i+1; j < cou; j ++)
// if(a[i] != a[j] && b[i] != b[j])
// sum ++;
最新文章
- EntityFramework之监听者判断SQL性能指标
- jQuery静态方法parseJSON方法使用和源码分析
- 20145301&;20145321&;20145335实验五
- 【读书笔记】iOS网络-保护网络传输
- hadoop资料收集
- RMAN的恢复篇
- ML 02、监督学习
- Java 获取*.properties配置文件中的内容 ,常见的两种方法
- ZOJ 3810 Pretty Poem 分类: ACM 2015-05-17 14:40 83人阅读 评论(0) 收藏
- Pyhton 一行代码求Fibonacci第N项
- 1分钟快速生成用于网页内容提取的xslt
- Set无序怎么办?
- mysql 用户权限设置
- Oracle的instr函数
- 软工+C(2017第5期) 工具和结构化
- Nginx-keepalived+Nginx实现高可用集群
- 什么是HTML?HTML5是什么?HTML5有那些优势和特性?
- dbms_redefinition在线重定义表结构
- 常见的爬虫分析库(1)-Python3中Urllib库基本使用
- UE4 几个好用的插件和Wiki教程