头像

智障也有春天

杭州拱墅大关中学




离线:3小时前


最近来访(150)
用户头像
Henry1
用户头像
NirvanaCensor
用户头像
小灰灰我是
用户头像
L-China
用户头像
BT7274
用户头像
gmm
用户头像
院止.
用户头像
dushucheng0901
用户头像
超市里扫货
用户头像
JcWing
用户头像
吴梦涵2023
用户头像
gohacker
用户头像
Futaba双葉
用户头像
wangyc
用户头像
HeXing
用户头像
ryngar
用户头像
吃吃花椒的喵酱
用户头像
lieflat
用户头像
王玄忠
用户头像
误入佬群

活动打卡代码 工程课 Linux-1.0. homework_0

top显示当前进程的运行状况
文件名的第一个是.,代表隐藏文件,要ls -a才能看到
ls XXX -l会给出某个文件的详细信息,参数部分加上h,ls XXX -lh可以更人性化的输出,如将1024输出为1K
在某个文件夹内用ls -A,不同于-a,会不输出当前目录和上层目录,即...
ll等于ls -la
cd后什么都不加,直接返回家目录
cd -返回之前访问的目录
可以用\转义,如mkdir y\ c,会创建一个名称为y c的文件夹
mkdir a/b/c -p,可以在当前目录创建一个a文件夹,且a里有文件夹b,b里有文件夹c
history显示之前在命令行输入的指令
-r是指递归,如rm XXX -r就是删XXX文件夹,递归删XXX下的所有文件以及XXX本身
*为正则表达式,如rm *.txt就是删当前目录下所有非隐藏的txt文件
对rm命令,有些文件是受保护的删不了,可以加参数-f,如rm /* -rf,高危命令!!!




QQ截图20230119112657.png
注:上图将绿化图看作A矩阵,藏宝图看作B矩阵。坐标系向上为x轴,向右为y轴。

此题的突破口在于,藏宝图的左下角一定是有一棵树,而西西艾弗岛绿化图中最多只有1000棵树,因此只需依次枚举藏宝图左下角的树对应于绿化图中的1000棵树的1000种情况。

#include<iostream>
using namespace std;

#define x first
#define y second

const int S = 55, N = 1010, INF = 1e9;
typedef pair<int , int> PII;

PII tree[N];
int b[S][S];
int n, l, s;

int main(){
    cin >> n >> l >> s;
    for(int i = 0; i < n; i ++){
        cin >> tree[i].x >> tree[i].y;
    }
    int cnt = 0;   //记录藏宝图中树的总数
    for(int i = s; i >= 0; i --){
        for(int j = 0; j <= s; j ++){
            cin >> b[i][j];
            cnt += b[i][j];
        }
    }
    //枚举绿化图中的所有树
    int res = 0;   //记录绿化图中有多少处坐标满足条件
    for(int i = 0; i < n; i ++){
        int sx = tree[i].x, sy = tree[i].y;    //将枚举到的绿化图中的树对应到藏宝图的左下角
        if(sx + s > l || sy + s > l) continue;   //若以绿化图中的某棵树作为藏宝图的左下角时,藏宝图会超出绿化图范围时,跳出该循环
        int tc = 0;   //记录绿化图中有多少棵树与藏宝图中的树对应,若最后tc==cnt,则res+=1
        for(int j = 0; j < n; j ++){
            int x = tree[j].x, y = tree[j].y;
            if(x >= sx && x - sx <= s && y >= sy && y - sy <= s){   //不判断范围则x-sx可能为负,数组越界。另外只有符合范围,绿化图中的树才可能与藏宝图中的树相对应
                if(!b[x - sx][y - sy]) tc = -INF;   //令tc为负无穷,则之后tc再怎么增加也仍是负数,不可能等于cnt
                else tc += 1;
            }
        }
        if(tc == cnt) res += 1;
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 4455. 出行计划

满分做法,差分

QQ截图20230118193603.png
上图求解对于$t_{i}$时刻进入的某场所,我们在什么样的时间范围内做核酸才可以进入该场所。
进而求解出对于某一项出行计划,应该在什么样的时间范围内做核酸。
QQ截图20230118200921.png
建立一个各元素为0的数组s[200010],s[i]表示在i时刻做核酸可以满足多少个出行计划。因此对于给出的每一个出行计划,使$s[t_{i}-k-c_{i}+1]$到$s[t_{i}-k]$均加一。进而想到用差分来降低时间复杂度。

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, k;
int a[200100] = {0};

int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++){
        int t, w;
        cin >> t >> w;
        int l = t - w - k + 1, r = t - k;
        if(r > 0){
            a[max(1, l)] ++, a[r + 1] --;
        }
    }
    for(int i = 1; i <= 200100; i ++) a[i] += a[i - 1];   
    //这里是算出每一个时刻做核酸可以满足的出行计划总数,而不能写成for(int i = 1; i <= n; i ++)
    for(int i = 0; i < m; i ++){
        int x;
        cin >> x;
        cout << a[x] << endl;
    }

    return 0;
}

我的做法(70分)

二分只优化了算法中的一部分的时间复杂度,但总时间复杂度仍为$n^{2}$

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, k;
int a[100010], b[100010];

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

    int l = 0;
    for(int i = 0; i < m; i ++){
        int test;
        cin >> test;
        int get_result = test + k;

        //二分
        int r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] < get_result) l = mid + 1;
            else r = mid;
        }

        if(a[l] >= get_result){
            int res = n - l;
            for(int j = l; j < n; j ++){
                if(a[j] - b[j] >= get_result) res --;
            }
            cout << res << endl;
        }else{
            cout << 0 << endl;
        }
        /*
        如果不进行特判,可能会出现以下情况,测试样例为:
        2 1 10
        1 24
        2 24
        1
        得结果为1,实际应为0
        */
    }

    return 0;
}

