首页 > 其他分享 >csp-s真题题解

csp-s真题题解

时间:2024-10-11 18:33:43浏览次数:8  
标签:lg mmib 20 真题 int 题解 ll ans csp

csp题目讲解

P8818 [CSP-S 2022] 策略游戏

学习笔记

感觉非常复杂?对于现在的我还是有深度的,首先第一个大坑就是并不需要真的求出c矩阵,这个题意就是让你在区间中选数,但要求乘积最大,所以要分讨。

你假定 \(a_i\ge0\),那这时如果 \(min(b_i)\ge0\) 取 \(max(a_i)\),否则取 \(min(a_i\ge0)\),相反的,假定\(a_i<0\),那这时如果 \(max(b_i)\ge0\) 取 \(max(a_i)\),否则取 \(max(a_i<0)\)。

这就是贪心的思想,感觉非常有深度(菜),然后就需要维护6个ST表,非常糟糕啊,然后就没有然后了,你就慢慢维护去吧。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;

int a[N],b[N],lg[N];
int n,m,q;

int mxa[N][20];
int mia[N][20];
int rmxa[N][20];
int rmia[N][20];

int mxb[N][20];
int mib[N][20];

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	lg[1]=0;
	for(int i=2;i<=max(n,m);i++){
		lg[i]=lg[i>>1]+1;
	}
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mxa[i][0]=mia[i][0]=a[i];
		rmia[i][0]=0<=a[i]?a[i]:INT_MAX;//正数中取最小,没正数取intmin标记为无 
		rmxa[i][0]=a[i]<0?a[i]:INT_MIN;//负数中取最大,没负数取intmax标记为无 
	}
	
	for(int i=1;i<=m;i++){
		cin>>b[i];
		mxb[i][0]=mib[i][0]=b[i];
	}
	
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			int p=i+(1<<(j-1));
			mxa[i][j]=max(mxa[i][j-1],mxa[p][j-1]);
			rmxa[i][j]=max(rmxa[i][j-1],rmxa[p][j-1]);
			mia[i][j]=min(mia[i][j-1],mia[p][j-1]);
			rmia[i][j]=min(rmia[i][j-1],rmia[p][j-1]);
		}
	}
	
	for(int j=1;j<=lg[m];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			int p=i+(1<<(j-1));
			mxb[i][j]=max(mxb[i][j-1],mxb[p][j-1]);
			mib[i][j]=min(mib[i][j-1],mib[p][j-1]);
		}
	}
	
	while(q--){
		int la,ra,lb,rb;
		cin>>la>>ra>>lb>>rb;
		int x=lg[ra-la+1],y=lg[rb-lb+1];
		int pa=ra-(1<<x)+1,pb=rb-(1<<y)+1;
		
		int mmxa=max(mxa[la][x],mxa[pa][x]);
		int rmmxa=max(rmxa[la][x],rmxa[pa][x]);
		
		int mmia=min(mia[la][x],mia[pa][x]);
		int rmmia=min(rmia[la][x],rmia[pa][x]);
		
		int mmxb=max(mxb[lb][y],mxb[pb][y]);
		int mmib=min(mib[lb][y],mib[pb][y]);
		
		long long ans=LONG_LONG_MIN;
		
		ans=max(ans,(ll)mmxa*(mmxa>=0?mmib:mmxb));
		ans=max(ans,(ll)mmia*(mmia>=0?mmib:mmxb));
		
		if(rmmxa!=INT_MIN){
			ans=max(ans,(ll)rmmxa*(rmmxa>=0?mmib:mmxb));
		} 
		if(rmmia!=INT_MAX){
			ans=max(ans,(ll)rmmia*(rmmia>=0?mmib:mmxb));
		}
		cout<<ans<<"\n";
	}

	return 0;
}

标签:lg,mmib,20,真题,int,题解,ll,ans,csp
From: https://www.cnblogs.com/sadlin/p/18459059

