头像

wyc1996

哈尔滨工业大学




在线 



wyc1996
19分钟前

题目描述

给定一颗树,树中包含n个结点(编号1~n)和n-1条无向边。

请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

算法:深度优先搜索

时间复杂度:O(N)

需要注意

(1)本题的树存储的是双向边,因此需要布尔数组防止出现循环调用。
(2)由子节点信息更新父节点信息,先更新子节点信息。
(3)树定义是当且仅当任何两个点之间仅有一条路径的图,N个点共有N-1个边

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
bool st[N];
int n;
int res=N;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    int s=0;
    int sum=0;
    st[u]=true;

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(st[j])continue;
        int cnt=dfs(j);
        s=max(s,cnt);
        sum+=cnt;
    }
    s=max(s,n-sum-1);
    res=min(res,s);
    return sum+1;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);

    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<<res<<endl;
    return 0;
}



wyc1996
51分钟前

题目描述

在一个3×3的网格中,1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。

例如:

1 2 3
x 4 6
7 5 8

在游戏过程中,可以把“x”与其上、下、左、右四个方向之一的数字交换(如果存在)。

我们的目的是通过交换,使得网格变为如下排列(称为正确排列):

1 2 3
4 5 6
7 8 x

例如,示例中图形就可以通过让“x”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下:

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。

算法:宽度优先搜索

时间复杂度:指数

C++代码

#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<iostream>

using namespace std;
string ter="12345678x";
string str;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int bfs(string s)
{
    unordered_map<string,int>d;
    d[s]=0;
    queue<string>q;
    q.push(s);

    while(q.size()){
        auto t=q.front();
        q.pop();
        if(t==ter)return d[t];
        int k=t.find('x');
        int x=k/3,y=k%3;
        int distance=d[t];
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=3 || b<0 || b>=3)continue;
            swap(t[k],t[a*3+b]);
            if(!d.count(t)){
                d[t]=distance+1;
                q.push(t);
            }
            swap(t[k],t[a*3+b]);
        }
    }
    return -1;
}

int main()
{
    char s[2];
    while(scanf("%s",s)!=-1)str+=*s;
    cout<<bfs(str)<<endl;
    return 0;
}



wyc1996
2小时前

题目描述

给定一个n*m的二维整数数组,用来表示一个迷宫,数组中只包含0或1,其中0表示可以走的路,1表示不可通过的墙壁。

最初,有一个人位于左上角(1, 1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问,该人从左上角移动至右下角(n, m)处,至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0,且一定至少存在一条通路。

时间复杂度:$O(N·M)$

C++代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=110;
typedef pair<int,int>PII;
int g[N][N];
int d[N][N];
int dx[N]={-1,0,1,0};
int dy[N]={0,1,0,-1};
PII q[N*N];
int n,m;

int bfs()
{
    memset(d,-1,sizeof d);
    d[0][0]=0;
    int hh=0,tt=-1;
    q[++tt]={0,0};

    while(hh<=tt){
        auto t=q[hh++];
        for(int i=0;i<4;i++){
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a<0 || a>=n || b<0 || b>=m || d[a][b]!=-1|| g[a][b]==1)continue;
            d[a][b]=d[t.first][t.second]+1;
            q[++tt]={a,b};
        }
    }
    return d[n-1][m-1];
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&g[i][j]);
    cout<<bfs()<<endl;
    return 0;
}



wyc1996
9小时前

题目描述

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数n,请你输出所有的满足条件的棋子摆法。

暴力枚举:按照行枚举

时间复杂度:$N·N!$

需要注意

(1)存在不同的枚举方式:按照每个位置进行枚举(复杂度比较高)/按照行进行枚举(复杂度相对比较低)
(2)枚举的过程中需要保证包含所有的方案

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=10;
bool col[N],dg[2*N],udg[2*N];
char g[N][N];
int n;

