题目链接:https://codeforces.com/contest/1475/problem/C

题意要求:需组成的2对,男的序号不能重,女的序号不能重

比如这例

输入:

  行1--测试个数

  行1` --男生个数p,女生个数q,成对数k

  接下两行`--分别为这k对男女序号(上下为一对)

1
3 4 4
1 1 2 3
2 3 2 4
输出:
合法的组队对数

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,结果超时;

其实,这个不难想,每组寻找匹配的组时,只要分别去除了男女的重合序号,

但需注意的是:

  1. 每组寻找时,会把所有的选一遍,所以最后合法的组数需要/2;
  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 ++;


最新文章

  1. EntityFramework之监听者判断SQL性能指标
  2. jQuery静态方法parseJSON方法使用和源码分析
  3. 20145301&amp;20145321&amp;20145335实验五
  4. 【读书笔记】iOS网络-保护网络传输
  5. hadoop资料收集
  6. RMAN的恢复篇
  7. ML 02、监督学习
  8. Java 获取*.properties配置文件中的内容 ,常见的两种方法
  9. ZOJ 3810 Pretty Poem 分类: ACM 2015-05-17 14:40 83人阅读 评论(0) 收藏
  10. Pyhton 一行代码求Fibonacci第N项
  11. 1分钟快速生成用于网页内容提取的xslt
  12. Set无序怎么办?
  13. mysql 用户权限设置
  14. Oracle的instr函数
  15. 软工+C(2017第5期) 工具和结构化
  16. Nginx-keepalived+Nginx实现高可用集群
  17. 什么是HTML?HTML5是什么?HTML5有那些优势和特性?
  18. dbms_redefinition在线重定义表结构
  19. 常见的爬虫分析库(1)-Python3中Urllib库基本使用
  20. UE4 几个好用的插件和Wiki教程

热门文章

  1. JavaWeb——Http
  2. 域环境SID相同如何解决
  3. linux 下载源
  4. docker学习笔记(4)- 应用数据管理(容器外)
  5. P2P图书馆实践:让知识更好的传播
  6. 使用 rabbitmq 的场景?
  7. java线程池源码分析
  8. Spring 配置文件 ?
  9. 使用jquery
  10. nginx优化的一些建议