【题解】牛客小白月赛25-E和G的另一种解法

E

官方给出的解法已经很明确了,这里分享一下我的另一种写法。
整体思路是一样的,只是其实可以在输入的时候就进行处理,因为总是相邻的俩个消除,在读入的时候可以调整循环的角标。也就是跟前一个字符进行对比,如果一样的话角标自减2,退回到上一个字符位置。容易证明对于任意可以消除的情况,这样的方法总是成立的,最后对于全部消除的情况特判一下就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max_n 301000
char c,a[max_n];
int main() {
    c=getchar();
    a[1]=c;
    for(int i=2;i<300100;i++){
        a[i]=getchar();
        if(a[i]=='\n')break;
        if(a[i]==a[i-1])i-=2;
    }
    for(int i=1;i<300100;i++){
        if(a[i]!='\n'){
            printf("%c",a[i]);
        }else break;
    }if(a[1]=='\n'){
        puts("0");
    }
    return 0;
}

G

同样是迭代,这里介绍另一种迭代,牛顿迭代。对于一个方程形如:


给定一个初值,当函数和初值满足一定条件以后(具体条件省略,网上可以找到很多的证明),
可以建立迭代方程:


然后就是放到循环里面,判断精度。类似的迭代方法还有一个简单迭代法,但是牛顿迭代的优势是可以达到
二阶收敛,可以粗略的认为它的复杂度比简单迭代和二分法(两者都是线性收敛)小一个量级。类似的数值
求解如积分,求导的方法可以参考一门叫做计算方法的课程,在某些专业内的地位相当重要,以下是代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max_n 200100
ll n,m,r,l,ans;
double a,b,c,x,xn;
map<int,int> mo;
int main() {
    cin>>a>>b>>c;
    x=1.,xn=1.1;
    while(fabs(x-xn)>=1e-8){
        x=xn;
        xn=x-(pow(x,a)+b*log(x)-c)/(a*pow(x,a-1)+b/x);
    }cout<<fixed<<setprecision(12)<<xn<<endl;
}
全部评论

相关推荐

在努力的外卷侠很靠谱:怎么,大家都没保底吗?我这美团已经入职了,不说了,系统派单了。
点赞 评论 收藏
分享
无情咸鱼王的秋招日记之薛定谔的Offer:好拒信,偷了,希望有机会用到
点赞 评论 收藏
分享
头像
11-09 12:17
清华大学 C++
out11Man:小丑罢了,不用理会
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务