首页 > 其他分享 >CF933-Div3 大致思路+题解

CF933-Div3 大致思路+题解

时间：2024-03-18 11:13:22浏览次数：15  
标签：ch int 题解 long -- qr CF933 Div3 getchar

A - Rudolf and the Ticket

纯水题 暴力枚举直接过

$code$ 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=200005;
const int maxx=INT_MAX;
int T,n,m,k;
int b[N],c[N];
int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	cin>>T;
	while(T--)
	{
		cin>>n>>m>>k;
		int cnt=0;
		for(int i=1;i<=n;i++)
			cin>>b[i];
		for(int i=1;i<=m;i++)
			cin>>c[i];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(b[i]+c[j]<=k)
					cnt++;
		printf("%d\n",cnt);
	}
	return Ratio;
}

B - Rudolf and 121

题目中要求的是变换\(i\)同时修改两边的值

换个角度就是变换\(i-1\)的同时修改\(i\)和\(i+1\)

过一遍循环 当出现$a[i] $$<$$0$时标记并直接退出循环

输出\(YES\)的条件是没有标记并且\(a[n-1]\)和\(a[n]\)均为\(0\)

$code$ 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=200005;
const int maxx=INT_MAX;
int n;
int a[N];
int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	int T=qr;
    while(T--)
    {
        n=qr;
        fo(i,1,n)
            a[i]=qr;
        bool fla=true;
        fo(i,1,n-2)
        {
            if(a[i]<0)
            {
                fla=false;
                break;
            }
            a[i+1]-=2*a[i];
            a[i+2]-=a[i];
            a[i]=0;
        }
        if(fla==true&&a[n-1]==0&&a[n]==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
	return Ratio;
}

C - Rudolf and the Ugly String

字符串！噔咚噔

还是较为简单的 毕竟是\(c\)题

简单观察后就能发现要求的字符串\(map\)和\(pie\)唯一结合的方式是变成\(mapie\) 不会出现重叠和套娃的情况

因此我们选用方便的\(substr\)来判定以下情况：

  1. 若前方存在\(mapie\) 则答案++ 同时向右走\(5\)位

  2. 其次 若前方存在\(map\)或\(pie\) 答案++ 同时向右走\(3\)位

  3. 否则 向右走\(1\)位

$code$ 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=200005;
const int maxx=INT_MAX;
int n,cnt;
string s;
int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	int T=qr;
    while(T--)
    {
        n=qr;
        cin>>s;
        cnt=0;
        int i=0;
        while(i<n)
        {
			if(i+5<=n&&s.substr(i,5)=="mapie")
                cnt++,i+=5;
			else if(i+3<=n&&s.substr(i,3)=="map")
                cnt++,i+=3;
			else if(i+3<=n&&s.substr(i,3)=="pie")
                cnt++,i+=3;
			else 
                i++;
		}
        printf("%d\n",cnt);
    }
	return Ratio;
}

D - Rudolf and the Ball Game

一眼转圈问题 这道题难在有个"\(?\)" 直接暴力\(dfs\)会在第\(3\)个测试点\(T\)掉

接下来 请出本场\(MVP\) ：\(set！\)

众所周知（其实我\(T\)了好久才想起来 \(set\)的特性是维护一个严格单调递增的数列 但本题选用它的原因主要在 它会自动删除重复的元素！

因此 在这道可能性很多且易重复的题里面 \(set\)成为了比剪枝\(dfs\)更好的选择

学习\(set\)请自行跳转\(cppreference\)和\(CSDN\)

$code$ 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=200005;
const int maxx=INT_MAX;
int n,m,x;
int dis;
char c;
int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	int T=qr;
    while(T--)
    {
        n=qr,m=qr,x=qr;
        set<int>dh,yy;
        dh.insert(x-1);
        fo(i,1,m)
        {
            dis=qr;
            cin>>c;
            if(c=='0')
                for(auto i:dh)
                    yy.insert((dis+i)%n);
            else if(c=='1')
                for(auto i:dh)
                    yy.insert((i+n-dis)%n);
            else if(c=='?')
                for(auto i:dh)
                {
                    yy.insert((dis+i)%n);
                    yy.insert((i+n-dis)%n);
                }
            dh=yy;
            yy.clear();
        }
        printf("%d\n",dh.size());
        for(auto i:dh)
            printf("%d ",i+1);
        printf("\n");
    }
	return Ratio;
}

