头像

稳重




离线:3天前


最近来访(10)
用户头像
hjx_0
用户头像
irMisato_0593
用户头像
香香小马
用户头像
OI
用户头像
crystalcheung
用户头像
高兴的小七
用户头像
CFerrr
用户头像
辉_03
用户头像
Aze

分享 Dijkstra

稳重
8天前

int g[N][N]; // 稠密图用邻接矩阵存
int dist[N]; // 存1号点到N的最短距离
bool st[N]; // 判断点N是否搜索过

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n; i ++ ) 
{
    int t = -1;
    for (int j = 1; j <= n; j ++ )
        if (!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j; // t存的是当前还没定好最短距离的点中距离最近的点

    st[t]=1;

    for (int j = 1; j <= n; j ++ )
        dist[j] = min(dist[j], dist[t] + g[t][j]);

}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];

}




稳重
1个月前

题目描述

【题目描述】

唐马儒童鞋有收集种子的爱好(真的只是普通的种子)。

他有个n种子,编号为0~n-1。同时他有a个“箱子”,编号为0~a-1。如果一个种子编号为i,它将被放进编号i%a的“箱子”。但是后来时间长了,马儒新建b了个“箱子”,编号为0~b-1,这样就需要把一些种子从原来的a个箱子移动到新的b个箱子,同样的,编号为i的种子将被放进编号i%b的“箱子”。

假设把一个种子从x号箱子移动到y号箱子的花费为|x-y|,童鞋们,你们能帮马儒找出重新安排所有种子需要的花费吗?

【输入描述】
第一行一个整数,表示有 T(1<=T<=10) 组数据。
对于每组数据:

每行代表一组数据,且只有三个整数n,a,b分别代表种子的个数,一开始“箱子”的个数和后来新建“箱子”的个数。

(1<=n<=1,000,000,000, 1<=a,b<=4,000)

【输出描述】
对于每组数据,输出一行:

在这一行输出输出总的花费。

样例

2
8 2 4
11 5 3

输出

8
16

blablabla

C++ 代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int gkd(int a,int b)
{
    if(b==0)
    return a;
    else
    return gkd(b,a%b);  
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,a,b;
        scanf("%d %d %d",&n,&a,&b);
        long long int sum=0;
        int k=a*b/gkd(a,b);        //分周期来算,暴力没法解
        int c=n/k;
        int d=n%k;

        for(int i=0;i<k;i++)
        {
            sum+=abs(i%a-i%b);
        }
        sum*=c;
        for(int i=0;i<d;i++)
        sum+=abs(i%a-i%b);
        printf("%lld\n",sum);
    }
}




稳重
2个月前

思路

拓扑思想就是从入度为0开始,一步一步走到尾。
先存储每个数的入度,并用vector数组存i节点指向的那些节点,
然后在询问是建立一个数组存储题目给出顺序,然后交有judge函数进行判断
判断过程 先看此数入度是否为0(为0才说明拓扑顺序到它了),然后将此数指向的节点入度减1.
依次判断,如果不符合直接返回.

样例

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

输出

3 4

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

int n;
vector<int> G[1010]; //存G[i]中i节点所指向的节点
int in[1010];  // in[]数组存入度,to[]数组用来还原in[]
int to[1010];
int path[1010]; // 存询问时给的顺序

int judge(){
    for(int i=1;i<=n;i++)   //n次循环,确保遍历全部数
    {
        if(in[path[i]]!=0)   //判断是否此数入度是否为0
        return 1;
        for(int j=0;j<G[path[i]].size();j++)   //依次对path[i]这个数指向的节点进行入度减1的操作
        {
            int y=G[path[i]][j];       
            if(in[y]==0)          //如果入度已经为0就不需要再减了
            continue;
            in[y]--;
        }
    }
    return 0;

}

int main()
{
    int m,o,p;
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        cin >> o >> p;
        G[o].push_back(p);      //存图,o点指向p
        in[p]++; 
        to[p]++;
    }
    cin >> m;
    for(int l=0;l<m;l++)
    {
        for(int i=0;i<=n;i++)   //还原in数组
        in[i]=to[i];          
        memset(path,0,sizeof(path));
        for(int i=1;i<=n;i++)
        {
            cin >> p;
            path[i] = p;          //存储询问顺序
        }
        int flag=judge();    //判断
        if(flag)
        {
            cout << l << " ";     //这里是英文字母L,不是1
        }
    }
    return 0;
 } 




稳重
2个月前

起因

周测一题

学姐起始坐标(0,0)。每次只能从(x1,y1)移动至(x2,y2),
并且两点距离为整数.
求从(0,0)移动至(x,y)的最小步数.

第一行为单独整数t(1<=t<=3000),代表样例个数。
每个样例包含x和y,代表目的地坐标

样例

1
3 4

输出

1

C++ 参考代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;


