wrj
3分钟前

C++ 代码

#include<iostream>

using namespace std;

int main(){
    double a,b,c;
    cin>>a>>b>>c;

    if(a<b) swap(a,b);
    if(a<c) swap(a,c);
    if(b<c) swap(b,c);

    if(a>=b+c) cout<<"NAO FORMA TRIANGULO"<<endl;

    else 
    {   if(a*a==b*b+c*c) 
            cout<<"TRIANGULO RETANGULO"<<endl;
        if(a*a>b*b+c*c) 
            cout<<"TRIANGULO OBTUSANGULO"<<endl;
        if(a*a<(b*b+c*c)) 
            cout<<"TRIANGULO ACUTANGULO"<<endl;
        if(a==b&&a==c) 
            cout<<"TRIANGULO EQUILATERO"<<endl;
        if((a==b&&a!=c)||(a==c&&a!=b)||(b==c&&b!=a)) 
            cout<<"TRIANGULO ISOSCELES"<<endl;
    }
    return 0;
}



新鲜事 原文

AcWing《语法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/21/group_buy/199715/


新鲜事 原文

whistle_04
7分钟前
算法基础课拼团算法基础课拼团 https://www.acwing.com/activity/content/introduction/11/group_buy/199672/?from=app_share



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

using namespace std;
const int N = 1010, M = 500010;
int n, m, k;
int p[N];
struct edge
{
    int a, b;
} e[M];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &e[i].a, &e[i].b);

    while (k -- )
    {
        int x;
        scanf("%d", &x);
        for (int i = 0; i <= n; i ++ ) p[i] = i;
        //-1:减去被重点关注的城市
        int cnt = n - 1; 
        for (int j = 0; j < m; j ++ )
        {
            int a = e[j].a, b = e[j].b;
            if(a != x && b != x)
            {
                int pa = find(a), pb = find(b);
                if(pa != pb){
                    p[pa] = pb;
                    cnt--;//每合并一次,连通图数量减1
                }
            }
        }
        //连通图数量再减1,即为要连接连通图的高速公路的条数
        cout << cnt - 1 << endl;
    }

    return 0;
}



学习打卡第八天

明天就是正式上课了,要忙起来了
这几天的生物钟都非常不规律,今天开始要把它调整好
今日的学习任务:
学习蓝桥杯辅导课之树状数组和线段树第一讲
学习javaweb一个章节
解决昨天的周赛遗留问题
励志的图片




scl
15分钟前

个人对于为什么在求分子分母的最大公因数时用辗转相除法求的不正确

对于辗转相除法求的最大公因数并不一定只是针对于已经给出的数值是最大公因数,但不一定适用于全局,并且此时求出来的最大公因数,并没有假设a / b满足那两个最简的条件,所以可能会出现求出的最大公因数是公比的k次幂的次幂。
例如:
3
4 64 4096
按照辗转相除法求的最大公因数应该是16,而答案是4,此处的16就是4的次幂形式

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 110;

int n;
LL x[N], a[N], b[N];

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

LL gcd_sub(LL a, LL b)
{
    if(a < b)
        swap(a, b);
    if(b == 1) 
        return a;
    return gcd_sub(b, a / b);
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%lld",&x[i]);
    sort(x, x + n);

    int cnt = 0;
    for(int i = 1; i < n; i ++)
    {
        if(x[i] != x[i - 1])
        {
            LL t = gcd(x[i], x[0]);
            a[cnt] = x[i] / t;
            b[cnt ++] = x[0] / t; 
        }
    }

    LL up = a[0], down = b[0];
    for(int i = 1; i < cnt; i ++)
    {
        up = gcd_sub(up, a[i]);
        down = gcd_sub(down, b[i]);
    }
    cout << up << "/" << down << endl;

    return 0;
}



dioy
15分钟前

题目描述

blablabla

样例

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int m, n;

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

    for(int i = 0; i<m; i++) scanf("%d", &q[i]);

    while(n--){
        int x;
        scanf("%d", &x);
        int l = 0, r = m-1;

        while(l<r){
            int mid = (l+r)>>1;
            if(q[mid]>=x) r = mid;
            else l = mid+1;
        }
        if(q[l] != x) cout << "-1 -1" << endl;
        else{
            printf("%d ", l);
            int l = 0, r = m-1;
            while(l < r){
                int mid = (l+r+1)>>1;
                if(mid<=x) l = mid;
                else r = mid-1;
            }
            printf("%d\n", l);
        }

    }

    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



第一次 WA

#include<bits/stdc++.h>
using namespace std;

int n;
int res=0;
int vis[10];

//num分子,don分母,整数intp

