【题解】NOIP2015提高组 复赛
传送门：
【Day1】
【T1】
【题目描述】
幻方是由 \(1,2,3...n*n\) 共 \(n^2\) 个数组成一个的 \(n*n\) 的矩阵。
当 \(n\) 为奇数时，可按以下方式构造一个幻方：
首先将 \(1\) 写在第一行的中间。
之后，按如下方式从小到大依次填写每个数 \(K(K=2,3,…,n*n)\) ：
\((1).\) 若 \(\text{(K-1)}\) 在第一行但不在最后一列，则将 \(K\) 填在最后一行，\(\text{(K-1)}\) 所在列的右一列；
\((2).\) 若 \(\text{(K-1)}\) 在最后一列但不在第一行，则将 \(K\) 填在第一列，\(\text{(K-1)}\) 所在行的上一行；
\((3).\) 若 \(\text{(K-1)}\) 在第一行最后一列，则将 \(K\) 填在 \(\text{(K-1)}\) 的正下方；
\((4).\) 若 \(\text{(K-1)}\) 既不在第一行，也不在最后一列，如果 \(\text{(K-1)}\) 的右上方还未填数，则将 \(K\) 填在\(\text{(K-1)}\)的右上方，否则将 \(K\) 填在 \(\text{(K-1)}\) 的正下方。
现给定 \(n\) \((n \leqslant 39\) 且 \(n\) 为奇数 \()\)，请按上述方法构造 \(n*n\) 的幻方。
【分析】
模你送分题。
按照题面说的一个一个地填就好了。
【Code】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define Re register int
using namespace std;
const int N=55;
int n,x,y,nx,ny,a[N][N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
// freopen("magic.in","r",stdin);
// freopen("magic.out","w",stdout);
in(n);
a[x=1][y=n/2+1]=1;
for(Re i=2;i<=n*n;++i){
if(x==1&&y<n)nx=n,ny=y+1;
else if(y==n&&x>1)nx=x-1,ny=1;
else if(x==1&&y==n)nx=x+1,ny=y;
else if(x>1&&y<n){
if(!a[x-1][y+1])nx=x-1,ny=y+1;
else nx=x+1,ny=y;
}
a[x=nx][y=ny]=i;
}
for(Re i=1;i<=n;puts(""),++i)
for(Re j=1;j<=n;++j)
printf("%d ",a[i][j]);
fclose(stdin);
fclose(stdout);
return 0;
}
【T2】
【题目描述】
有 \(n\) \((n \leqslant 200000)\) 个同学（编号为 \(1\) 到 \(n\)）。
游戏开始时，每人都只知道自己的信息，之后的每一轮，\(i\) 会将自己所知的所有信息都传递给 \(T_i\) \((T_i\) \(\text{!=}\) \(i)\)，当有人从别人口中得知自己的信息时，游戏结束。问该游戏可以进行几轮？。
【分析】
每个点都只会有一条出边，很明显是一个内向基环树森林，只要找到长度最小的环即可。
找法可以是并查集，也可以用 \(tarjan\) 。
【Code】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2e5+3;
int n,ans,Q_o,a[N],ip[N],gs[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Tarjan{//用Tarjan跑强连通模板
int h,t,dfn_o,Q[N],pan[N],low[N],dfn[N];
inline void tarjan(Re x){
dfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;
Re to=a[x];
if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]);
else if(pan[to])low[x]=min(low[x],dfn[to]);
if(low[x]==dfn[x]){
++Q_o;
while(1){
ip[Q[t]]=Q_o,++gs[Q_o],pan[x]=1;
if(x==Q[t--])break;
}
}
}
inline void SuoPoint(){
for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);
}
}T1;
int main(){
// freopen("message.in","r",stdin);
// freopen("message.out","w",stdout);
in(n),ans=n;
for(Re i=1;i<=n;++i)in(a[i]);
T1.SuoPoint();
for(Re i=1;i<=Q_o;++i)if(gs[i]>1)ans=min(ans,gs[i]);
//只有长度大于1的强连通分量才是环
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
【T3】
【题目描述】
模拟斗地主。
有 \(T\) \((T \leqslant 100)\) 组数据，每组数据给出 \(n\) \((n \leqslant 23)\) 张手牌，可以按给定的 \(11\) 种牌型出牌，求出完所有牌所需的最小出牌次数。
【分析】
一天考两道模拟？真够神奇的。
由于数据较小，可以直接暴搜，但只是单纯的搜索可能会炸，需要一些技巧来进行优化。
\((1).\) 先抛开有顺子的情况，对于三张，四张（炸弹）的牌，一定会一起打出去，因为把它们拆开只会消耗更多的次数，而带不带牌并不影响它们在一起这一事实，所以凡是发现有 \(3\) 张或 \(4\) 张的，直接统计一下它的张数。关于带牌的问题，三张的话，直接带一个单牌或双牌，而四张要优先带两张单牌或双牌，如果带不了就带一个双牌（题意不明确，不知道到底能不能带一个双牌）。
\((2).\) 仍然是先抛开有顺子的情况，在处理了三张和四张得情况后，剩下的全是单牌和双牌，只需要统计一下张数就可以了。
\((3).\) 现在只剩下有顺子的情况，可以直接暴力枚举搜索了。
然后就是处理的小技巧，从学长那儿学了一些，最后写出来后发现代码并不长。
写完后突然发现有一个漏洞，如果只有三个不连续的三张，那么可以将其中拆成两半，而上述贪心并没有涵盖这一情况。但是由于数据随机生成，所以随便水一水就可以了。
【Code】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define Re register int
using namespace std;
int n,x,y,T,ans,gs[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void dfs(Re g){
Re p4=0,p3=0,p2=0,p1=0;
for(Re i=1;i<=14;++i){//扫描3~king (1~14)
if(gs[i]==1)++p1;//单牌
if(gs[i]==2)++p2;//双牌
}
for(Re i=1;i<=14;++i)//扫描3~king
if(gs[i]==4){//4牌
++p4;//不管带不带.这个四牌肯定要出
if(p1>=2){p1-=2;continue;}//带两个单牌
if(p2>=2){p2-=2;continue;}//带两个双牌
if(p2>=1){p2-=1;continue;}//带一个双牌(两个一样的单牌)
//一个四牌(炸弹)
}
for(Re i=1;i<=14;++i)//扫描3~king (1~14)
if(gs[i]==3){//3牌
++p3;//不管带不带,这个三牌肯定要出
if(p1>=1){p1-=1;continue;}//带一个单牌
if(p2>=1){p2-=1;continue;}//带一个双牌
//一个三牌
}
ans=min(ans,g+p1+p2+p3+p4);//没有顺子的最小答案
for(Re i=1,j;i<=8;++i){//单顺子,最大为(10~A)8~12
for(j=i;j<=12;++j){
gs[j]-=1;//反正最后要回溯，先减了再说
if(gs[j]<0)break;//无法继续连下去了,退出
if(j-i+1>=5)dfs(g+1);//单顺子长度至少为5
}
if(j==13)--j;//如果全部连完了,2(13)是不用回溯的
while(j>=i)gs[j]+=1,--j;//最后放在一起回溯
}
for(Re i=1,j;i<=10;++i){//双顺子,最大为Q~A(10~12)
for(j=i;j<=12;++j){
gs[j]-=2;
if(gs[j]<0)break;
if(j-i+1>=3)dfs(g+1);//双顺子长度至少为3
}
if(j==13)--j;
while(j>=i)gs[j]+=2,--j;
}
for(Re i=1,j;i<=11;++i){//三顺子,最大为Q~A(10~12)
for(j=i;j<=12;++j){
gs[j]-=3;
if(gs[j]<0)break;
if(j-i+1>=2)dfs(g+1);//三顺子长度至少为2
}
if(j==13)--j;
while(j>=i)gs[j]+=3,--j;
}
}
int main(){
// freopen("landlords.in","r",stdin);
// freopen("landlords.out","w",stdout);
in(T),in(n);
while(T--){
memset(gs,0,sizeof(gs));
for(Re i=1;i<=n;++i){
in(x),in(y);
if(x==0)++gs[14];//14: 大王
if(x==2)++gs[13];//13: 2
if(x==1)++gs[12];//12: A
if(x>=3)++gs[x-2];//x-2: x
// J: 11-2=9
// Q: 12-2=10
// K: 13-2=11
}
ans=2e9,dfs(0);
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
【Day2】
【T1】
【题目描述】
给出终点坐标 \(L\) 与 \(n\) \((0 \leqslant n \leqslant 50000)\) 个石头的坐标（起点坐标为 \(0\)），可以删掉至多 \(m\) \((0 \leqslant m \leqslant 50000)\) 个石头，求每两个相邻石头距离的最小值最大可以为多少。
【分析】
最小值最大，很明显的二分标志。
\(check\) 函数就从 \(1\) 到 \(n\) 扫一遍，只要有石头与前一个的距离大于 \(mid\)，那么 \(cnt++\)，表示必须要多移走一个石头，如果 \(cnt<=m\) 那么扩大下界，否则缩小上界。
坑点：从起点 \(0\) 开跳，并且最后还要跳到终点 \(L\)，这两次跳跃的距离都应在 \(check\) 中扫描到。
【Code】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e4+3;
int n,m,L,a[N],b[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int check(Re mid){
for(Re i=1;i<=n;++i)b[i]=a[i];
Re tmp=m;
for(Re i=1;i<=n;++i)
if(b[i]-b[i-1]<mid){
if(tmp)--tmp,b[i]=b[i-1];
else return 0;
}
return 1;
}
int main(){
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
in(L),in(n),in(m);
for(Re i=1;i<=n;++i)in(a[i]);
a[++n]=L;
Re l=0,r=L;
while(l<r){
Re mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
printf("%d\n",l);
fclose(stdin);
fclose(stdout);
return 0;
}
【T2】
【题目描述】
给出两个长度分别为 \(n,m\) \((1 \leqslant n \leqslant 1000,0 \leqslant m \leqslant 200)\) 的字符串 \(A,B\)，现要从 \(A\) 中依次取出 \(K\) \((1 \leqslant K \leqslant m)\) 个互不重叠的非空子串，使其组合起来刚好为 \(B\) 。求合法方案数。
【分析】
首先可以想到一个 \(n^2mK\) 的暴力 \(dp\)，大约有 \(30\) ~ \(50\) 分。
用 \(dp[p][i][j]\) 表示 \(A,B\) 分别处理到 \(i,j\) 位置，已经选出了 \(p\) 个子串的方案数，那么转移方程为：
\(dp[p][i][j]=\begin{cases}0(a[i]\ !=a[j])\\dp[p][i-1][j-1]+\sum_{k=0}^{i} dp[p-1][k][j] (a[i]==a[j])\end{cases}\)
注意：只有 \(i\) 不断地在取前面的状态，所以 \(i\) 应该在最外层枚举。
发现求和部分可以用前缀和优化，于是时间复杂度便降到了 \(nmK\) 。
类似背包降维，倒序枚举 \(p,j\) 即可将 \(i\) 这一维去掉。
【Code】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1003,M=203,P=1e9+7;
int n,m,K,dp[M][M][2];char a[N],b[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
// freopen("substring.in","r",stdin);
// freopen("substring.out","w",stdout);
in(n),in(m),in(K);
scanf("%s%s",a+1,b+1);
dp[0][0][0]=1;
for(Re i=1;i<=n;++i){
for(Re j=m;j>=1;--j)
if(a[i]==b[j]){
for(Re p=min(K,j);p>=1;--p){
(dp[p][j][1]=(dp[p][j-1][1]+dp[p-1][j-1][0])%P)%=P;
(dp[p][j][0]+=dp[p][j][1])%=P;//偷了个懒直接用dp[p][j][0]表示1到i的dp[p][j]前缀和
}
}
else for(Re p=min(K,j);p>=1;--p)dp[p][j][1]=0;
}
printf("%d\n",dp[K][m][0]);//注意答案应是1到n的前缀和
fclose(stdin);
fclose(stdout);
return 0;
}
【T3】
【题目描述】
给出一颗 \(n\) \((n \leqslant 300000)\) 个节点的带边权树和 \(m\) \((m \leqslant 300000)\) 条简单路径的两个端点，现可选出任意一条边将其边权变为 \(0\)，使得 \(m\) 条简单路径中最长的最小，输出这个最小值。
【分析】
最长的最小，又是一个二分。。。。
考如何 \(check\) 函数，现要判断的是：最长的路径是否小于等于 \(mid\) 。
换言之，就是要找出一条边免费通过，使得所有原本长度大于 \(mid\) 的路径都变成小于 \(mid\) 。
假设原本一共有 \(need\) 条路径长度大于 \(mid\)，那么选出的这条免费边必须同时被这 \(need\) 条边覆盖，否则就无法减小它们的长度。
于是问题变成了：在被覆盖了 \(need\) 次的各个边中选出一条边，使得这 \(need\) 条不合法路径在减去这个边权之后都尽量小，所以免费边应该选边权最大的那一条。
思路已经有了，那么如何实现呢？
首先跑 \(lca\) 预处理出 \(m\) 条路径的原本长度（按长度排个序）。
二分的初始上界为树上最长链的长度（也可以直接取所有边权和）。
每次 \(check\) 找所有路径两个端点的 \(lca\)，然后差分快速处理每个点被覆盖的次数，\(dfs\) 回收差分数组时顺手找出边权最大的边。
时间复杂度为：\(O(logS*(n+m*logn))\)，其中 \(S\) 为最长链的长度。
【Code】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define Re register int
using namespace std;
const int N=3e5+3,logN=19;
int n,m,o=1,x,y,z,l,r,T,tmp,need,C[N],head[N];
struct QAQ{int w,to,next;}a[N<<1];
struct QWQ{int x,y,dis;inline bool operator<(QWQ O)const{return dis<O.dis;};}A[N];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct LCA{
int dis[N],deep[N],anc[N][23];
inline void dfs(Re x,Re fa,Re w){
deep[x]=deep[anc[x][0]=fa]+1,dis[x]=dis[fa]+w;
for(Re i=1;(1<<i)<=deep[x];++i)anc[x][i]=anc[anc[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x,a[i].w);
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[anc[x][i]]>=deep[y])x=anc[x][i];
if(x==y)return x;
for(Re i=logN;i>=0;--i)
if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
}T1;
inline void dfs(Re x,Re fa){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
C[x]+=C[to];
if(C[to]==need&&a[i].w>tmp)tmp=a[i].w;
}
}
inline int check(Re mid){
for(Re i=1;i<=n;++i)C[i]=0;
need=0,tmp=-1;
for(Re i=T;i>=1;--i)
if(A[i].dis>mid){
++C[A[i].x],++C[A[i].y],++need;
C[T1.lca(A[i].x,A[i].y)]-=2;
}
else break;
tmp=-1,dfs(1,0);
for(Re i=1;i<=T;++i)if(A[i].dis-tmp>mid)return 0;
return 1;
}
int main(){
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
in(n),in(T),m=n-1;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z),r+=z;
for(Re i=1;i<=T;++i)in(A[i].x),in(A[i].y);
T1.dfs(1,0,0);
for(Re i=1;i<=T;++i)A[i].dis=T1.dis[A[i].x]+T1.dis[A[i].y]-(T1.dis[T1.lca(A[i].x,A[i].y)]<<1);
sort(A+1,A+T+1);
while(l<r){
Re mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d\n",r);
fclose(stdin);
fclose(stdout);
return 0;
}