void dfs(int u)
{
    if(u==n){
        for(int i=0;i<n;i++)printf("%s\n",g[i]);
        puts("");
        return;
    }    

    for(int i=0;i<n;i++){
        if(!col[i] && !dg[u+i] && !udg[n-u+i]){
            col[i]=dg[u+i]=udg[n-u+i]=true;
            g[u][i]='Q';
            dfs(u+1);
            g[u][i]='.';
            col[i]=dg[u+i]=udg[n-u+i]=false;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);
    return 0;
}



wyc1996
9小时前

题目描述

给定一个整数n,将数字1~n排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。

算法:爆搜(排列型枚举)

时间复杂度:$N!$

C++代码1:bool数组记录状态

#include<iostream>
#include<cstring>

using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;

void dfs(int u)
{
    if(u==n){
        for(int i=0;i<n;i++)cout<<path[i]<<" ";
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false; //bool变量需要恢复现场
            //path[u]=0; 这里path不需要恢复现场 因为全局变量可以被其他情况覆盖
        }
    }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

C++代码2:传递参数记录状态

这里有二进制位运算的思想

#include<iostream>
#include<cstring>

using namespace std;
const int N=10;
int path[N];
int n;

void dfs(int u,int state)
{
    if(u==n){
        for(int i=0;i<n;i++)cout<<path[i]<<" ";
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!(state>>i&1)){
            path[u]=i;
            state+=1<<i;
            dfs(u+1,state);
            state-=1<<i;
        }
    }
}

int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}



wyc1996
1天前

题目描述

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是TYVJ今年举办了一次线下七夕祭。

Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去TYVJ七夕祭游玩。

TYVJ七夕祭和11区的夏祭的形式很像。

矩形的祭典会场由N排M列共计N×M个摊点组成。

虽然摊点种类繁多,不过cl只对其中的一部分摊点感兴趣,比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani预先联系了七夕祭的负责人zhq,希望能够通过恰当地布置会场,使得各行中cl感兴趣的摊点数一样多,并且各列中cl感兴趣的摊点数也一样多。

不过zhq告诉Vani,摊点已经随意布置完毕了,如果想满足cl的要求,唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻,当且仅当他们处在同一行或者同一列的相邻位置上。

由于zhq率领的TYVJ开发小组成功地扭曲了空间,每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在Vani想知道他的两个要求最多能满足多少个。

在此前提下,至少需要交换多少次摊点。

算法:贪心 前缀和 公式递推

时间复杂度:$3N+Nlog(N)$

(1) 将行和列分别看成独立的操作
(2) 一维的环形均分问题可看参考题目:https://www.acwing.com/problem/content/124/

C++代码

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
const int N=100010;
int row[N],col[N],s[N],c[N];

LL execute(int a[],int n)
{
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    if(s[n]%n)return -1;
    int avg=s[n]/n;

    c[1]=0;
    for(int i=2;i<=n;i++)c[i]=s[i-1]-(i-1)*avg;

    sort(c+1,c+1+n);
    LL res=0;
    for(int i=1;i<=n;i++)res+=abs(c[i]-c[(n+1)/2]);
    return res;
}

int main()
{
    int n,m,cnt;
    scanf("%d%d%d",&n,&m,&cnt);

    for(int i=0;i<cnt;i++){
        int r,c;
        scanf("%d%d",&r,&c);
        row[r]++,col[c]++;
    }
    LL r=execute(row,n);
    LL c=execute(col,m);
    if(r!=-1 && c!=-1)printf("both %lld\n",r+c);
    else if(r!=-1)printf("row %lld\n",r);
    else if(c!=-1)printf("column %lld\n",c);
    else printf("impossible\n");
    return 0;
}



wyc1996
1天前

题目描述

在这个问题中,您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理n个不同整数的序列,直到序列按升序排序。

对于输入序列9 1 0 5 4,超快速排序生成输出0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

算法:归并排序求逆序对

时间复杂度:$N·log(N)$

笔记.jpg
每一只能消除一个逆序对,因此逆序对的数量就是需要的操作的数量

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=500010;
typedef long long LL;
int w[N];
int tmp[N];

LL merge_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=l+r>>1;
    LL res=merge_sort(l,mid)+merge_sort(mid+1,r);

    int i=l,j=mid+1,k=0;
    while(i<=mid && j<=r){
        if(w[i]<=w[j])tmp[k++]=w[i++];
        else{
            res+=mid-i+1;
            tmp[k++]=w[j++];
        }
    }
    while(i<=mid)tmp[k++]=w[i++];
    while(j<=r)tmp[k++]=w[j++];
    for(int i=l,j=0;i<=r;i++,j++)w[i]=tmp[j];
    return res;
}