void dfs(int intp,int num,int don,int cnt) //cnt表示当前用了几个数
{
    //stop
    if(cnt==9&&num%don==0&&(intp+num/don)==n)
    {
        res++;
        memset(vis,0,sizeof vis);
        return;
    }

    //剪枝
    if(intp>=n||num/don>=n||num%don!=0||cnt>=9)
    {
        memset(vis,0,sizeof vis);
        return;
    }

    //shensou
    for(int i=1;i<=9;i++)
    {
        //整数
        if(!vis[i])
        {
            intp=intp*10+i;
            vis[i]=1;
            dfs(intp,num,don,cnt+1);
            vis[i]=0;
        }
    }


    for(int i=1;i<=9;i++)
    {
        //fenzi
        if(!vis[i])
        {
            num=num*10+i;
            vis[i]=1;
            dfs(intp,num,don,cnt+1);
            vis[i]=0;
        }
    }

    for(int i=1;i<=9;i++)
    {
        //分母
        if(!vis[i])
        {
            intp=intp*10+i;
            vis[i]=1;
            dfs(intp,num,don,cnt+1);
            vis[i]=0;
        }
    }
}

int main()
{
    cin>>n;

    dfs(0,0,0,0);

    cout<<res;

    return 0;
}

寄了,我写的这么完美,可恶。

分析

您的代码中有几个问题需要修正:

  1. 重置vis数组的逻辑:您在递归函数dfs中每次递归返回时都执行了memset(vis,0,sizeof vis);,这会导致回溯时丢失之前的状态信息。实际上,您应该依赖于递归的自然回溯来恢复状态,而不是在每次递归返回时重置vis数组。
  2. 分母枚举逻辑:在处理分母don时,您错误地复用了处理整数intp的逻辑。您应该为分母don单独编写逻辑,而不是复制整数intp的处理代码。
  3. 分子和分母的初始化和更新逻辑:您需要在深度优先搜索过程中分别更新分子num和分母don,而不是只更新num。
  4. 检查条件:在检查是否形成有效的带分数时,num%don==0&&(intp+num/don)==n这个条件仅适用于完整遍历完数字后的情况。您应该更准确地控制这一检查的时机。

让我们对代码进行一些修改:

  1. 移除不必要的memset(vis,0,sizeof vis);调用。
  2. 分别处理整数部分intp、分子num和分母don的枚举。
  3. 确保分母don不为0,且在递归的每一步正确更新和回溯状态。

第二次

ps:自己看了题解,豁然开朗
枚举1-9组合数不会超时,之后分段(intp,num,don)
最大的收获:分数分母不能为0,将除法转化为加法、乘法、赋值判断,太妙了

还有就是看完题解思路,一次AC,没调bug

#include<bits/stdc++.h>
using namespace std;

//step1:枚举9个数字的组合
//step2:组合分三段,判断

int n;
int res;
int vis[10];
vector<int> p;


int culr(int l,int r)
{
    int number=0;
    for(int i=l;i<=r;i++)
    {
        number=number*10+p[i];
    }
    return number;
}

void divi()
{
    for(int i=0;i<7;i++)  //a,b,c  整数 num  don
    {
        for(int j=i+1;j<9;j++)
        {
            int intp=culr(0,i);
            int num=culr(i+1,j);
            int don=culr(j+1,8);

            if(intp*don+num==n*don)
                res++;
        }
    }
}

//枚举1-9组合数
void dfs()
{
    if(p.size()==9)
    {
        //分三段
        divi();
        return;
    }

    for(int i=1;i<=9;i++)
    {
        if(!vis[i])
        {
            p.push_back(i);
            vis[i]=1;
            dfs();
            vis[i]=0;
            p.pop_back(); //回溯写完整 别丢东西 状态记得改变
        }
    }
}

int main()
{
    cin>>n;

    dfs();

    cout<<res;

    return 0;
}


分享 408笔试

zrn
18分钟前



acwing_99939
18分钟前

include[HTML_REMOVED]

using namespace std;
const int N=100010;
int q[N];
void quick_sout(int q[],int l,int r)
{
if(l>=r) return ;
int i=l-1,j=r+1;//边界
int x=q[(l+r)>>1];//确定初始边界值
while(i[HTML_REMOVED]x);//比x大往左划
if(i<j)//交换二者的值
{
int t;
t=q[i];
q[i]=q[j];
q[j]=t;
}

};
quick_sout(q,l,j);//以边界元素两侧递归继续
quick_sout(q,j+1,r);

}

int main()
{
int n;
scanf(“%d”,&n);
for (int i=0;i<n;i++)
{
scanf(“%d”,&q[i]);

}
quick_sout(q,0,n-1);
for (int i=0;i<n;i++)
{
    printf("%d ",q[i]);


}




return 0;

}