本文共 4094 字，大约阅读时间需要 13 分钟。

Powered by:AB_IN 局外人

打表出来二分即可，发现打表到6的时候，就已经超10000了，我其实打多了。

#include<bits/stdc++.h>using namespace std;int a[20],n,ans = 1,b[20];int main(){       cin >> n;    for(int i = 1 ;i <= 10; i++){           a[i] = ans;        ans *= 7;        b[i] = a[i] + b[i-1];    }    int id = lower_bound(b+1, b+11, n) - b;    cout<< id <<endl;}

题意就是要从$1$走到$2$再走到$3$，一直走到$n$的最短距离，中间有设$m$个传送点，可以使在任何地方都能到达传送点。

所以$a_i$到$a_{i+1}$最短路径无非就是两种情况：

• 第一种：直接过去
• 第二种：传送至传送门，从传送门直接过去。

#include <bits/stdc++.h>using namespace std;const int N=5e3+10;struct sa{       int x;    int y;}a[N];vector <int> v;int n,m,x,y,c,mn,ans;int main(){       scanf("%d%d",&n,&m);    for(int i = 1; i <= n ;i++){           scanf("%d%d",&a[i].x,&a[i].y);    }    for(int i = 1; i <= m ;i++){           scanf("%d",&c);        v.push_back(c);    }    for(int i = 1; i <= n - 1 ;i++){           if( find(v.begin(),v.end(),i+1) != v.end()) continue;        mn = abs(a[i].x - a[i+1].x) + abs(a[i].y - a[i+1].y);        for(auto j : v){               mn = min(mn , abs(a[j].x - a[i+1].x) + abs(a[j].y - a[i+1].y));        }        ans += mn;    }    printf("%d\n",ans);    return 0;}

想要代码量少，思维量一定要大。
这个题可以用$dfs$爆搜，但我太菜了写不出来 ，比赛时写了个$bfs$只得了30分。赛后看了眼大佬们的代码，才发现是真的巧妙。

首先核心思想是贪心。反向输入图形，把第$n$行当作第$1$行，现在的目标就是尽可能的去让球去填满上面的空。但是，有三种情况是会封死路的

• xx
• .x
  x.
• x.
  .x

所以要分区。所以现在问题就转化成了，让球去尽量往上填这一分区的空。

先给出代码

#include<bits/stdc++.h>using namespace std;const int N = 3e5+10;int n , r , f , Q[N << 1];long long ans=0;char a[N][5];int main(){       scanf("%d", &n);    for(int i = n; i >= 1;i--) scanf("%s", a[i]);    for(int i = 1; i <= n;i++)    {       	if(a[i][0] != 'x') Q[r++] = i;    	if(a[i][1] != 'x') Q[r++] = i;    	if(a[i][0] == 'o') ans += i - Q[f++];    	if(a[i][1] == 'o') ans += i - Q[f++];    	if((a[i][0]=='x'&&a[i][1]=='x')||(a[i][0]=='x'&&a[i+1][1]=='x')||(a[i+1][0]=='x'&&a[i][1]=='x')) r = f = 0;	}	printf("%lld\n", ans);    return 0;}

一一解释变量。

• $Q$数组下标是递增的，代表目前除了x的个数；
  $Q$数组的值代表这个不是x的字符是第几行的。
  顺着下来，上去的球就也相当于点了。

• $r$就是下标。

  if(a[i][0] != 'x') Q[r++] = i;if(a[i][1] != 'x') Q[r++] = i;

• $f$为全部空位（包括点和已经上去的球）已被球占用了的个数，也同样作为$Q$的下标。

  if(a[i][0] == 'o') ans += i - Q[f++];if(a[i][1] == 'o') ans += i - Q[f++];

  $ans$加上当前行减去目前存在空位最上面的行，$f$继续自增。

• 最后，就是当出现三种拦路的情况，直接让 $r,f$都清$0$即可。相当于就是开辟了个新的分区，啥都清$0$了。

思路很简单，先给每个点跑一遍最短路，记录$a_i$到$a_{i+1}$的路径长度$l_1$。再去管传送门，从每个传送门这跑一遍最短路，记录传送门到$a_{i+1}$的路径$l_2$，$l_1$和$l_2$取个最小值即可。

我一开始为了图个方便，把传送门和每个点都建了个边权为$0$的边，导致凭空多出来至少$6e5$条边，就T了，呜呜呜。。。

#include<bits/stdc++.h>using namespace std;#define ll long longconst int N=1e6+10;const int inf=0x3f3f3f3f;struct sa{       int dis;    int pos;};bool operator <(const sa &a,const sa &b) {    return a.dis>b.dis; }priority_queue<sa>q;struct Edge{       int u, v, w, next;}edge[N<<2];int head[N];int cnt;void add_edge(int u, int v, int w){       edge[cnt].u = u;    edge[cnt].v = v;    edge[cnt].w = w;    edge[cnt].next = head[u];    head[u] = cnt++;}int dis[N];bool vis[N];int n,m,s,t,u,v,w,T,k;void dij(int s,int v,int d[]){       memset(vis,0,sizeof(vis));    for (int i=1;i<=n;i++) d[i] = inf;    d[s]=v;    q.push( (sa) {   v,s});	while(!q.empty())	{   		sa ns=q.top();		q.pop();		int x=ns.pos;		if(vis[x]) continue;		vis[x]=1;		for(int i=head[x]; i!=-1 ; i=edge[i].next)		{   			int to=edge[i].v;			int dd=d[x]+edge[i].w;			if(d[to]>dd)			{   				d[to]=dd;				q.push( (sa) {   d[to],to});			}		}	}}int cnt1[N];int main(){       memset(head,-1,sizeof(head));    scanf("%d%d%d",&n,&m,&k);    for(int i = 1 ;i <= m ;i++){           scanf("%d%d%lld",&u,&v,&w);        add_edge(u, v, w);        add_edge(v, u, w);    }    for(int i = 1 ;i <= n - 1 ;i++){           dij(i, 0, dis);        cnt1[i + 1] = dis[i + 1];    }    for(int i = 1 ;i <= k; i++){           scanf("%d",&u);        dij(u , 0 , dis);        for(int j = 1 ;j <= n - 1; j++){              cnt1[j + 1] = min( cnt1[j + 1] , dis[j + 1]);        }    }    long long ans = 0;    for (int i = 2; i <= n; i++) {           ans += cnt1[i];    }    printf("%lld",ans);	return 0;}

完结。