Yet Another Permutation Problem
算法本质
思维
题目大意
需要玩家构建长度n的循环排列，定义其美丽值：
- 相邻元素的gcd值的不同个数
输出最大化的构建方案。
思路推演
稍加模拟：
对于1而言，其跟和相邻，gcd值都是1，对于2而言，其与2的倍数相邻gcd值才是2，考虑其与4相邻是最优解（因为其他元素可能有更好的解法）。
同理，2的右边放4，左边没什么用了，就放1吧。
对于4而言，右侧应该放4的倍数，8是最优解，以此类推，我们找到了gcd值的1 2 4 8 ...，当大小不够时，回身找3，同理即可。
最终构建出的数组形如：[1, 2, 4, 8, 16, ...., 3, 6, 12, 24, ...., 5, 10, 20, ....]
Trees and Segments
算法本质
思维
题目大意
给定01串，设置l0表示串中连续0的最大长度，l1表示串中连续1的最大长度。
现在至多可以执行k次操作：
- 反转某位
有式子：f(x) = x*l0 + l1
独立地回答，当x属于[1~n]，输出操作后最大化的f(x)。
n <= 3e3思路推演
稍加模拟可以发现，首先完全贪心思路是无法解决的，所以寻求dp解决。
这里会有个经常的问题是，大概率不会是O(n)求一个f(x)，若需要如此，完全可以将n修改为1e6，然后随机赋予一个x值求解。
所以一定会有用到n^2^的算法的：
- 预处理O(n^2^)，所有x都能受益
- x之间存在关系，可以借用
操作完后，肯定是存在2个无交集区间，分别是全0的最长区间和全1的最长区间，暂且默认全0区间在左。
dp处理同时维护全0区间和全1区间不行（其权重未知，没有同一标准），但是维护单个信息还是可行的。
比如dp[i][j]表示[1~i]中用j次操作后，最长的0区间长度。
一个想法是，区间之间一定存在分界线，枚举分界线，然后枚举左边的操作次数和右边的操作次数，就能得到两个区间的长度。
但是，对于每种区间长度，还需要枚举x的n个取值，这总体的复杂度达到了O(n^3^)。
一个朴素的优化方式是：
这里有n^2^种两个区间的长度，其存在部分单调性，用0区间长度作为key来记录，1区间的长度就具备了单调性，情况可以优化至n种。
然后再对这相对优解枚举其x值，就可以O(n^2^)解决。
回过头来，再来看dp[][]的设置，其实是存在一些小问题的。
之前的状态设置完全转移困难，所以重新设计dp[i][j]表示操作j次以i结尾的最长0区间长度。
这样转移十分好写：
if s[i]==0:
dp[i][j] = dp[i-1][j] + 1 # 不需要额外操作
else:
dp[i][j] = dp[i-1][j-1] + 1 # 需要额外操作，注意i j边界然后再建立一个状态：$pre[i][j] = \max_{t=1}^idp[t][j]$
来表示以1~i中，使用j次操作后的最长连续0区间。
这样就拿到了所需要的东西，但是这仅仅是某一个，其实有4个东西需要拿到：
1~i中，使用j次操作后的最长连续0区间长度i~n中，使用j次操作后的最长连续0区间长度1~i中，使用j次操作后的最长连续1区间长度i~n中，使用j次操作后的最长连续1区间长度
建议使用函数优化。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<vector<int>> f(string s, char c)
{
s = " " + s;
vector<vector<int>> dp(n+5, vector<int>(k+5)), pre(n+5, vector<int>(k+5));
for (int i=1; i<=n; i++)
{
for (int j=0; j<=min(k, i); j++) // 注意操作数可能为0，要从0开始
{
if (s[i]==c)
dp[i][j] = dp[i-1][j] + 1;
else if (j>0) // 注意别越界
dp[i][j] = dp[i-1][j-1] + 1;
pre[i][j] = max(pre[i-1][j], dp[i][j]);
}
}
return pre;
}
inline void solve()
{
string s;
cin>>n>>k>>s;
vector<vector<int>> pre0, suf0, pre1, suf1;
pre0 = f(s, '0');
pre1 = f(s, '1');
reverse(s.begin(), s.end()); // 倒过来就是suf了
suf0 = f(s, '0');
suf1 = f(s, '1');
vector<int> to(n+5, -1); // to[0区间长度] = 最大的1区间长度
for (int i=0; i<=n; i++) // 枚举分界点
{
for (int l=0; l<=k; l++) /// 枚举左右方的操作数
{
int r=k-l;
int len0=pre0[i][l]; // 假设0区间在左，1区间在右的情况
int len1=suf1[n-i][r];
to[len0] = max(to[len0], len1);
len0=suf0[i][r]; // 假设0区间在右，1区间在左的情况
len1=pre1[n-i][l];
to[len0] = max(to[len0], len1);
}
}
vector<int> ans(n+5, -1);
for (int len0=0; len0<=n; len0++) // 存在n个相对优解
{
if (to[len0]==-1) continue;
for (int x=1; x<=n; x++)
ans[x] = max(ans[x], x*len0 + to[len0]);
}
for (int i=1; i<=n; i++) // 输出
cout<<ans[i]<<" \n"[i==n];
return;
}Rollbacks (Easy Version)
算法本质
思维
题目大意
初始存在一个空数组，接下来有q次操作：
+ x
数组末尾增加值x的元素- x
数组末尾减去x个元素!
回溯上一个操作（类似于栈，无法回溯回溯的操作）?
询问目前数组不同元素的个数
Hard版本强制要求在线
全部值 <= 1e6思路推演
Eszy版本并不要求在线，这点提醒了我们。
稍加模拟可以发现，减法的形态，有点类似于树的一个分支。例如当[1, 3, 2, 5, 3, 6]遇到减去3个元素后，数组末尾的[5, 3, 6]就可以视作树的一个分支。
同时当前点需要跳转至2，这样的大幅度跳转需要优化至log级别，在线倍增符合我们的要求。
还需要注意的一个点是回溯操作，其实其本质很简单，回溯到上一次操作的点，我们仅需要每次操作的时候，都记录一下之前的点即可。
遇到问好，就在树上做个标记：第x个问号在次询问。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<int> g[maxn];
int up[maxn][20];
int a[maxn];
vector<int> cod[maxn];
int swim(int x, int step) // 向上移动step步的基础函数
{
for (int wei=0; step>0; wei++)
{
if (step&1) x=up[x][wei];
step /= 2;
}
return x;
}
int ans[maxn];
int mp[maxn]; // 这里用map会爆内存（题目卡的比较死）
int siz=0;
void dfs(int u=0)
{
if (u < 0) return;
if (u!=0)
{
mp[ a[u] ]++;
if (mp[a[u]]==1)
siz++;
}
for (int pos:cod[u])
ans[pos] = siz;
for (int v:g[u])
dfs(v);
mp[ a[u] ]--;
if (mp[a[u]]==0)
siz--;
}
inline void solve()
{
int q=in(); int y=q;
int cnt=0, p=0, wen=0; // cnt记录出现的点数，p记录当前点的id，wen记录?出现的次数
vector<int> lastp; // 记录操作前的id，方便回溯
while (q--) // 维护树结构，然后记录有的节点需要答案
{
string op;
cin>>op;
if (op=="+")
{
lastp.push_back(p);
int num=in();
int u = ++cnt; // 新增点
g[p].push_back(u); // 记录其父亲多了一个子节点，方便之后访问
a[u] = num; // 记录点的值
up[u][0] = p;
for (int i=1; i<=19; i++) // 更新一下树上倍增
up[u][i] = up[ up[u][i-1] ][i-1];
p = u; // 更新当前点
}
else if (op=="-")
{
lastp.push_back(p);
int num=in();
int u = swim(p, num); // 利用倍增log级别查询
p = u; // 更新当前点
}
else if (op=="?")
cod[p].push_back(++wen); // 记录问号
else if (op=="!")
p=lastp.back(), lastp.pop_back();
}
dfs();
for (int i=1; i<=wen; i++)
cout<<ans[i]<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)