实验室培训

简单算法暨算法学习经验

简单算法1 – 前缀和

一维前缀和裸板 AcWing 795. 前缀和

S[i] = a[1] + a[2] + … a[i]–>S[i] = s[i-1] + a[i]

a[l] + … + a[r] = S[r] - S[l - 1]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 100010;

int n,m;
int q[N],s[N];

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

    for(int i = 1 ; i <= n ; i ++) cin >> q[i];

    for(int i = 1 ; i <= n ; i ++)
        s[i] = s[i-1] + q[i];

    while(m --)
    {
        int l,r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }

    return 0;
}

举一反三

Codeforces Round #748 (Div. 3) C. Save More Mice

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 4e5+10;

int T,loc,n;
LL q[N],s[N],a[N];

void solve()
{
    cin >> loc >> n;
    for (int i = 1; i <= n; i ++ ) 
        cin >> q[i],q[i] = loc - q[i];
    sort(q+1,q+n+1);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i-1] + q[i];//猫的位置

    int flag = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(s[i] >= loc)
        {
            cout << i-1 << endl;
            flag = 1;
            break;
        }
    }

    if(!flag) cout << n << endl;
}

int main()
{
    cin >> T;
    while(T --)
    {
        solve();
    }
    return 0;
}

Educational Codeforces Round 112 (Rated for Div. 2)C. Coin Rows

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5+10;
typedef long long LL;

int T;
int ans = 1e12;
int q[3][N];
int s1[N],s2[N];

void solve()
{
    int n;
    cin >> n;
    memset(s1, 0, sizeof s1);
    memset(s2, 0, sizeof s2);
    for (int i = 1; i <= 2; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            cin >> q[i][j];
            if(i == 1) s1[j] = s1[j-1] + q[i][j];
            else s2[j] = s2[j-1] + q[i][j];
        }
    }//前缀和

    LL sum = 1e12;
    for (int i = 1; i <= n; i ++ )
    {
        LL num1,num2;
        num1 = s1[n] - s1[i];
        num2 = s2[i-1];

        sum = min(sum,max(num1,num2));
    }

    cout << sum << endl;
}

int main()
{
    cin >> T;
    while (T --)
    {
        solve();
    }

    return 0;
}

简单算法2 – 位运算 求二进制中1的个数

first 求整数n的二进制表示中第k位是多少

n=15=(1111)2n=15=(1111)2

1. 先把第k位移到最后一位n>>k

2. 看个位是几，x&1

即n>>k&1

second lowbit(x):返回x的最后一位1

x=1010,lowbit(x)=10

x=101000,lowbit(x)=1000

表达式：x&-x = x&(~x+1)

作用：求二进制中1的个数

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

int lowbit(int x);

int main()
{
    int a,x,i,cnt;
    scanf("%d",&a);
    for(i=0;i<a;i++){
        cnt=0;
        scanf("%d",&x);
        while(x) {
            x=x-lowbit(x);
            cnt++;
        }
        printf("%d ",cnt);
    }
    return 0;
}

int lowbit(int x)
{
    return x & (-x); 
}

刷题网站

牛客
洛谷
ACwing
Codeforces
Atcoder
Vjudge