首页 > 其他分享 >Codeforces Round #831 (Div. 1 + Div. 2)

Codeforces Round #831 (Div. 1 + Div. 2)

时间:2022-11-23 16:37:38浏览次数:35  
标签:831 int ll Codeforces long ans Div 我们

C

核心思路:这个题目其实是一个规律题,它有一个很重要的前提,那就是在分配方案最优的情况下,要不然我们直接选几个差值最大的就ok,那他这句话,其实我们结合几个样例就知道,有一个必须得是紧挨另外一个的,也就是次大值。

所以我们可以先排好序,然后我们从前往后遍历下,在从后往前。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 10e9 + 7;
const int N = 1e7;
int primes[N], st[N], cnt;

void solve()
{

}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll n;
		cin >> n;
		vector<ll> a;
		for (int i = 0;i < n;i++)
		{
			int x;
			cin >> x;
			a.push_back(x);
		}
		sort(a.begin(), a.end());
		ll ans = 0;
		for (int i = 0;i < n - 2;i++)
		{
			ans = max(ans, a[i + 1] - a[i] + a[n - 1] - a[i]);
		}
		for (int i = n - 1;i >1;i--)
			ans = max(ans, a[i] - a[i - 1] + a[i] - a[0]);
		cout << ans << endl;
	}
}

D

核心思路:这个我们要读懂题意。然后模拟下就会发现只要我们有两个空位那么就肯定可以将棋子移动到指定位置,也就是我们整个棋盘的最大承载容量是n*m-4,因为(1,1)和(n,m)是已经固定了,如果要大于(不可以取等号)这个最大容量肯定就不可以。然后我们可以使用树状数组来维护这个棋子数目前缀和。

其实为什么可以使用这个我们可以注意a[i]的值正好对应\(1\sim n\),所以我们需要注意我们使用树状数组时,区间需要连续.不连续可以用离散化是其连续

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
ll n,m,k;
int a[N], ans[N], tr[N];
int lowbit(int x)
{
    return x & -x;
}
int ask(int x)
{
    int res = 0;
    for (int i = x;i;i -= lowbit(i))
        res += tr[i];
    return res;
}
void add(int x, int v)
{
    for (int i = x;i <= k;i += lowbit(i))//一定要注意这个地方是小于k,不要把模板背得太死了。这个是小于我们的数组容量.
        tr[i] += v;
}
void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) cin >> a[i], tr[i] = 0;
    bool flag = true;
    for (int i = 1; i <= k; i++) {
        if (ask(a[i]) >= n * m - 3) flag = false;
        add(a[i], 1);
    }
    if (flag) cout << "YA" << endl;
    else cout << "TIDAK" << endl;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

标签:831,int,ll,Codeforces,long,ans,Div,我们
From: https://www.cnblogs.com/xyh-hnust666/p/16918729.html

相关文章

  • Codeforces Round #790 (Div.4) A-H2题解
    原题链接:https://codeforces.com/contest/1676A.Lucky?题意:给定长度为6由数字组成的字符串问前三个数字的和是否等后三个数字的和。题解:直接相加比较即可。#include<......
  • Codeforces Round #835 (Div.4) A-G题解
    原题链接:https://codeforces.com/contest/1744A.MediumNumber题意:给定三个数,求中间那个数(倒数第二小or倒数第二大)。题解:直接用数组存,sort一下输出中间的数即可。#in......
  • Educational Codeforces Round 36 (Rated for Div. 2) E Physical Education Lessons
    PhysicalEducationLessons珂朵莉树模板#include<iostream>#include<cstdio>#include<set>usingnamespacestd;#defineItset<ran>::iteratorstructran{......
  • Codeforces Round #449 (Div. 1) C Willem, Chtholly and Seniorious
    Willem,ChthollyandSeniorious珂朵莉树慕名而来操作\(3\)直接排序是我没想到的,因为随机数据所以才能过吧\(split\)操作中忘了开\(longlong\),\(wa3\)#include<......
  • Codeforces Global Round 23 D
    D.PathsontheTree思考问题我们发现我们路径总是可以走到底的而不会中途中断而且对于每一个分叉点也就是每个儿子至少都会有当前还剩的k/儿子数取余剩下的我们可以......
  • Codeforces Round #835 (Div4)
    A.MediumNumber题意:输入三个不同的数字,输出中位数思路:没啥说的,比较一下大小即可代码:<bits/stdc++.h>usingnamespacestd;intmain(){int_;cin>>......
  • CodeForces - 320E Kalila and Dimna in the Logging Industry
    题意:你有要拿一把锯子砍树。锯子有有电和没电两个状态,只有在有电的时候才能工作,每次工作都可以砍1单位高度的树,然后就会没电。没电后要充电才能工作。充电有代价,代价为,当前......
  • Codeforces997A-Convert to Ones
    期末考炸完后重新开始做OI,先在Codeforces里面做一段时间锻炼一下思维,最近几篇都会写CF的文章,尽量把思维写得详细一点。题解:这题里面x,y的大小是很重要的。我们发现如果......
  • Codeforces Round #835 (Div. 4) A-G
    比赛链接A题意给出三个不同的数,求中位数。题解知识点:模拟。显然。时间复杂度\(O(1)\)空间复杂度\(O(1)\)代码#include<bits/stdc++.h>#definelllonglong......
  • Codeforces887C-Solution for Cube
    C.SolutionforCubetimelimitpertestmemorylimitpertestinputoutput......