首页 > 其他分享 >P9754 题解

P9754 题解

时间:2024-01-13 16:46:25浏览次数:20  
标签:P9754 变量 一个 题解 siz 操作 mx 结构

题意

不难理解,不多赘述。

思路

首先考虑对于性质 A 的情况,我们可以这样做:

定义一个代表变量的结构体,里面存几个参数:首先肯定要存种类(\(type\))和名称(\(name\)),其次为了方便,我们把该变量的大小(\(siz\)),起始位置(\(fir\))和对齐要求(\(mx\))也存了。

操作二

\(type\),\(name\),\(siz\) 和 \(mx\) 可以直接知道,对于 \(fir\),注意到 \(mx\) 最大为 \(8\),所以我们定义一个全局变量 \(siz\) 表示当前占用地址的个数,然后暴力往后面找 \(8\) 个即可。

操作三

我们定义一个 \(map\) \(id\) 来建立变量名与变量编号之间的映射,然后直接查找即可。

操作四

我们把所有变量的 \(fir\) 独立出来建一个数组 \(Fir\),然后直接二分是在哪一个变量范围内,最后通过该变量的 \(siz\) 判断是否为空地址。

接下来我们考虑把 \(1\) 操作加上:

发现对于一个结构体内的过程,其实和全局的过程是相似的,于是我们直接把处理全局的方法搬到结构体里:定义一个代表结构体的结构体,里面放一个代表变量的结构体数组,一个 \(map\) \(id\) 用来建立映射,和一个用来二分起始位置的数组 \(Fir\),最后自然要把结构体包含的变量个数 \(k\) 也存进去(全局也要存)。

操作一

相当于在结构体内做 \(k\) 次操作二,唯一不同的是我们要更新 \(mx\),就是每个变量的 \(mx\) 取 \(\max\)。

操作二

跟上面没有区别。

操作三

在上面处理完后进入递归就行。

操作四

同操作三,直接用 string 处理,是否合法可以单独拿一个变量记录一下。

然后就完了。

几个需要注意的点:

  1. 结构体内每个变量需要按变量的对其要求来对齐,而非按结构体的对齐要求来对齐,例如:在一个结构体内先后封装两个 int 和 一个 long 中间是没有“空隙”的。

  2. 注意操作四如果合法最后是没有点的,可以在合法时不输出最后一个字符,也可以在递归时特判,但注意还要在递归外特判

  3. 记得特判 byte,short,int,long。

当然,我们可以把所有的二操作也看成在一个结构体内进行,对于这个结构体的名字,我们可以利用原题中 “所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 \(10\) 个字符的小写字母组成” 这句话,把 \(name\) 设成一个长度为 \(11\) 的字符串,然后把操作全部封装,只需要记录一个结构体名和编号的映射在外面就行,这样码量应该会小一些。

标签:P9754,变量,一个,题解,siz,操作,mx,结构
From: https://www.cnblogs.com/BINYU/p/17962547

相关文章

  • AT_cf17_final_j 题解
    题意给定一棵既有点权也有边权的树,构造一个完全图,图中两点间边的边权为树中两点点权之和加上两点间的距离,求该图的最小生成树。思路发现完全图总边数太大,考虑减少边数。这里有一个性质:如果在一个图中选取任意个联通的边集,使得它们的并为全集,则整个图的最小生成树中的边一定在......
  • [AGC022F] Checkers 题解
    题目链接点击打开链接题目解法很妙的题!!!考虑\(x\)是无穷大的数,所以可以认为\(x^i\)的系数是单独的一项,不会和\(x^j(j\neqi)\)合并所以问题转化成了:每个数初始是\(x^i\)(\(x\)可以理解是元),进行题目中的操作,问最后形成的\(n\)次多项式的个数由\(B\)向\(A\)连边,这......
  • CF1006E Military Problem 题解
    CF1006EMilitaryProblem题解题意给定一颗有\(n\thinspace(2\leqn\leq2\times10^5)\)个节点的树,树根为\(1\)。对于每个节点\(i\thinspace(2\leqi\leqn)\)都有它的父节点\(p_i\),并且每个节点的子节点都是按从小到大的顺序排列的的。有\(q\thinspace(1......
  • 【题解】CatOJ C0458C 滑动窗口定期重构
    标题trick的名字我也不知道是什么,就这样吧。link。首先有显然的dp式子:\(f(i)=\min\{f(j)\times\max\{a_{j+1},\dots,a_i\}\}\)。考虑怎么去优化它。有显然的\(\mathcalO(n\logn)\):考虑线段树优化dp。用增的单调栈维护\(a\),若每次弹出顶部一个下标\(p\),则\([p+1,i......
  • 1.11模拟赛 T1题解
    简要题意\(n\le10^3,\sumK_i\le3\times10^5\)思路首先容易想到一个暴力DP,\(f_{l,r,x}\)表示区间中最大值为\(x\)的最大值稍微想亿下可以发现如果这个位置选的不是区间最大值的话,答案一定不优所以我们可以直接\(f_{l,r}\)DP转移,但复杂度还是没变,我们把柿子列出来\(......
  • AT_joisc2018_b 题解
    AT_joisc2018_b题解传送门题意有一个以原点为中心的正方形,有\(n(n\le100)\)条不在正方形内部的线段,你需要画一些不在正方形内部的线段,使得这些线段可以把正方形围起来,要求最小化你画的线段的长度和。思路我们需要画出一条闭合折线,并且能够把正方形包围。考虑我们一定是......
  • 1.11模拟赛 T2题解
    简要题意每个点有一定概率向前面的点连边,求两点之间距离的期望思路推柿子code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineN1000005intn,m,u,v;constintmod=1e9+7;inta[N],sum[N],c[N],dep[N],s[N],f[N],g[N],h[N];intksm(intx......
  • P4103 [HEOI2014] 大工程 题解
    题目链接:大工程先考虑只有一次查询,很显然我们可以暴力树上dp处理出答案。对于每个节点而言,有:容易看出类似点分治逐个遍历子树计算前面一堆子树对后面子树的贡献思想,我们可以很容易的知道:对于路径总和,显然多了一段新的贡献,这段贡献为当前关键点和前面点多的一段\(2\)号路......
  • 《算法竞赛》题解---三分
    三分法模板三分法#include<bits/stdc++.h>#defineeps1e-8//或者constdoubleeps=1e-8;--主要是doubleusingnamespacestd;intn;doublea[15],l,r;doublecheck(doublex){ doubleans=0; for(inti=n;i>=0;i--) ans=ans*x+a[i];//秦九韶公式 returnans;}......
  • P4093 [HEOI2016/TJOI2016] 序列 题解
    题目链接:序列对于LIS问题,很显而易见的有dp方程为:\[dp_i=\max{dp_j}+1\(j<i,a_j\lea_i)\text{dp表示以某个位置结尾的最长LIS}\]本题考虑到对于转移的两位置,如果能从\(j\rightarrowi\),那么在以上条件成立的基础情况下,我们由于可以更改二者中的任意一个值(因为同一......