这篇 blog 在我的博客后台躺了好几天了，只不过今天才记起来发。
种树 (plant)
首先看到因数个数，想到在质因数分解后的序列上考虑问题。进一步观察，每个不同质因子的贡献是独立的。
也就是说，我们单独考虑某一个质因子对答案的贡献，是这样的问题：
给长度为 \(n\) 的序列 \(a\) 和一个数 \(w\)，每次操作你可以选择一个 \(i\)，令 \(a_i\gets a_i+1\)，可以重复选择同一个位置。至多操作 \(w\) 次，最大化 \(\prod\limits_{i=1}^n a_i\)。
这是一个经典问题，容易证明每次贪心操作最小值是最优的。数据范围放了 \(O(n^2)\) 通过，所以怎么实现都行。
#define int long long
const int N=1e4+5,mod=998244353;
int n,w;
int a[N],cnt[N],ans=1;
priority_queue<int,vector<int>,greater<int> >q;
il void solve(int x,int sum)
{
for(int i=1;i<=n;i++)
{
cnt[i]=1;
while(a[i]%x==0) cnt[i]++,a[i]/=x;
q.push(cnt[i]);
}
while(sum)
{
int x=q.top(); q.pop();
q.push(x+1),sum--;
}
for(int i=1;i<=n;i++) ans=ans*q.top()%mod,q.pop();
}
signed main()
{
n=read(),w=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=2;i*i<=w;i++)
if(w%i==0)
{
int now=0;
while(w%i==0) now++,w/=i;
solve(i,now);
}
if(w>1) solve(w,1);
for(int i=1;i<=n;i++)
{
for(int j=2;j*j<=a[i];j++)
{
int now=1;
while(a[i]%j==0) a[i]/=j,now++;
ans=ans*now%mod;
}
if(a[i]>1) ans=ans*2%mod;
}
printf("%lld\n",ans);
return 0;
}
汪了个汪 (woof)
感觉这个构造挺人类智慧，可能脑电波一下跟出题人对上就会了。
不会基于严谨理论的做法，大致阐述一下猜到这个东西的过程吧。
首先，我们知道有 \(\dfrac{n(n-1)}{2}\) 个横向相邻数对，\(\dfrac{n(n-1)}{2}\) 个本质不同二元组。这两个数量是相等的，也就是说每种本质不同二元组在棋盘中恰好出现了一次。
那或许可以尝试把这些二元组进行分类，按照相同的类别来摆放。
进一步瞎猜，发现：两个元素差为 \(1\) 的有 \(n-1\) 对，差为 \(2\) 的有 \(n-2\) 对，同理，差为 \(n-1\) 的有 \(1\) 对。我们把这些数对分成了大小分别为 \(1,2,\dots,n-1\) 的组。
然后你发现这和棋盘上每行的相邻棋子数正好对上了！
但是没做完，因为 \((1,4),(2,5),(3,6),\dots\) 这堆东西显然没法放到一行里。再继续找能和这个分组形式对上的东西。
考虑转一下方向，棋盘每列能放下的二元组数量同样满足这个性质。
也就是说，我们试图在第 \(1\) 列放 \(n-1\) 个差为 \(1\) 的数对，第 \(2\) 列放 \(n-2\) 个差为 \(2\) 的数对，以此类推。
知道了大致方向，我们再考虑对于每一行的构造，设这一行有 \(n\) 个数。我们要让其形如第一对差为 \(1\)，第二对差为 \(2\)，并始终在 \([1,n]\) 范围内，不难想到加减交替构造。
设开头为 \(x\)，则这一行的值为：
又因为已知每行开头的数不相同，我们依次枚举每个 \(x\)，重复构造上述序列直到超出范围。例如 \(n=7\)，可以写出：
把它们按长度顺序排序，即为答案。
时间复杂度 \(O(n^2)\)。
const int N=4005;
int n,t,a[N][N];
int main()
{
n=read(),t=read();
for(int i=1;i<=n;i++,cout<<endl)
{
int st=(i&1)?(2*n-i+1)/2:(i>>1);
for(int j=1,len=1;j<=i;j++,len++)
{
cout<<st<<" ";
if(j&1) st+=len; else st-=len;
}
}
return 0;
}
挑战 NPC IV (npc)
Part 1. \(k=1\)
首先考虑 \(k=1\) 的时候怎么做。
考虑最终的位置 \(i\) 会被多少个区间统计到，不难发现它计入贡献的次数是 \(b_i=i(n-i+1)\)。
也就是说问题转化成，令 \(a_i=f(i)\)，\(b_i=i(n-i+1)\)，我们要对 \(a\) 序列指定一个顺序，最小化 \(\sum\limits_{i=1}^n a_i\times b_i\)。
这个问题有显然的贪心，\(a\) 序列升序排序，\(b\) 序列降序排序，对应位相乘即为最小值。证明是容易的：设 \(a<b\) 且 \(c<d\)，有 \((b-a)d>(b-a)c\)，移项即得 \(ac+bd>ad+bc\)。
Part 2. \(n\in [29,10^6]\)
在上述过程中发现这么一个问题，方案本质不同的定义是 \(p\) 不相同，但 \(f(p_i)\) 中有很多数相同。交换它们中的一部分不会使贡献序列改变，但可以使 \(p\) 改变。因此我们估计，在不改变贡献序列的情况下，本质不同的 \(p\) 是相当多的。
考虑估计这个具体数目，\(a\) 序列中大约有 \(\frac{n}{2}\) 个 \(1\)，\(\frac{n}{2^2}\) 个 \(2\)（暂不讨论上下取整的问题），那么我们至少能搞出 $cnt=\prod\limits_{i=1}^{\log_2 n} (\frac{n}{2^i})! $ 种取到最小值的排列。这里没考虑交换 \(b\) 序列的情况，因此实际值会比这更多。
这说明 \(k\le cnt\) 的时候答案都可以取到最小值。写个代码求上面的式子，可以发现 \(n=29\) 的时候 \(cnt\) 就超过了 \(10^{18}\)。也就是说，\(n>29\) 时 \(k\) 为任何值的答案都和 \(k=1\) 相等。
\(O(n)\) 地模拟上述贪心，配合爆搜可以通过前 \(13\) 个点。有 52pts 暴力分，好良心！
Part 3. \(n\in [29,10^{18}]\)
这一部分没有单独的部分分，但我们需要加速贪心的过程。
只要快速求出 \(a\) 序列中每个数的数量，就能找到它们在 \(b\) 序列中对应的连续区间。根据基础位运算知识可以得出值为 \(i\) 的出现次数。
令 \(s(l,r)=\sum\limits_{i=l}^r b_i\)，推式子：
现在这两个序列都能快速计算，我们可以在 \(O(\log n)\) 的时间复杂度内处理单次询问。
Part 4. \(n\le 28\)
看起来即使仅考虑本质不同的 \(a\) 序列，这样的数量依然很多。但是我们发现一条关键性质：这种情况下优美度的值域很小，只有 \(10^4\) 左右。
考虑基于这个进行 dp。进一步观察，\(a\) 序列中至多有 \(5\) 种不同的值。因为优美度已经计入了状态，我们显然只关心它们填了几个，而不关心它们的位置。
故设 \(f_{a,b,c,d,e,sum}\) 表示 \(1,2,3,4,5\) 分别填了 \(a,b,c,d,e\) 个，总优美度为 \(sum\) 的方案数。
转移时枚举当前位填什么数，式子是容易写出的。
这样的有效状态数在 \(n=28\) 时取到上界，大致有 \(16\times 9\times 5\times 3\times 2\times 1.1\times 10^4=4.752\times 10^7\) 种状态。开数组时请注意空间消耗。
结合 Part 3 的做法即可获得 100pts。
#define int long long
const int N=1e6+5,mod=998244353;
int T,n,k;
int f[16][9][5][3][2][11005];
int a[N],b[N],cnt[N],mx=11000,now[6],jc[N];
il int qpow(int n,int k=mod-2)
{
int res=1;
for(;k;n=n*n%mod,k>>=1) if(k&1) res=res*n%mod;
return res;
}
il int S(int x) {x%=mod;return x*(x+1)%mod*(2*x+1)%mod*qpow(6)%mod;}
il int get(int l,int r,int n)
{
if(l>r) return 0;
if(r>n/2&&l<=n/2) return (get(l,n/2,n)+get(n/2+1,r,n))%mod;
if(l>n/2) l=n-l,r=n-r,swap(l,r);
int res=n%mod*((l+r)%mod)%mod*((r-l+1)%mod)%mod*qpow(2)%mod-(S(r)-S(l-1)+mod)%mod;
return (res%mod+mod)%mod;
}
il void solve(int n)
{
int l=1,r=n,res=0;
for(int i=__lg(n)+1;i;i--)
{
int sum=(n>>(i-1))+(n>>(i-1)&1);
int ls=sum/2,rs=sum-ls;
if(l<n-r+1) swap(ls,rs);
(res+=i*get(l,l+ls-1,n+1)%mod)%=mod,(res+=i*get(r-rs+1,r,n+1)%mod)%=mod;
l+=ls,r-=rs;
}
printf("%lld\n",res);
}
signed main()
{
T=read(); jc[0]=1;
for(int i=1;i<=15;i++) jc[i]=jc[i-1]*i;
while(T--)
{
n=read(),k=read();
if(n>28) {solve(n);continue;}
for(int i=1;i<=n;i++) a[i]=1+__lg(i&(-i));
for(int i=1;i<=n;i++) b[i]=i*(n-i+1);
sort(a+1,a+n+1),sort(b+1,b+n+1);
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[a[i]]++;
int Cnt=1;
if(n<=28) for(int i=1;i<=__lg(n)+1;i++) Cnt=Cnt*jc[cnt[i]];
f[0][0][0][0][0][0]=1;
for(now[1]=0;now[1]<=cnt[1];now[1]++)
for(now[2]=0;now[2]<=cnt[2];now[2]++)
for(now[3]=0;now[3]<=cnt[3];now[3]++)
for(now[4]=0;now[4]<=cnt[4];now[4]++)
for(now[5]=0;now[5]<=cnt[5];now[5]++)
{
int sum=0;
for(int i=1;i<=5;i++) sum+=now[i];
if(!sum) continue;
for(int j=0;j<=mx;j++)
{
int i=0;
for(int k=1;k<=5;k++)
{
if(now[k]==0) continue;
if(j-k*b[sum]<0) continue;
now[k]--;
i+=f[now[1]][now[2]][now[3]][now[4]][now[5]][j-k*b[sum]];
now[k]++;
}
f[now[1]][now[2]][now[3]][now[4]][now[5]][j]=i;
}
}
int ans=0;
for(int i=0;i<=mx;i++)
{
ans+=Cnt*f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][i];
if(ans>=k) {printf("%lld\n",i);break;}
}
}
return 0;
}
四暗刻单骑 (mahjong)
Part 1. \(O(nm)\)
先观察题目的一些基本性质。
- 交替摸牌，所以每张牌被谁摸到是固定的。
- 因为游戏过程中每个人手里的两张牌都不会相同（不然就结束了），他们一定不会打出和对手手里一样那张牌。所以最后和牌的方式一定是一个人从牌堆中摸到了和自己一样的牌。
- 再考虑两个人手牌一样的情况，他们任何一人都不能丢掉这张牌，不然对面就赢了。因此这种情况的结局是能够直接判定的：判断下一张相同的牌被谁摸到即可，如果没有就是平局。
那么，一个人想和牌，他的策略一定是从某个时刻开始一直拿着某张牌，直到摸到下张一样的。
考虑某个人一直拿着第 \(i\) 张牌会产生什么效果：
- 如果下一张同色的牌被自己摸到，设它的位置是 \(x\)。那么拿着这张牌的结果是在 \(x\) 时刻胜利。
- 如果下一张同色的牌被对手摸到，对手必然不能把这张牌丢掉。因此双方手牌相同，结局已经确定。
- 再下一张被自己摸到，但因为从 \(x\) 时刻开始对面就没有翻盘的机会了，我们记它的结果是在 \(x\) 时刻直接胜利。
- 被对手摸到，记它的结果是在 \(x\) 时刻失败。
- 否则是在 \(x\) 时刻达成平局。
那么我们可以在序列上模拟这个过程，如果牌的效果是胜利就选择胜利更早的；失败就选择失败得更晚的，因为可能后面能摸到胜利的牌而翻盘。如果当前已经到达了某个人手里的牌的胜利或失败时刻，则判定答案。
然而直接这样搞并不正确，可怜的樱雪喵写假了一天也没想明白哪里不对。
考虑这样的一组数据：牌堆依次为 \(3,1,4,3,4\)，初始手牌为 \(1,2\)。
Alice 在第一轮是否把牌换成 \(3\) 都是平局，她更希望等到后面胜利。而 Bob 如果寄希望于后面胜利，不选择把 \(2\) 换成 \(1\)，他最后只能失败。而如果他的目标是平局，他会摸走牌堆中的 \(1\)，并成功平局。
这启发我们思考一个问题：存在一些情况，如果一个人目标是取得胜利，他就输了；但如果他的目标仅仅是保住平局，却能成功阻止对面赢。这是不能直接贪心判断的。
考虑用如下做法改变他们的目标：先钦定平局算 Alice 赢，这等价于 Alice 的目标是保住平局。如果此时 Bob 仍然能赢，才算作 Bob 必胜。反之同理。
如果正反都不满足条件，则说明存在一种方式使本来要输的人保住平局，答案为平局。
细节想不清楚的话很容易写假，可以参考代码理解。
const int N=2e5+5;
int id,n,m,k,a[N],flag;
vector<int> pos[N];
il int find(int x,int l,int r)
{
auto qwq=upper_bound(pos[x].begin(),pos[x].end(),l);
if(qwq==pos[x].end()||(*qwq)>r) return -1;
return *qwq;
}
il int getw(int x,int l,int r,int fg=0)
{
int qwq=find(x,l+fg,r);
if(qwq==-1) return (l&1)==flag?n+1:-n-1;
if((qwq&1)==(l&1)) return qwq;
int nqwq=find(x,qwq,r);
if(nqwq==-1) return (l&1)==flag?qwq:-qwq;
else if((nqwq&1)==(l&1)) return qwq;
else return -qwq;
}
il int solve(int x,int y,int l,int r)
{
if(x==y)
{
int nxt=find(x,l-1,r);
if(nxt==-1) return flag?1:-1;
else if((nxt&1)==(l&1)) return 1;
else return -1;
}
int wx=getw(x,l-2,r,1),wy=getw(y,l-1,r);
for(int i=l;i<=r;i++)
{
if(wx==i) return 1; if(wy==i) return -1;
if(-wx==i) return -1; if(-wy==i) return 1;
if(x==y)
{
int nxt=find(x,i-1,r);
if(nxt==-1) return flag?1:-1;
else if((nxt&1)==(l&1)) return 1;
else return -1;
}
if((i&1)==(l&1))
{
int nxt=getw(a[i],i,r);
if(nxt>0&&(nxt<wx||wx<0)) wx=nxt,x=a[i];
else if(nxt<0&&wx<0&&nxt<wx) wx=nxt,x=a[i];
}
else
{
int nxt=getw(a[i],i,r);
if(nxt>0&&(nxt<wy||wy<0)) wy=nxt,y=a[i];
else if(nxt<0&&wy<0&&nxt<wy) wy=nxt,y=a[i];
}
}
return flag?1:-1;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]].push_back(i);
while(m--)
{
id++;
int x=read(),y=read(),l=read(),r=read();
flag=1; int res1=solve(x,y,l,r);
flag=0; int res0=solve(x,y,l,r);
if(res1==-1) printf("B\n");
else if(res0==1) printf("A\n"); else printf("D\n");
}
return 0;
}
Part 2. \(O((n+m)\log n)\)
假设每张牌的结局是已经确定的，依旧不容易快速地维护答案，因为输了要尽可能晚输，赢了又要尽可能早赢。
我们继续观察性质。
注意到，到达某张手牌判定答案的时刻时，被判定的一定是赢的那张牌。换句话说，一个人必然不会一直拿着一张输的牌，直到因为这张牌而输掉。
考虑证明这个结论。假设 Alice 现在手里拿着一张输的牌，并且下一轮就要输了；这时候她又摸到了另一张要输的牌。因为这两张牌不同，它们输的位置也一定不同。那么新摸的这张牌一定输得比原来那张要晚。每当出现这种情况 Alice 就换牌，即可保证始终不因为输的牌而输掉。
当然这里要特判拿着初始手牌在第一轮就输掉的情况，因为此时他们没有选择权。
因此我们只需判断一段区间内最早赢的牌被谁摸到了。
考虑离线询问，从左向右扫描 \(r\)。对于在 \(i\) 位置的牌，它的贡献只与它下一张相同的牌、下下张相同的牌是否在区间内有关。因此一张牌的贡献只会改变 \(3\) 次，可以每次修改暴力求新值。
那么对于每个询问，最早赢的牌即为区间内最小值所在的位置，判断这张牌位置的奇偶性即可。
我们需要一个数据结构支持单点修改，区间查询最小值和最小值的位置。这里使用线段树维护。
const int N=2e5+5,inf=1e9;
int id,n,m,k,a[N],flag;
vector<int> pos[N];
il int find(int x,int l,int r)
{
auto qwq=upper_bound(pos[x].begin(),pos[x].end(),l);
if(qwq==pos[x].end()||(*qwq)>r) return -1;
return *qwq;
}
il int getw(int x,int l,int r,int fg=0)
{
int qwq=find(x,l+fg,r);
if(qwq==-1) return inf;
if((qwq&1)==(l&1)) return qwq;
int nqwq=find(x,qwq,r);
if(nqwq==-1) return (l&1)==flag?qwq:inf;
else if((nqwq&1)==(l&1)) return qwq;
else return inf;
}
struct segtree
{
struct node{int mn,pos;} tr[N<<2];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid (l+r>>1)
il node pushup(const node &l,const node &r)
{
if(l.mn<r.mn) return l;
else return r;
}
void build(int x,int l,int r)
{
if(l==r) {tr[x]={inf,l};return;}
build(ls,l,mid),build(rs,mid+1,r);
tr[x]=pushup(tr[ls],tr[rs]);
}
void upd(int x,int l,int r,int p,int k)
{
if(l==r) {tr[x]={k,l};return;}
if(p<=mid) upd(ls,l,mid,p,k);
else upd(rs,mid+1,r,p,k);
tr[x]=pushup(tr[ls],tr[rs]);
}
node query(int x,int l,int r,int ml,int mr)
{
if(l==ml&&r==mr) return tr[x];
if(mr<=mid) return query(ls,l,mid,ml,mr);
else if(ml>mid) return query(rs,mid+1,r,ml,mr);
else return pushup(query(ls,l,mid,ml,mid),query(rs,mid+1,r,mid+1,mr));
}
}seg;
int ans[2][N];
vector<int> nd[N];
struct node{int x,y,l,r,id;};
vector<node> q[N];
il int calc(int x,int y,int l,int r)
{
if(x==y)
{
int nxt=find(x,l-1,r);
if(nxt==-1) return flag?1:-1;
else if((nxt&1)==(l&1)) return 1;
else return -1;
}
if(y==a[l])
{
int nxt=find(y,l,r);
if(nxt!=-1&&((nxt&1)==(l&1))) return 1;
else if(nxt==-1) return flag?1:-1;
}
int wx=getw(x,l-2,r,1),wy=getw(y,l-1,r);
int ans=min(wx,wy),pos=(wx<wy)?l-2:l-1;
segtree::node qwq=seg.query(1,1,n,l,r);
if(qwq.mn<ans) ans=qwq.mn,pos=qwq.pos;
if(ans==inf) return flag?1:-1;
return ((l&1)==(pos&1))?1:-1;
}
void solve()
{
seg.build(1,1,n);
for(int r=1;r<=n;r++)
{
for(auto x:nd[r]) seg.upd(1,1,n,x,getw(a[x],x,r));
for(auto i:q[r])
{
int x=i.x,y=i.y,l=i.l,r=i.r,id=i.id;
ans[flag][id]=calc(x,y,l,r);
}
}
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]].push_back(i);
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),l=read(),r=read();
q[r].push_back({x,y,l,r,i});
}
for(int i=1;i<=n;i++)
{
int nxt=find(a[i],i,n);
if(nxt==-1) continue;
nd[nxt].push_back(i);
int nnxt=find(a[i],nxt,n);
if(nnxt!=-1) nd[nnxt].push_back(i);
}
for(flag=0;flag<2;flag++) solve();
for(int i=1;i<=m;i++)
{
if(ans[1][i]==-1) printf("B");
else if(ans[0][i]==1) printf("A");
else printf("D");
printf("\n");
}
return 0;
}
祝看到这里的大家 NOIP 2023 RP++ >w<