A.Grasshopper on a Line
算法本质
思维
题目大意
给定n k，表示一维坐标中你在0点，需要达到n点，每次可以花费1秒时间走任意非k整数的距离。
给出花费时间最少的方案。
思路推演
显然，如果n模k不为0，则可以一步走到。
反之，我们手动模拟一下即可发现，n-1必定模k不为0，我们可以用1 + (k-1)来完成。
B.Comparison String
算法本质
思维
题目大意
给定长度n由<和>组成的字符串s，用于指定长度n+1的a[]数组相邻元素大小比较。
s[i] = >表示a[i]>a[i+1]，反之同理
输出构建满足条件的a[]至少需要几个不同的值。（[1, 2, 3, 3]看作使用了3个不同的值）
思路推演
既然需要最少的值，核心思想就是复用。
我们根据s画个轨迹图，形象地表示a[]，可以发现当某一段大量连续上升或者下降的时候，可以视作别人对其的复用。
我们将每段连续上升、下降看作一个区间，设定一个上限值和下限值，每个区间的开头结尾都必须是上下限值，中间的复用即可。
最后值的个数为：最长连续>或<符号长度+1。
C.Best Binary String
算法本质
思维
题目大意
给定由0 1 ?组成的字符串s。其中?可以表示为0或1。
现在需要确定?的表示，并使得最后得到的s成本最小。
01字符串s的成本定义，最小的操作次数使得s呈现非递增序列：
- 选择
l r使得s[l~r]字符发生反转（010 --> 101这种）
思路推演
这个题从成本整体去思考，有一定的难度。
我们先着眼于单个?的角度来看。
- 当连续多个
?，?的值应该一致 - 当
?的两侧一致都是1或0时，?的值应该与两侧相同 - 当
?两侧不一致时，任意取1或0 - 当
?在边缘，应该与另一侧值保持相同 - 当
?两侧都是边缘时，随意取值
以上的规则我们可以简化为：
- 若
?存在前值，就取前值，否则取后值，否则取0（1也行）
从字符角度去思考，讨论所有最佳情况即可。
D.Bracket Coloring
算法本质
思维
题目大意
给定括号序s，定义括号序美丽满足：
- 满足常见对应形式 或者 顺序颠倒后满足常见对应形式
现对s顺序自由分成若干组，每组括号徐美丽，输出分组数最小的分组方案。
思路推演
容易发现的是，任何美丽的字符串按照原来顺序任意组合，任然美丽。
所以显然，如果括号序可行，最多分成2组即可。
我们开一个队列栈一一对应即可。
E.Playoff Fixing
算法本质
思维
题目大意
现在有2**n支队伍，id从[1~2**n]分配，在比赛中id较小的队伍必然获胜。
比赛采取常见的2分方法，比n个回合。
现在我们希望，最后的排名完全符合队伍实力：
- id为1的队伍一定是冠军、id为2的队伍是第2名、id为34的队伍是第34名（因为赛制没法分出更细的名次），以此类推
初始存在2**n个格子，每支队伍存在于一个格子，现在已有若干个格子已经确定好队伍了。
请问有多少种情况，可以满足条件。（取模xxx）
n <= 19思路推演
首先需要考虑的就是，如何才能实现目标：
- 每一轮比赛，都需要让id最大的队伍淘汰
而情况数目来自于未知id的不定性。
对于每一轮比赛，每支队伍有3种可能：
当前需要淘汰的队伍、当前不需要淘汰的队伍、未知（以下简称“淘”“不淘”“未知”）
每场比赛由2支队伍组成，就需要讨论8种情况，做出分类
- 淘+淘 或者 不淘+不淘
2支队伍都需要淘汰，但是无法做到，必然会导致最后不能达到目的。
直接给ans赋值0 - 未知+未知
未知定义为淘汰和不淘汰
淘汰队伍位置不定、id不定 - 淘+非淘
淘汰队伍位置确定、id确定 - 不淘+未知
未知定义为淘汰
淘汰队伍位置确定、id不定
我们每轮比赛，讨论当前轮次的情况数，同时更新下一轮的队伍id情况，即可算出。
许多小细节没说明白，可以结合代码一起看
思路推演-另辟蹊径
这是别人的一种做法，思想上区别不大，核心区别是构建了队伍id-->队伍位置。
每轮比赛，都遍历后一半的队伍id，收集他们所在的比赛场和不确定值数（对队伍位置用除法来判断所处的比赛场）
根据这些数据来判断是无效或者具体情况数即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int dp[20][maxn];
int fac[maxn];
int ck(int x, int l, int r) // 判断x值是否属于[l,r]范围，正确返回1错误返回0，若x为-1则返回-1
{
if (x==-1) return -1;
return x>=l && x<=r;
}
inline void solve()
{
//init
cin>>k;
n = 1ll<<k;
for (int i=1; i<=n; i++)
cin>>dp[k][i]; // dp[x][y]表示第x个伦次的第y场比赛的胜者id
int ans=1;
for (int i=k; i>=1; i--, n/=2) // 第i轮，目前有n支队伍
{
int l=n/2+1, r=n; // [l, r]表示当前伦次需要被淘汰的队伍id范围
int val=1, num=r-l+1; // val表示当前伦次的情况数，num表示当前伦次需要淘汰但是值不确定的id数
for (int j=1; j<=n; j+=2) // 有n/2场比赛，遍历每场比赛
{
int p1=dp[i][j], p2=dp[i][j+1]; // 队伍id
int a=ck(p1,l,r), b=ck(p2,l,r), res; // 队伍id带来的3个状态，res表示当前比赛的胜者id
// 淘+淘 或者 不淘+不淘：无法达成目标，值归零
if (a==b && a!=-1)
val = 0;
// 未知+未知：未知定义为淘汰和不淘汰，淘汰队伍位置不定、id不定
else if (a==b && a==-1)
res=a, val = (val*2)%mod;
// 淘+非淘：位置确定、id确定
else if (a==1)
res=p2, num--;
else if (b==1)
res=p1, num--;
// 不淘+未知：未知为淘汰，位置确定、id不定
else if (a==0 && b==-1)
res=p1;
else if (a==-1 && b==0)
res=p2;
dp[i-1][j/2+1] = res; // 更新胜者id
}
val = (val*fac[num])%mod; // 有num个id的值不确定，阶乘种情况
ans = (ans*val)%mod; // 更新到总ans上
}
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)