普及第六场题解报告

T1

*事实上T1可以打表，这使你充满了决心

#include<bits/stdc++.h>
using namespace std;

int n,sum,i=0,pw=1;

int main(){
    scanf("%d",&n);
    for(i=1;sum<n;++i,pw*=7){
        sum+=pw;
        if(sum>=n) break;
    }
    printf("%d",i);
    return 0;
}

T2

60%的数据:

考虑当前处在第 $i$ 的位置，分两类
第一类:直接走到 $i+1$ 的位置
第二类:先到一个传送门，再从传送门走到 $i+1$ 位置
复杂度为 $O(n^3)$

100%的数据:

由于可以从一个位置到达所有传送门的位置
所以可以预处理数组 $doors[x]$ 表示从传送门出来到位置 $x$ 的最短路
仍然分为两类
第一类：直接走到 $i+1$
第二类： $doors[i+1]$
复杂度为 $O(n^2)$

#include<bits/stdc++.h>
#define maxn 5010
#define INF 10000010
using namespace std;

int n,m,foot[maxn],X[maxn],Y[maxn],door[maxn],doors[maxn];//foot i  从i去往i+1
long long ans;

int main(){
//    freopen("test.in","r",stdin);
//    freopen("test.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%d",&X[i],&Y[i]),doors[i]=INF;
    for(int i=1;i<=m;++i) scanf("%d",&door[i]);
    for(int i=1;i<=n;++i){
        if(i<n) foot[i]=abs(X[i]-X[i+1])+abs(Y[i]-Y[i+1]);
        for(int j=1;j<=m;++j){
            int dis=abs(X[i]-X[door[j]])+abs(Y[i]-Y[door[j]]);
            doors[i]=min(doors[i],dis);
        }
    }
    for(int i=1;i<n;++i) ans+=1LL*min(doors[i+1],foot[i]);
    printf("%lld",ans);
    return 0;
}

T3

subtask1

可以打表，但是很累

subtask2

通过dfs枚举每个小球移动的位置，暴力计算出答案

60%的数据

我们考虑 $x$ 这个字符会把整个板子分成许多的空间
对于每一个空间，空间的球是绝对无法到达其他空间的，且整个空间内部只有球和空格
所以对于每个空间的小球进行位置的枚举
我们考虑最优答案是向下移动最多的情况，
对于每一个空间
最终小球会堆积在底部，这肯定是最优的。
而且每次使一个能移动的小球填充最底下的空格，是不会造成道路堵塞的问题的。证明:若每一个小球都不能直接移动到底部，则这不满足一个空间的定义。
枚举这次堆积在底部的球是怎么移动得到的。
复杂度:未知

100%的数据

我们考虑一个空间中的球，个数为 $n$ ，他们的高度为 $h_1,h_2,h_3...h_{n-1},h_n$
那么掉落掉底部后他们的高度为 $k_1,k_2,k_3...k_{n-1},k_n$
最终得分为 $h_1-k_1+h_2-k_2...h_{n-1}-k_{n-1}+h_n-k_n$
即 ${(h_1+h_2...+h_n)-(k_1+k_2...+k_n)}$
所以不必再用dfs枚举每个小球的位置

#include<bits/stdc++.h>
#define maxn 300010
#define ll long long
using namespace std;

int n,nums,num;
ll sum1,sum2[maxn],ans;
bool Map[maxn][3],v[maxn][3],have[maxn][3];

void dfs(int y,int x){
    if(x<1||x>2||y<1||y>n||v[y][x]||Map[y][x]) return;
    v[y][x]=true;
    if(have[y][x]) sum1+=1LL*y,++num;//计算h的总和
    ++nums;sum2[nums]=sum2[nums-1]+1LL*y;//计算k的前缀
    dfs(y,x-1);//先考虑左右，再考虑上面，因为要使小球尽量堆积在底部
    dfs(y,x+1);
    dfs(y+1,x);
}

int main(){
//    freopen("test.in","r",stdin);
//    freopen("test.out","w",stdout);
    scanf("%d",&n);
    for(int i=n;i>=1;--i){
        for(int j=1;j<=2;++j){
            char c;
            cin>>c;
            if(c=='x') Map[i][j]=true;
            if(c=='o') have[i][j]=true;
        }
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=2;++j){
            if(!v[i][j]){
                dfs(i,j);
                ans+=sum1-sum2[num];
                while(nums--) sum2[nums]=0;
                sum1=0,num=nums=0;
            }
        }
    printf("%lld",ans);
    return 0;
}

T4

基本原理和T2一致

subtask1

dfs大法

subtask2

对于k=0的情况，每次跑单源最短路进行从 $i$ 到 $i+1$ 的最短路线即可

60%的数据

如上述，可以用 $spfa$ 对每个点跑最短路，然后用T2同理的 $doors$ 进行记录，后分类即可

100%的数据

要堆优化的dij处理从每个位置出发的最短路
复杂度 $O(n^2log_2(n+m))$

#include<bits/stdc++.h>
#define maxn 2010
#define ll long long
#define INF 10000000000010
using namespace std;

int n,m,k,door[maxn];
ll foot[maxn],doors[maxn],ans;

struct EDGE{
    int nxt,to;
    ll dis;
}edge[maxn<<4];
int head[maxn],edge_num;
void add_edge(int from,int to,ll dis){
    edge[++edge_num].nxt=head[from];
    edge[edge_num].to=to;
    edge[edge_num].dis=dis;
    head[from]=edge_num;
}

ll dis[maxn];
struct node{
    int drop;
    ll dis_sum;
}tmp;
bool operator <(node x,node y){
    return x.dis_sum>y.dis_sum;
}

bool v[maxn];
priority_queue <node> q;
void PusH(int dr,ll d){
    tmp.drop=dr,tmp.dis_sum=d;
    q.push(tmp);
}
void Dij(int s){
    for(int i=1;i<=n;++i) dis[i]=INF,v[i]=false;
    dis[s]=0;
    PusH(s,0);
    while(!q.empty()){
        ll dis_sum=q.top().dis_sum;int x=q.top().drop;
        q.pop();
        if(v[x]) continue;
        v[x]=true;
        for(int i=head[x];i;i=edge[i].nxt){
            int gr=edge[i].to;
            if(dis[gr]>edge[i].dis+dis_sum){
                dis[gr]=edge[i].dis+dis_sum;
                PusH(gr,dis[gr]);
            }
        }
    }
}


int main(){
//    freopen("test.in","r",stdin);
//    freopen("test.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i) doors[i]=INF;
    for(int i=1;i<=m;++i){
        int a,b;ll c;
        scanf("%d%d%lld",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    for(int i=1;i<=k;++i) scanf("%d",&door[i]);
    for(int i=1;i<=n;++i){
        Dij(i);
        if(i<n) foot[i]=dis[i+1];
        for(int j=1;j<=k;++j)
            doors[i]=min(doors[i],dis[door[j]]);
    }
    for(int i=1;i<n;++i) ans+=min(doors[i+1],foot[i]);
    printf("%lld",ans);
    return 0;
}