P9506 题解

描述给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列。括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。数据范围：字符串长度0≤n≤10000要求：空间复杂度O(n)，时间复杂......

题目链接 题意：时间轴上分布着$n$位乘客（$1\len\le500$），$i$号乘客的位置为$t_i$（0\let_i\le4\times10^6），用互相距离不小于$m$的车次将时间轴分为若干部分，并管辖以自己为右端点的这个区间（除了第一趟车包括$0$，其他车次左开右闭），求最小费用和。每个车次的费用来自：管辖区间内所......

题意这道题是让我们把一段区间分成四个不为空的连续子序列，并算出每个区间的和，最后用四个和的最大值减去最小值，算出最终答案。分析大家首先想到的肯定是暴力法用三个循环枚举四个区间，对于每一个区间，在单独算和，这样的时间复杂度$O(n^4)$，肯定会超时。现在我们进行优化：最后求和的......

P4899[IOI2018]werewolf狼人题解题目描述省流：\(n\)个点，\(m\)条边，\(q\)次询问，对于每一次询问，给定一个起点\(S\)和终点\(T\)，能否找到一条路径，前半程不能走\(0\thicksimL-1\)这些点，后半程不能走\(R+1\thicksimN-1\)这些点。中途必须有一个点在\(L\thicksimR\)之......

简述题意这什么破翻译，看了AtCoder的英文才看懂。给定一个长度为\(n\)序列\(a\)，要求构造一个数列\(b\)，使得对于任意\(i\)，满足：\(1\lei\len\)将\(b\)序列下标为\(i\)的倍数的值相加使得这个总和模2等于\(a_i\)。求序列\(b\)中值为1的个数与值为1......

思路看数据范围，发现范围很小，直接用搜索。搜索时枚举每个点，如果有棋子就枚举方向，如果这个方向合法，则将剩余棋子数减一，继续搜索。搜索时参数只需要传当前棋子数就行了。有以下几点需要注意多组数据每次需要初始化。判断是否合法时要注意。每次记得回溯棋子。ACCODE......

考虑动态规划。思路设\(dp_{i,j}\)为\((1,1)\)到\((i,j)\)的方案数，而如果要到这个点，肯定是从左边和上边来。所以递推公式为：\(dp_{i,j}=dp_{i,j-1}+dp_{i-1,j}\)。预处理：将横或纵坐标为1的点赋值为1，因为到达这些点的只有一种方法。注意：每次需要清零数组。ACC......

这题其实可以数学方法差小积大解决。差越小积越大，那肯定是让最小的数加一啦。将所有数的积除以最小值再乘上最小值加一。#include<bits/stdc++.h>usingnamespacestd;signedmain(){ intT; cin>>T; while(T--){ longlongcnt=0,n,a[10],minn=LONG_LONG_MAX,ans=1; c......

原题翻译发现所有长度相同的简单路径的权值可能情况相同，且最长的简单路径长度为\(O(\logn)\)级别，考虑维护所有长度的简单路径在一棵树上出现的次数，每种简单路径的权值在所有树上出现的次数，相乘即使答案。我们考虑长度为\(x\)的路径对答案的贡献，考虑枚举这条路径的贡献\(......

CF1542E2首先时间复杂度肯定是\(\mathcal{O}(n^3)\)的。容易想到先枚举最长公共前缀，然后枚举\(p_{len+1}\)和\(q_{len+1}\)，再枚举逆序对数进行统计。令\(f_{i,j}\)表示有\(j\)个逆序对的\(i\)阶排列的个数。易得转移\(f_{i,j}=\sum\limits_{k=\max(j-i+1,0)}^{j}f......