算法基础课的模板题中也有特判过程



活动打卡代码 AcWing 4700. 何以包邮?

①暴搜,递归(70分)

#include<iostream>
#include<algorithm>
using namespace std;

int n, x;
int a[35] = {0};
int res = 1e9;

int dfs(int u, int sum){
    if(u == n){                             //不可以if(u == n && sum >= x) res = min(res, sum);
        if(sum >= x) res = min(res, sum);
    }else{
        dfs(u + 1, sum);
        dfs(u + 1, sum + a[u]);
    }
    return res;
}

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

    cout << dfs(0, 0) << endl;

    return 0;
}

②用二进制数的每一位表示某本书买或是不买(70分)

#include<iostream>
#include<algorithm>
using namespace std;

int n, x;
int a[35] = {0};
int res = 1e9;

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

    for(int i = 0; i < (1 << n); i ++){
        int sum = 0;
        for(int j = 0; j < n; j ++){
            if((i >> j) & 1 == 1) sum += a[j];
            if(sum >= x && sum < res) res = sum;
        }
    }
    cout << res << endl;

    return 0;
}

③最优解,01背包(100分)

考查转化模型的能力。设总价格为sum,包邮最低价为x,则此题可转化为总体积为sum-x的01背包问题
QQ截图20230118105615.png

朴素

#include<iostream>
using namespace std;

int n, x;
int w[33], v[33];
int f[33][300010];

int main(){
    cin >> n >> x;
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
        v[i] = w[i];
        sum += w[i];
    }
    int m = sum - x;

    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << sum - f[n][m] << endl;

    return 0;
}

优化

#include<iostream>
using namespace std;

int n, x;
int w[33];
int f[300010];

int main(){
    cin >> n >> x;
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
        sum += w[i];
    }
    int m = sum - x;

    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= 0; j --){
            f[j] = f[j];
            if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + w[i]);
        }
    }
    cout << sum - f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 4699. 如此编码

#include<iostream>
using namespace std;

typedef long long LL;

int n;
LL m;                      //其实不会爆int,因为0≤m<Cn,而Cn≤1e9

int main(){
    cin >> n >> m;
    int c_o = 1;
    for(int i = 0; i < n; i ++){
        int a;
        cin >> a;
        int c_c = c_o * a;
        cout << (m % c_c) / c_o << ' ';
        c_o = c_c;
    }

    return 0;
}


活动打卡代码 AcWing 4509. 归一化处理

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int n;
int a[1010];

