头像

shiye




离线:1天前


最近来访(11)
用户头像
爱吃干煸鱼的大布丁
用户头像
糖糖_8
用户头像
佘晔
用户头像
AlRookie
用户头像
no_one
用户头像
智障还有冬天
用户头像
123456@
用户头像
tyjz_yyds
用户头像
记着别人的好
用户头像
amnesia
用户头像
zts

活动打卡代码 AcWing 868. 筛质数

shiye
2个月前
    bool b[10010], a[1000];
    memset(b, true, sizeof b);
    b[1] = false;
    for(int i = 2; i <= 100; i ++)
    {
        if(b[i]) 
        {
            for(int j = i; j <= 100000; j ++ )
            {
                b[i * j] = false;
            }
        }
    }
    int k = 0; 
    for(int i = 2; i <= 10000; i ++ )
        if(b[i])
         {
            a[++ k] = i;
         }



活动打卡代码 AcWing 422. 校门外的树

shiye
2个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int l, m;

struct seg{
    int l, r; 
}seg[N];

int main()
{
    cin >> l >> m;
    for(int i = 1; i <= m; i ++ )
        cin >> seg[i].l >> seg[i].r;
    // 对线段按左端点从小到大关系进行排序,是合并的前提条件
    sort(seg, seg + m);
    // 因为整个数轴的两个端点上都有树
    int res = l + 1;
    int st = seg[1].l , end = seg[1].r;
    // 从第二个线段开始判断是否需要合并
    for(int i = 2; i <= m; i ++ )
    {
        // 线段左端点小于前线段的右端点,合并,注意需要max考虑包含关系
        if(seg[i].l <= end ) end = max(seg[i].r, end);
        // 增加新的线段,计算剩余树,更新新线段的左右端点
        else {
            res =- end - st + 1;
            st = seg[i].l, end = seg[i].r;
        } 
    }

    // 注意,循环中最后的线段没有被计算,需要处理
    res -= end - st + 1;

    cout << res << endl;




    return 0;
}



活动打卡代码 AcWing 418. 花生采摘

shiye
2个月前
#include <iostream>

using namespace std;

const int N = 30;

typedef struct node{
    int x, y;
}Node;

int g[N][N];

int n, m, k;

// 找出最大的花生数位置
Node get_max()
{
    Node r = {0, 0};

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
        {
            if(g[r.x][r.y] < g[i][j])
                r = {i, j};
        }
        return r;
}

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

    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j <= m; j ++ )
        cin >> g[i][j];

    // 第一步 找到最大值位置  
    Node t = get_max();
    // 判断第一步采摘后是否超时
    if(t.x * 2 + 1 > k) puts("0");
    else
    {
        // 计算花生总数
        int res = g[t.x][t.y];
        // 第一步采摘完成后剩余的时间, 注意不需要考虑y
        k -= t.x + 1;
        // 将第一步位置花生数置零
        g[t.x][t.y] = 0;

        while(true)
        {
            // 获得下一个点的最大值位置
            Node r = get_max();

            // 计算当前位置到下一位置的曼哈顿距离花费的时间
            int d = abs(r.x - t.x) + abs(r.y = t.y);
             // 计算完成下一步采摘后是否超时,如果超时,就不进入下一个点,直接退出
            if(d + r.x + 1 > k) break;
            // 如果下一个点的花生数量为零,则直接结束;
            if(!g[r.x][r.y]) break;
            // 累加下一步花生总数
            res += g[r.x][r.y];
            // 将下一步的花生点数清零
            g[r.x][r.y] = 0;
            // 下一步完成后剩余的时间
            k -= d + 1;
            // 把r变成当前点
            t = r;
        }
        cout << res;
    }


    return 0;
}



shiye
4个月前

题目描述

778 字符串最大跨距,今天练习时碰到一件很诡异的事,写得代码用调试代码运行,和标准答案输出一致,但是用提交答案运行,就报错,输出为-1???

