首页 > 其他分享 >[题解](更新中)Refact.ai Match 1 (Codeforces Round 985)

[题解](更新中)Refact.ai Match 1 (Codeforces Round 985)

时间:2024-11-11 21:11:22浏览次数:1  
标签:std ai 题解 Codeforces cin int ge -- include

A - Set

显然答案是\(\max(\lfloor\frac{r}{k}\rfloor-l+1,0)\)。

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,l,r,k;
signed main(){
	cin>>t;
	while(t--){
		cin>>l>>r>>k;
		cout<<max(0ll,r/k-l+1)<<"\n";
	}
	return 0;
}

B - Replacement

我们发现只要\(0\)和\(1\)各存在至少\(1\)个,操作就能进行下去。所以\(r_i=1\)的操作可以看做删掉一个\(0\),\(r_i=0\)的操作则可以看做删掉一个\(1\)。

这样模拟就可以了,每次操作前如果剩余\(0,1\)的个数存在\(0\)则答案是NO

点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t,n;
string s,r;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>s>>r;
		int cnt0=0,cnt1=0;
		bool f=1;
		for(char i:s) (i=='0'?cnt0:cnt1)++;
		for(char i:r){
			if(!cnt0||!cnt1){
				f=0;
				break;
			}
			(i=='0'?cnt1:cnt0)--;
		}
		cout<<(f?"YES\n":"NO\n");
	}
	return 0;
}

另一种做法很简单,如果\(s[1,n]\)中\(1\)的个数减去\(r[1,n-2]\)中\(0\)的个数为\(1\),答案就是YES,否则NO。原理差不多,目的是让执行最后一次操作前,序列中恰好有一个\(0\)和一个\(1\)。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t,n;
string s,r;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>s>>r;
		r.pop_back();
		int cnts=0,cntr=0;
		for(int i:s) cnts+=(i=='1');
		for(int i:r) cntr+=(i=='0');
		if(cnts-cntr==1) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

C - New Rating

二分解法

考虑二分答案\(x\),转为判断“是否能让最终得分\(\ge x\)”。

用\(f[i]\)表示参加第\(i\)场比赛之后的得分;\(g[i]\)表示\(i\)这场比赛前可能的最小得分,使得最终得分\(\ge x\)。\(f\)可以通过模拟求出,\(g\)可以用下面的方法求得:

\[g[i]=\begin{cases} x&i=n\\ g[i+1]-1&i\le n,a[i]\ge g[i+1]\\ g[i+1]+1&i\le n,a[i]<g[i+1] \end{cases}\]

只要存在区间\(l\le r\),使得\(f[l-1]\ge g[r+1]\),则说明我们可以让最终得分\(\ge x\)。

时间复杂度\(O(n\log n)\)。

点击查看代码
#include<bits/stdc++.h>
#define N 300010
using namespace std;
int t,n,a[N],f[N];
bool check(int x){
	int g=x;
	for(int i=n;i>=1;i--){
		if(f[i-1]>=g) return 1;
		if(a[i]>=g) g--;
		else g++;
	}
	return 0;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		int cur=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]>cur) cur++;
			else if(a[i]<cur) cur--;
			f[i]=max(f[i-1],cur);
		}
		int l=0,r=n;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(check(mid)) l=mid;
			else r=mid-1;
		}
		cout<<l<<"\n";
	}
}

DP解法

\(f[i][j\in[0,2]]\)来表示考虑前\(i\)个比赛,第\(i\)场的状态是\(j\)的答案。其中\(j=0,1,2\)分别表示在跳过的比赛之前、属于跳过的比赛、在跳过的比赛之后。则

\[f[i][j]=\begin{cases} g(f[i-1][0],a[i])&j=0\\ \max(f[i-1][0],f[i-1][1])&j=1\\ \max(g(f[i-1][1],a[i]),g(f[i-1],a[i]))&j=2 \end{cases}\]

转移可以滚掉第\(1\)维。最终答案就是\(\max(f[n][1],f[n][2])\)。

时间复杂度\(O(n)\)。

点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 300010
using namespace std;
int t,n,a[N],f[3];
int g(int a,int b){return a+(b>a)-(b<a);}
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		f[0]=0,f[1]=f[2]=INT_MIN;
		for(int i=1;i<=n;i++){
			f[2]=max(g(f[1],a[i]),g(f[2],a[i]));
			f[1]=max(f[1],f[0]);
			f[0]=g(f[0],a[i]);
		}
		cout<<max(f[1],f[2])<<"\n";
	}
	return 0;
}

D - Cool Graph