int main()
{
    int t;
    cin >> t;
    int a,b;
    while(t--)
    {
        cin >> a >> b;
        int k=a*a+b*b;
        if(a+b)
        {
            if(sqrt(k)==floor(sqrt(k)))
            {
                cout << "1" << endl;
            }else
            {
                cout << "2" << endl;
            }
        }else
        {
            cout << "0" << endl;
        }
    }
    return 0;
}

问题–如何判断两点间距离是否为整数

1.可以使用floor函数,自动向下取整.
k=x*x+y*y

sqrt(k)==floor(sqrt(k))

2.可以巧用强制类型转换.

double z=sqrt(x*x+y*y);   
int k = (int)z; 
if(k == z) 
.....

```




稳重
2个月前

题目描述

史学长很热爱学习,他打算假期偷偷跑回学校学习,为了多学习他希望可以找最快的路线回到学校。 洛阳市里有N个(2 <= N <= 1000)个地铁站,编号分别为1..N。他的家在1号地铁站旁边,洛阳师范学院站是N号地铁站。地铁站之间共有M (1 <= M <= 2000)条双向路径。 史学长现在在1号地铁站,他希望知道到学校最短要多长时间。可以保证史学长能到达学校。忽略史学长在换乘地铁时需要的等待时间。

  • 第一行输入两个整数m和n

  • 接下来m行,每行三个整数a、b、c,表示a号地铁站和b号地铁站间要花费时间c(1<=c<=100).

样例

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出

90

算法1

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

const int N=1010;

int G[N][N];    //存边的权重
int dist[N];    //存1点到n点的最短距离
bool vis[N];    //标记是否走过
int m,n;

void dijkstra()
{
    memset(dist,0x3f,sizeof(dist));   //初始化
    dist[1]=0;                     

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&(t == -1 || dist[t] > dist[j]))
        t=j;     //t存的是当前还没定好最短距离的点中距离最近的点
        for(int j=1;j <= n ;j++)
        dist[j] = min(dist[j],dist[t]+G[t][j]); 
        vis[t] = 1;
    }
}

int main()
{
    cin >> m >> n;
    int a,b,c;
    memset(G,0x3f,sizeof(G));  //初始化
    while(m--)
    {
        cin >> a >> b >> c;
        G[b][a]=G[a][b]=min(G[a][b],c);   //存图(学一下)
    }
    dijkstra();
    cout << dist[n] << endl;
    return 0;
}





稳重
2个月前

题目描述

世界上有许多宗教,你感兴趣的是你学校里的同学信仰多少种宗教。你的学校有 nn 名学生(0 < n ≤ 50000),你不太可能询问每个人的宗教信仰,因为他们不太愿意透露。但是当你同时找到 22 名学生,他们却愿意告诉你他们是否信仰同一宗教,你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。

输入格式
输入包括多组数据。每组数据的第一行包括 n 和 m,0 <= m <= n(n-1)/2,其后 m 行每行包括两个数字 i 和 j,表示学生 i 和学生 j 信仰同一宗教,学生被标号为 1 至 n。

输入以一行 n=m=0 作为结束。

样例

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

样例输出

Case 1: 1
Case 2: 7


算法1–简单并查集

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

const int N=1e5;
int dos;
int fa[50010];         //fa[i]数组含义是i节点指向的根节点

int find_s(int x)     //并查集核心算法
{
    if(fa[x]!=x) return fa[x]= find_s(fa[x]);  //fa[x]!=x成立时,意味着没有找到根节点,进行一个简单的递归
    return fa[x];
}

void op(int x,int y)
{
    x=find_s(x);            //x,y找到各自的根节点再判断
    y=find_s(y);
    if(x!=y)                //注意判断
    {
        fa[x]=y;
        dos--;             //dos为根节点个数,有两个学生信一个宗教,根节点就要减1.
    }
}

int main()
{
    int n,m;
    int i,j;
    int flag=1;
    while(scanf("%d %d",&n,&m)!=EOF&&(n+m)!=0)
    {
        memset(fa,0,sizeof(fa));           
        dos=n;
        for(int i=0;i<50002;i++)             //初始化fa[N]数组
        fa[i]=i;
        while(m--)
        {
            scanf("%d %d",&i,&j);       //使用cin输入要54ms,scanf只要23ms
                op(i,j);
        }
        cout << "Case " << flag << ": " << dos << endl;
        flag++;
    }
    return 0;
}


分享 不同子串

稳重
2个月前

QQ图片20220407162332.png



分享 欧拉筛

稳重
2个月前

QQ图片20220407161058.png

const int N=1e5;

int number[N];
bool vis[N];

int main()
{
int cnt=0;
vis[0]=vis[1]=1;
for(int i=2;i<N;i)
{
if(!vis[i])
{
number[cnt
]=i;
vis[i]=1;
}
for(int j=0;j<=cnt&&inumber[j]<N;j++)
{
vis[i
number[j]]=1;
if(i%number[j]==0)
break;
}
}
cout << cnt << endl;
}