头像

ROKANARBITER




离线:2小时前


最近来访(7)
用户头像
thinkwe11
用户头像
记着别人的好
用户头像
jn666
用户头像
no_one
用户头像
ABBEJ
用户头像
tyjz_yynb
用户头像
yxc


ROKANARBITER
2小时前
#include <iostream>
#include <vector>

using namespace std;

vector<int> res[5010];

vector<int> add(vector<int> &A,vector<int> &B)
{
    if(A.size() < B.size()) return add(B,A);

    vector<int> C;
    int t = 0;

    for(int i = 0; i < A.size() ;i++)
    {
        t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t) C.push_back(t);

    return C;
}
int main()
{
    res[0].push_back(0);
    res[1].push_back(1);
    res[2].push_back(2);

    int n;

    cin >> n;

    for(int i = 3;i <= 5001; i++)
    {
        auto C = add(res[i-1],res[i-2]);
        //res[i] = C;
        res[i].assign(C.begin(),C.end());//赋值
    }

    for(int i = res[n].size()-1;i >= 0; i--) cout << res[n][i];
}



ROKANARBITER
15小时前
const int N = 1e5+5;
class Solution {
public:

    int f[N],g[N];//非递减就是严格递增
    vector<int> goodIndices(vector<int>& nums, int k) {
        f[0]=1;
        for(int i = 1; i < nums.size();i ++)
        {
            f[i] = f[i-1] + 1; // if else在修改同一个元素时可以这样写
            if(nums[i]>nums[i-1]) f[i] = 1;
        }

        g[nums.size()-1] = 1;
        for(int i = nums.size() - 2;i >= 0; i--)
        {
            g[i] = 1;
            if(nums[i] <= nums[i + 1]) g[i] = g[i+1] + 1;
        }

        vector<int> res;
        for( int i = k ; i < nums.size() - k; i ++)
        {
            if(f[i-1] >= k&& g[i+1] >= k) res.push_back(i); 
        }
        return res;
    }
};



ROKANARBITER
17小时前
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int val=0;

        for(auto & i : nums)
        {
            val = max( i , val);
        }

        int res = 0;

        for(int i = 0, j = 0; i < nums.size(); i ++)
        {
            if(nums[i] == val)
            {
                j ++;
                res= max ( res,j);
            }
            else j = 0;
        }
        return res;
    }
};


活动打卡代码 LeetCode 2418. 按身高排序

ROKANARBITER
17小时前
class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<pair<int,string>> res;

        for(int i = 0 ; i < heights.size(); i++)
        {
            res.push_back({-heights[i],names[i]});
        }

        sort(res.begin(),res.end());

        vector<string> ans;

        for(auto &i : res)
        {
            ans.push_back(i.second);
        }
        return ans;
    }
};


活动打卡代码 AcWing 885. 求组合数 I

#include <iostream>

using namespace std;

const int N = 2e3+4,MOD = 1e9+7;
int f[N][N];

void init()
{
    for(int i = 0;i< N;i ++)
        for(int j = 0; j <= i; j++)
        {
            if(!j) f[i][j] = 1;//j为0
            else f[i][j]=(f[i-1][j]+f[i-1][j-1])%MOD;
        }
}
int main()
{
    int n;
    init();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    while(n--)
    {
        int a , b;
        cin >> a >> b;
        cout << f[a][b] << endl;
    }
}



#include <iostream>

using namespace std;

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x =1,y=0;
    }
    else 
    {
        int x1,y1;
        exgcd(b,a%b,x1,y1);
        x = y1, y = x1- a/b*y1;;
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int n;

    cin >> n;

    while(n--)
    {
        int a , b , x , y;

        cin >> a >> b;
        exgcd(a,b,x,y);
        cout << x << ' ' << y << endl;
    }
}


活动打卡代码 AcWing 876. 快速幂求逆元

简单定义 即 $b\times x ≡ $ $1$ $mod$ $m$且$b$与$m$互质 则$x$为$b$的逆元

#include <iostream>

using namespace std;
typedef long long LL;
long long qmi(int a , int b,int p)
{
    LL res = 1;
    while(b)
    {
        if(b & 1) res = res * (LL) a % p;
        a = a * (LL) a %p;
        b >>= 1;
    }
    return res;
}
int main()
{
    int n;

    cin >> n;

    while(n --)
    {
        int a ,b;
        cin >> a >> b;

        if(a%b) //为什么是a%b,而不是b%a,因为b是质数,所以只能是a是b 的倍数就不互质了
        {
            cout << qmi(a,b-2,b)<< endl;//公式
        }
        else cout << "impossible"<< endl;
    }
}


活动打卡代码 AcWing 875. 快速幂

#include <iostream>

using namespace std;

typedef long long LL;

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

int main()
{
    int a,b,p;

    int n;
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    while(n--)
    {
        cin >> a >> b >> p;
        cout << qmi(a,b,p) << endl;
    }
}



#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e6+4;

int primes[N], cnt;
int euler[N];
bool st[N];//经典的合数数组

void get_euler(int n)
{
     euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }

        for(int j = 0;primes[j] <= n/i;j++)
        {
            st[primes[j] * i]=true;

            if(i%primes[j]==0) //这个质数不是i * primes的最小质数
            {
                euler[primes[j] * i] = euler[i] * primes[j];
                break;
            }
            euler[primes[j] * i] = euler[i] * (primes[j]-1);
        }
    }
}
int main()
{
    int n;

    cin >> n;

    get_euler(n);

    LL res = 0;

    for(int i = 1; i <= n;i++)
    {
        res+=euler[i];
    }

    cout << res;
}


活动打卡代码 AcWing 873. 欧拉函数

#include <iostream>

using namespace std;

long long phi(int x)
{
    long long res = x;

    for(int i = 2; i <= x/i;i++)
    {
        if(x%i==0) 
        {
            res=res*(i-1)/i;//讨厌的地方在于可能会有精度损失
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res*(x-1)/x;
    return res;
}
int main()
{
    int n;

    cin >> n;

    while(n --)
    {
        int x;

        cin >> x;

        cout << phi(x) << endl;
    }
}