首页 > 其他分享 >Codeforces Round 905 (Div

Codeforces Round 905 (Div

时间:2024-02-27 16:34:59浏览次数:21  
标签:arr 905 int scanf Codeforces 端点 cnt multiset Div

Codeforces Round 905 (Div. 3)

A. Morning

此题将其看为光标一直移动,其中移动次数就是坐标之差的绝对值,0看做10,由于其显示也需一次操作,所以加上四。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
	    int arr[4],count=0;
	    char k;
	    for(int i=0;i<4;i++)
	    {
		    cin>>k;
		    arr[i]=k-'0';
		    if(arr[i]==0)
		    {
		    	arr[i]=10;
			}
 	    }
 	    count=abs(arr[0]-1)+abs(arr[1]-arr[0])+abs(arr[2]-arr[1])+abs(arr[3]-arr[2])+4;
    	cout<<count<<endl;
	}
	return 0;
}

B. Chemistry

这道题读题出问题了,在删除后会重新排列这点没有读到,并且在测样例6打印了YES,当时一直想为什么不是NO,原来是会重新排列。所以这道题排列后就比较简单了,然后就统计字母出现次数为奇数的情况,分最后是奇数还是偶数就行。

    int t;
    scanf("%d",&t);
    while(t--)
    {
    	int n,k;
    	scanf("%d%d",&n,&k);
    	string s;
    	cin>>s;
    	int arr[26]={0};
    	for(int i=0;i<n;i++)
    	{
    		arr[s[i]-'a']++;
		}
		int count=0;
		for(int i=0;i<26;i++)
		{
			if(arr[i]%2==1)
			{
				count++;
			}
		}
		if((n-k)%2==0)
		{
			if((k-count)%2==0&&k>=count)
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
		else
		{
			if(k-count==1||n-k==1)
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
    }

C. Raspberries

注意到k的范围在2—5之间,那么只用分情况讨论即可,其中只有4需要讨论数组元素偶数个数(当k==4时num取最大也就2),其余情况要是有元素被k整除则直接为0,要是没有则需穷举每个元素被整除时增加了多少,取最小即可。

#include<iostream>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		int arr[n];
		for(int i=0;i<n;i++)
		{
			scanf("%d",&arr[i]);
		}
		int num=9;
		if(n!=1)
		{
			if(k!=4)
			{
				for(int i=0;i<n;i++)
				{
					if(arr[i]%k==0)
					{
						num=0;
						break;
					}
					else
					{
						num=min(num,(k-arr[i]%k));
				    }
			    }
			}
			else
			{
				int cnt=0,count=9,p;
				for(int i=0;i<n;i++)
				{
					if(arr[i]%4==0)
					{
						num=0;
						cnt=2;
						count=0;
						break;
					}
					if(arr[i]%2==0)
					{
						cnt++;
					}
					if(arr[i]%4==3)
					{
						count=1;
					}
				}
				num=max(0,2-cnt);
				num=min(num,count);
			}
		}
		else
		{
			if(arr[0]%k==0)
			{
				num=0;
			}
			else
			{
				num=k-arr[0]%k;
			}
		}
		printf("%d\n",num);
    }
    return 0;
}

D. In Love

这道题就是考察multiset的用法(刚学了set相关用法就写。。。题目直接写了multiset,大抵是暗示我吧,样例中也有多次添加同一段的),定义一个左端点,右端点的集合就行,最后只需判断右端点最小值是否小于左端点最大值,左端点multiset中的元素是按照从小到大的顺序排列的,其中的最大值就是最右侧的线段的右端点。同样,右端点multiset中的最小值就是最左侧的线段的左端点,当右端点multiset R中的最小值小于左端点multiset L中的最大值时,意味着存在一个右端点小于左端点的情况。找那个multiset的最大值最开始用的end一直不对,后面才查了end指向最后一个的下一个位置,用rbegin就行另外rend指向第一个元素的前一个(逆向迭代器)。

#include<bits/stdc++.h>
using namespace std;
multiset<int> L, R;
int main()
{
	int t;
	scanf("%d",&t);
	char k;
    int l, r;
	while(t--)
	{
        cin>>k>>l>>r;
        if(k == '+') L.insert(l), R.insert(r);
        else L.erase(L.find(l)), R.erase(R.find(r));
        if(L.size()!=0&& *R.begin() < *L.rbegin()) 
        printf("YES\n");
        else printf("NO\n");
	}
	return 0;
}

E. Look Back

这个题就是因为不能让他爆数据所以不能一直遍历使其一直增加,用一个cnt来记录上一个数被乘的次数然后后面再进行比较的时候只需让后一个数乘以2大于前一个数记录进行的次数加上cnt就是总共进行的次数,然后要是这个数比前一个数大那么久也可能要乘也可能不乘,就让它除以2和这个cnt!=0来判断最后加上就行。(再也不用cin和cout了,每次都会超时)

