头像

雪凝++




离线:6天前


活动打卡代码 AcWing 756. 蛇形矩阵

雪凝++
20天前
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
typedef long long ll;

using namespace std;
int n,m,t,zt=1,x=1,y=1;
int a[105][105];
int main()
{
    cin>>n>>m;
    for(int i=0; i<=n+1; i++)
        a[i][0]=a[i][m+1]=2147483647;
    for(int i=0; i<=m+1; i++)
        a[0][i]=a[n+1][i]=2147483647;
    while(t<n*m)
    {
        a[x][y]=++t;
        if(zt==1)y++;
        if(zt==2)x++;
        if(zt==3)y--;
        if(zt==4)x--;
        if(a[x][y]>0)
        {
            if(zt==1)y--,x++;
            if(zt==2)x--,y--;
            if(zt==3)y++,x--;
            if(zt==4)x++,y++;
            zt=zt%4+1;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            cout<<a[i][j]<<' ';
        cout<<endl;
    }




    return 0;
}


活动打卡代码 AcWing 1346. 回文平方

雪凝++
20天前
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
typedef long long ll;

using namespace std;
int b,he;
bool check(int x)
{
    int a[1000005];
    int t=0;
    while(x>0)
    {
        t++;
        a[t]=x%b;
        x/=b;
    }
    for(int i=1; i<=t; i++)
        if(a[i]!=a[t-i+1])return false;
    return true;
}
int main()
{
    cin>>b;
    for(int i=1; i<=300; i++)
        if(check(i*i))cout<<i<<' '<<i*i<<endl;





    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

雪凝++
21天前
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
typedef long long ll;

using namespace std;
int n,m;
int a[100005];
bool check(double x)
{
    int sum=0;
    for(int i=1; i<=n; i++)
        sum+=a[i]/x;
    if(sum>=m)return true;
    else return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    double l=0,r=100000001,mid; 
    while(r-l>1e-3)
    {
        mid=(l+r)/2.00;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.2f",l);





    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

雪凝++
21天前
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
typedef long long ll;

using namespace std;
int n,k;
int h[100005],w[100005];
bool check(int x)
{
    long long he1=0,he2=0,sum=0;
    for(int i=1; i<=n; i++)
        he1=h[i]/x,he2=w[i]/x,sum+=he1*he2;
    if(sum>=k)return true;
    else return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d%d",&h[i],&w[i]);
    int l=0,r=100001,mid;
    while(l+1<r)
    {
        mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    cout<<l;





    return 0;
}


活动打卡代码 AcWing 429. 奖学金

雪凝++
1个月前
#include<bits/stdc++.h>

using namespace std;
int t1,t2,n;
struct datas
{
    int zf,yw,xh;
}a[305];
bool cmp(datas ha,datas hi)
{
    return ha.zf>hi.zf||ha.zf==hi.zf&&ha.yw>hi.yw||ha.zf==hi.zf&&ha.yw==hi.yw&&ha.xh<hi.xh;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].yw>>t1>>t2;
        a[i].zf=a[i].yw+t1+t2,a[i].xh=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=5; i++)
        cout<<a[i].xh<<' '<<a[i].zf<<endl;






    return 0;
}


活动打卡代码 AcWing 422. 校门外的树

雪凝++
1个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
bool st[N];

int main()
{
    scanf("%d%d", &m, &n);
    while (n -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        for (int i = l; i <= r; i ++ ) st[i] = true;
    }

    int res = 0;
    for (int i = 0; i <= m; i ++ )
        if (!st[i])
            res ++ ;

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

雪凝++
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[999][999];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
            a[i][j]+=max(a[i+1][j+1],a[i+1][j]);
    cout<<a[1][1];
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

雪凝++
1个月前
#include<bits/stdc++.h>

using namespace std;
int n,sum;
int a[100005];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1; i<=n; i++)
        sum+=abs(a[i]-a[(n+1)/2]);
    cout<<sum;






    return 0;
}



雪凝++
2个月前

题目描述

学校有 n 台计算机,编号是 1∼n,为了方便数据传输,现要将它们用数据线连接起来,同一条数据线中数据的传输可以是 双向 的。

两台计算机被连接是指它们有数据线连接。

由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。

当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。

为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。

现在由你负责连接这些计算机,任务是使任意两台计算机都连通(不管是直接的或间接的)。

样例

输入:

3
0 1 2
1 0 1
2 1 0

输出:

2


算法1

(prim算法) $O(n^2)$

普及:最小生成树的概念:生成树是在一个图中的一个连通图,最小生成树即所有生成树中,每条边的权值加起来最小的一颗生成树。这里使用一个集合来存储已经加入生成树的点。

这是prim裸题,没看过的建议到y总的算法基础课里看一遍,这里给出文字解析:

1:找到集合外距离集合最近的点,用t储存

2:用t更新其他点到集合的距离

3:把t加入到集合中

4:继续迭代,总共迭代n次

(prim算法其实就是dijkstra算法的升级版,与dijkstra的区别就是t储存的是到集合的距离,而dijkstrea储存的是到源点的距离)

时间复杂度

prim的时间复杂度是O(n^2),和dijkstra算法是一样的

参考文献

无(算法基础课算吗)

C++ 代码

#include<bits/stdc++.h>//万能头文件

using namespace std;
int n;//n储存点数
int a[105][105];//储存每两个点之间的距离
int dist[105];//储存每个点到集合的距离(实时更新)
bool st[105];//储存每个点是否在集合中
int prim()//由于每两台计算机之间都一定能链接,也就是这是一个连通图,不存在impossible的情况,所以可以直接输出prim()函数返回的值
{
    int res=0,t;//res储存答案,t储存集合外距离集合的距离
    memset(dist,0x3f,sizeof(dist));//将dist数组初始化为正无穷,因为迭代之前每个点到集合都没有路径
    for(int i=1; i<=n; i++)
    {
        t=-1;
        for(int j=1; j<=n; j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;//如果当前点不在集合中(!st[j])且该点到集合的距离比当前的t到集合的距离要近,那么更新t
        for(int j=1; j<=n; j++)
            if(j!=t)dist[j]=min(dist[j],a[j][t]);//用t更新其他点到集合的距离,Dijkstra算法写的是min(dist[j],a[j][t]+dist[t]),区别在于t已经加入集合,所以直接用j到t的距离来更新j到集合的距离
        if(i>1)res+=dist[t];//将t到集合的距离加上,注意第一次迭代时是将第一个点加入集合,所以不需要统计总长度
        st[t]=true;//t标记为已加入集合
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>a[i][j];//输入每两个点之间的距离
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            a[i][j]=min(a[i][j],a[j][i]);//刷新距离
    cout<<prim();//输出






    return 0;//PS:C++可以不打return 0
}


活动打卡代码 AcWing 794. 高精度除法

雪凝++
4个月前
a=input()
b=input()
print(a/b)