苦修者
2分钟前

这道题目,可以按照右端点排序吗?

不可以的话,原因是什么?




wyc1996
17分钟前

题目描述

给定一个二分图,其中左半部包含n1个点(编号1~n1),右半部包含n2个点(编号1~n2),二分图共包含m条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

算法:匈牙利求二分图的最大匹配

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

C++代码

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

using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
int n1,n2,m;
int match[N];
bool st[N];
int cnt;

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

bool find(int x)
{
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            if(!match[j] || find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin>>n1>>n2>>m;
    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof st);
        if(find(i))cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


新鲜事 原文

RobertTarjan
29分钟前
Hi



刘小可
32分钟前

(暴力枚举)

将环拆成链的方法:将字符串复制一遍拼接在原字符串后面

C++ 代码

#include<iostream>
using namespace std;
const int N=710;
char s[N];
int get(char ch)
{
    if(ch=='b') return 1;
    else if(ch=='r') return 2;
    else return 0;
}
int main()
{
    int n;
    cin>>n>>s;
    for(int i=0;i<n;i++) s[i+n]=s[i];
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int l=i,r=i+n-1;
        int left=0,right=0,cnt=0;
        while(l<=r&&(s[l]=='w'||(get(s[l])|left)!=3))  //位运算优先级很低 记得加括号
        {
            left|=get(s[l]);
            l++;
            cnt++;
        }
        while(l<=r&&(s[r]=='w'||(get(s[r])|right)!=3))
        {
            right|=get(s[r]);
            r--;
            cnt++;
        }
        ans=max(ans,cnt);
    }
    cout<<ans;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



题目描述

一个数n可以进行两种变换:

1.除以一个非自身的约数
2.加上1

输出能使数字n变成1的最小变换次数

输入

  1. 第一行一个整数 $t$, $ 1 <= t <= 1000 $, 表示测试数据数量
  2. 接下来的$t$行,每行包含一个整数 $n$, $ 1 <= n <= 10^9$

输出

共$t$行,每一行输出把$n$变成$1$的最小变换次数

样例

输入:
6
1
2
3
4
6
9

输出:

0
1
2
2
2
3

解释:

1
2→1
3→2→1
4→2→1
6→2→1
9→3→2→1

算法1

(数学) $O(1)$
  1. 将$n$分成以下几种情况讨论
    1. $n == 1$, $ ans = 0 $.
    2. $n == 2$, $ ans = 1 $, 因为 $2→1$
    3. $n == 3$, $ ans = 2 $, 因为 $3→2→1$
    4. $n > 3$:
      • 如果 $3|n$, 那么 $ans = 3$, 因为 $n→3→2→1$
      • 如果 $2|n$, 那么 $ans = 2$, 因为 $n→2→1$
      • 如果 $ n mod 2 == 1$, 那么 $ ans = 3$, 因为总有 $n→ (n + 1) → 2→1$ 且 $3|n$的情况不优于这种情况。
  2. 因此分情况讨论$n$的类型即可。

时间复杂度

  1. 只需要判断$n$是否是 $1$, $2$, $3$, 或其$奇偶性$,因此时间复杂度为 $O(1)$.

C++ 代码

int T;
cin >> T;
while(T --){
    int x;
    cin >> x;
    if (x == 1) cout << 0 << endl;
    else if (x == 2) cout << 1 << endl;
    else if (x == 3) cout << 2 << endl;
    else if (x % 2 == 0) cout << 2 <<endl;
    else cout << 3 << endl;
}



静态链表重点分析

相信很多只学过动态链表的同学刚接触到静态链表的时候会一脸懵,但其实只要将两种链表对比来看就很清晰了:

动态链表的逻辑结构与实际结构是一致的;

静态链表的逻辑结构与实际结构是不一致的;

动态链表是利用指针将一个个节点连接起来,而静态链表是用两个数组来实现的;

也即是说,对于动态链表,只要得到其头节点的指针p,按照p = p->next即可进行遍历;

但对于静态链表,如果按照for(int i = 0; i < n; i ++)这样通用的方式去遍历e[N]数组,是无法得到正确的序列的。

对于静态链表的正确遍历方式是,由i = head进入,读取e[i]作为value,ne[i]作为next,直到 i = -1停止;

index作为实际结构的标识,标志着数组存储邻接表的实际索引。

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int head, e[N], ne[N], index;//最好不要命名为index,会与string库中的函数冲突
//index实际上是标识头节点的指针,即头节点的下标索引
void init()//初始化
{
    head = -1;// -1相当于动态链表里的NULL
    index = 0;//两个数组从0开始存储
}

void insert_head(int x)//插到头节点后
{
    e[index] = x;
    ne[index] = head;
    head = index;
    index ++ ;
}

void delete_node(int k)
{
    ne[k - 1] = ne[ne[k - 1]];
    //注意这里不能按照动态链表的思想写成ne[k - 1] = ne[k]
    //因为ne[k]是ne[k - 1]实际上的下一个位置 而不是逻辑上的下一个位置
}

void insert_node(int k, int x)
{
    e[index] = x;
    ne[index] = ne[k - 1];
    ne[k - 1] = index;
    index ++ ;
}

int main()
{   
    init();
    int m;
    cin >> m;
    for(int i = 0; i < m; i ++ )
    {
        char button;
        int x, k;
        cin >> button;
        if(button == 'H')
        {
            cin >> x;
            insert_head(x);
        }
        else if(button == 'D')
        {
            cin >> k;
            if(!k) head = ne[head];
            else delete_node(k);
        }
        else if(button == 'I')
        {
            cin >> k >> x;
            insert_node(k, x);
        }
    }
    for(int i = head; i != -1; i = ne[i])
    {
        cout << e[i] << ' ';
    }
    return 0;
}



wyc1996
53分钟前

题目描述

给定一个n个点m条边的无向图,图中可能存在重边和自环。

请你判断这个图是否是二分图。

算法:深度优先搜索

时间复杂度:O(N+M)

C++代码

#include<iostream>
#include<cstring>

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

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

bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(color[j]==-1){
            if(!dfs(j,!c))
                return false;
        }
        else if(color[j]==c)return false;
    }
    return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    memset(color,-1,sizeof color);

    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }

    bool success=true;
    for(int i=1;i<=n;i++){
        if(color[i]==-1){
            if(!dfs(i,0)){
                success=false;
                break;
            }
        }
    }
    if(success)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}



