1475C Ball in Berland (思维)

系统管理员 2021-07-16 15:33 289阅读 0赞

[题目][Link 1]

思路：看N为2e5可知复杂度为O(n)或O(nlogn)，在这我用两个map分别记录每个男和女各自可以和多少匹配，首先选好一组匹配，那么还可以找出多少组匹配与之组成两组呢？答案为：k - 此组匹配中男生可以匹配女生数 - 此组匹配中女生可以匹配男生数+1（他们自身匹配那条线多匹配了一次）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 5e5 + 5;
    int Mod = 1e9 + 7;
    int lst[Max];
    int men[Max], women[Max];
    int main()
    { 
    	FAST;
    	int t;
    	cin >> t;
    	while (t--)
    	{ 
    		map<int, int> nan, nv;
    		int a, b, k;cin >> a >> b >> k;
    		for (int i = 1;i <= k;i++)
    		{ 
    			int j;cin >> j;
    			nan[j]++;
    			men[i] = j;
    		}
    		for (int i = 1;i <= k;i++)
    		{ 
    			int j;cin >> j;
    			nv[j]++;
    			women[i] = j;
    		}
    		ll ans = 0;
    		for (int i = 1;i <= k;i++)
    		{ 
    			ans += k - nan[men[i]] - nv[women[i]] + 1;
    		}
    		cout << ans/2 << endl;
    
    
    	}
    
    }

[Link 1]: https://codeforc.es/contest/1475/problem/C
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/d1320e0c2d3c43fe86ba82879f2d7b7e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，289人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Stack)1475. Final Prices With a Special Discount in a Shop

1.问题 You are given an integer array prices where prices\[i\] is the price of the ith

短命女/ 2023年09月25日 21:36/ 0 赞/ 98 阅读

相关 codeforces 25C. Roads in Berland

有n个城市，每个城市都能到达别的城市，n\n的矩阵表明i到j城市的最短距离，现在要建造一些新的道路，在两个城市之间。问每次建造这些道路之后每两个城市之间的距离之和为多少。如

旧城等待，/ 2022年08月03日 08:23/ 0 赞/ 26 阅读

相关 Color the ball

Color the ball Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K

清疚/ 2022年08月01日 12:15/ 0 赞/ 183 阅读

相关 Codeforces 25 D.Roads not only in Berland（并查集）

Description Berland Government decided to improve relations with neighboring countries.

柔光的暖阳◎/ 2022年06月13日 12:19/ 0 赞/ 167 阅读

相关 CodeForces - 723D - D. Lakes in Berland

-------------------- 题目连接：[http://codeforces.com/problemset/problem/723/D][http_codefor

蔚落/ 2022年06月12日 12:59/ 0 赞/ 160 阅读

相关 Color the ball

Problem Description： N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电

ゝ一世哀愁。/ 2022年05月29日 07:13/ 0 赞/ 211 阅读

相关 HDU 4811-Ball

> Ball > > Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Jav

怼烎@/ 2022年02月23日 03:38/ 0 赞/ 212 阅读

相关 C - Bouncing Ball

C - Bouncing Ball C. Bouncing Ball time limit per test 1 second memory l

小灰灰/ 2021年07月16日 23:28/ 0 赞/ 271 阅读

相关 1475C Ball in Berland (思维)

[题目][Link 1] 思路：看N为2e5可知复杂度为O(n)或O(nlogn)，在这我用两个map分别记录每个男和女各自可以和多少匹配，首先选好一组匹配，那么还可以找

系统管理员/ 2021年07月16日 15:33/ 0 赞/ 290 阅读

相关 B. Berland Crossword (构造)

[题目][Link 1] 对于下面这个图可以知道当U涂中间三个时是不会对其它的三种产生限制的，而如果涂了4个则必然会占到L R其中一个相邻的格子，涂了5个必然会占掉相邻的

男娘i/ 2021年07月16日 15:28/ 0 赞/ 301 阅读