【题解】牛客小白月赛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; }