T1 被神秘数据 hack 了挂了 20pts。
T3 想到了真真假假假假真真做法。结果挂完了。
80+100+0+0。
T1 No Problem
题意
有一个 \(n \times m\) 的教室，每个人会和自己周围八个方向的人握手。
如果还有空位, 老师会挑一个空位坐下使得总的握手次数最多。
求一共会有多少次握手。
赛时
糖糖题，写了糖糖做法。
结果忘了判初始就全是人的情况了。
严肃被 hack。
题解
没什么好解的。
枚举老师的位置然后暴力算。\(O(n^4)\) 都能过。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;int n,m;
int mp[52][52];int wa[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}};int calc(){int res=0;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]) for(int w=0;w<8;w++) res+=mp[i+wa[w][0]][j+wa[w][1]];return res/2;
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;if(c=='.') mp[i][j]=0;else mp[i][j]=1;}}int ans=calc();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mp[i][j]) continue;mp[i][j]=1;ans=max(ans,calc());mp[i][j]=0;}}cout<<ans<<"\n";return 0;
}
T2 Str
题意
定义对字符串的变换 \(f([s_1,s_2,s_3,\dots,s_n])=[s_1,s_n,s_2,s_{n-1},\dots]\)。
给定经过 \(k\) 次变换后的字符串，还原原字符串。
赛时
打了表。
然后秒了。
题解
不难注意到这东西有周期性。
然后打个表上 OEIS 上找，你就能惊奇地发现：
Also, the order of the so-called "milk shuffle" of a deck of n cards, which maps cards (1,2,...,n) to (1,n,2,n-1,3,n-2,...).
我想要说的前人们都说过了。
然后不难发现单独打一个表的复杂度只有 \(O(n^2)\)。
然后就秒了。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;int a[1010],b[1010];
int calc(int n){for(int i=1;i<=n;i++) a[i]=i;int cnt=0;bool chk=true;do{chk=true;int id=0;int l=1,r=n;while(l<=r){b[++id]=a[l],l++;if(l>r) break;b[++id]=a[r],r--;}for(int i=2;i<=n;i++) chk&=(b[i]==b[i-1]+1);cnt++;for(int i=1;i<=n;i++) a[i]=b[i];}while(!chk);return cnt;
}int n,m;
string s;int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>m>>s;n=s.length();int w=calc(n);m%=w;while(m--){string newl="",newr="";for(int i=0;i<n;i++){if(i&1) newr+=s[i];else newl+=s[i];}reverse(newr.begin(),newr.end());s=newl+newr;}cout<<s<<"\n";return 0;
}
T3 Not TSP
题意
给定编号从 \(1\) 到 \(n\) 的 \(n\) 个点，\(i\) 到 \(j\) 的距离是 \(d(i,j)\)。
任意指定起点和终点，你需要访问所有点恰好一次。
特别限制：当访问第 \(i\) 个地区的时候，要么 \(1\dots i-1\) 这些点都还没访问过，要么这些地区都已经访问过了。
求最短时间。
赛时
想了一堆解法，真真假假假假真真。结果最后还是假了。
最后看了别人的代码也是一知半解。。这啥题啊。。
题解
抄了别人的代码。。看不懂一点。。
为什么还不放题解。。
自己理解一下吧。虽然我自己也不理解这个代码。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;int n;
long long mp[1510][1510];
long long dp[1510][1510];int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>mp[i][j];memset(dp,0x3f,sizeof dp);dp[1][1]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int p=max(i,j)+1;if(p==n+1) break;dp[i][p]=min(dp[i][p],dp[i][j]+mp[j][p]);dp[p][j]=min(dp[p][j],dp[i][j]+mp[i][p]);}}long long ans=infll;for(int i=1;i<=n;i++) ans=min(ans,min(dp[i][n],dp[n][i]));cout<<ans<<"\n";return 0;
}
T4 Game
题意
Alice 和 Bob 在做游戏。
平面上有 \(n\) 个点，Alice 先手，先画一条平行于 \(x\) 或 \(y\) 轴的一条直线，必须穿过这 \(n\) 个点中的某个点。之后 Bob，Alice 轮流操作，每次每个人需要画一条直线，需要满足以下要求：
- 平行于 \(x\) 轴或 \(y\) 轴。
- 与前一条直线相交。
- 经过 \(n\) 个点中的某个点。
- 不与之前画的之前重合。
不能操作的人输。
求在最优策略下谁赢。
赛时
看不懂。
听了 xxxalq 大佬的讲解之后会了。
其实是 T4 < T3。
题解
不难注意到，这 \(n\) 个点中有多少个不同的横坐标，就能画多少条互不重合的竖线；有多少个不同的纵坐标，就能画多少条互不重合的横线。
而不难发现，两个人画的线一定是一横一竖交替。
而不管上一个人画在哪，只要当前方向互不重合的线没有画满，就一定能画出来一条线。
所以 Alice 会输当且仅当能画的横线和竖线数相等。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;int n;
set<int> sx,sy;int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;sx.insert(x);sy.insert(y);}if(sx.size()==sy.size()) cout<<"Bob\n";else cout<<"Alice\n";return 0;
}
总结
挂完了。
没仔细想 T4。而且 T4 那个题面不太清楚。