头像

莫争


访客:347

离线:6小时前



莫争
4天前

记录一些东西,当备忘录用

⭐1 spfa判断负环(正环)的时候,dist数组初始值是多少都行,但这个前提是你最初要把所有点都放进队列,因为这样才能确保有点能够更新其他点。如果是只加一个点(当然要确保这个点能走到环),dist数组还是要初始化成正无穷(最短路判负环)或者负无穷(最长路判正环)的。


⭐2 堆优化的迪杰斯特拉算法,每个点第一次出队的时候就是其最短路,第二次出队就是其第二短路,第k次出队就是其第k短路。


⭐3 一个广为人知的结论:图的染色问题中,最少颜色数量=最大团点的数量,但实际上这句话是错误的,因为只有 完美图才能满足这句话,而完美图的充要条件是:该图不包含点数大于等于5的奇数环(奇数环是指点数为奇数的环)。实际上这个充要条件目前也是个猜想,未被证明。


⭐4 在Bellman-Ford算法和Floyd算法中,有可能出现不可到达的两个点互相更新的情况,所以要判断一下dist[i][j]>=INF/2


⭐5 设a矩阵为恰好经过d1条边的最短路径矩阵,设b矩阵为恰好经过d1条边的最短路径矩阵,则通过一下这种加法后,c矩阵就是恰好经过(d1+d2)条边的最短路径矩阵

void add(int c[][N],int a[][N],int b[][N]) 
{
    static int temp[N][N];
    memset(temp,0x3f,sizeof temp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]);
    memcpy(c,temp,sizeof temp);
}

具体题目 345.牛站




莫争
5天前

题目描述

给你两个整数序列a和b,a长度为n,b长度为m。
请你求出两个长度相同的非空子序列(a中一个,b中一个),使其点积最大。

输入描述

第1行为n和m,第2行为a的n个数,第3行为b的m个数

输出描述

输出最大的点积

样例输入

4 3
2 1 -2 5
3 0 -6

样例输出

18

解释:a中选(2,-2),b中选(3,-6)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N],b[N];
int f[N][N],n,m; //f[i][j]为只从a数组的前i个和b数组的前j个中选的最大点积
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            //都选
            f[i][j]=max(0,f[i-1][j-1])+a[i]*b[j];
            //不选a[i]
            if(i>1) f[i][j]=max(f[i][j],f[i-1][j]);
            //不选b[j]
            if(j>1) f[i][j]=max(f[i][j],f[i][j-1]);
            printf("%d %d=%d\n",i,j,f[i][j]);
        }
    cout<<f[n][m];
    return 0;
}


分享 买电池

莫争
9天前

题目描述

在 N 个方格的一维走廊上,放置 K 个扫地机器人,扫地机器人可以向左右方向移动,并将该方格清扫干净。每个机器扫完地后都需要回到初始位置,同时每个方格区域至少被清扫一次,每个机器人移动一格花费一节电池。

假设我们只需要花费所有机器人中消耗电池最多的那个机器人的电池数(其他机器人不管)。那么请输出我们需要购买电池数的最小值。

输入格式

多组测试数据,第一行是数据组数。
之后每组测试数据的第一行包含两个整数 N 和 K。接下来 K 行,每行一个整数 Ai。

输出格式

输出一个整数表示答案,每个答案占一行。

样例输入

1
10 3
5
2
10

样例输出

6

数据规模

1 ≤ T ≤ 20 (T为数据组数)
1 ≤ K < N ≤ 100000
1 ≤ Ai ≤ N

思路

一看到这种求最大xxx的最小值(k小值),或者最小xxx的最大值(k大值),就要想到二分。
二分答案,然后check是否可以,check的方法就是先假设所有机器人都有着最多电池数,然后从小到大枚举每个机器人,然后先向左走,把左边界走到了后,再尽量向右走,若连左边界都走不到,那么就return false。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,k,robot[N];
bool check(int x)
{
    int l=1;
    for(int i=0;i<k;i++)
    {
        int t=x-max(0,robot[i]-l);
        if(t<0) return false;
        l=robot[i]+t+1;
    }
    if(l<=n) return false;
    return true;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<k;i++) scanf("%d",&robot[i]);
    sort(robot,robot+k);
    int l=0,r=N-3;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<2*l<<endl;

    return 0;
}



莫争
10天前

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=205,INF=0x3f3f3f3f;
int n,k,m,S,E;
int g[N][N],d[100][N][N];