标签:std,ai,题解,Codeforces,cin,int,ge,--,include
From: https://www.cnblogs.com/Sinktank/p/18537920

相关文章

  • 题解:P11262 [COTS 2018] 题日 Zapatak
    https://www.luogu.com.cn/article/i7ajvm8e哈希好题。题意给定一个序列,每次询问给定两个长度相等的区间,问这两个区间是否只有一个数不一样。思路发现我们要求的信息只与数的出现次数有关,自然想到桶。那么如果有两个区间合法,那这两个区间的桶只有两个位置不同且桶内的值均相......
  • gcc-13.2 grpc 编译错误(absl-cpp build fails)
    使用gcc-13.2编译absl-cpp会出现以下报错:third_party/abseil-cpp/absl/strings/internal/str_format/extension.h:34:6:warning:elaborated-type-specifierforascopedenummustnotusethe‘class’keyword  34|enumclassFormatConversionChar:uint8_t; ......
  • P8162 [JOI 2022 Final] 让我们赢得选举 (Let's Win the Election) 题解
    P8162[JOI2022Final]让我们赢得选举(Let'sWintheElection)题解朴素的想法是先抓一部分人,再一起去发表演讲。这样就要按\(b\)的值从小到大排序,枚举选择的一部分\(b\)值,在后面挑选一些最小的\(a\)选择即可。但这样显然是错误的。观察到\(n\le500\),显然是\(O(n^3......
  • Azure Availability Sets and Availability Zones
    InMicrosoftAzure,AvailabilitySetsandAvailabilityZonesarebothkeyfeaturesthatprovidehighavailabilityandfaulttoleranceforyourapplicationsandworkloads,buttheyareusedindifferentwaysandhavedifferentpurposes.Here'sabreak......
  • 平时有使用过AI服务吗——AI人工服务案例助力你了解底层代码逻辑!
    让我们详细说明这个智能客服系统包含的内容,并提供完整的代码示例。我们将涵盖以下几个方面:智能客服(使用Rasa)情感分析(使用HuggingFaceTransformers)自然语言生成(NLG)(使用HuggingFaceTransformers)语音识别(ASR)(使用SpeechRecognition)语音合成(TTS)(使用gTTS)用户行为分析(使用Pandas......
  • Educational Codeforces Round 158 (Rated for Div. 2) - VP记录
    A.LineTrip油量必须支持车子通过所有加油站间的空间,还要注意开回来的时候终点不能加油。点击查看代码#include<cstdio>#include<algorithm>usingnamespacestd;constintN=55;intn,x,a[N];intmain(){ intT;scanf("%d",&T); while(T--) { scanf("%d%d",&am......
  • 题解:P11062 【MX-X4-T2】「Jason-1」加法
    一道简单的分讨。思路可分成两种情况。当\(a\)和\(b\)同号时:这种情况,显而易见的是\(|a-b|\)的最小值必定是\(|a|,|b|,|a-b|\)之一。当\(a\)和\(b\)异号时:对\((a,b)\)执行欧几里得算法可以将一个变为\(0\),另一个变为\(\gcd(a,b)\)(忽略正负号)。再将\(0\)变......
  • 题解:P10967 [IOI2000] 邮局(原始版)
    思路首先将坐标排序。定义\(dp_{i,j}\)为前\(i\)个村庄放\(j\)个邮局的前\(i\)个村庄的最小距离总和,\(f(i,j)\)表示村庄区间\([i,j]\)内放一个村庄时该区间的总和。转化式易得\(dp_{i}{j}=dp_{k}{j-1}+f(k+1,i),k\in[0,i)\)。则本题的难点就为求\(f(k-1,i)\)。......
  • 题解:UVA1362 Exploring Pyramids
    思路:显然的,若不是叶子结点都应该至少遍历两次。于是两个相同访问之间就可能是一颗子树。更加具体的,如同\(s_l,\dots,s_k,\dots,s_r\),使得\(s_l=s_k\),那么就可以认为\(s[l,k]\)是\(s[l,r]\)的一颗子树,设区间\(s[l,r]\)的结构数量为\(f_{l,r}\),那么根据乘法原理,当把\(......
  • 241111 noip 题解
    省流:\(100+50+10+30\)。还是不稳定啊,noip上不了270就真的要退役了。T1题意:给定一个长度为\(n\)的序列\(a\),每次你可以交换相邻两个位置,求出最小交换次数以及字典序最小的交换方案使得\(a\)的每个不是本身的前缀都不是排列。\(n\leq10^5\)。注意到每次交换至多会减少一......