样例

#include <iostream>

using namespace std;

int main(){
    string s[3];

    for(int i = 0; i < 3; i++){
        getline(cin, s[i], ',');
        // cout << s[i].size() << endl;
    }

    // for(int i = 0; i < 3; i ++){
    //     cout << s[i];
    // }
    if(s[0].size() < s[1].size() || s[0].size() < s[2].size()) puts("-1");
    else{
        int l = 0;
        while(l + s[1].size() <= s[0].size()){
            int k = 0;
            while(k < s[1].size()){
                if(s[0][l + k] != s[1][k]) break;

                k ++ ;

            }
            if(k == s[1].size()) break;
            l ++ ;
        }

        //cout << l << endl;


        int r = s[0].size() - s[2].size();
        // cout << r << endl;
        // printf("%c\n", s[0][99]);
        // cout << s[2][2] << endl;
        while(r >= 0){
            int k = 0;
            while(k < s[2].size()){
                if(s[0][k + r] != s[2][k]) break;

                k ++ ;
            }

            if( k == s[2].size()) break;
            r -- ;
        } 
        // cout << r << endl;

        l += s[1].size() - 1;

        //cout << l << endl;

        if(l >= r) puts("-1");

        else printf("%d", r - l - 1);
    }

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

今天练习时碰到一件很诡异的事,写得代码用调试代码运行,和标准答案输出一致,但是用提交答案运行,就报错,输出为-1???


新鲜事 原文

shiye
4个月前


活动打卡代码 AcWing 823. 排列

shiye
4个月前
#include <iostream>

using namespace std;

int n;
int a[10];
bool mark[20];

void dfs(int k){
    if(k > n){
        for(int i = 1; i <= n; i++) cout << a[i] << ' ';
        cout << endl;
    }
    else{
        for(int i = 1; i <= n; i++){
            if(mark[i]  == false){
                mark[i] = true;
                a[k] = i;
                dfs(k + 1);
                mark[i] = false;
            }
        }

    }

}

int main(){
    cin >> n;

    dfs(1);



    return 0;
}


活动打卡代码 AcWing 822. 走方格

shiye
4个月前
#include <iostream>

int n, m;
int ans;

void dfs(int x, int y){
    if(x >=n || y>=m ) ans++;
    else{
        if(y < m) dfs(x, y + 1);
        if(x < n) dfs(x + 1, y);
    }
}


using namespace std;

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

    dfs(0, 0);

    cout << ans ;

    return 0;
}


活动打卡代码 AcWing 821. 跳台阶

shiye
4个月前

```

include [HTML_REMOVED]

using namespace std;

int step(int n){
if(n==1 || n==0){
return 1;
}
else return step(n - 1) + step(n - 2);
}

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

cout << step(n);


return 0;

}```



活动打卡代码 AcWing 818. 数组排序

shiye
4个月前
#include <iostream>

using namespace std;



void sort(int a[], int l, int r ){
    for(int i = l; i <= r; i++){
        for(int j = i + 1; j <= r; j++){
            if(a[j] < a[i]){
                swap(a[i], a[j]);
            } 
        }
    }
}

int main(){
    int n, l, r;
    cin >> n >> l >> r;

    int a[1000];

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

    sort(a, l, r);

    for(int i = 0; i < n; i++){
        cout << a[i] << ' ';
    }




    return 0;
}


活动打卡代码 AcWing 817. 数组去重

shiye
4个月前
#include <iostream>

using namespace std;

int a[1000];

int get_unique_count(int a[], int n){
    int cnt = 0;

    for(int i = 0; i < n; i++){
        bool is_exist = false;
        for(int j = i + 1; j < n; j++){
            if(a[i] == a[j]){
                is_exist = true;
            }
        }
        if(!is_exist) cnt++;
    }

    return cnt;
}

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

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

    cout << get_unique_count(a, n);



    return 0;
}