省流：\(100 + 50 + 45 + 32\)。rk8，喜提前十名中唯一没过t2的。
T1
题意：对于一棵树，记 \(f(i)\) 表示 \(\sum_{1 \leq j \leq n} dis(i,j)\)，其中 \(dis(i,j)\) 表示树上 \(i,j\) 之间的距离。
多测，每次给定一个 \(x\)，你需要找出最小的一个 \(n\)，使得存在一个 \(n\) 个点的树，其上存在两个点 \(u,v\) 使得 \(f(u) - f(v) = x\)，输出 \(n\)。
\(T \leq 10^5,x \leq 10^{18}\)。
对于一颗树，我们选择 \(u\) 为某叶子节点，\(v\) 为树的重心，可以近似找到树的最大能匹配到的 \(x\)，考虑 \(f(v)\) 换根到 \(f(u)\) 的过程，发现每次换到一个节点 \(s\) 时，\(f(s) - f(v)\) 会增加 \(2sz_v - n\)，发现这个值形如 \(1 + 3 + \cdots + (2 \times p - 1)\) 或 \(2 + 4 + \cdots + 2 \times p\)，于是我们可以找出最小的 \(p\) 满足这个值大于等于 \(x\)，稍微处理一下奇偶性就行。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
__int128 val(int x) {
int tmp=(x+1)/2;
if(x&1) return (__int128)tmp*tmp;
else return (__int128)tmp*(tmp+1);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t;
while(t--) {
int x;
cin>>x;
int l=1,r=1e18,ans;
while(l<=r) {
int mid=l+r>>1;
if(val(mid)>=(__int128)x) ans=mid,r=mid-1;
else l=mid+1;
}
if(!(ans&1)&&(x&1)) cout<<ans+3<<'\n';
else cout<<ans+2<<'\n';
}
return 0;
}
T2
可以看这篇题解，讲的很好。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m,k,a[N][N];
struct node {int x,y,z,c;};vector<node> ve;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>k;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>a[i][j];
for(int i=m; i>=1; i--) {
for(int j=2; j<=m-i+1; j++) for(int k=1; k<=n; k++) ve.push_back((node){k,i,j,a[k][i]});
for(int j=i+1; j<=2*i-1; j++) for(int k=1; k<=n; k++) ve.push_back((node){k,j,m-i+1,a[k][i]});
for(int j=m-i+2; j<=m+k; j++) for(int k=1; k<=n; k++) ve.push_back((node){k,2*i-1,j,a[k][i]});
}
for(int i=m+1; i<=m+k; i++) {
for(int j=2; j<=2*m-2; j+=4) for(int k=1; k<=n; k++) ve.push_back((node){k,j,i,i-m});
if((2*m-4)%4!=0) for(int k=1; k<=n; k++) ve.push_back((node){k,2*m-2,i,i-m});
for(int j=1; j<=2*m-1; j++) ve.push_back((node){n+1,j,i,i-m});
}
cout<<ve.size()<<endl;
for(int i=0; i<ve.size(); i++) cout<<ve[i].x<<" "<<ve[i].y<<" "<<ve[i].z<<" "<<ve[i].c<<endl;
return 0;
}
闲话：noip 模拟 t2 放 *3100 构造素质呢/fn
T3
题意：给定一个长为 \(n\) 的序列 \(a\)，\(a\) 中只有 \(0,1,2,-1\)，分别表示石头，布，剪刀和不确定，你需要求出所有替换 \(-1\) 为 \(0,1,2\) 的情况中一个最优出拳策略的得分的和。如果你这局赢了，获得 \(1\) 分，平局不获得，输了获得 \(-10^9\) 分。你必须保证相邻两局出的拳不同。
\(n \leq 2000\)。
首先可以暴搜每个 \(-1\) 取的值，然后设 \(dp_{i,j}\) 表示第 \(i\) 局出了 \(j\) 的最大得分，转移显然，这样我们就得到了一个 \(\Theta(3^nn)\) 的做法。注意到我们求最优的局数的 dp 中对于每个 \(i\)，只有 \(dp_{i,0},dp_{i,1},dp_{i,2}\) 是有用的，所以我们可以把这三个值扔进 dp 里做，设 \(f_{i,x,y,z,o}\) 表示第 \(i\) 局出了 \(o\)，三个值分别为 \(x,y,z\) 的方案数，这样时间复杂度是 \(\Theta(n^4)\)。发现这三个值中只有两个是有用的，因为我一定可以找到一种方案使得没有一局输掉，这跟 \(o\) 有关，时间复杂度降为 \(\Theta(n^3)\)。观察 dp 柿子，发现我们只保留 \(x - y\) 的值也能够正常转移计算答案，这样时间复杂度为 \(\Theta(n^2)\)。具体实现中可以在转移中算出最小值的贡献，最后算出差值的贡献。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005,p=998244353;
int n,a[N],b[N],pw[N],dp[N][N<<1][3],ans=0;
int win[3][3]={
{0,-1,1},
{1,0,-1},
{-1,1,0}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
pw[n+1]=1;
for(int i=n; i>=1; i--) {
pw[i]=pw[i+1];
if(a[i]==-1) pw[i]=pw[i]*3%p;
}
if(a[1]!=-1) dp[1][1+n][a[1]]=1;
else dp[1][1+n][0]=dp[1][1+n][1]=dp[1][1+n][2]=1;
for(int i=1; i<n; i++) {
for(int j=-i; j<=i; j++) {
for(int x=0; x<=2; x++) {
if(a[i]!=x&&a[i]!=-1) continue;
for(int y=0; y<=2; y++) {
if(a[i+1]!=y&&a[i+1]!=-1) continue;
if(win[x][y]==1) {
if(j<0) (ans+=dp[i][j+n][x]*pw[i+2]%p)%=p;
if(j>=0) (ans+=dp[i][j+n][x]*pw[i+2]%p*j%p)%=p;
(dp[i+1][min(j,0ll)+1+n][y]+=dp[i][j+n][x])%=p;
} else if(win[x][y]==0) {
if(j>0) (ans+=dp[i][j+n][x]*pw[i+2]%p)%=p;
(dp[i+1][1-j+n][y]+=dp[i][j+n][x])%=p;
} else {
if(j<=0) (ans+=dp[i][j+n][x]*pw[i+2]%p*(-j)%p)%=p;
(dp[i+1][max(j,0ll)+1+n][y]+=dp[i][j+n][x])%=p;
}
}
}
}
}
for(int i=-n; i<=n; i++) (ans+=abs(i)*(dp[n][i+n][0]+dp[n][i+n][1]+dp[n][i+n][2])%p)%=p;
cout<<ans;
return 0;
}
T4
还不会。
标签：tmp,pw,noip,int,else,leq,模拟,241119,dp From： https://www.cnblogs.com/System-Error/p/18555600