【题解】牛客小白月赛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;
} 
查看9道真题和解析