A.The Man who became a God
算法本质
思维
题目大意
给定a[]信息，在不改变相对顺序条件下，把a[]分成k个组，每个组的成本为：（总成本为每组成本之和）
- 相邻2个数绝对值差之和
输出最小化的所有组成本和。
思路推演
分组的实际意义是，切断了a[i]和a[i+1]之间的连续，使得成本下降了abs(a[i]-a[i+1])。
所以记录n-1个绝对值差，减去前k-1个值，即得到剩余的最小化组成本和。
B.Hamon Odyssey
算法本质
思维
题目大意
给定a[]信息，在不改变相对顺序条件下，把a[]分成若干组，每组的成本为：（总成本为每组成本之和）
a[l] & a[l+1] & ... & a[r]
输出保证最后成本最小能分的最大组数。
思路推演
首先可知，若a[1] & a[2] & .. a[n]不为0，则一定不可分割，因为必然会导致值增加。
若其全部与运算后为0，则需要保证分割前后都是0才行——即a[l~r]中，每个二进制位都存在某个数此位0。
我们选择从左往右遍历，一旦满足这个条件，则记录重置条件。（用贪心思想看，显然正确）
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], b[maxn][40]; // 数组、数组二进制
inline void solve()
{
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>a[i];
for (int j=0, x=a[i]; j<=30; j++, x/=2)
b[i][j] = x%2;
}
int ans=0;
set<int> st;
for (int i=1; i<=n; i++)
{
for (int j=0; j<=30; j++)
{
if (b[i][j]==0)
st.insert(j);
}
if (st.size()==31) // 重置
{
ans++;
st.clear();
}
}
ans = max(ans, 1ll); // 担心整体与运算>0导致ans=0
cout<<ans<<endl;
return;
}C.Vampiric Powers, anyone?
算法本质
思维、数据结构
题目大意
给定长度n的a[]信息，现在可以对其进行若干次操作：
- 选择
l使得x = a[l] ^ a[l+1] ^ ... a[n]
将x放入a[]末尾，使得其长度+1
输出最大化操作后a[]的最大值。
n <= 1e5
a[i] <= 2^8思路推演
首先抽象操作，设前两次操作分别选择了l1 l2，可以发现，a[n+1]的范围是l1~n，a[n+2]的范围是l1~l2（或l2~l1）。
以此类推，a[n+1]和a[n+2]可以看作一起，范围是l2~n。
所以后面制造出来的数的实质是：区间异或和。
其题目的本质是最大区间异或和。
但是数据范围给的耐人寻味，显然存在某种暴力之法。
思路推演 - 暴力
最基本的暴力是O(n^2^)的，即每次遍历时确定r，然后遍历l去获取不同区间的值。
但是由于其值上限只有256，所以其至多有256种情况，可以用256*n的复杂度搞定。
思路推演 -
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
inline void solve()
{
cin>>n;
rep(i,1,n) cin>>a[i];
set<int> st;
int res=0, ans=0;
st.insert(0); // 0下标的异或值
for (int i=1; i<=n; i++)
{
res ^= a[i]; // res表示[1~i]的异或和
for (int x:st) // 遍历前面区间的可能性——至多256种情况
ans = max(ans, res^x);
st.insert(res);
}
cout<<ans<<endl;
return;
}D.Professor Higashikata
算法本质
思维
题目大意
给定01字符串s，指定了m个区间，接下来会有q次询问，每次询问会翻转某位字符信息，玩家可以执行若干次操作：（并不赋值给下一次s，假设性操作）
- 交换某2个字符位置
操作后需要保证：
- 根据指定的
m个区间截取s生成子串t(1) t(2) ... t(m)，再顺序连接组成新01子串t，使得t的字典序尽可能大
输出每次询问的最小操作数。
思路推演
既然是使得t的字典序大，观察给出m个区间，可以对s的下标进行权重的排序，即先给出的下标权重更大。
这里就涉及一个多区间修改的问题，设立R[]来表示右侧未被权重赋值的下标，配合类似并查集find()，能够较好应对。
能被赋予权重的下标数目可能达不到n，这里设为len表示，用num1表示当前s中1的数目，会有2种情况：
num1 >= len
则赋权下标可以全修改为1，计算赋权下标中为0的数目即可。num1 < len
记录赋权下标中前s前num1下标为0的数目即可。
可以看到的是，这部分是单点修改，区间查询，暴力一点的话，用树状数组可以直接搞定，复杂度为log。
当然，这里的区间查询之间的变化至多为1，所以也可以通过一些技巧避开树状数组，但是想要降低复杂度还是比较难。（也能降低，但是写起来比较麻烦）
这里选择用树状数组，检查一下，需要原下标到新下标的映射。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
// 差分树状数组忽略
int R[maxn], vis[maxn]; // R[i]需要赋值为i+1
int find(int x) // 找到右边（含自己）第一个未被遍历的
{
if (vis[x]==0) return x;
return R[x] = find(R[x]);
}
inline void solve()
{
int q, num1=0, len=0; // num1表示s中1的数目，len表示赋权的下标数目
cin>>n>>m>>q>>s;
s = " " + s;
for (int i=1; i<=n; i++)
{
R[i] = i+1;
num1 += s[i]=='1';
}
map<int, int> mp; // 旧id-->新id（新id越小，说明权重越高）
while (m--)
{
int l, r;
cin>>l>>r;
for (int p=find(l); p<=r; p=find(p))
{
vis[p] = 1;
mp[p] = ++len; // 更新mp
add(len, len, s[p]=='1'); // 树状数组依照新id建立，因为len<=n，所以长度给n没问题
}
}
while (q--)
{
int x, val;
cin>>x;
if (s[x]=='1')
s[x]='0', val=-1;
else
s[x]='1', val=1;
num1 += val;
if (mp.count(x)) // 说明有对应的新id
add(mp[x], mp[x], val);
int r=min(len, num1); // 检查树的范围[1~r]中0的个数
int ans = r - getsum(1, r);
cout<<ans<<endl;
}
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
F.The Boss's Identity
算法本质
思维
题目大意
给定无限长数组a[]前n个元素信息，其后面元素的大小定义：
a[i] = a[i-n] | a[i-n+1]（i>n）
接下来有q次询问，每次询问给出x，找到大于x的a[]种的最小下标。（无则返回-1）
前缀知识
以或运算为例，长度n、大小范围0~2^m-1的a[]的区间异或和至多存在n*m个值。
先确定r，遍历l，这是个以r为右端点后缀异或和，显然至多有m个不同值。
存在n个这样的r，至多为n*m个值。（实际严格小于这个值）不仅或运算，与运算（看作0的或运算）、gcd（看作未取素数的或运算）同理。
思路推演
手动模拟n=5情况：（a1隐藏）
| 长度 | a2结尾 | a3结尾 | a4结尾 | a5结尾 |
|---|---|---|---|---|
| 1 | a2 | a3 | a4 | a5 |
| 2 | a1~a2 | a2~a3 | a3~a4 | a4~a5 |
| 3 | a5~a2 | a1~a3 | a2~a4 | a3~a5 |
| 4 | a4~a2 | a5~a3 | a1~a4 | a2~a5 |
| 5 | a3~a2（全部） | a4~a3（全部） | a5~a4（全部） | a1~a5（全部） |
可以发现的是，后面的元素实际上是前面元素的区间或结果，所以从区间的角度思考。
结合前缀知识，一个显然的想法是，将这所有区间或至多nlog(1e9)个值取出来，按编号排序，再删去某些点保证其严格递增（删除的点总是存在更优解替代）。
那应该如何取出来呢，思考单个元素的贡献，考虑这是位运算，思考单个元素的单个二进制的贡献。
我们假设确立a[i]为左端点，其二进制第一位是1，r不断向右延申（注意这里相当于是环形的），首先当r=l时，其对自身的[l,l]区间二进制第一位做出了贡献，接着当r>l时，其对[l, r]二进制第一位做出贡献。
当然，前提是[l+1, r]的所有数都没有对其二进制第一位做出贡献。
如果发现了在此之前有其他元素先于其做出贡献了，则停止（因为后面做出贡献的时间都是更晚的，存在更优解替代）。
在记录这些贡献时，以r为key值来记录，这样就可以得到了r --> 每个二进制位为1的时间点，大概是这样的数据：tim[r][j]=len所有右端点为r的区间，第j位二进制数为1的贡献，最早记录来自于长度为len时（即由r-len+1这个左端点贡献）。
我们可以据此每个右端点写出31个{出现id + 异或和值}，共计n * 31个值，排升序，然后遍历删去某些点保证id和值都严格升序，将值作为检索，之后对q次询问二分查找。
注意看模拟的图，a1结尾的只有其自身一个，写下标的时候请注意
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], b[maxn][40]; // b[i][j]:a[i]的第j为二进制数
int tim[maxn][40]; // tim[r][j]=len：以r为右端点的区间，第j位二进制为1的首先贡献是r-len+1的左端点
int er[40]; // 记录二进制值，方便用
inline void solve()
{
cin>>n>>m;
for (int i=1; i<=n; i++)
{
int x;
cin>>x;
a[i] = x;
for (int j=0; j<=30; j++)
{
b[i][j] = x%2; // 二进制位记录
x /= 2;
tim[i][j] = 0; // 顺便清洗一下tim[][]
}
}
for (int l=1; l<=n; l++)
{
for (int j=0; j<=30; j++)
{
if (b[l][j]==0) continue;
int len=1;
tim[l][j] = len; // 自己对自己的贡献
for (int r=l%n+1; r!=l; r=r%n+1) // 数学推论，这里不会T
{ // 这里注意别让r>n了
if (b[r][j]==1) break; // 之后的地方，用r做左端点是更优解，所以break
tim[r][j] = ++len;
}
}
}
vector<pair<int, int>> v1, v2; // {id， 值} v1记录n*m个，只能保证id递增，v2清洗v1，保证id、值都递增
v1.push_back({1, a[1]}); // a[1]特殊处理
for (int i=2; i<=n; i++)
{
map<int, vector<int>> cod; // cod[len]={a, b, c}：r-len+1的左端点首先贡献了第a b c二进制位的值
for (int j=0; j<=30; j++)
{
if (tim[i][j]==0) continue; // 说明第j位二进制都没有，忽略
cod[tim[i][j]].push_back(j);
}
int val=0;
for (auto it:cod)
{
for (int x:it.second) // 遍历这些二进制位，把值加入val
val += er[x];
int len=it.first, idx=(len-1)*(n-1)+i; // 计算id
v1.push_back({idx, val});
}
}
sort(v1.begin(), v1.end()); // 以idx排序
// 清洗v1，保证id、值都递增，放置v2
for (auto [idx, val]:v1)
{
if (v2.size()==0 || val>v2.back().second)
v2.push_back({idx, val});
}
// v2放到mp中，以值为key值方便二分查找
map<int, int> mp;
for (auto [idx, val]:v2)
mp[val] = idx;
// 正式开始询问
while (m--)
{
int x;
cin>>x;
auto it = mp.upper_bound(x); // 第一个>x的下标
int ans=-1;
if (it!=mp.end()) // 说明没有比x大的值，输出最后一个
ans = it->second;
cout<<ans<<endl;
}
return;
}
inline void solve_init()
{
er[0] = 1;
for (int i=1; i<=30; i++)
er[i] = er[i-1]*2;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)