Preface
补题，不得不说一边晒太阳一边想题目真的纯在折磨，眼睛要被反光晃瞎了
这场ABCD和F都比较简单，E的话一个关键性质想到了但统计的时候棋差一招，G的话就是纯纯的巧妙，后面两题没看
总体来说这场质量极高，可惜和考试周冲突了没法现场打的说
（不过题目都是丁真题狠狠地好评）
A. Tenzing and Tsondu
显然只要比较两边的总战力大小即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,m,a[N],b[N]; long long sa,sb;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d",&n,&m),sa=0,sb=0,i=1;i<=n;++i) scanf("%d",&a[i]),sa+=a[i];
for (i=1;i<=m;++i) scanf("%d",&b[i]),sb+=b[i];
if (sa>sb) puts("Tsondu"); else if (sa==sb) puts("Draw"); else puts("Tenzing");
}
return 0;
}
B. Tenzing and Books
显然我们可以通过枚举每个书架里取了多少书来做到\(O(n^3)\)的检验
但实际上由于或运算的性质，每个书架中本质不同的数最多只有\(\log n\)个（最少每次选一个\(0\)位变成\(1\)）
因此给所有可能的取值去重后再枚举即可，复杂度\(O(n\log n+\log^3 n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,x,y,pfx[3][N],cnt[3];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j,k; for (scanf("%d%d",&n,&x),i=0;i<3;++i)
{
for (j=1;j<=n;++j) scanf("%d",&y),pfx[i][j]=pfx[i][j-1]|y;
sort(pfx[i],pfx[i]+n+1); cnt[i]=unique(pfx[i],pfx[i]+n+1)-pfx[i]-1;
}
bool flag=0; for (i=0;i<=cnt[0];++i) for (j=0;j<=cnt[1];++j) for (k=0;k<=cnt[2];++k)
if ((pfx[0][i]|pfx[1][j]|pfx[2][k])==x) flag=1; puts(flag?"Yes":"No");
}
return 0;
}
C. Tenzing and Balls
简单DP题，很容易想到设\(f_i\)表示前\(i\)个球最多可以删去多少个球
转移的话显然可以枚举一个\(j<i\)的位置，满足\(a_j=a_i\)，则有\(f_{j-1}+(i-j+1)\to f_i\)
考虑我们只能从和\(a_i\)值相同的地方转移来，因此记\(g_x\)表示所有\(a_j=x\)的位置中\(f_{j-1}-j\)的最大值，转移变为\(g_{a_i}\to f_i\)
复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=1e9;
int t,n,a[N],f[N],g[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),g[i]=-INF;
for (i=1;i<=n;++i) f[i]=max(f[i-1],g[a[i]]+i+1),g[a[i]]=max(g[a[i]],f[i-1]-i);
printf("%d\n",f[n]);
}
return 0;
}
D. Tenzing and His Animal Friends
不太容易看出的最短路题，但手玩一下其实还是很明显的
首先不妨把每个关系看作一条无向带权边，很显然如果\(1,n\)不在一个连通块内则一定inf，因为此时我们可以让除了\(n\)以外的所有动物一起和\(1\)玩
否则说明必然有一些点和\(n\)是有边的，对于那些直接和\(n\)有边的点，它们最多能玩的时间就是它们与\(n\)之间的边的边权
然后这些点之前的点最多能玩的时间呢，很明显就是两条边权的和，然后画画图会发现每个点能玩的时间上限其实就是它到\(n\)的最短路长度
那么要构造答案就很简单了，我们根据能玩的时间种类从小到大来枚举，如果当前点还能玩就拉去玩，否则就没得玩了，具体看代码很好理解
注意处理好所有点到\(n\)的最短路都是\(0\)的情况，刚开始这里没判好卡了好久
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=105,INF=1e18;
int n,m,x,y,z,dis[N][N],t[N],rst[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (scanf("%lld%lld",&n,&m),i=1;i<=n;++i) for (j=1;j<=n;++j) dis[i][j]=INF;
for (i=1;i<=n;++i) dis[i][i]=0; for (i=1;i<=m;++i)
scanf("%lld%lld%lld",&x,&y,&z),dis[x][y]=dis[y][x]=z;
for (k=1;k<=n;++k) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
if (dis[1][n]==INF) return puts("inf"),0;
for (i=1;i<=n;++i) rst[i]=t[i]=min(dis[1][n],dis[i][n]);
sort(rst+1,rst+n+1); int cnt=unique(rst+1,rst+n+1)-rst-1;
for (printf("%lld %lld\n",dis[1][n],cnt-1),i=1;i<=cnt;++i)
{
if (!rst[i]) continue;
for (j=1;j<=n;++j) putchar(t[j]>=rst[i]?'1':'0');
printf(" %lld\n",rst[i]-rst[i-1]);
}
return 0;
}
E. Tenzing and Triangle
好题，首先上来画画图会发现所有三角形之间一定没有交点，否则我们一定可以将它们合并，使得覆盖的点更多而花费相同
然后直接处理的话会不太好做，我们可以先假设对所有点都花费\(c_i\)代价将其清除，然后在覆盖三角形时如果这个点被选中就加上\(-c_i\)的贡献
接下来考虑DP，设\(f_i\)表示已经处理了\(y\ge i\)的点时花费的最小代价，转移的话由于前面讲的不相交的性质，我们只要枚举一个边长\(j\)来转移即可
其中\(S(x,y)\)表示选中\(x,y\)做三角形时被覆盖的点的代价之和，由于不相交的性质因此是从\(f_{i+j+1}\)转移来
接下来考虑怎么优化这个式子，我们先把变量交换一下，用\(j\)去代换\(i+j+1\)得到：
经典的考虑把和\(j\)有关的量提出来，令\(g_j=f_j+A\times j-S(k-j+1,i)\)的最大值，则转移就是一个区间取\(\max\)的过程
而维护\(g_j\)的瓶颈显然就在后面那个\(S(k-j+1,i)\)的部分，直接下手很难处理，我们不妨换个角度想一想
我们按照\(y\)从大到小，\(x\)从大到小的顺序遍历处理所有点，则遇到一个点\((x,y,c)\)后它会对那些的\(g_j\)产生影响
由于\(S(k-j+1,i)\)包含\((x,y)\)的充要条件为\(k-j+1\le x\)（由于枚举顺序\(y\)肯定是包含的），因此我们只需要对\(j\ge k+1-x\)的所有\(g_j\)做区间修改，集体减去\(-c\)即可
用线段树维护上面的过程，总复杂度为\(O(n\log k)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,k,A,x,y,z,sum,f[N]; vector <pi> p[N];
class Segment_Tree
{
private:
struct segment
{
int mi,tag;
}node[N<<2];
#define MI(x) node[x].mi
#define T(x) node[x].tag
#define TN CI now=1,CI l=0,CI r=k+1
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void pushup(CI now)
{
MI(now)=min(MI(now<<1),MI(now<<1|1));
}
inline void apply(CI now,CI mv)
{
MI(now)+=mv; T(now)+=mv;
}
inline void pushdown(CI now)
{
if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;
}
public:
inline void modify(CI beg,CI end,CI mv,TN)
{
if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS); pushup(now);
}
inline int query(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return MI(now); int mid=l+r>>1,ret=1e18; pushdown(now);
if (beg<=mid) ret=min(ret,query(beg,end,LS)); if (end>mid) ret=min(ret,query(beg,end,RS)); return ret;
}
#undef MI
#undef T
#undef TN
#undef LS
#undef RS
}SEG;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld%lld%lld",&n,&k,&A),i=1;i<=n;++i)
scanf("%lld%lld%lld",&x,&y,&z),p[y].push_back(pi(x,z)),sum+=z;
auto cmp=[&](const pi& A,const pi& B)
{
return A>B;
};
for (i=0;i<=k;++i) sort(p[i].begin(),p[i].end(),cmp);
for (SEG.modify(k+1,k+1,A*(k+1)),i=k;i>=0;--i)
{
for (auto [x,z]:p[i]) SEG.modify(k+1-x,k+1,-z);
f[i]=min(0LL,SEG.query(i+1,k+1)-A*(i+1));
SEG.modify(i,i,f[i]+A*i);
}
return printf("%lld",f[0]+sum),0;
}
F. Tenzing and Tree
这题怎么感觉比D还一眼啊，不过我一般比赛的时候肯定不敢开的说
考虑枚举一个点\(rt\)为根，令其为第一个黑点，然后设每个点子树内黑点的个数为\(sz_x\)，则答案的式子就是：
这个绝对值的存在让我们很棘手，但现在让我们先来考虑如果去掉绝对值的式子怎么求最值：
不难发现要最小化后面那部分的值，则分别考虑每个点会对哪些点的\(sz\)产生贡献，显然就是它到根这段路径上的点
因此我们根据每个点的深度从小到大把点染黑即可，此时复杂度为\(O(n^2\log n)\)（如果写桶排可以做到\(O(n^2)\)）
但最关键的问题是这个绝对值随便去掉真的没问题吗，考虑我们上述的构造方法满足一个关键性质，枚举的\(rt\)一定是所有黑点的重心
而重心的一个重要性质就是其任意一个子树的大小\(\le \frac{k}{2}\)，因此我们可以直接去掉绝对值
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
int n,x,y,dep[N]; long long ans[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
dep[now]=dep[fa]+1; for (int to:v[now]) if (to!=fa) DFS(to,now);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;++i)
{
int cur=0; for (DFS(i),sort(dep+1,dep+n+1),j=1;j<=n;++j)
cur+=dep[j]-1,ans[j]=max(ans[j],1LL*j*(n-1)-2LL*cur);
}
for (i=0;i<=n;++i) printf("%lld ",ans[i]);
return 0;
}
G. Tenzing and Random Operations
好题，计数题总是能给我一种brain fuck的感觉，实在是智力不够的说
如果我们记\(pos_j\)表示第\(j\)次操作选择的位置，则答案的式子可以写作：
不妨暴力展开这个式子，由期望的线性性我们可以对展开后的每一项求和
观察展开后的每一项的构成，就是在\(i\)个括号内取出一个数然后相乘
然后由于这道题操作的重要性质，我们让\(i\)从左到右枚举每个括号的取值，对于某个\([pos_j\le i]\times v\)的取值：
- 若\([pos_j\le i]\times v=0\)，则不论后面怎么取，这一项的值始终为\(0\)，我们可以不统计这类情况
- 若\([pos_j\le i]\times v=v\)，则后面的\(i\)在选到\(pos_j\)的时候值始终为\(v\)，因为\(i\)的值始终增加
因此我们可以这般设计状态：令\(f_{i,j}\)表示已经处理了前\(i\)个括号，其中有效\(pos_j\)的取值种类有\(j\)种时，前\(i\)个部分的乘积的期望，则转移有：
- 这个括号选\(a_{i+1}\)：\(f_{i,j}\times a_{i+1}\to f_{i+1,j}\)
- 这个括号选一个之前已经出现过的\(pos_j\)，共有\(j\)种方案：\(f_{i,j}\times j\times v\to f_{i+1,j}\)
- 这个括号选一个之前未出现过的\(pos_j\)，由于要满足\(pos_j\le i+1\)，因此要乘上\(\frac{i+1}{n}\)：\(f_{i,j}\times (m-j)\times \frac{i+1}{n}\times v\to f_{i+1,j+1}\)
最后答案就是\(\sum_{i=0}^n f_{n,i}\)，总复杂度\(O(n^2)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,mod=1e9+7;
int n,m,v,a[N],f[N][N],inv_n,ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%d%d",&n,&m,&v),i=1;i<=n;++i) scanf("%d",&a[i]);
for (f[0][0]=1,inv_n=quick_pow(n),i=0;i<n;++i)
for (j=0;j<=i;++j) if (f[i][j])
{
inc(f[i+1][j],1LL*f[i][j]*a[i+1]%mod);
inc(f[i+1][j],1LL*f[i][j]*j%mod*v%mod);
inc(f[i+1][j+1],1LL*f[i][j]*(m-j)%mod*(i+1)%mod*inv_n%mod*v%mod);
}
for (i=0;i<=n;++i) inc(ans,f[n][i]);
return printf("%d",ans),0;
}
Postscript
爽训，爽写