int main(){
    cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        sum += a[i];
    }
    double mean = (double)sum / n;
    double d_sum;
    for(int i = 0; i < n; i ++){
        d_sum += pow((double)a[i] - mean, 2);
    }
    double d = d_sum / n;
    double standard_d = sqrt(d);
    for(int i = 0; i < n; i ++){
        printf("%f\n", (a[i] - mean) / standard_d);
    }

    return 0;
}


活动打卡代码 AcWing 4454. 未初始化警告

#include<iostream>
using namespace std;

int n, k;
bool s[100010] = {false};

int main(){
    cin >> n >> k;
    s[0] = true;
    int res = 0;
    for(int i = 0; i < k; i ++){
        int a, b;
        cin >> a >> b;
        if(s[b] == false) res ++;
        s[a] = true;
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 3400. 统计次数

暴力枚举

#include<iostream>
#include<cstring>
using namespace std;

int n, k;

int main(){
    cin >> n >> k;
    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(auto c : to_string(i)){
            if(c - '0' == k) res ++;
        }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 4655. 重新排序

此题用到了算法基础课,贪心的排序不等式。当各元素查询次数和各元素值均取升序时,依次相乘再求和,即得最大值;当各元素查询次数取升序,但各元素值取降序时,依次相乘再求和,得最小值。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
typedef long long LL;

int n, q;
LL s[N] = {0}; 
int a[N] = {0}, c[N] = {0};                //a数组存各元素值,c数组存储各元素的查询次数

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];                  //前缀和
    }
    cin >> q;
    LL inital_sum = 0;
    for(int i = 0; i < q; i ++){
        int l, r;
        cin >> l >> r;
        c[l] += 1;                               //差分
        c[r + 1] -= 1;
        inital_sum += s[r] - s[l - 1];
    }
    for(int i = 1; i <= n; i ++){
        c[i] += c[i - 1];                        //得到每个元素的查询次数
    }
    sort(a + 1, a + n + 1);
    sort(c + 1, c + n + 1);
    LL changed_sum = 0;
    for(int i = 1; i <= n; i ++){
        changed_sum += (LL)a[i] * c[i];
    }

    cout << changed_sum - inital_sum << endl;

    return 0;
}

Y总的代码与我略有不同,Y总没有用前缀和去求初始查询之和,而是直接将各元素的查询次数去乘以该元素值再求和,代码更简洁。



活动打卡代码 AcWing 4261. 孤独的照片

对每一头牛进行遍历,如果它是‘H’,则向左找到L个连续的‘G’,向右找到R个连续的‘G’;
如果它是‘G’,则向左找到L个连续的‘H’,向右找到R个连续的‘H’。

假设当前遍历到的牛为‘G’,则扔掉的所有照片中含有当前遍历到的牛‘G’的照片可能会出现三种情况:
①该牛的左边和右边都有连续的‘H’牛,共LR张
②仅在该‘G’牛的左边有连续的‘H’牛,共L-1张
③仅在该‘G’牛的右边有连续的‘H’牛,共R-1张

QQ截图20230110115405.png

#include<iostream>
#include<algorithm>
using namespace std;

int n;
char a[500010];
int l[500010], r[500010];  //第i头牛左边和右边与第i头牛不同品种的牛有连续多少个

int main(){
    cin >> n;
    cin >> a;
    int g = 0, h = 0;
    //对第一次从左向右遍历,g(h)表示当前遍历到的牛的左边有多少头连续的g(h)牛
    for(int i = 0; i < n; i ++){
        if(a[i] == 'G'){
            g ++;
            l[i] = h;
            h = 0;
        }else{
            h ++;
            l[i] = g;
            g = 0;
        }
    }

    g = 0, h = 0;
    //对第二次从右向左遍历,g(h)表示当前遍历到的牛的右边有多少头连续的g(h)牛
    for(int i = n - 1; i >= 0; i --){
        if(a[i] == 'G'){
            g ++;
            r[i] = h;
            h = 0;
        }else{
            h ++;
            r[i] = g;
            g = 0;
        }
    }

    long long ans = 0;
    for(int i = 0; i < n; i ++){
        ans += (long long)l[i] * r[i];    //若改为(long long)(l[i] * r[i]),就错了
        ans += max(l[i] - 1, 0);         //此处容易错写为ans += l[i] - 1;
        ans += max(r[i] - 1, 0);
    }

    cout << ans << endl;

    return 0;
}