E - Rudolf and k Bridges

一眼\(dp\) 关于它感觉不需要特别说明

首先 在输入桥时直接求出每一行的最优值

然后直接一个\(for\)找\(k\)个连续的较小值作答案即可

记得开\(long long\)！！！

插叙

第一遍

const int maxx=INT_MAX;

第二遍

"哦 不对 是long long"

const int maxx=1e18;

第三遍

const ll maxx=1e18..

乐

$code$ 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=200005;
const ll maxx=1e18;
int n,m,k,d;
int dh[N];
ll dp[N],cost[N];
int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	int T=qr;
    while(T--)
    {
        n=qr,m=qr,k=qr,d=qr;
        fo(k,1,n)
        {
            fo(i,1,m)
                dh[i]=qr,dp[i]=maxx;
			deque<pair<ll,ll> >q;//钱 位置
			dp[1]=1;
			q.push_back(make_pair(1,1));
			for(int i=2;i<=m;i++){
				dp[i]=min(dp[i],q.front().first+dh[i]+1);
				while(!q.empty()&&dp[i]<=q.back().first)
                    q.pop_back();
				q.push_back(make_pair(dp[i],i));
				if(i-d>q.front().second)
                    q.pop_front();
			}
			// cout<<dp[m]<<endl;
            cost[k]=dp[m];
			// cost[k]=cost[k-1]+dp[m];
            // cout<<cost[k]<<"||||||||"<<endl;
        }
        ll ans=maxx;
        fo(i,1,n-k+1)
        {
            ll res=0;
            fo(j,i,i+k-1)
                res+=cost[j];
            ans=min(ans,res);
        }
        printf("%lld\n",ans);
    }
	return Ratio;
}

F - Rudolf and Imbalance

\(MVP\)再次登场

严格单增 完美契合\(set\)

一开始直接找初始\(a[N]\)中最大差和次大差

然后对最大差进行操作 用给的\(f\)和\(d\)操作将它分成两个尽量大的差 因为这样才能保证它们中较大的那个更小 更满足题意

然后还是\(long long\)

别的没什么太要紧的了 关于\(lower_bound\)返回指针类型等的小点 我在代码中也加入了部分注释