int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
	    scanf("%d",&n);
	    vector<long long> a(n);
	    for(int i = 0; i < n; i ++ ) 
		scanf("%lld",&a[i]);
	    long long cnt = 0, sum = 0;
	    for(int i = 1; i < n; i ++ ) 	
		{
	        int x = a[i];
	        if(x < a[i - 1]) {
	            while(x < a[i - 1]) x *= 2, cnt ++;
	        }
	        else {
	            while(x >= a[i - 1] * 2 && cnt!=0) x /= 2, cnt --;
	        }
	        sum += cnt;
    	}
    printf("%lld\n",sum);
	}

F. You Are So Beautiful

题意就是对于每个子序列(l,r),无法从a中按另一种顺序挑出r-l+1个数(可以不连续)构成这个子序列。一开始以为必须连续样例4怎么算都是8(,那么对于一段序列(l,r)合法,必须满足l左边没有al,ar右边没有ar所以对于一个序列al .... ar,只需要满足它的左端点al没在之前出现过,ar没在之后出现过即可。

标签:arr,905,int,scanf,Codeforces,端点,cnt,multiset,Div
From: https://www.cnblogs.com/godcy/p/18037156

相关文章

  • Codeforces Round 900 (Div
    CodeforcesRound900(Div.3)A.HowMuchDoesDaytonaCost?这个题简单,在子段上最常见的元素其实只要这个元素出现就行intt; cin>>t; intn,k; while(t--) { cin>>n>>k; intarr[n]; intout=0; for(inti=0;i<n;i++) { cin>>arr[i]; } for(......
  • Codeforces Round 888 (Div
    CodeforcesRound888(Div.3)A.EscalatorConversations推导即可,判断条件就是abs(h[i]-H)%k==0&&abs(h[i]-H)/k<m&&h[i]!=H,先要整除再能相隔abs(h[i]-H)/k个台阶谁高谁矮任意不影响,但是最后这个我就没注意到h[i]!=H小卡一会。#include<bits/stdc++.h>usingnamespacestd;......
  • Codeforces 1906L Palindromic Parentheses
    考虑先判定有无解对应的\(k\)的范围。首先若\(k=n\)一定无解,因为字符串开头是\(\texttt{(}\)结尾是\(\texttt{)}\)匹配不上。下界因为各有\(\frac{n}{2}\)个\(\texttt{()}\),所以可以先猜测下界就为\(\frac{n}{2}\)。考虑构造到这个下界。能发现只需要形如\(\te......
  • 如何计算两个正太分布的KL散度 —— 正太分布的KL散度 (Kullback-Leibler divergence)
    参考:https://blog.csdn.net/int_main_Roland/article/details/124650909给出实现代码:defget_kl():mean0,log_std0,std0=policy_net(Variable(states))mean1=Variable(mean0.data)log_std1=Variable(log_std0.data)std1......
  • Educational Codeforces Round 162 (Rated for Div. 2)
    Preface开学了没时间组队训练就抽空把之前欠下的CF补一补这场当时玩《拔作岛》上头了忘记有比赛了,等想起来的时候已经快结束了就没现场打赛后补题发现A~E都很简单,F的话一个地方没太想清看了题解才会A.MovingChips签到,找一个极小的且包含了所有\(1\)的区间,这个区间中\(0\)......
  • Codeforces 1451F Nullify The Matrix
    因为保证了这个路径必须是向下和向右,就可以考虑每一条\(i+j=x\)的斜线上的点,因为一条路径经过的点对应的\(i+j\)一定是每次\(+1\)的。考虑到因为对于同一条直线,每个点是独立的,因为一条路径至多经过这条直线上的一个点。于是可以考虑用\(\text{Nim}\)的思想把这条......
  • CF1923 Educational Codeforces Round 162 (Rated for Div. 2)
    C.FindB给出一个数组A,对于q个询问,每个询问给出[l,r],对于A的子数组[l,r],问是否存在一个相同大小的数组B,使得两个数组的和相同,且任意相同下标的元素不同?Solution:A中任意一个大于1的元素,可以把他变成1,多余的那部分给到其他位置的元素上(如最后一个)对于等于1的元素,把......
  • CF1932 Codeforces Round 927 (Div. 3)
    E.FinalCountdown我愿称之为今年最傻逼的一次,思路很快想出来了,但是实现一直搞不对观察发现答案是n的所有前i位数相加(如12345,那么ans=12345+1234+123+12+1)要证明的话就是按照题目的Note那样算,(以12345为例,ans=(12345-1234-123-12-1)+21234+2123+212+21)然后傻逼的事情......
  • 2024 蓝桥杯模拟赛3(div1+div2)
    P8834[传智杯#3决赛]序列\(O(N^2)\)枚举defread():returnmap(int,input().split())n,k=read()a=list(read())res=0foriinrange(n):forjinrange(i):ifa[i]*a[j]<=k:res+=1print(res)P8780[蓝桥杯2022省......
  • 2024 蓝桥杯模拟赛3(div1+div2)
    题目A.暴力枚举#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn,k;cin>>n>>k;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];......