int main()
{
    int n;
    while(cin>>n,n){
        for(int i=0;i<n;i++)scanf("%d",&w[i]);
        cout<<merge_sort(0,n-1)<<endl;
    }
    return 0;
}



wyc1996
1天前

题目描述

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

算法:对顶堆

时间复杂度:$N·log(N)$

对顶堆算法的典型应用,动态求序列的中位数
对顶堆算法基本仅用在这种情况

C++代码

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--){
        int id,n;
        scanf("%d%d",&id,&n);
        printf("%d %d\n",id,(n+1)/2);

        priority_queue<int,vector<int>,greater<int>>up;
        priority_queue<int>down;
        int cnt=0;

        for(int i=1;i<=n;i++){
            int t;
            scanf("%d",&t);
            if(down.empty() || t<=down.top())down.push(t);
            else up.push(t);
            if(down.size()>up.size()+1)up.push(down.top()),down.pop();
            if(up.size()>down.size())down.push(up.top()),up.pop();
            if(i&1){
                cout<<down.top()<<" ";
                if(++cnt%10==0)puts("");
            }
        }
        if(cnt%10)puts("");
    }
    return 0;
}



wyc1996
1天前

题目描述

从前有个人名叫 WNB,他有着天才般的记忆力,他珍藏了许多许多的宝藏。

在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。

题目是这样的:给你一大串数字(编号为 1 到 N,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你 M 个询问,每次询问就给你两个数字 A,B,要求你瞬间就说出属于 A 到 B 这段区间内的最大数。

一天,一位美丽的姐姐从天上飞过,看到这个问题,感到很有意思(主要是据说那个宝藏里面藏着一种美容水,喝了可以让这美丽的姐姐更加迷人),于是她就竭尽全力想解决这个问题。

但是,她每次都以失败告终,因为这数字的个数是在太多了!

于是她请天才的你帮他解决。如果你帮她解决了这个问题,可是会得到很多甜头的哦!

算法:RMQ(ST表)

时间复杂度:$Nlog(N)$

ST表(RMQ)主要解决区间最值的查询

C++代码

//RMQ问题:用于求解区间的最值问题
//本质是利用倍增的思想和DP的手段进行的预处理
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
const int N=200010;
const int M=20;
int w[N];
int f[N][M];  //状态表示的含义:以i开始,长度为1<<j这段区间的最值
int n,m;

void init()
{
    //先枚举长度 再枚举起点
    //保证在枚举长度比较大的区间之前 长度较小的区间已经被计算过
    for(int j=0;j<M;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(!j)f[i][j]=w[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
}
//区间最值查询
int query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);
    //可以确保覆盖整个区间
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    init();
    cin>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        cout<<query(l,r)<<endl;
    }
    return 0;
}



wyc1996
1天前

题目描述

有N个元素,编号1.2..N,每一对元素之间的大小关系是确定的,关系具有反对称性,但不具有传递性。

注意:不存在两个元素大小相等的情况。

也就是说,元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。

然而,这是一道交互式试题,这些关系不能一次性得知,你必须通过不超过10000次提问来获取信息,每次提问只能了解某两个元素之间的关系。

现在请你把这N个元素排成一行,使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。

例如,编号为a和b的两个元素,如果元素a小于元素b,则compare(a,b)返回true,否则返回false。

将N个元素排好序后,把他们的编号以数组的形式输出,如果答案不唯一,则输出任意一个均可。

算法:二分

时间复杂度:$O(N^2·log(N))$

C++代码

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

// 不一定一定要具有单调的全局关系才能进行二分
//二分不需要严格的边界关系
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int>res(1,1);
        for(int i=2;i<=N;i++){
            //找到小于等于i的最大的位置
            int l=0,r=res.size()-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(compare(res[mid],i))l=mid;
                else r=mid-1;
            }
            //现将结果插入到序列的末尾
            res.push_back(i);
            //将最末尾的结果交换到r+1
            for(int j=res.size()-2;j>r;j--)swap(res[j],res[j+1]);
            if(compare(i,res[r]))swap(res[r],res[r+1]);
        }
        return res;
    }
};