$code$ 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
typedef long long ll;
inline ll qr()
{
	char ch=getchar();ll x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
using namespace std;
const int Ratio=0;
const int N=200005;
const int maxint=INT_MAX;
const ll  maxll=1e18;
int n,m,k;
ll a[N];
ll deta,detaa,lb,rb,ans;
set<ll>f,d;
int main()
{
	// freopen("1.inll","r",stdin);
	// freopen("1.out","w",stdout);
	int T=qr;
    while(T--)
    {
        n=qr,m=qr,k=qr;
        f.clear(),d.clear();
        deta=0,detaa=0;
        fo(i,1,n)
        {
            a[i]=qr;
            if(i!=1)//输入时直接寻找最大差和次小差
                if(deta<a[i]-a[i-1])
                {
                    detaa=deta;
                    deta=a[i]-a[i-1];
                    lb=a[i-1],rb=a[i];
                    //由于单增排序 左边界为小
                }
                else if(detaa<a[i]-a[i-1])
                    detaa=a[i]-a[i-1];
        }
        fo(i,1,m)
        {
            ll dd=qr;
            d.insert(dd);
        }
        fo(i,1,k)
        {
            ll ff=qr;
            f.insert(ff);
        }
        ans=deta;
        for(auto i:f)
		{
            auto dh=d.lower_bound((lb+rb)/2-i),yy=dh;
            //找最接近中间的 分开后两差大的尽量小
            ll dh1=*dh,yy1=*yy;
            //lower_bound值是指针类型无法运算 加*
            ans=min(ans,max(dh1+i-lb,rb-i-dh1));
            if(yy!=d.begin())
            //不是队首 指针会向上取 需--
            {
                yy--;
                yy1=*yy;
                ans=min(ans,max(yy1+i-lb,rb-i-yy1));
            }
        }
		cout<<max(detaa,ans)<<endl;
        //此时再次比较次大值和更改后最大值
    }
	return Ratio;
}//

G - Rudolf and Subway

太蒻了 还没做出来。。

标签：ch,int,题解,long,--,qr,CF933,Div3,getchar
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18079919

相关文章

  • 【题解】A18535.来自领导的烦恼
    题目跳转思路：本题可以使用动态规划或递归的方式来实现，本质上是一道01背包的变型题。假设一共有\(n\)名员工，每一位员工的技能水平用\(a[i]\)表示。要使得两个部门的员工技能总和之差最小，意思就是尽可能地将一个部门的技能之和”凑“到\(\sum\limits_{i=1}^{n}a[i]\times\frac{1}......
  • 【题解】A18536.星光交错的律动
    题目跳转思路：这道题可能跟博弈论有一点关系，没有学习过博弈论做起来应该问题也不大。思考一个问题，先手必胜的前提是什么？有关更多的内容可以前往：浅谈有向无环图先手必胜的前提是，在任何一种局面下，先手都有至少一种操作可以使后手处于必败的局面。若先手进行任何操作后，后手都可以......
  • 【题解】A18537.我心中珍藏的游戏
    题目跳转思路：题目问最多可以获得的额外伤害，其实就是询问在这些技能中，如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点，把每一个攻击加成看作图的边，权制为\(Ei,j\)。由于\(Ei,j\)与\(Ej,i\)相等，则可以将这个图视为无向图。可以样样......
  • 【题解】P2627 [USACO11OPEN] Mowing the Lawn G
    【题解】P2627[USACO11OPEN]MowingtheLawnG题目跳转数据量比较大，暴力肯定是不行的。只能考虑用动态规划的方式来做。这道题有许多dp设计的思路，这里提供两个：方法一：普通状态设计定义\(dp[i][1/0]\)表示截止遍历到第\(i\)个元素时，选择第\(i\)个元素或不选第\(i\)个元素可以......
  • cfRound933div3-E题解
    E-RudolfandkBridges题意:选择的桥在连续的行中,每个桥的支架安装位置是可以不一样的.做法：赛时也感觉也感觉是dp,但是害怕dp,就选择了逃避.往贪心方向想,认为每次到了每个跳板都要跳到最远距离,实际上这样是不行的.很明显,可能存在近一点的点花费更少。实际上是dp,而且也不......
  • [ABC258F] Main Street 题解
    题意：你要在平面直角坐标系中行走，每一步可以上下左右四个方向任意移动$1$，耗时$k$秒。特别地，存在若干条快速通道，若该步起点和终点均满足$x\equiv0\pmod{B}$或$y\equiv0\pmod{B}$，则认为该步是在快速通道上进行，仅需耗时$1$秒。询问从$(S_x,S_y)$到$(G_x,G_y)$最......
  • P3939 数颜色 题解
    题目链接：数颜色经典题目了，暴力数据结构随便过，不过这种不带修的单个颜色的数量查找有个经典的做法：分桶+二分。具体的为每个颜色分桶，记录有序下标，这样就可以二分出\([l,r]\)上的下标个数。对于一次交换来说，如果相邻的颜色相同那么并不会发生交换，如果不同那么就发生交换，由于下标在......
  • P10218 [省选联考 2024] 魔法手杖 题解
    Description给定\(a_1,a_2,\dots,a_n\)以及\(b_1,b_2,\dots,b_n\)，满足\(a_i\in[0,2^k-1]\)以及\(b_i\geq0\)，你需要给出\(S\subseteq\{1,2,\dots,n\}\)以及\(x\in[0,2^k-1]\)满足以下条件：\(\sum\limits_{i\inS}b_i\leqm\)；满足以上条件的前提下，最大化\......
  • P2746 [USACO5.3] 校园网Network of Schools 题解
    题目链接：校园网NetworkofSchools这个题得翻译下题目意思才知道在干嘛，题目一开始表明了这个是一个有向图，因为边是单向的。其次关于第一个问题：基于一个事实，如果有\(x\rightarrowy\rightarrowz\)，那么只需要\(x\)接受协议，它所在的\(scc\)强连通分量上的点一定都能不需要......
  • AT_abc345_c [ABC345C] One Time Swap 题解
    题目传送门解法对于\(S_{i}\)，设\(num_{S_{i}}\)表示\(S_{i+1\simn}\)中\(S_{i}\)出现的次数，则\(S_{i}\)对答案产生的贡献为\(n-i-num_{S_{i}}\)。注意原串在存在两个相同的元素的时候，也要统计在内。代码#include<bits/stdc++.h>usingnamespacestd;#definell......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99