头像

15358022392




离线:10小时前


最近来访(95)
用户头像
ING__
用户头像
sklit8
用户头像
RainSure
用户头像
Kiss_3
用户头像
小猪快跑ya
用户头像
hhhhkk
用户头像
用户头像
垫底抽風
用户头像
V1
用户头像
喧豗灬
用户头像
呵呵_875
用户头像
OI
用户头像
Shen666
用户头像
Moon_2
用户头像
2850g
用户头像
手可摘太阳
用户头像
cht
用户头像
LittleGoose
用户头像
pccc
用户头像
2010

活动打卡代码 AcWing 4247. 糖果

```



活动打卡代码 AcWing 4220. 质数路径

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

#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;

ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 100010;
int dist[N];
int primes[N], cnt;
bool st[N];
void init() 
{
    for (int i = 2; i < 9999; i ++) 
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; i * primes[j] < N; j ++) 
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int main()
{
    IOS;
    init();//筛法选出所有的素数

    int t;
    cin >> t;
    while(t -- )
    {
        memset(dist, -1, sizeof dist);
        int x, y;
        cin >> x >> y;
        queue<int> q;
        q.push(x);  dist[x] = 0;
        vector<int> a(4), d = {1000, 100, 10, 1};

        while(q.size())
        {
            auto t = q.front(); q.pop();
            for (int i = t, j = 3; i; i /= 10, j -- )   a[j] = i % 10;//按位拆分每一位

            for (int i = 0; i < 10; i ++ )//枚举40种情况
            {
                for (int j = 0; j < 4; j ++ )//四个位置
                {
                    if(!i && !j)    continue;//千位上不能是0
                    int sum = t + d[j] * (i - a[j]);//将这j这一位改成i的结果
                    if(!st[sum] && dist[sum] == -1) 
                    {
                        q.push(sum);
                        dist[sum] = dist[t] + 1;
                    }
                }
            }
        }
        cout << dist[y] << endl;
    }

    return 0;
}



前缀和+二分

class Solution {
public:
    vector<int> answerQueries(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        int n = a.size();
        for (int i= 1; i < n; i ++ )    a[i] += a[i - 1];

        vector<int> ans;
        int n2 = b.size();
        for (int i = 0; i < n2; i ++ )
        {
            int k = b[i];
            int l = 0, r = n - 1;
            while(l < r)
            {
                int mid = (l + r + 1) / 2;
                if(a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            if(a[l] <= k)
            ans.push_back(l + 1);
            else ans.push_back(0);
        }
        return ans;
    }
};


活动打卡代码 AcWing 3564. 日期类

15358022392
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int months[] = {
    0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int year, month, date;
        cin >> year >> month >> date;
        date ++ ;
        if (date > months[month])
        {
            date = 1;
            month ++ ;
            if (month > 12)
            {
                month = 1;
                year ++ ;
            }
        }

        printf("%04d-%02d-%02d\n", year, month, date);
    }

    return 0;
}



活动打卡代码 AcWing 3625. 幂次方

15358022392
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

int qmi(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int main()
{
    int x, n;
    cin >> x >> n;
    cout << qmi(x, n, 233333);
}


活动打卡代码 AcWing 3587. 连通图

15358022392
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n, m;
const int N = 100010;
int p[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


int main()
{
    while(cin >> n >> m)
    {
        for (int i = 1; i <= n; i ++ )  p[i] = i;
        while (m -- )
        {
            int a, b;
            cin >> a >> b;
            p[find(a)] = find(b);
        }
        bool fg = true;
        int t = find(1);
        for (int i = 2; i <= n; i ++ )
            if (find(i) != t)   fg = false;
        if(fg)  puts("YES");
        else    puts("NO");
    }
}


活动打卡代码 AcWing 3381. 手机键盘

15358022392
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int number[] = {
    2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 
    6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9
};

int main()
{
    string str;
    while(cin >> str)
    {
        int res = 0, last = -1;
        for (auto c : str)
        {
            int t = c - 'a';
            for (int i = t; i >= 0; i -- )
                if (number[i] == number[t]) res ++;
                else break;

            if (number[t] == number[last]) res += 2;
            last = t;
        }
        cout << res << endl;
    }
}



15358022392
2个月前
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>

using namespace std;

const int N = 15;

int n, res;
int a[N];
bool st[N];

//求完全平方数
//下面的原理是: 例如25 sqrt 之后等于5, 5 * 5 == 25,说明是完全平方数
bool check(int num)
{ 
    int p = (int)sqrt(num); 
    return p * p == num;
}

/**参数说明 u: 当前序列长度 , last序列的上一个元素 **/
void dfs(int u, int last)
{
    //如果序列长度达到n,说明找到一个方案,res++
    if (u >= n)
    {
        res ++;
        return; 
    }

    //类似于全排列一样的搜,加上一点剪枝
    for (int i = 0; i < n; i ++)
    {
        //如果当前这个元素跟上一个元素是一样的,那么我们需要排除重复的
        //因为这是在递归中,在当前这一层中每一个i在递归中的层数是一样的
        //举例[3 3 5 6], 如果当前6是元素,那么第二层会是3 3 5其中一个
        //然后我们如果第二层连续两次使用这个相同的3,就会使得搜到的结果是一样的
        //[6 3(第一个3) 5 3(第二个三)]  === [6 3(第二个3) 5 3(第一个三)]
        //所以需要跳过,只需要搜其中一个就行
        // 然后为什么要判断这个呢 (!st[i - 1]) 因为前面一个数肯定是回溯之后,
        //恢复现场了,st肯定是false,
        //如果是被标记的,说明是相同元素而已,dfs的不同层数
        if (i > 0 && !st[i - 1] && a[i] == a[i - 1]) continue;
        if (st[i]) continue; //如果这个元素已经搜过了,那就跳过
        //判断这个元素 跟序列的上一个元素last能不能构成完全平方数
        if (check(last + a[i]))  
        {
            st[i] = true;  //标记当前数
            dfs(u + 1, a[i]); //递归下一个位置
            st[i] = false; // 恢复现场
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];

    sort(a, a + n);  //排序。方便排除重复元素

    //将每一个数作为序列首元素,进行dfs
    for (int i = 0; i < n; i ++) 
    {
        //如果当前这个数跟他前面的数是一样的,说明以这个数位序列首元素
        //收到的结果也是一样的,题目要求不能重复,所以直接跳过continue
        if (i > 0 && a[i] == a[i - 1]) continue;
        st[i] = true; //然后将当前首元素进行标记
        dfs(1, a[i]); //递归dfs
        st[i] = false; // 恢复现场,方便下一组dfs
    }

    cout << res << endl;  //输出答案
    return 0;
}


活动打卡代码 AcWing 2074. 倒计数

15358022392
2个月前
#include<iostream>

using namespace std;
const int N=2e5+10;
int a[N];

int main()
{
    int T;
    cin >>T;
    for(int t = 1;t <= T; t ++)
    {
        int n, m;
        cin >> n >> m;
        for(int i = 1;i <= n; i ++) 
            cin >> a[i];

        int res = 0;
        for(int i = n; i > 0; i --)
        {
            if(a[i] == 1)
            {
                int j = i;
                while(j > 0&& a[j-1] - a[j] == 1)  //经典的双指针算法
                {
                    j --;
                }
                if(i - j + 1 >= m) //只要是比目标长都算
                    res ++;
                i = j;
            }
        }

        printf("Case #%d: %d\n",t , res);
    }

    return 0;
}



活动打卡代码 AcWing 3601. 成绩排序

15358022392
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
struct stu
{
    string name;
    int a, b;
    bool operator < (const stu &t) const
    {
        if(b != t.b)    return b < t.b;
        else if (name != t.name)    return name < t.name;
        else return a < t.a;
    }
}st[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> st[i].name >> st[i].a >> st[i].b;

    sort(st, st + n);
    for (int i = 0; i < n; i ++ )
        cout << st[i].name << ' '<< st[i].a << ' ' << st[i].b << endl;
    return 0;
}