houghstc
55分钟前

这篇分享记录一下我对数组模拟邻接表的理解。


首先假设我们有n个点(n <= N),m条边(m <= M)。


我们可以想一下对于任意一个结点u, 需要记录邻边的哪些信息。
这些信息应该包括这条邻边的终点,权重,以及下一条邻边的编号。
所以我们可以定义一个struct来表示邻边:

struct Edge     // 注意这里不需要记录边的起点
{
    int eid;    // 该条边的编号
    int e;      // 该条边的终点
    int w;      // 该条边的权重
    int nxt;    // 下一条邻边的编号
};

如果我们用上面的数组来记录邻边的信息,那么我们只需要定义如下变量来表示邻接表:

// 注意N和M的区别
int h[N];
Edge edges[M];
int eidx;

由于每条边都记录了下一条边的编号,这样我们只要把每个结点的第一条邻边的编号记录在h数组,我们就可以遍历它的每一条邻边了。


如果我们把Edge里的信息分开存到不同数组里,那么我们可以得到平时我们看到的变量定义:

// 注意N和M的区别
int h[N];
int e[M], w[M], nxt[M];   // 注意这些数组的下标表示了边的编号
int eidx;

这里每个数组的下标的含义不一样。
关键的事情说三遍:h数组的下标为结点的编号,e,w,nxt数组的下标为边的编号,eidx为边的编号
关键的事情说三遍:h数组的下标为结点的编号,e,w,nxt数组的下标为边的编号,eidx为边的编号
关键的事情说三遍:h数组的下标为结点的编号,e,w,nxt数组的下标为边的编号,eidx为边的编号


如果理解了以上,下面就很好理解了。
有向图的邻接表存储就是对于每个点 u 对应一个头节点h[u],记录第一条邻边的编号。
e, w, nxt数组的编号和建图的顺序有关,对于某一个点u, 它的所有邻边的编号不一定是连续的。
nxt[eidx]=h[u]; h[u]=eidx; 这个操作就是把新建的边插入表头。(先把新建的边的next指向现在队头的next,然后更新队头的next)
然后再eidx++, 给下一次建边使用


