答答题sol
本可看错题了搞了半天我不行了。
完全图 \(i\to j\) 的边权是 \(|2^i-2^j|\)，贡献是 \(|s_i-s_j|\)，要求边权单调递增的路径的最大贡献和。
要求边权单调递增又边权严格不相等，那么边两两之间的前后顺序一定，设 \(dis_u\) 表示以 \(u\) 结尾的最长路，可以考虑按照边权从小到大去取边更新。问题在于因为空间限制边存不下来，氮素考虑到 \(2^i\) 量级差很大直接先枚举 \(i=1\to n\) 再枚举 \(j=i-1\to 1\) 就单调惹，严谨地说 \(2^i>2^i-2^j\geq 2^{i-1}\)。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=5005, inf=1e13;int T, n, s[N], tag[N], f[N], Ans;void mian() {cin >> n, Ans=-inf;up(i,1,n) f[i]=0;up(i,1,n) cin >> tag[i];up(i,1,n) cin >> s[i];up(i,1,n) dn(j,i-1,1) if(tag[i]!=tag[j]) {int fi=f[i], fj=f[j];f[i]=max(f[i],fj+abs(s[i]-s[j]));f[j]=max(f[j],fi+abs(s[i]-s[j]));}up(i,1,n) Ans=max(Ans,f[i]);cout << Ans << '\n';
}signed main() {freopen("sol.in","r",stdin);freopen("sol.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> T;while(T--) mian(); return 0;
}
金币coin
嗯大概就是 \(1+ki\) 看起来很不顺眼吧不妨令编号变成 \(0,\dots,n-1\)，这样子每一轮去掉 \(k\) 的倍数位置上的人，所以一轮的位置变化形如 \(x\to x-\lfloor \frac{x}{k}\rfloor-1\)。然后有一个观察就是只有 \(ik\) 和 \(ik-1\) 这样变化之后的值相同。
正着推很难想想怎么倒过来，对于 \(y \to x\) 有 \(y-\lfloor \frac{y}{k}\rfloor-1=x\)，考虑到相同的值只有两个直接乘出来取小的就可以惹，嗯对就是 \(\frac{xk}{k-1}+1\to x\)，注意到暴力可以做轮数不多的就是 \(k\leq \sqrt m\) 的了，后面只用考虑怎么做 \(k>\sqrt m\)。
\(k>\sqrt m\) 的话显然 \(\lfloor\frac{x}{k}\rfloor\leq \sqrt m\) （其实带等号是xp），不妨考虑将增量相等的放在一起做，从小到大考虑增量 \(i\) 要加 \(Ans\) 次，只需要考虑一边的不等式 \(\lfloor\frac{x+Ans\times i}{k}\rfloor+1=i\)，至少有一个 \(Ans\leq \frac{(i-1)k-x}{i}\)，这个时候我们会困惑要是算出来 \(k|x+Ans\times i\) 怎么办惹，氮素注意到尽量多加 \(ik-1\) 肯定比 \(ik\) 优先就不困惑惹。
最后就是 lgj oj 对我来讲有点卡常，可以调 \((k=2)\sqrt m\) 为界限，再加上火车头。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;int T, n, m, k;void mian() {cin >> n >> k, m=sqrt(n)/2;if(k<=m) {int now=0, cnt=0;__int128 p;while((p=(__int128)now*k/(k-1)+1)<n) {if(++cnt>1e7) {assert(0);}now=p;}cout << now+1 << '\n';}if(k>m) {int now=0;up(i,1,n/m) {int l=(n-now+i-1)/i-1, r=(i*k-now+i-1)/i-1;if(l<r) now+=i*l; else now+=i*r;}cout << now+1 << '\n';}
}signed main() {freopen("coin.in","r",stdin);freopen("coin.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> T;while(T--) mian();return 0;
}