Codeforces Round #703 (Div. 2)个人总结

男娘i 2022-10-30 13:28 120阅读 0赞

A. Shifting Stacks  
[https://codeforces.com/contest/1486/problem/A][https_codeforces.com_contest_1486_problem_A]  
题意：  
有一个操作对于1<=i<n;  
if(a\[i\]>0)a\[i\]–,a\[i+1\]++;  
给你一个序列a\[\],长度为n,是否能够构成一个严格上升数组  
即：a\[i\]<a\[i+1\] (1<=i<n)  
思路：  
贪心、  
对于每一位至少为i-1;  
每次将第i位多的往后添加就行  
参考代码：

B. Eastern Exhibition  
[https://codeforces.com/contest/1486/problem/B][https_codeforces.com_contest_1486_problem_B]  
题意：  
二维平面给定n个点求到这n个点曼哈顿距离相等的点的数量；  
思路:  
假设点为（x,y) ;  
曼哈顿距离  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]  
可以对x轴y轴分开看  
对于给定一个序列a\[\],长度为n;求![在这里插入图片描述][20210219222216742.png]  
直接是结论中点；  
1.先给a【】从小到大排序  
2当n为奇数x取n的中间项  
3.当n为偶数中间两项之间  
![在这里插入图片描述][20210219223014952.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70 1]  
参考代码：

C  
[https://codeforces.com/contest/1486/problem/C2][https_codeforces.com_contest_1486_problem_C2]  
题意：  
交互题 二分 分块 分治，，，  
一般和分有关关键在思维具体二分什么这个题具体二分l~r 到第二大数的距离  
参考代码;

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <queue>
    #include <map>
    #include <climits>
    #include <cassert>
    #include<unordered_map>
    #define LL long long
    using namespace std;
    const int N = 2e5+10;
    int n;
    int a[N];
    int query(int l, int r)
    {
        
    	int tmp;
    	cout << "? " << l << " " << r << "\n";
    	fflush(stdout);
    	cin >> tmp;
    	return tmp;
    }
    void write(int x)
    {
        
    	cout << "! " << x << endl;
    }
    int main()
    {
        
    	cin >> n;
    	int key = query(1, n);
    	int l, r;
    	if (key == 1 || key == n)
    	{
        
    		if (key == 1)l = 2, r = n;
    		else l = 1, r = n - 1;
    	}
    	else
    	{
        
    		if (query(1, key) == key)l = 1, r = key - 1;
    		else l = key + 1, r = n;
    	}
    	if (l>key)
    	{
        
    		int res = l;
    		while (l <= r)
    		{
        
    			int mid = (l + r) / 2;
    			if (query(key, mid) == key)r = mid - 1, res = mid;
    			else l = mid + 1;
    		}
    		write(res);
    	}
    	else
    	{
        
    		int res = l;
    		while (l <= r)
    		{
        
    			int mid=(l + r) >> 1;
    			if (query(mid,key) == key)l = mid + 1, res = mid;
    			else r = mid - 1;
    		}
    		write(res);
    	}
    
    	return 0;
    
    }

D. Max Median  
[https://codeforces.com/contest/1486/problem/D][https_codeforces.com_contest_1486_problem_D]  
题意：  
1,.给你一个长度为n(1≤n≤2e5)的数组

要你求至少长度为k(1<=k<=n)的连续数组的中位数的最大值  
2.给定一个序列a\[\],长度为n;给定一个数k;  
定义一个  
Amedian in an array of length n, median=n/2取下界；  
For example: median(\[1,2,3,4)= 2, median(\[3,2,1\])= 2 , median(\[2,1,2,1\])= 1.  
要找出序列a\[\]中大于连续k段最大的median;  
思路：  
感觉是没一点思路  
数据小且median 具有二分性质  
在这就二分答案+前缀和技巧  
首先假设数组只有1和-1的元素

那么怎么判断这个答案为1还是-1

可以利用前缀和与前缀和的前缀的最小值

来计算答案是1还是-1

然后观察发现最终的答案可以二分

cek的时候大于等于这个值当作1，否则当作-1

参考代码：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <queue>
    #include <map>
    #include <climits>
    #include <cassert>
    #include<unordered_map>
    #define LL long long
    using namespace std;
    const int N = 2e5+10;
    int n, k;
    int a[N], pre_sum[N];
    bool cek(int x)
    {
        
    	for (int i = 1; i <= n; i++)
    		pre_sum[i] = pre_sum[i - 1] + (a[i] >= x ? 1 : -1);
    	int minv = 0;
    	for (int i = k,j=1; i <= n; i++,j++)
    	{
        
    		if (pre_sum[i] - minv > 0)return true;
    		minv = min(pre_sum[j], minv);
    	}
    	return false;
    }
    int main()
    {
        
    	cin >> n >> k;
    	int l = N, r = 1;
    	for (int i = 1; i <= n; i++)
    	{
        
    		cin >> a[i];
    		l = min(a[i], l);
    		r = max(a[i], r);
    	}
    	int res = l;
    	while (l <= r)
    	{
        
    		int mid = (l + r) >> 1;
    		if (cek(mid))l = mid + 1, res = mid;
    		else r = mid - 1;
    	}
    	printf("%d", res);
    	return 0;
    
    }

[https_codeforces.com_contest_1486_problem_A]: https://codeforces.com/contest/1486/problem/A
[https_codeforces.com_contest_1486_problem_B]: https://codeforces.com/contest/1486/problem/B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]: /images/20221024/ce66cfae40394f9bb98f528110fc90d4.png
[20210219222216742.png]: /images/20221024/cb18039a4e2849a89ece33c0cd764d2a.png
[20210219223014952.png]: /images/20221024/a06a70dff64b4f4c8f45857d9eeeb89a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70 1]: /images/20221024/f3e3c437ba83453e9de20e191eb5248b.png
[https_codeforces.com_contest_1486_problem_C2]: https://codeforces.com/contest/1486/problem/C2
[https_codeforces.com_contest_1486_problem_D]: https://codeforces.com/contest/1486/problem/D