T1
注意到没有限制解决问题次数和顺序，不妨转化为图上问题，两点边 \(u\to v\) 当且仅当 \(tag_i\neq tag_j\)，转移按照边权升序排序即可，观察发现由于边权特殊性，升序其实就是在 \(i\) 递增时，\(j\) 从 \(i-1\) 到 \(1\) 的过程，由于边是双向的要放在一起做，不需要真正算出边权，直接枚举转移即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e3+5;
const LL INF=1e18;
int n,tag[N],s[N];
LL f[N];
int main(){//freopen("sol.in","r",stdin);//freopen("sol.out","w",stdout);int t;scanf("%d",&t);while(t--){LL mx=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&tag[i]);for(int i=1;i<=n;i++)scanf("%d",&s[i]),f[i]=0;for(int i=2;i<=n;i++){for(int j=i-1;j>=1;j--){if(tag[i]==tag[j])continue;LL 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]));mx=max(mx,max(f[i],f[j]));}}printf("%lld\n",mx);}return 0;
}
T2
正向转移是总数 \(n\leftarrow n-\lceil\frac{n}{k}\rceil\)，根据某种神秘理论本质不同 \(\lceil\frac{n}{k}\rceil\) 只有 \(O(\sqrt n)\) 个，因此可以快速计算轮数。反向转移位置 \(z\) 是 \(z\leftarrow z+\lceil\frac{z}{k-1}\rceil\)，根据某种神秘理论本质不同 \(\lceil\frac{z}{k-1}\rceil\) 也只有 \(O(\sqrt n)\) 个，因此在 \(O(T\sqrt n)\) 的时间内可以解决。
另：\(\lceil\frac{a}{b}\rceil=\lfloor\frac{a+b-1}{b}\rfloor\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,k;
int main(){//freopen("coin.in","r",stdin);//freopen("coin.out","w",stdout);int t;scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&k);LL cnt=0,dtn=n;while(dtn>0){LL now=(dtn+k-1)/k;LL buk=(dtn+k-1-now*k)/now+1;cnt+=buk;dtn-=now*buk;}cnt--;LL z=1;while(cnt){LL mns=(z+k-2)/(k-1);LL go=((mns+1)*(k-1)-(z+k-2)-1)/mns+1;if(cnt>=go){cnt-=go;z+=go*mns;}else {z+=cnt*mns;break;}}printf("%lld\n",z);}return 0;
}