头像

Chosen1.




离线:1天前



算法

(树状数组维护区间最值) $O(nlogn)$
ask1(l,r)    维护[l,r]区间的最小值
ask2(l,r)    维护[l,r]区间的最大值

C++ 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse-lm")
//不开O2会超时 无限卡常

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define read(x) scanf("%d",&x)


//要记得初始化tree的最小值和最大值 

int a[N],tree1[N],tree2[N],ans[N],p;
int n,m;
inline int lowbit(int x){return x & (-x);}
void init()
{
    memset(tree1,0x3f,sizeof tree1);
    memset(tree2,-0x3f,sizeof tree1);
}

inline void update(int k)
{
    tree1[k]=a[k],tree2[k]=a[k];
    for(int i=1;i<lowbit(k);i<<=1) tree1[k]=min(tree1[k],tree1[k-i]);
    for(int i=1;i<lowbit(k);i<<=1) tree2[k]=max(tree2[k],tree2[k-i]);

}
inline int ask2(int l,int r)
{
    int res=a[r];
    while(l<=r)
    {
        res = max(res, a[r --]);
        for(;l < r - lowbit(r);r -= lowbit(r))
            res = max(tree2[r], res);
    }
    return res;
}
inline int ask1(int l,int r)
{
    int res=a[r];
    while(l<=r)
    {
        res = min(res, a[r --]);
        for(;l < r - lowbit(r);r -= lowbit(r))
            res = min(tree1[r], res);
    }
    return res;
}
int main()
{
    init();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        update(i);
    }

    for(int i=1;i<=n;i++)
    {
//      cout<<a[i]<<endl;
//      cout<<"前max:  "<<ask2(1,i-1)<<endl;
//      cout<<"后min:  "<<ask1(i+1,n)<<endl; 
        if(i==1)
        {
            if(ask1(i+1,n)>a[i]) ans[p++]=a[i];
        }
        else if(i==n)
        {
            if(ask2(1,i-1)<a[i]) ans[p++]=a[i];
        }
        else
            if(ask2(1,i-1)<a[i]&&ask1(i+1,n)>a[i]) ans[p++]=a[i];
    }
    sort(ans,ans+p);

    if(p)
    {
        cout<<p<<endl;
        for(int i=0;i<p;i++) cout<<ans[i]<<" ";
    }
    else
    {
        cout<<p<<endl;
        puts("");
    }



    return 0;
}




Chosen1.
11天前

浮点数比较精度问题


今天被浮点数精度问题关了小黑屋,整理了一下两个浮点数的任意比较形式

eps

   eps缩写自epsilon,表示一个小量,但这个小量又要确保远大于浮点运算结果的不确定量。
   eps最常见的取值是1e-8左右。引入eps后,我们判断两浮点数a、b相等的方式如下:

定义三出口函数如下:

double eps = 1e-8;
int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}

则各种判断大小的运算都应做如下修正:

传统意义       修正写法1         修正写法2

a == b      sgn(a - b) == 0      fabs(a – b) < eps

a != b      sgn(a - b) != 0      fabs(a – b) > eps

a < b       sgn(a - b) < 0         a – b < -eps

a <= b      sgn(a - b) <= 0        a – b < eps

a > b       sgn(a - b) > 0         a – b > eps

a >= b      sgn(a - b) >= 0        a – b > -eps


活动打卡代码 AcWing 3227. 折点计数

Chosen1.
11天前
#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%d",&x)

int a[1010];

int main()
{
    int n; read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    int ans=0;
    for(int i=2;i<=n-1;i++)
    {
        if((a[i]<a[i+1]&&a[i]<a[i-1])||(a[i]>a[i+1]&&a[i]>a[i-1]))
            ans++;
    }

    cout<<ans<<endl;

    return 0;   
} 


活动打卡代码 AcWing 1477. 拼写正确