//设a矩阵为恰好经过d1条边的最短路径矩阵,设b矩阵为恰好经过d1条边的最短路径矩阵
//则通过这种加法后,c矩阵就是恰好恰好经过(d1+d2)条边的最短路径矩阵
void add(int c[][N],int a[][N],int b[][N]) 
{
    static int temp[N][N];
    memset(temp,0x3f,sizeof temp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]);
    memcpy(c,temp,sizeof temp);
}
unordered_map<int,int> mp;
int main()
{
    cin>>k>>m>>S>>E;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
       int x,y,z;
       cin>>z>>x>>y;
       if(!mp.count(x)) mp[x]=++n;
       if(!mp.count(y)) mp[y]=++n;
       x=mp[x],y=mp[y];
       g[x][y]=g[y][x]=min(g[x][y],z);
    }

    int res[N][N];
    memset(res,0x3f,sizeof res);
    for(int i=1;i<=n;i++) res[i][i]=0;

    while(k)
    {
        if(k&1) add(res,res,g);
        add(g,g,g);
        k>>=1;
    }
    cout<<res[mp[S]][mp[E]]<<endl;
}



莫争
11天前

题目来源

hdu 1530 Maximum Clique

题目描述

给定一个图G(V,E),让你求最大完全子图(最大团)。

输入

输入包含多个测试。对于每个测试: 第一行有一个整数n,即顶点数。 (1 <n <= 50) 接下来的n行分别具有n 0或1,表示在i(行号)和j(列号)之间是否存在边。 n = 0的测试表示输入结束。

输出

输出最大团中的顶点数目。

样例输入

5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0

样例输出

4

//最大团问题 hdu.1530

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int g[N][N],n,ans,res[N];
int f[N]; //f[i]表示从i到n-1挑最多的最大团点数
bool dfs(int tot,int may[],int mayc)
{
    if(!mayc)
    {
        if(tot>ans)
        {
            ans=tot;
            return 1;
        }
        return 0;
    }

    for(int i=0;i<mayc;i++)
    {
        int u=may[i];
        if(tot+n-u<=ans) return 0;
        if(tot+f[u]<=ans) return 0;

        int nmay[N],nmayc=0;
        for(int j=i+1;j<mayc;j++) if(g[u][may[j]]) nmay[nmayc++]=may[j];

        if(dfs(tot+1,nmay,nmayc)) return 1; //能更新说明能完成比ans多1的任务了,就不用往下走了,应为再走下去也只能多1.
    }

    return 0;
}
int main()
{
    while(cin>>n,n)
    {
        memset(f,0,sizeof f);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&g[i][j]);
        ans=1;
        for(int i=n-1;i>=0;i--)
        {
            res[0]=i;
            int may[N],mayc=0;
            for(int j=i+1;j<n;j++)  if(g[i][j]) may[mayc++]=j;
            dfs(1,may,mayc);
            f[i]=ans;
        }
        cout<<f[0]<<endl;
    }
    return 0;
}


分享 魔音吉他

莫争
11天前

魔音吉他

★问题描述

少年甲很喜欢音乐,有一天他来到了少年乙的村落。少年甲一曲高山流水,寻觅到了乙这位知音。然而,天下没有不散的宴席,少年甲要回村杀猪了,离别在即,少年乙拿出了自己珍藏多年的吉他,作为离别的礼物。就在少年甲欣喜之际,少年乙说,这把吉他变幻莫测,每次你拿起它的时候,它会有n根弦,每根弦可以演奏出10^18+1个音符,而这些个音符是连续的,取决于它每根弦的第一个音符(请看样例说明)。 此时,少年甲提出了一个疑问,如果给定一个区间l,r(包括端点),里面共有几种不同的音符呢?少年乙对此谙熟于心,但是他想考验一下你,于是将这个问题抛给了你。

★数据输入

第一行一个正整数n(1<=n<=100,000),表示吉他有几根弦。 第二行共n个数x,即代表对应弦的第一个音符(0<=x<=10^18)。 第三行一个正整数q(1<=q<=100,000),表示少年甲的询问次数。 接下来q行,每行两个数l,r(0<=l,r<=10^18+1),表示少年甲想要询问的区间。

★数据输出

输出共q个数,表示对应q个询问的答案。即询问区间内有多少个不同的音符。以空格隔开。

★输入示例

6
3 1 4 1 5 9
3
7 7
0 2
8 17

★输出示例

5 10 18

★样例说明

列下标:0 1 2 3 4 5 …… 弦一:3 4 5 6 7 8 …… 弦二:1 2 3 4 5 6 …… 弦三:4 5 6 7 8 9 …… 弦四:1 2 3 4 5 6 …… 弦五:5 6 7 8 9 10 …… 弦六:9 10 11 12 13 14 ……

