赛后——2.13 寒假模拟9
\(\text{T1}\) 打错变量挂 \(80\) 分祭（痛失 \(\text{rk}1\)）
\(\text{T1}\) No Problem
题意
新学期到了，有一个 \(n\times m\) 的教室，老师来组织同学们互相认识一下。
每个人会和自己周围 \(3\times 3\) 方格中的其他人握手（即左上、上、右上、左、右、左下、下和右下的八个人，若没有人则不会握手），如果还有空位，老师会挑一个空位坐下时的总的握手次数最多。
求这个最多次数。
思路
首先求出所有同学周围同学数的一半，就是握手次数。同时记录下一个空位周围同学的最大值，二者之和就是答案。
代码
点击查看代码
inline int get(int x,int y){
int res=0;
for(int i=x-1;i<=x+1;i++){
for(int j=y-1;j<=y+1;j++){
if(i==x&&j==y) continue;
if(i<1||i>n||j<1||j>m) continue;
if(s[i][j]=='o') res++;
}
}
return res;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){//SoyTony的殇
int tmp=get(i,j);
if(s[i][j]=='o') sum+=tmp;
else maxx=max(maxx,tmp);
}
}
printf("%d\n",sum/2+maxx);
return 0;
}
\(\text{T2}\) Str
题意
对于字符串 \(s\)，定义一个变换 \(f(s)\) 表示，\(\forall 1\le k\le\lfloor|s|/2\rfloor\)，将从后往前数第 \(k\) 个字符插入从前往后数第 \(k\) 个与第 \(k+1\) 个字符之间后得到的字符串例如，\(s=\text{abcdef}\)，变换后的 \(s'=\text{afbecd}\)。
现在给出变换过 \(k\) 次以后的字符串，求变换之前的字符串。
思路
首先把变换过 \(1\) 次字符串复原是 \(O(|s|)\) 的，而 \(k\) 有 \(10^9\) 之多。但是因为变换是有循环节的（这个可以写个程序计算下），就能够得到对于每个 \(|s|\) 的循环节大小，将 \(k\) 取模，剩下的就交给暴力吧。
代码
点击查看代码
int main(){
k=read();
scanf("%s",s+1);
n=strlen(s+1);
k=k%md[n];
for(int i=1;i<=k;i++){
char tmp[1005];
for(int j=1;j<=(n-1)/2+1;j++){
tmp[j]=s[j*2-1];
if(j*2<=n) tmp[n-j+1]=s[j*2];
}
for(int i=1;i<=n;i++){
s[i]=tmp[i];
}
}
for(int i=1;i<=n;i++){
cout<另外挂一个打表的代码。
点击查看代码
int main(){
t=read();
freopen("data.out","w",stdout);
for(int i=1;i<=t;i++){
for(int j=1;j<=i;j++){
s[j]=a[j]=j;
}
int cnt=0;
while(1){
cnt++;
for(int j=1;j<=i/2;j++){
tmp[j*2-1]=a[j];
tmp[j*2]=a[i-j+1];
}
if(i%2) tmp[i]=a[i/2+1];
bool pd=0;
for(int j=1;j<=i;j++){
if(s[j]!=tmp[j]){
pd=1;
break;
}
}
if(!pd){
printf("%d,",cnt);
break;
}
for(int j=1;j<=i;j++){
a[j]=tmp[j];
}
}
}
return 0;
}
\(\text{T3}\) Not TSP
题意
一个城镇有 \(n\) 个地区，第 \(i\) 个地区和第 \(j\) 个的地区是 \(dis(i,j)\)，即从 \(i\) 到 \(j\) 与从 \(j\) 到 \(i\) 都是一样的代价。
现在小 \(F\) 要恰好一次访问这些所有地区，为了降低难度，规定访问第 \(i\) 个地区的时候，\(1\dots i-1\) 这些地区要么全部去过要么全部未去过。
求恰好一次访问所有地区的最小代价。（起点终点任意）
思路
首先状压暴搜可以拿到 \(40\) 分，这里 \(n\le 20\)。
然而，发现从任意一个点起步，都只能向编号小于它的点移动（下文描述为向左走），因为向任何一个大于它的点移动，都不满足“全部未走过”的条件。同时，这样的走法可以选择一个一个“扫”，也可以选择直接“跳”，而这样向左的目的地是 \(1\)，而且当重新去到大于起点编号的点时，左面的点必须恰好访问一次。于是从 \(1\) 向右走的本质其实是，将向左走时“扫”过的点直接“跳”过，“跳”过的点中间部分一个一个“扫“过。
我们用 \(f(i,j)\) 来表示从 \(i\) 出发向左，到达 \(1\) 后向右到达 \(j\) 的最小代价，显然最终答案是 \(\min_{i=1}^{n-1}\{f(i,n)\}\)。发现其实 \([i+1,j]\) 的部分只能扫过，于是转移其实是由 \(f(i,i+1)\) 的得来的。接着，对于每个 \(f(i,i+1)\)，我们用一个 \(j\) 将其断开，路径大致是：\(i+1\to j \to 1\to i\)，于是 \([1,i+1]\) 的点就全部走完了，枚举这个 \(j\) 即可。
代码
点击查看代码
int main(){
n=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=read();
}
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+dis[i-1][i];
}
for(int i=0;i<=n;i++){
dp[0][i]=sum[i];
dis[0][i]=dis[1][i];
}
for(int i=2;i<=n;i++){
for(int j=0;j\(\text{T4}\) Game
题意
\(\text{Alice}\) 和 \(\text{Bob}\) 在做游戏。
平面上有 \(n\) 个点 \(\text{Alice}\) 先手，首先选择画一条平行于 \(\text{x}\) 轴或 \(\text{y}\) 轴的一条直线，穿过前一条直线穿过的某个点。不能画与之前直线重合的直线。不能操作的人输，求最优策略下谁赢。
思路
发现把每个直线当成一个节点，每个点作为节点的连边，就转化成类似于二分图上移动棋子的博弈论做法。当这个图有完备匹配时后手必胜。
代码
点击查看代码
inline bool dfs(int u,int c){
if(col[u]==c) return false;
col[u]=c;
for(auto v:G[u]){
if(dfs(l[v],c)||!l[v]){
l[v]=u,r[u]=v;
return true;
}
}
return false;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
int xx=read(),yy=read();
x.insert(xx),y.insert(yy);
G[xx].push_back(yy);
}
for(int i=1;i<=n;i++){
dfs(i,i);
}
for(auto i:x){
if(!r[i]) return printf("Alice\n"),0;
}
for(auto i:y){
if(!l[i]) return printf("Alice\n"),0;
}
printf("Bob\n");
return 0;
}