Chosen1.
16天前
#include<bits/stdc++.h>
using namespace std;
string num[20]={"zero","one","two","three","four","five","six","seven","eight","nine"};

int main()
{
    string old; 
    cin>>old;
    int ans=0;
    for(auto c:old) ans+=c-'0';
    vector<int>s;
    while(ans)
    {
        s.push_back(ans%10);
        ans/=10;
    }
    if(old=="0") s.push_back(0);
    for(int i=s.size()-1;i>=0;i--) cout<<num[s[i]]<<" ";


    return 0;
}


活动打卡代码 AcWing 449. 质因数分解

Chosen1.
16天前
/*
      1~N中最多只包含一个 大于sqrt(N)的质因子 
    (因为两个大于sqrt(N)的质因子相乘结果大于N) 
      复杂度    O(logn)~~~O(sqrt(n)) 
*/
#include<bits/stdc++.h>
using namespace std;
vector<int>ans;
int divide(int x)
{
    int ans;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
        {
            int cnt=0;
            while(x%i==0)
            {
                cnt++;
                x/=i;
            }
            ans=i;
        }

        if(x>1) return x;
        else return ans;

} 

int main()
{

        int a; cin>>a;
        cout<<divide(a)<<endl;


    return 0;
}


活动打卡代码 AcWing 445. 数字反转

Chosen1.
16天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s; cin>>s;
    int k=0;
    string ans;
    if(s[0]=='-')
    {
        ans+='-'; 
        k=1;    
    }
    reverse(s.begin()+k,s.end());
    while(s[k]=='0'&&k+1<s.size()) k++;

    for(int i=k;i<s.size();i++)
    {
        ans+=s[i];
    }
    cout<<ans<<endl;

    return 0;
}


活动打卡代码 AcWing 458. 比例简化

Chosen1.
19天前
/*
          我们分别从小到大枚举 A′,B′
    那么当 gcd(A′,B′)=d>1 时: 
 我们一定在此之前先枚举了 A′/d 和 B′/d,这两组的比值是相同的
 所以我们一定不会选择前一组,即一定不会选择不互质的一组。

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

int main()
{
    int A,B,l,a,b;
    double minv=0x3f3f3f3f;
    cin>>A>>B>>l;
    double X=1.0*A/B;


    for(int i=0;i<=l;i++)
        for(int j=1;j<=l;j++)
        {
            double x=1.0*i/j;
            if(x>=X&&x<minv)
            {
                a=i,b=j;
                minv=x; 
            }
        }

    cout<<a<<" "<<b<<endl; 

    return 0;
}



活动打卡代码 AcWing 428. 数列

Chosen1.
23天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int k,n;
    cin>>k>>n;
    vector<int>v;
    while(n)
    {
        v.push_back(n&1);
        n>>=1;
    }
    int ans=0;
    for(int i=0;i<v .size();i++)
    {
        if(v[i]) ans+=pow(k,i);
    }

    cout<<ans<<endl;

    return 0;
 } 


活动打卡代码 AcWing 126. 最大的和

Chosen1.
23天前
#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%d",&x);

const int N=1e3+10;
int s[N][N];

int main()
{
    int n; read(n); 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x; read(x);
            s[i][j]=s[i-1][j]+x;
        }
    }
    int res=-1e9;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            int f=0; 
            for(int k=1;k<=n;k++)
            {
                f=max(f+s[j][k]-s[i-1][k],s[j][k]-s[i-1][k]);
                res=max(res,f);     
            }
            //res=max(res,f);
        }
    }
    cout<<res<<endl;

    return 0;
 } 



活动打卡代码 AcWing 89. a^b

Chosen1.
23天前
#include<bits/stdc++.h>
using namespace std;
#define int long long


int qmi(int a,int b,int p)
{
    int res=1%p;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

signed main()
{
    int a,b,q;
    cin>>a>>b>>q;
    cout<<qmi(a,b,q)<<endl;
    return 0;
}