★Hint

(1)询问区间l,r即为样例说明中的列下标。 (2)所谓不同音符个数,即区间l,r内n行内不同的数字个数。 (3)由于l,r的范围巨大,请思考其与每行第一个数字的关系(即给出的第一个音符)。

代码(复杂度q*logn)

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10;
const ull INF=1000000000000000001;
int n,q,m;
ull a[N],s[N];
unordered_set<ull> se;
int main()
{
    cin>>m;
    ull t;
    while(m--)
    {
        scanf("%llu",&t);
        if(!se.count(t)) a[++n]=t;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n-1;i++)  a[i]=a[i+1]-a[i];
    a[n]=INF;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    cin>>q;
    while(q--)
    {
        ull x,y;
        scanf("%llu%llu",&x,&y);
        x=y-x+1;
        int l=0,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(a[mid]<=x) l=mid;
            else r=mid-1;
        }
        cout<<s[l]+x*(n-l)<<' ';
    }
    return 0;
}


分享 屋岛作战

莫争
14天前

屋岛作战

★问题描述

为了抵御使徒的入侵,第三新东京市现部署有 n 座从 1 到 n 编号的堡垒,这些堡垒间通过双向道路连接。每条道路的长度都是一个从 1 到 1000 的整数。NERV保证通过现有的道路,从任意堡垒出发都能到达其它所有堡垒,并且对于每一对堡垒,我们都知道它们之间的最短路。

然而再完美的防御措施都无法与使徒对抗,在遭遇第五使徒雷天使的入侵后,大量堡垒被击溃,EVA初号机也被击伤。在危机时刻,葛城美里提出了屋岛作战的方案。由于道路还未损坏,所以现在计划通过这些道路紧急抢修堡垒,以此吸引雷天使的火力,由EVA初号机在雷天使发动攻击露出核心的一瞬间使用阳电子炮狙击。

由于阳电子炮需要调集全国的电力供给,而变电设施需要在堡垒的火力掩护下进行操作。因此为了加快抢修速度,NERV计划临时修建 k 条新的双向道路,以便于工程人员在堡垒间往返。然而时间已经刻不容缓,无法给出具体的施工方案,只能建完一条评估效果之后再建下一条道路。

于是为了评估新建道路的效果,碇司令要求你在每条道路完工之后,计算当前道路网络中每对堡垒之间最短路的总和。注意每对堡垒只需要计算一次最短路。

★数据输入

输入第一行包括一个正整数 n(2 ≤ n ≤ 300),表示第三新东京市的堡垒数量。接下来的 n 行,每行有 n 个整数,用来表示最短路矩阵,第 i 行的第 j 个数——dij 表示堡垒 i 和 堡垒 j 之间的最短路距离。保证 dii = 0,dij = dji,并且矩阵中都是从 1 到 1000的整数。

接下来一行输入整数 k(1 ≤ k ≤ 300),表示计划修建的道路数量。接下来的 k 行,每行有三个整数 ai,bi,ci(1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1000),其中 ai 和 bi 表示道路连接的两个堡垒的编号,ci 表示道路的长度。一对堡垒间可能有许多道路,但不会有让堡垒连接到自己的道路。

★数据输出

输出 k 个整数 qi(1 ≤ i ≤ k),qi 表示修建完第 1 到 i 条道路之后,每对堡垒之间最短路的总和

★输入示例 1

2
0 5
5 0
1
1 2 3

★输出示例 1

3

★输入示例 2

3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1

★输出示例 2

17 12

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,k,sum;
int dist[N][N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&dist[i][j]),sum+=dist[i][j];
    sum/=2;
    cin>>k;
    while(k--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--,y--;
        if(dist[x][y]<=z) cout<<sum<<' ';
        else
        {
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                    if(dist[i][j]>min(dist[i][x]+z+dist[y][j],dist[i][y]+z+dist[x][j]))
                        dist[i][j]=min(dist[i][x]+z+dist[y][j],dist[i][y]+z+dist[x][j]);
                }

            sum=0;
            for(int i=0;i<n;i++)
                for(int j=i;j<n;j++)
                    sum+=dist[i][j];
            cout<<sum<<' ';
        }
    }
    return 0;
}




莫争
23天前

不知道有没有像我一样想搜真正的最大团问题却搜到这道题的人
真正的最大团定义: 最大完全子图
比如以下数据:
5 4 //5个点 4条边
1 2
2 3
1 3
4 5
真正的最大团只有{1,2,3}
而在这道题里,{1,2,3}和{4,5}都是最大团。。。