下边用图模拟一下加入四条边的过程
1. 初始状态
Screen Shot 2020-12-02 at 7.49.05 AM.png
2. 加完第一条边(1,2,9)之后
Screen Shot 2020-12-02 at 7.49.43 AM.png
3. 加完第二条边(2,4,1)之后
Screen Shot 2020-12-02 at 7.49.49 AM.png
4. 加完第三条边(1,3,3)之后
这里可以看到后加入的边,反而在邻接表的最前面
Screen Shot 2020-12-02 at 7.50.02 AM.png
5. 加完第四条边(3,4,5)之后
Screen Shot 2020-12-02 at 7.50.10 AM.png


最后是代码及注释

const int N = 1010, M = 1010;

int h[N], e[M], w[M], nxt[M], eidx;

void add(int u, int v, int weight)   // 添加有向边 u->v, 权重为weight
{
    e[eidx] = v;        // 记录边的终点
    w[eidx] = weight;   // 记录边的权重
    nxt[eidx] = h[u];   // 将下一条边指向结点u此时的第一条边
    h[u] = eidx;        // 将结点u的第一条边的编号改为此时的eidx
    eidx++;             // 递增边的编号edix, 为将来使用
}

void iterate(int u)   // 遍历结点u的所有邻边
{
    // 从u的第一条边开始遍历,直到eidx==-1为止
    for(int eidx = h[u]; eidx != -1; eidx = nxt[eidx])
    {
        int v = e[eidx];
        int weight = w[eidx];
        cout << u << "->" << v << ", weight: " << weight << endl;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);  // 初始化h数组为-1
    eidx = 0;                 // 初始化边的编号为0

    while(m--)
    {
        int u, v, weight;
        cin >> u >> v >> weight;
        add(u, v, weight);
    }

    for(int u = 1; u <= n; ++u)
        iterate(u);

    return 0;
}




cccd
1小时前

题目描述

树状数组动态维护区间修改,区间求和的模板题

C++ 代码

#include<bits/stdc++.h>//区间修改 区间求和
using namespace std;

typedef long long ll;
const int N=1e5+5;
ll t1[N],t2[N],n,m,sum[N],x;
inline void add1(ll x,ll k){
    for(;x<=n;x+=x&-x)t1[x]+=k;
}
inline void add2(ll x,ll k){
    for(;x<=n;x+=x&-x)t2[x]+=k;
}
inline ll ask1(ll x){
       ll ans=0;
       for(;x;x-=x&-x)ans+=t1[x];
       return ans;
} 
inline ll ask2(ll x){
       ll ans=0;
       for(;x;x-=x&-x)ans+=t2[x];
       return ans;
}

int main(){

       cin>>n>>m;
       for(int i=1;i<=n;i++)cin>>x,sum[i]=sum[i-1]+x;
       while(m--){
           char s;
           cin>>s;
           if(s=='C'){
               ll l,r,d;
               cin>>l>>r>>d;
               add1(l,d);
               add1(r+1,-d);
               add2(l,l*d);
               add2(r+1,-(r+1)*d);
           }
           else {
               ll l,r;
               cin>>l>>r;
               ll ans=(sum[r]+(r+1)*ask1(r)-ask2(r))-(sum[l-1]+l*ask1(l-1)-ask2(l-1));
               cout<<ans<<endl;
           }
       }
}



wyc1996
2小时前

题目描述

给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

算法:kruskal算法

时间复杂度:$Mlog(M)$

需要注意

(1)为了枚举边方便,不用使用邻接表或者邻接矩阵进行存储
(2)需要使用并查集维护集合的关系

C++代码

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

using namespace std;
const int N=100010,M=2*N;
struct Range
{
    int a,b,w;
    bool operator<(const Range& r)const{
        return w<r.w;
    }
}range[M];
int n,m;
int p[N];

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        range[i]={a,b,w};
    }
    sort(range,range+m);

    for(int i=1;i<=n;i++)p[i]=i;

    int cnt=0;
    int res=0;
    for(int i=0;i<m;i++){
        int a=range[i].a,b=range[i].b;
        int fa=find(a),fb=find(b);
        if(fa!=fb){
            p[fa]=fb;
            res+=range[i].w;
            cnt++;
        }
    }
    if(cnt!=n-1)cout<<"impossible"<<endl;
    else cout<<res<<endl;
    return 0;
}