2023.7.10
T1
题面
在一个迷宫中有一个蛋糕。作为一个吃货，Luna 非常想吃到这块蛋糕。现在Luna 手里有这个迷宫的地图，该地图是一个r 行c 列的网格图，每个格子包含了下述4 种字符中的一种：“#”表示这里是墙砖，不能通过；
“.”表示这里是空地，可以通过；
“S”表示Luna 的初始位置；
“C”表示蛋糕的位置。
Luna 只能在空地上行走，并且只能从一个格子走到与这个格子有公共边的相邻格子上。另外，整个地图的四周都是被墙砖所环绕的。
为了能更快吃到蛋糕，Luna 不知从哪里获得了一把次元枪，这把枪可以用来制造传送门。该枪的使用说明如下：
-
在任何时候，Luna 可以选择上下左右四个方向中的一个开一枪。当她向一个方向开枪之后，子弹会撞到这个方向上第一个遇到的墙砖，并在这个墙砖面向她的面上开启一个传送门。
-
由于能量限制，在同一时刻最多存在两个传送门。如果已经存在两个传送门，那么当Luna 再开枪时，其中一个传送门会被回收用于补充能量，回收哪一个由Luna 自己决定。当Luna 向某个传送门开枪时，会有一个新的传送门取代它，即在一块墙砖的一个面上同时只能存在一个传送门。
-
当存在两个传送门时，Luna 可以进入其中任意一个传送门，然后会从另外一个传送门走出。
由于Luna 枪法一流，所以开枪是不耗时的。Luna 从一个格子走到任意一个相邻格子的耗时为1，穿越传送门的耗时也为1。
现在Luna 把地图给了你，她想知道她吃到蛋糕的最少耗时是多少，你不忍心拒绝这样一位少女的请求，所以你绞尽脑汁也要把这个问题解决。
sol
最短路。预处理出每个点走到上，下，左，右的最远点。
走到 \((x,y)\) 时，正常走可以走到 \((x+1,y),(x,y+1),(x-1,y),(x,y-1)\)，如果用传送门，只需要走到最近的一面墙就能走到上下左右任意一面墙。跑 SPFA 即可。
#pragma GCC optimize("O2")
#include<queue>
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
const int M=1010,inf=1e9+7;
int n,m; int id(int x,int y){return (x-1)*m+y;}
int sx,sy,ex,ey;
char mp[M][M];
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
typedef pair<int,int> PII;
PII to[M][M][4];
#define qwq make_pair
#define nino first
#define miku second
void pre(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(mp[i][j]!='#'){
to[i][j][0]=(mp[i-1][j]=='#')?qwq(i,j):to[i-1][j][0];
to[i][j][1]=(mp[i][j-1]=='#')?qwq(i,j):to[i][j-1][1];
}
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--) if(mp[i][j]!='#'){
to[i][j][2]=(mp[i+1][j]=='#')?qwq(i,j):to[i+1][j][2];
to[i][j][3]=(mp[i][j+1]=='#')?qwq(i,j):to[i][j+1][3];
}
/*
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
printf("to[%d][%d]=",i,j);
for(int dir=0;dir<4;dir++)
printf("(%d,%d),",to[i][j][dir].nino,to[i][j][dir].miku);
putchar('\n');
}*/
}
int dis[M][M]; queue<PII>q;
bool inq[M][M];
int dist(PII u,PII v){
return abs(u.nino-v.nino)+abs(u.miku-v.miku);
}
#define D(x) dis[x.first][x.second]
#define Q(x) inq[x.first][x.second]
#define MP(x) mp[x.first][x.second]
void SPFA(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++) dis[i][j]=inf;
dis[sx][sy]=0; q.push(qwq(sx,sy)),inq[sx][sy]=true;
while(!q.empty()){
PII u=q.front(); q.pop(),Q(u)=false;
//printf("u=(%d,%d)\n",u.nino,u.miku);
int mndis=inf;
for(int dir=0;dir<4;dir++){
PII v=to[u.nino][u.miku][dir];
if(mndis>dist(u,v)) mndis=dist(u,v);
v=qwq(u.nino+dx[dir],u.miku+dy[dir]);
if(MP(v)=='#') continue;
//printf("(%d,%d)->(%d,%d) dis=1\n",u.nino,u.miku,v.nino,v.miku);
if(D(v)>D(u)+1){
D(v)=D(u)+1;
if(!Q(v)) q.push(v),Q(v)=true;
}
}
for(int dir=0;dir<4;dir++){
PII v=to[u.nino][u.miku][dir];
//printf("(%d,%d)->(%d,%d) dis=%d\n",u.nino,u.miku,v.nino,v.miku,mndis+1);
if(D(v)>D(u)+mndis+1){
D(v)=D(u)+mndis+1;
if(!Q(v)) Q(v)=true,q.push(v);
}
}
}
//for(int i=1;i<=n;i++,putchar('\n'))
// for(int j=1;j<=m;j++) printf("%d ",dis[i][j]);
}
int main(){
freopen("portals.in","r",stdin);
freopen("portals.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<=m+1;i++) mp[0][i]=mp[n+1][i]='#';
for(int i=1;i<=n;i++) scanf(" %s",mp[i]+1),mp[i][0]=mp[i][m+1]='#';
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]=='S') sx=i,sy=j;
else if(mp[i][j]=='C') ex=i,ey=j;
pre(),SPFA();
printf("%d",dis[ex][ey]);
return 0;
}
T2
题面
在2036 年的欧洲，老龄化现象已经渗透到了这个社会的各个角落，随之而来的是严重的健康问题。在欧洲有关部门的建议下，老年人被派遣去递送（也是给老年人的）信件。这项建议将在全欧洲得以实施。有关部门将欧洲划分为若干个邮区。邮区是一个由双向街道和交叉路口组成的网络，每个区内都可以雇佣任意多的老年人。每天早晨，邮递员接到包裹并按一定路线投送。路线需要满足以下要求：
-
路线的起点和终点相同；
-
同一个路口不能经过两次（体谅老年人）；
-
每条街道必须被恰好一条路线覆盖（体谅老年人）。
希望你帮助有关部门求出可行的路线分配方案。
sol
先找到一条不走任何重复边的最长路径。根据题意从 \(1\) 开始走最后一定回到 \(1\)，而且一定每条边都恰好走一次。记录走到的节点顺序 \(ord\)。
若有 \(ord_i = ord_j = u\) 说明 \([i,j)\) 形成一个环，输出并删除即可。
由题意，每个节点度数都是偶数，所以最后刚好删完。
用栈代替了 dfs 以防递归爆栈。
#include<cstdio>
#include<cstring>
const int M=5e5+10;
bool mark[M<<1];
int head[M],cur[M],cnte=1;
struct Edge{int to,next;}e[M<<1];
void add(int u,int v){
e[++cnte]=(Edge){v,head[u]};
head[u]=cnte;
}
int n,m;
int stk[M],top;
int ord[M<<1],top0;
bool vis[M];
int main(){
freopen("postmen.in","r",stdin);
freopen("postmen.out","w",stdout);
memset(head,-1,sizeof head);
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(int i=1;i<=n;i++) cur[i]=head[i];
stk[++top]=1;
while(top>0){
int u=stk[top],t=cur[stk[top]];
if(t==-1){
ord[++top0]=u; top--;
continue;
}
cur[u]=e[cur[u]].next;
if(mark[t]) continue;
mark[t]=mark[t^1]=true;
stk[++top]=e[t].to;
}
for(int i=1;i<=top0;i++){
int cur=ord[i];
if(vis[cur]){
int tmp;
do{
tmp=stk[top--];
printf("%d ",tmp),vis[tmp]=false;
}while(tmp!=cur);
putchar('\n');
}
stk[++top]=cur,vis[cur]=true;
}
return 0;
}
T3
题面
有 \(m\) 个长度为 \(n\) 的01字符串，编号为 \(1\) 到 \(m\)，每个字符串中的位都按升序或降序排列。
用 \(H(a,b)\) 表示汉明距离，即两个相同长度的字符串对应位不同的位置的个数。计算所有由三个编号不同的串 \(a,b,c\) 组成的三元组中，\(H(a,b)+H(b,c)+H(c,a)\) 最大的三元组有多少个。
输入时将每个串用两个整数 \(s_i\in[0,1]\) 和 \(f_i\in[0,n]\) 来表示，意为串的前 \(f_i\) 个位为 \(s_i\)，后 \(n-f_i\) 个位为 \(1-s_i\)。
sol
先考虑两个数的情况。
将 \(f\) 从小到大排序就可以脱掉绝对值。
将所有数排序去重，然后设 \((f_a, s_a)<(f_b, s_b)<(f_c, s_c)\)。
- \((s_a, s_b, s_c)=(0, 0, 0) / (1, 1, 1)\)
\(H(a, b)+H(b, c)+H(c, a) = 2(f_c - f_a)\)
- \((s_a, s_b, s_c)=(0, 0, 1) / (1, 1, 0)\)
\(H(a, b)+H(b, c)+H(c, a) = 2(n + f_b - f_c)\)
- \((s_a, s_b, s_c)=(0, 1, 1) / (1, 0, 0)\)
\(H(a, b)+H(b, c)+H(c, a) = 2(n + f_a - f_b)\)
- \((s_a, s_b, s_c)=(1, 0, 1) / (0, 1, 0)\)
\(H(a, b)+H(b, c)+H(c, a) = 2n\)
到此并没有分类完，事实上还有 \((f_a, s_a)=(f_b, s_b)<(f_c, s_c)\) 和 \((f_a, s_a)<(f_b, s_b)=(f_c, s_c)\) 的情况。其实只需要去重完特判这几种情况即可，因为若有三个或以上不同的数，那么这两种情况一定不优。
所以考虑枚举 \(b\)，维护 \(s = 0/1\) 时 前缀/后缀 的 个数/最大值/最小值/最大值个数/最小值个数即可。
#include<cstdio>
#include<algorithm>
const int M=1e5+10,inf=1e9+7;
struct node{
int f,s,cnt;
bool operator<(const node&o)const{return f==o.f?s<o.s:f<o.f;}
}v[M];
int n,m,mx;
int pcnt[2][M],pmax[2][M],pmin[2][M],pcmx[2][M],pcmn[2][M];
int scnt[2][M],smax[2][M],smin[2][M],scmx[2][M],scmn[2][M];
int main(){
freopen("hamming.in","r",stdin);
freopen("hamming.out","w",stdout);
for(int i=0;i<2;i++)
for(int j=0;j<M;j++) pmin[i][j]=smax[i][j]=inf;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&v[i].s,&v[i].f),v[i].cnt=1;
std::sort(v+1,v+1+m); int tot=0;
for(int i=1;i<=m;i++)
if(v[i].f!=v[i-1].f||v[i].s!=v[i-1].s||i==1) v[++tot]=v[i];
else v[tot].cnt+=v[i].cnt;
m=tot; //printf("m=%d\n",m);
for(int i=1;i<=m;i++){
int col=v[i].s;
pcnt[col][i]=pcnt[col][i-1]+v[i].cnt,pcnt[col^1][i]=pcnt[col^1][i-1];
pmax[col][i]=v[i].f,pmax[col^1][i]=pmax[col^1][i-1];
pcmx[col][i]=v[i].cnt,pcmx[col^1][i]=pcmx[col^1][i-1];
//pmin[col][i]=std::min(pmin[col][i-1],v[i].f),pmin[col^1][i]=pmin[col^1][i-1];
if(pmin[col][i-1]==inf)
pmin[col][i]=v[i].f,pcmn[col][i]=v[i].cnt;
else
pmin[col][i]=pmin[col][i-1],pcmn[col][i]=pcmn[col][i-1];
pmin[col^1][i]=pmin[col^1][i-1],pcmn[col^1][i]=pcmn[col^1][i-1];
}
for(int i=m;i>=1;i--){
int col=v[i].s;
scnt[col][i]=scnt[col][i+1]+v[i].cnt,scnt[col^1][i]=scnt[col^1][i+1];
smin[col][i]=v[i].f,smin[col^1][i]=smin[col^1][i+1];
scmn[col][i]=v[i].cnt,scmn[col^1][i]=scmn[col^1][i+1];
//smax[col][i]=std::max(smax[col][i+1],v[i].f),smax[col^1][i]=smax[col^1][i+1];
if(smax[col][i+1]==inf)
smax[col][i]=v[i].f,scmx[col][i]=v[i].cnt;
else
smax[col][i]=smax[col][i+1],scmx[col][i]=scmx[col][i+1];
smax[col^1][i]=smax[col^1][i+1],scmx[col^1][i]=scmx[col^1][i+1];
}
// for(int i=1;i<=m;i++)
// printf("p[%d][1]={%d,%d,%d,%d,%d}\n",i,pcnt[1][i],pmax[1][i],pcmx[1][i],pmin[1][i],pcmn[1][i]);
// for(int i=1;i<=m;i++)
// printf("s[%d][1]={%d,%d,%d,%d,%d}\n",i,scnt[1][i],smax[1][i],scmx[1][i],smin[1][i],scmn[1][i]);
long long cnt=0; int ans=0;
for(int b=1;b<=m;b++){
int col=v[b].s;
//(fa,sa)<(fb,sb)<(fc,sc)
//(0,0,0),(1,1,1)
if(pcnt[col][b-1]&&scnt[col][b+1]){
//printf("case 1!\n");
int tmp=2*(smax[col][b+1]-pmin[col][b-1]);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*pcmn[col][b-1]*v[b].cnt*scmx[col][b+1];
}
//(1,0,0),(0,1,1)
if(pcnt[col^1][b-1]&&scnt[col][b+1]){
//printf("case 2!\n");
int tmp=2*(n-v[b].f+pmax[col^1][b-1]);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*pcmx[col^1][b-1]*v[b].cnt*scnt[col][b+1];
}
//(0,0,1)(1,1,0)
if(pcnt[col][b-1]&&scnt[col^1][b+1]){
//printf("case 3!\n");
int tmp=2*(n+v[b].f-smin[col^1][b+1]);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*pcnt[col][b-1]*v[b].cnt*scmn[col^1][b+1];
}
//(0,1,0),(1,0,1)
if(pcnt[col^1][b-1]&&scnt[col^1][b+1]){
//printf("case 4!\n");
int tmp=2*n;
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*pcnt[col^1][b-1]*v[b].cnt*scnt[col^1][b+1];
}
//(fa,sa)<(fb,sb)=(fc,sc)
//(0,0),(1,1)
if(pcnt[col][b-1]){
//printf("case 5!\n");
int tmp=2*(v[b].f-pmin[col][b-1]);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*pcmn[col][b-1]*v[b].cnt*(v[b].cnt-1)/2;
}
//(1,0),(0,1)
if(pcnt[col^1][b-1]){
//printf("case 6!\n");
int tmp=2*(n-v[b].f+pmax[col^1][b-1]);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*pcmx[col^1][b-1]*v[b].cnt*(v[b].cnt-1)/2;
}
//(fa,sa)=(fb,sb)<(fc,sc)
//(0,0),(1,1)
if(scnt[col][b+1]){
//printf("case 7!\n");
int tmp=2*(smax[col][b+1]-v[b].f);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*scmx[col][b+1]*v[b].cnt*(v[b].cnt-1)/2;
}
//(1,0),(0,1)
if(scnt[col^1][b+1]){
//printf("case 8!\n");
int tmp=2*(n+v[b].f-smin[col^1][b+1]);
if(tmp>ans) ans=tmp,cnt=0;
if(tmp==ans) cnt+=1ll*scmn[col^1][b+1]*v[b].cnt*(v[b].cnt-1)/2;
}
//(fa,sa)=(fb,sb)=(fc,sc)
if("smr ak ioi"){
//printf("case 9!\n");
int tmp=0;
if(tmp==ans) cnt+=1ll*v[b].cnt*(v[b].cnt-1)*(v[b].cnt-2)/6;
}
}
printf("%lld",cnt);
return 0;
}
T4
题面
程序员不能总是整天坐着编程。有时站起来离开办公桌，休息一下，与同事闲聊，甚至玩一会，也是十分好的主意。F 公司的程序员就特别喜欢一种球类游戏。
让我们想象一个在笛卡尔坐标系平面上玩的游戏。玩家坐落在点(0; 0) 上，选择任意一个方向，扔出球。飞了一会儿的球在距离原点d 的地方撞击了平面，然后按照原来的方向继续飞。在第一次撞击之后，它继续飞且在距离原点
2d 的地方第二次撞击平面，接着诸如此类（按照选定的方向继续飞行，并且每隔d 单位距离撞击一次平面）。因为在F 公司的所有程序员都非常强壮，所以球可以飞到无穷远处。
平面上画有n 个圆。如果球撞击平面且撞在一个画在平面上的圆内（包括边界），那么玩家得一分。球可以一次击中多个圆，并且对于它们每一个得一分（如果球在移动过程中一共撞击了某一个圆x 次，那么玩家从中能得到x 分）。
计算玩家向任意方向扔一个球所能得到的最大分数。注意可能有实数坐标。
sol
很厉害的一道计算几何+差分。
对于一个圆看它能和多少个 \((0,0)\) 为圆心，半径为 \(k \cdots d\) 的圆相交/相切。
相交/相切会产生交点。可以发现，在一条射线旋转的过程中（对应扔球方向），只有经过这些交点，才会影响到答案。
所以考虑对角度差分。若交点为 \(A,B\) 两点，那么在 \(\angle AOB\) 之间答案加一。最后寻找最大答案即可。
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long double LD;
const double pii=acos(-1);
const int M=2e4+10,N=5e5+10;
int cnt; LD pos[N],neg[N];
int n,d,ans,tot;
#define sq(x) ((x)*(x))
#define ichika(x,y) make_pair(x,y)
#define nino first
#define miku second
int main(){
scanf("%d%d",&n,&d);
for(int i=1,x,y,r;i<=n;i++){
scanf("%d%d%d",&x,&y,&r);
LD alpha=atan2(y,x);
if(alpha<0) alpha+=pii*2;
LD dis=sqrt(sq(x)+sq(y));
for(int k=ceil((dis-r)/d);k<=floor((dis+r)/d);k++){
LD R=k*d;
LD beta=acos((sq(dis)+sq(R)-sq(r))/(2*dis*R));
LD v1=alpha-beta,v2=alpha+beta;
if(v2>2*pii) v2-=2*pii,tot++;
pos[++cnt]=v1,neg[cnt]=v2;
}
}
ans=tot;
sort(pos+1,pos+1+cnt),sort(neg+1,neg+1+cnt);
for(int i=1,j=1;i<=cnt;){
LD ang=pos[i];
for(;i<=cnt&&pos[i]==ang;i++) tot++;
for(;j<=cnt&&neg[j]<ang;j++) tot--;
ans=max(ans,tot);
}
printf("%d",ans);
return 0;
}