首页 > 其他分享 >Codeforces Round #809 (Div. 2)

Codeforces Round #809 (Div. 2)

时间:2023-01-12 20:56:04浏览次数:60  
标签:return NO int Codeforces long 809 Div define

题目链接

A

核心思路

就是一个简单的模拟,没什么好说的,居然做了我十五分钟。还是太菜了。

// Problem: A. Another String Minimization Problem
// Contest: Codeforces - Codeforces Round #809 (Div. 2)
// URL: https://codeforces.com/contest/1706/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 
const int N=1e5+10;

int a[N];
int ans[N],vis[N];

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	cin>>a[i];
	memset(ans,0,sizeof ans);
	for(int i=0;i<n;i++)
	{
		int b=a[i];
		int c=m+1-a[i];
		int maxn=max(b,c);
		int minn=min(b,c);
		if(!ans[minn])
		ans[minn]=1;
		else
		ans[maxn]=1;
	
	
	}
	for(int i=1;i<=m;i++)
	{
		if(ans[i]==1)
		cout<<"A";
		else
		cout<<"B";
	}
	cout<<endl;
}

signed  main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

B

核心思路

读题目读了半天,唉,太菜了。

b题其实就是需要挖掘出来一个简单的性质,不会很难的。模拟两组样例后可以发现只要两个相同的数坐标之差是一个奇数,那么就一定可以加到答案里面去,因为可以转个弯到时候。所以我们只需要开一个pre数组记录之前的坐标就好了。

这个怎么记录前面的值的表示当时居然没有想到,引以为戒。

// Problem: B. Making Towers
// Contest: Codeforces - Codeforces Round #809 (Div. 2)
// URL: https://codeforces.com/contest/1706/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 
const int N=1e5+10;
int a[N],vis[N];
int ans[N],pre[N];
void solve()
{
	map<int,int> mp;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	memset(ans,0,sizeof ans);
	memset(pre,0,sizeof pre);
	for(int i=1;i<=n;i++)
	{
		if(!pre[a[i]]||(i-pre[a[i]])%2)
		ans[a[i]]++,pre[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	cout<<ans[i]<<" ";
	cout<<endl;
	
}

signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

C

核心思路

首先题目要求我们cool楼房最大,但是最大也只可以是(n-1)/2(向下取整).然后我们可以想到这个cool楼房怎么安放呢,很显然只能放在偶数的位置。

那么这个时候我们就需要对n分类讨论:

  • n为奇数,我们只需要把所有偶数位置的楼房变为cool就好了。
  • n为偶数,这个我们就需要注意了,因为我们的第一个和最后一个是不可以变为cool的。所以我们可以先模拟下样例看还可不可以发现一个性质,010010,所以我们可以发现肯定是会有两个不是cool是相邻的,所以我们找出这个找出来这个分界点就好了。然后从前往后求sum,然后从后往前求下就好了。
// Problem: C. Qpwoeirut And The City
// Contest: Codeforces - Codeforces Round #809 (Div. 2)
// URL: https://codeforces.com/contest/1706/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 
const int N=1e5+10;
int INF=1e18;
int a[N],s[N],p[N];
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	memset(s,0,sizeof s);
	memset(p,0,sizeof p);
	s[0]=s[n+1]=p[0]=p[n+1]=0;
	for(int i=2;i<=n-1;i+=2)
	{
		int maxv=max(a[i-1],a[i+1]);
		s[i]+=max(1ll*0,1ll*maxv+1-a[i]);
	}
	for(int i=n-1;i>=2;i-=2)
	{
		int maxv=max(a[i-1],a[i+1]);
		p[i]+=max(1ll*0,1ll*maxv+1-a[i]);
	}
	for(int i=1;i<=n;i++)
	s[i]+=s[i-1];
	for(int i=n;i>=1;i--)
	p[i]+=p[i+1];
	if(n&1)
	{
		cout<<s[n-1]<<endl;
		return;
	}
	int res=INF;

		for(int i=1;i<=n;i++)
		res=min(res,s[i]+p[i+1]);

	cout<<res<<endl;
	
}



signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

D

核心思路

首先我们可以确定下maxv的范围,因为我们整个数组a数单调不下降的。所以m的范围就是:\([\frac{a[n]}{k},a[n]]\).

然后怎么求最小值呢,因为我们需要的是最大值和最小值的差值最小。所以我们的最小值应该是第一个小于maxv的数。这里我们注意下check的用法就好了,因为我们那个数是有限制的是\(a_i/p_i\).

这个代码还是有不少细节的,有一些剪枝的东西,比如从大到小枚举减低时间复杂度。

// Problem: C. Qpwoeirut And The City
// Contest: Codeforces - Codeforces Round #809 (Div. 2)
// URL: https://codeforces.com/contest/1706/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 
const int N=1e5+10;
int INF=1e18;
int n,m;
int a[N],k;
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	if(k>a[n])
	{
		cout<<0<<endl;
		return;
	}
	int res=1e9;
	for(int maxv=a[n]/k;maxv<=a[n];maxv++)
	{
		int minv=INF;
		bool flag=true;
		for(int j=n;j>=1;j--)
		{
			if(a[j]/k>maxv)//因为最大值已经确定了。
			{
				flag=false;
				break;
			}
			int l=1,r=k;
			while(l<r)//一定要注意的这里是除啊,所以我们如果l=mid是会更加远离我们的边界.
			{
				int mid=l+r>>1;
				if(a[j]/mid<=maxv)
				r=mid;
				else
				l=mid+1;
			}
			minv=min(minv,a[j]/r);
			
		}
		if(flag)
		res=min(res,maxv-minv);
	}
	cout<<res<<endl;
	
}



signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

标签:return,NO,int,Codeforces,long,809,Div,define
From: https://www.cnblogs.com/xyh-hnust666/p/17047887.html

相关文章

  • Codeforces Round #763 (Div. 2)C
    CodeforcesRound#763(Div.2)C这个D实在是不会,只能先补了CCC这个题是我们可以选择从3到n我们可以选择一个d(d>=0&&d<=ai/3),可以把2d给ai-2,那么ai-2+=2d,把d给ai-......
  • CodeForces 1733E Conveyor
    洛谷传送门CodeForces传送门考虑差分,如果\(t-1\)时刻经过\((x,y)\)的史莱姆个数等于\(t\)时刻经过\((x,y)\)的史莱姆个数,答案为NO,否则为YES。发现两只史莱姆......
  • UVA10256 The Great Divide
    洛谷传送门UVA传送门考虑对两个点集求出凸包,显然如果这两个凸包相离就合法,然后问题就转化成了这两个凸包是否有交。设红点凸包包围的点集为\(A\),蓝点凸包包围的点集为......
  • 视频直播APP源码,通过css控制div内容展开更多/收起效果
    视频直播APP源码,通过css控制div内容展开更多/收起效果一.实现思路1.需要设置一个变量控制展开/收起效果2.提前写好最高高度的class样式,超出这个高度多余内容会隐藏......
  • Codeforces Round #843 (Div. 2)(B,C,D,E)
    CodeforcesRound#843(Div.2)(B,C,D,E)23年的第一场比赛(现场的),结果还是只是做出了两个题B想起这道题就好笑,我又又又看错题了,这个题里面讲的一直是或,我在比赛全程都以为是......
  • Codeforces Round #843 (Div. 2)ACE 补D
    A.GardenerandtheCapybaras题意:给定一个由ab串,将该字符串拆分成3个部分,使中间部分的字典序最大或者最小。分析:考虑简单的最小情况:中间只有一个a,两边总会\(......
  • Codeforces Edu Round 106 Div2
    解题A.DominoonWindowsill这个题给一个2xn的方格,一个行有k1个白块,第二行有k2个白块,那么现在有w个2x1的白块和b个2x1黑块,白对白,黑对黑,问能不能全放下这个就是判断下白......
  • 818 Div 2.F. Madoka and The First Session
    Problem-F-Codeforces818Div2.F.MadokaandTheFirstSession思路:不妨转化一下题意:将条件转化为:\(b_v+1,b_v+1\),然后使得其中一个-2那么在\(a\)上就是使\(a_......
  • [Codeforces Round #822 (Div. 2)](https://codeforces.com/contest/1734)
    CodeforcesRound#822(Div.2)ProblemF.ZerosandOnes解法定义:\(f(x)\)为在\(S\)串中位置为\(x\)的值。显然\(f(x)\in0,1\)有一重要性质:若\(f(x)\)为1,那么二进制......
  • Codeforces Round #843 (Div. 2)
    Preface难得的7点场CF,结果反而遇上了我最困的时候(吃完晚饭血糖上来就贼困,我一般反而凌晨场比较清醒)但是这场表现还可以,写的题基本都是一发入魂而且速度也比较快比较可惜......