相关文章

  • P3959 [NOIP2017 提高组] 宝藏 题解
    P3959[NOIP2017提高组]宝藏题解搜索魅力时刻怎么说,四种做法比较??的模拟退火跑得快但是正确性有问题的状压DP跑得慢但是一定正确的状压DP时间复杂度很玄学的DFS+剪枝我就选择了搜索的做法先打个暴搜,70pts点击查看暴搜代码#include<bits/stdc++.h>usingna......
  • 有关 OneDrive 中 Copilot 的常见问题解答
    很多小伙伴已经用上了OneDrive中的Copilot功能:Copilot重磅更新!OneDrive全新功能炸裂一个技巧实现在SharePoint中使用Copilot针对大家提问比较多的问题,在此做一个汇总:1、OneDrive中的Copilot目前在哪里可用?OneDrive中的Copilot目前在 OneDriveWeb上仅适用于商......
  • P5547 [BJ United Round #3] 三色树 题解
    Description请你对满足以下要求的\(n\)个节点的无标号无根树计数:每个节点是三种颜色之一:红,蓝,黄红色节点度数不超过\(4\),蓝色和黄色节点度数均不超过\(3\)黄色节点不能相邻注意无标号无根树的意义是:如果两颗树可以通过重新编号的方法使得对应点颜色相同,对应连边一致......
  • 颠倒原理题解
    颠倒原理/reverse时间限制:1000ms空间限制:512MB题目描述\(GreenDuck\)想学习转置原理,但由于它太难了,因此他转而学习更为简单的和图的染色有密切联系的“颠倒原理”\((reverseprinciple)\)。颠倒原理中有个重要的操作叫做“颠倒操作”。对于一个无向连通图\(G\),其节点要么......
  • [CSP-S2020] 函数调用
    这个题真的有那么简单吗?首先是cornercase,新建一个点连向1~n表示起点。显然这个图是DAG,然后考虑dp。全局mul的标记好算,主要是每次的加法到底会被mul如何影响。主要是你肯定无法直接维护每个函数的2操作集合,因为这可以到平方级别。所以我们直接维护每个2操作的操......
  • 23 真题前两题
    密码锁没什么好说的,要么暴力判断,要么手推。消消乐我们观察一下这个能消除的结构,因为是每次消除相邻两个,所以不难想到很像括号匹配,或者说可消除的是有对称性的,所以我们一定可以找到一个节点开始反转左右手性,所以我们就可以用栈来保持前半部分的手性,后半部分遇到转折点就是可以消......
  • Day4 备战CCF-CSP练习
    题目描述有若干个任务需要在一台机器上运行。它们之间没有依赖关系,因此可以被按照任意顺序执行。该机器有两个CPU和一个GPU。对于每个任务,你可以为它分配不同的硬件资源:在单个CPU上运行。在两个CPU上同时运行。在单个CPU和GPU上同时运行。在两个CPU和GPU......
  • 华为OD机试真题】68、矩阵扩散
    packagemainimport( "errors" "fmt" "strconv" "strings")typepointstruct{ xint yint valueint}typeimagestruct{ wint hint allPointint points[][]*point}func(i......
  • 数据结构题解报告
    [GDOI2016]疯狂动物城对于大多树上区间问题往往加个树剖就能变成普通区间问题,只是说复杂度会加个\(log\),出题人这么做的理由可能是想锻炼一下评测姬吧选手的码力吧。而强制在线只需要可持久化数据结构即可。本题同理可视作区间问题用线段树维护,考虑推式子降次以便于维护\(ans......
  • [AGC054D] (ox) 题解
    感觉看到交换就应该要想到逆序对。思路一个前置小知识,我们把一个排列用相邻交换复原的最小次数是逆序对数量。考虑没有ox的情况。我们顺着扫一遍字符串。把左括号正一,右括号看作负一,当前缀和小于零以后,我们把后面最近的左括号提过来,这样可以构造出交换次数最少的合法括号串......