2023.2.27 日寄
一言
\(~~~~\) 旦逢良辰，顺颂时宜。——《诗经》
模拟赛
多线并行
题意
\(~~~~\) 每个东西占的空间为 \(a_i\) ，总容量为 \(m\)，第 \(i\) 件物品需要用 \(a_i\) 的时间浏览，用 \(1\) 的时间删除，删除完全完成后才释放空间，任何时候都只能浏览一个东西，但同时可以删除东西。求最小用多少时间把所有东西都浏览且删除。
\(~~~~\) \(1\leq n\leq 10^6,1\leq a_i\leq m\leq 10^9\).
题解
\(~~~~\) 注意到可以节约时间仅在于删除东西和浏览东西的重叠，那我们考虑什么情况下可以重叠：在删除 \(a_i\) 时浏览一个空间在 \(m-a_i\) 以内的物品，显然这个值越大越好，所以我们在 set 内直接 upper_bound 即可。
\(~~~~\) 而显然对于每个物品只要能重叠就必定重叠，因为你不重叠省下来也最多只能再满足一个，显然不优。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
ll Ans;
int arr[200005];
multiset <int> S;
int main() {
// freopen("multithreading.in","r",stdin);
// freopen("multithreading.out","w",stdout);
int T,n,m;read(T);
while(T--)
{
read(n);read(m); S.clear(); Ans=0;
for(int i=1;i<=n;i++) read(arr[i]),Ans+=arr[i]+1,S.insert(arr[i]);
while(!S.empty())
{
int u=*prev(S.end()); S.erase(prev(S.end()));
while("I am an idiot.")
{
auto it=S.upper_bound(m-u);
if(it==S.begin()) break;
it--; u=*it,Ans--,S.erase(it);
}
}
printf("%lld\n",Ans);
}
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
也就是找到最多后继使得可以同时进行
那么贪心地每个点去找最大的可以匹配的后继点即可。
*/
空当接球
题意
\(~~~~\) 给出 \(n\) 堆球，每堆球初始都在 \([1,m]\) 之内。每次操作可以选择不同的 \(i,j\) 满足 \(a_i \geq a_j\)，则令 \(a_i' \leftarrow a_i-a_j\),\(a_j'\leftarrow 2a_j\)。请构造 \(8\times 10^5\) 内操作，使得最后只有最多两堆球（两个数为 \(0\)）。
\(~~~~\) \(1\leq n\leq 3\times 10^5,1\leq m\leq 10^{10}\).
题解
\(~~~~\) 很神仙的题。
\(~~~~\) 考虑对于较少堆的操作是左移 \(1\) 为，对于较多堆的操作，如果最开始最低位和较少堆是一样的，那我们把这两个操作过后最低位就是一样的。因此我们可以考虑按位开始考虑。
\(~~~~\) 那我们建出Trie树（从低到高建），注意到 \(a,b\) 从最低位开始相同的连续最多，那最低位的升高就越多，这样可以省下来更多的操作。所以我们从低位开始操作，不停往 \(0\) 儿子移动，同时操作 \(1\) 儿子，从底到顶合并，合并的LCA深度越深，那显然升位就越多。
\(~~~~\) 当然这样就只剩 \(\mathcal{O(\log n)}\) 的数了，剩下的随便乱搞合并应该也能过，当然还是介绍一下正解。
\(~~~~\) 对于 \(a<b<c\) 的三个数，我们想一个快速清空某一个的方法。令 \(t=\lfloor \frac{b}{a} \rfloor\) ，把 \(t\) 的二进制位从低到高枚举，当某位为 \(0\) 时操作 \((a,c)\) ，否则操作 \((b,c)\)，显然过程中始终有 \(a\leq c\)，操作完成后 \(b \leftarrow b \bmod a\)，这样最小值是变小了的。而假设 \(b\) 最终均匀随机落在 \([0,a)\) 内，最终应该很快就能清零。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct node{
ll Val,id;
node(){}
node(ll V,ll Id){Val=V,id=Id;}
}P[300005];
vector <PII> op;
void OP(ll p,ll q,bool Ins);
struct Trie{
ll ch[30000005][2],tot;
vector <ll> V[30000005];
Trie(){tot=1;}
void Insert(ll Val,ll id)
{
ll now=1;
for(ll i=0;i<=50;i++)
{
ll Bit=(Val>>i)&1;
if(!ch[now][Bit]) ch[now][Bit]=++tot;
now=ch[now][Bit];
}
V[now].push_back(id);
}
ll Solve(ll now)
{
if(!now) return 0;
if(V[now].empty())
{
ll u=Solve(ch[now][0]),v=Solve(ch[now][1]);//剩下一个
if(!u||!v) return u|v;
OP(u,v,1);
return 0;
}
ll Fi=-1,Se=-1;
for(ll qwq=0;qwq<(ll)V[now].size();qwq++)
{
if(!(~Fi)) Fi=V[now][qwq];
else
{
Se=V[now][qwq];
OP(Fi,Se,1);
Fi=Se=-1;
}
}
return Fi==-1?0:Fi;
}
void dfs()
{
ll now=1;
while(now) Solve(ch[now][1]),now=ch[now][0];
}
}Trie;
void OP(ll p,ll q,bool Ins=true)
{
if(P[p].Val<P[q].Val) swap(p,q);
P[p].Val-=P[q].Val; P[q].Val<<=1;
op.push_back(mp(P[p].id,P[q].id));
if(Ins&&P[p].Val) Trie.Insert(P[p].Val,P[p].id);
if(Ins&&P[q].Val) Trie.Insert(P[q].Val,P[q].id);
}
set<PII>S;
void Print()
{
printf("%lld\n",(ll)op.size());
for(ll i=0;i<(ll)op.size();i++) printf("%lld %lld\n",op[i].first,op[i].second);
exit(0);
}
ll arr[500005];
int Del(int ind1,int ind2,int ind3)
{
while("I am an idiot.")
{
if(!P[ind1].Val) return ind1;
if(!P[ind2].Val) return ind2;
if(!P[ind3].Val) return ind3;
if(P[ind1].Val>P[ind2].Val) swap(ind1,ind2);
if(P[ind2].Val>P[ind3].Val) swap(ind2,ind3);
if(P[ind1].Val>P[ind2].Val) swap(ind1,ind2);
ll V=P[ind2].Val/P[ind1].Val;
for(int B=0;V>>B;B++)
{
if((V>>B)&1) OP(ind1,ind2,0);
else OP(ind1,ind3,0);
}
}
}
int main() {
// freopen("ball.in","r",stdin);
// freopen("ball.out","w",stdout);
ll n,m;
read(n);read(m);
for(ll i=1,x;i<=n;i++)
{
read(x);P[i]=node(x,i);
Trie.Insert(x,i);
}
Trie.dfs();int cnt=0;
for(ll i=1;i<=n;i++) if(P[i].Val) P[++cnt]=P[i];
vector <int> Tmp;
for(int i=1;i<=cnt;i++)
{
Tmp.push_back(i);int res;
if(Tmp.size()==3)
{
int T1=Tmp[0],T2=Tmp[1],T3=Tmp[2];
res=Del(Tmp[0],Tmp[1],Tmp[2]);
Tmp.clear();
if(res==T1) Tmp.push_back(T2),Tmp.push_back(T3);
if(res==T2) Tmp.push_back(T1),Tmp.push_back(T3);
if(res==T3) Tmp.push_back(T1),Tmp.push_back(T2);
}
}
Print();
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
*/
列序号括
题意
\(~~~~\) 给出一个括号串，进行若干次（可以为 \(0\)）次操作，每次操作允许删除 \(s_i,s_j\) 满足 \(i<j\) 且 \(s_i='(',s_j=')'\)。求最后字典序最小的括号串。
\(~~~~\) \(1\leq |s|\leq 10^6\).
题解
\(~~~~\) 考场写了【九转大肠已删除】 一样的代码，然后被强强组题人卡到40，众生平等，狗门！蛋门！
\(~~~~\) 考虑一个性质，如果删了一个 \((i,j)\) 以内的括号，那中间的必定要跟着一起删，证明：
\(~~~~\) 如果中间夹了一个 ( 那删除这个 ( 显然可以使得更多的 ( 往前靠。如果夹了一个 ) 那删除这个 ) 可以使得 ) 往后延。综上所述，每次删肯定删的都是连续段。
\(~~~~\) 那我们就可以写一个 \(\mathcal{O(n^2)}\) 的 dp 了：\(dp_{i}\) 表示从 \([i,n]\) 字典序最小的串，\(to_i\) 表示与 \(i\) 位置上的左括号匹配的右括号，那么：
\(~~~~\) 若 \(to_i\) 存在，则 \(dp_{i}=\min(dp_{to_i+1},s_i+dp_{i+1})\) ，否则 \(dp_{i}=s_i+dp_{i+1}\)。根据上面的结论显然正确。
\(~~~~\) 现在优化这个dp：我们需要做的是：可持久化数据结构，支持在某个版本前加入字符，或比较两个版本的字典序（也即比较LCP），主席树？\(\mathcal{O(n \log^2 n)}\) ，危。
\(~~~~\) 我们来考虑倍增，\(f_{i,j}\) 表示从 \(i\) 开始的 \(dp\) 往后 \(2^j\) 个位置到哪里，\(Hash_{i,j}\) 表示从 \(i\) 开始的 \(dp\) 往后 \(2^j\) 个位置的Hash。在每个位置 \(\mathcal{O(\log n)}\) 维护上述两个东西，然后对每个位置LCP搞搞就好了。
代码
查看代码
#include <bits/stdc++.h>
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
const int MOD=998244353,base=233;
char S[1000005],f[1000005][22];
int n,Sta[1000005],Top,To[1000005],p[1000005][22],Hash[1000005][22],Pow[1000005],nxt[1000005];
int main() {
scanf("%s",S+1); n=strlen(S+1); Pow[0]=1;
for(int i=1;i<=n;i++) Pow[i]=Pow[i-1]*base%MOD;
for(int i=1;i<=n;i++)
{
if(S[i]=='(') Sta[++Top]=i;
else if(Top) To[Sta[Top--]]=i+1;
}
p[n+1][0]=nxt[n+1]=n+1;
for(int i=n;i>=1;i--)
{
p[i][0]=nxt[i+1]; Hash[i][0]=S[i],nxt[i]=i;
for(int j=1;j<=20;j++)
{
p[i][j]=p[p[i][j-1]][j-1];
Hash[i][j]=(Hash[i][j-1]+1ll*Hash[p[i][j-1]][j-1]*Pow[1<<(j-1)]%MOD)%MOD;
}
if(To[i])
{
int x=i,y=nxt[To[i]];
for(int j=20;~j;j--)
if(p[x][j]&&p[y][j]&&Hash[x][j]==Hash[y][j]) x=p[x][j],y=p[y][j];
if(y==n+1||S[x]>S[y]) nxt[i]=nxt[To[i]];
}
}
int x=nxt[1];
while(x<=n) putchar(S[x]),x=p[x][0];
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
)(()(())))
)((())))
)((()())))
)((()())))
*/
可爱路径 / 「集训队互测2023 Round 6」>.<
没补，对不起
鲜花
\(~~~~\) 今天开始算是正式准备演讲吧。找到班主任给自己把ddl定死了。
\(~~~~\) 怎么说呢？虽然我很不想做，但是去打破comfort zone其实对我而言不是一件坏事。毕竟太内倾了也不是很好嘛。而且我其实对不同的人讲的不同的内容还挺感兴趣的 （涉猎广泛但不精本人了
\(~~~~\) 而且谁会不喜欢能对一件事侃侃而谈，畅聊自己意见的人呢？（星星眼
\(~~~~\) 就是班级氛围总是太压抑了？或者说是：大家都被教育 “完美” 而非 “勇敢” 了，说不清这是社会和学校希望如此还是我们本就被磨平了意气。虽然说确实我们也没有太多试错的机会，但作为高中这个试错机会还相对较多的时间其实多去涉猎一点找到自己的方向没什么大问题吧。
\(~~~~\) 还得思维导图，再见。
标签：ch,leq,read,ll,2023.2,27,now,dp From： https://www.cnblogs.com/Azazel/p/17162312.html