牛客算法周周练7

A、收集纸片

题意：给出一个大小 $x*y$ 的房间，还有一个人的初始位置和n个纸片的位置，每个相邻格子的距离为1。问收集完所有纸片后回到起点最小需要走多少路。典型的旅行商问题。
思路：
1. $n$ 个纸片和起点组成 $n+1$ 个点，预处理 $dis[i][j]$ ，表示第i个点和第j个点之间的距离。
2.状压dp的状态dp[s][i]，表示经过集合s到达点i的花费（s采用二进制存储的形式，表示集合中的元素，列如s=3，3的二进制是11，表示起点和第一个纸片在集合s中）。
3.初始化dp[1][0]=0，意思就是在起点的时候花费为0，对于那些还没有转移的状态明显初始化是无穷大。
5.写过旅行商问题这题就很简单了，状态转移方程很好懂的，代码里面有不是注释，看看就明白了。
Code：

#include<bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int ans,a[11][2],dis[11][11],dp[1<<11][11];
int main() {
    int T,n,x,y,lim;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d%d%d",&x,&y,&a[0][0],&a[0][1],&n);//a[0]是初始位置
        for (int i=1; i<=n; i++)
            scanf("%d %d",&a[i][0],&a[i][1]);
        for (int i=0; i<=n; i++)
        for (int j=i+1; j<=n; j++)
                dis[j][i]=dis[i][j]=abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]);
                //计算n+1个点之间的距离（包括起点） 
        memset(dp,0x3f,sizeof dp),ans=0x3f3f3f3f;
        dp[1][0]=0,lim=(1<<(n+1))-1;//lim经过了n+1个点 
        for(int i=0;i<=lim;++i)
        for(int j=0;j<=n;++j){
            if(i&(1<<j)==0) continue;//集合i里没有j 
            for(int k=0;k<=n;++k) {
                if(i&(1<<k)) continue;
                dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dis[j][k]);
            }
        }//集合i中的j走到k
        for (int i=1; i<=n; i++)
            ans=min(ans,dp[lim][i]+dis[i][0]);//枚举所有可能 
        printf("The shortest path has length %d\n",ans);
    }
}

D、华华和月月逛公园

题意：n个点m条边，接下来m条无向边，保证给定的图是连通的，无重边和自环。可能有几条路是不一定要经过的，输出一行一个非负整数表示不一定要经过的边有几条。
思路：Tarjan算法变形
Tarjan算法我就写过有向边判断强连通分量的 $\Rightarrow$ 模板。这一题可以看成只有一个强连通分量，而且又是一组数据，所以相对于模板，可以省去初始化和给每个强连通分量编号。
1.给每个处理的点编号，先处理的编号小，当后处理的点的编号比前面的小，表示出现回退边。
2.有回退边表示成环了，也就是说这个边多余了。
3.记录不是回退边的边，也就是必须走的边数ans。
4.总边数m减去ans就是最后的答案。
Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=6e5+7;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int cnt;//强连通分量（SCC）的个数
int low[maxn],num[maxn],dfn;
int head[maxn],Next[maxm],to[maxm],tot;
int ans;
inline void add(int u,int v) {
    to[++tot]=v;
    Next[tot]=head[u];
    head[u]=tot;
}
void dfs(int u,int fa) {
    low[u]=num[u]=++dfn;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(!num[v]) {
            dfs(v,u); 
            low[u]=min(low[v],low[u]);
            if(low[v]>num[u])    ++ans;
            //有回退边表示成环了，也就是说这个边多余了 
        }
        else if(v!=fa)//相当于剪枝 
            low[u]=min(low[u],num[v]);
    }
}
int n,m;
int main() {
    read(n),read(m);
    for(int i=1;i<=m;++i) {
        int u,v; read(u),read(v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    printf("%d\n",m-ans);
    return 0;
}

E、数字比较

题意：输入 $x、y$ ，输出 $x^{y}$ 和 $y^{x}$ 的关系。
思路：比较大小比较常用的是做差法和做商法，当遇到最差的情况100^100显然做差法是不现实的，会直接溢出，取余也不行，可以考虑做商法，K= $图片说明$ ，（假设 $图片说明$ ），如果如果y>=x， $图片说明$ 一定不成立，接着就是考虑y<x的时候，y/x<1可以先求出y/x的幂然后乘y到K>1结束，或者直到乘完了y。由数论知道在等式 $图片说明$ 两边取对数不等号不改变（只要两边的数不为0或负数），于是转为直接判断 $ylogx$ 和 $xlogy$ 。
Code：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int x,y;
    scanf("%d%d",&x,&y);
    double a=y*log(x),b=x*log(y);
    if(a==b) puts("=");
    if(a<b) puts("<");
    if(a>b) puts(">");
}