头像

一花一世界




离线:14小时前


活动打卡代码 AcWing 1116. 马走日

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

const int N = 10;
int n, m, sx, sy, res, maxp;
// 八种走法的偏移量
int dx[] = {1, -1, 1, -1, 2, -2, 2, -2};
int dy[] = {2, 2, -2, -2, 1, 1, -1, -1};
// 标记点是否被遍历
bool st[N][N];
void dfs(int x, int y, int cnt){
    // 判断是否已遍历完所有点
    if(cnt == maxp){
        res++;
        return;
    }
    // 标记当前点
    st[x][y] = true;
    // 遍历8个方向
    for(int i = 0; i < 8; i++){
        int a = x + dx[i], b = dy[i] + y;
        // 越界、被遍历过
        if(a < 0||a >= n||b < 0||b >= m||st[a][b]) continue;
        // 所有合法点
        dfs(a, b, cnt + 1);
    }
    // 恢复现场
    st[x][y] = false;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        res = 0;
        cin >> n >> m >> sx >> sy;
        maxp = n * m;
        // 初始化所有点为未被遍历
        memset(st, false, sizeof st);
        dfs(sx, sy, 1);
        cout << res << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1014. 登山

#include<iostream>

using namespace std;


const int N = 1010;
int n, a[N], fu[N], fd[N];


int main(){
    scanf("%d", &n);
    int res = 1;
    // 读入
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    //计算从0 ~ i号位置的最长上升子序列的长度(登山过程能浏览的最大景点数)
    for(int i = 0; i < n; i++){
        fu[i] = 1;
        for(int j = i - 1; j >= 0; j--){
            if(a[j] < a[i]){
                fu[i] = max(fu[i], fu[j] + 1);
            }
        }

    }
    // 计算从i ~ n号位置最长下降子序列的长度(下山过程能浏览的最大景点数)
    for(int i = n - 1; i >= 0; i--){
        fd[i] = 1;
        for(int j = n - 1; j > i; j--){
            if(a[j] < a[i]){
                fd[i] = max(fd[i], fd[j] + 1);
            }
        }

    }

    //登上+下上 - 1(因为当前位置计算了两次) 
    for(int i = 0; i < n; i++){
        res = max(res, fu[i] + fd[i] - 1);
    }
    printf("%d", res);
    return 0;
}



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

const int N = 105;
int n, m;
int a[N], fu[N], fd[N];// a代表楼层高度,fu代表最长上升子序列长度, fd代表最长下降子序列长度
int main(){
    scanf("%d", &m);
    while(m--){
        // memset(fu, 0, sizeof fu);
        // memset(fd, 0, sizeof fd);
        // memset(a, 0, sizeof a);
        scanf("%d", &n);
        int res = 1;
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            fu[i] = 1;
            fd[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(a[j] < a[i]&&fu[i] < fu[j] + 1){
                    fu[i] = fu[j] + 1;
                }
                if(a[j] > a[i]&&fd[i] < fd[j] + 1){
                    fd[i] = fd[j] + 1;
                }
            }
            res = max(res, fu[i]);
            res = max(res, fd[i]);
        }
        printf("%d\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 1018. 最低通行费

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

const int N = 105, INT = 0x3f3f3f3f;
int n, m, w[N][N], f[N][N];

int main(){
    scanf("%d", &n);
    memset(f, 0x3f, sizeof f);
    f[1][0] = f[0][1] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &w[i][j]);
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
        }
    }
    printf("%d", f[n][n]);
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include<iostream>

using namespace std;

const int N = 105;
int res, n, m, t;
int w[N][N];
int f[N][N];
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                scanf("%d", &w[i][j]);
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
            }
        }
        printf("%d\n", f[n][m]);
    }

    return 0;
}


活动打卡代码 AcWing 1238. 日志统计

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

const int N = 100010;

struct Post{
    int t, id;
    bool operator < (Post &p){
        if(t == p.t){
            return id < p.id;
        }
        return t < p.t;
    }
}p[N];
int n, d, k;
int cnt[N];
bool st[N];
int main(){
    scanf("%d%d%d", &n, &d, &k);
    for(int i = 0; i < n; i++)    scanf("%d%d", &p[i].t, &p[i].id);
    sort(p, p + n);

    for(int i = 0, j = 0; i < n; i++){
        int id = p[i].id;
        ++cnt[id];
        while(p[i].t - p[j].t >= d) cnt[p[j++].id]--;
        if(cnt[id] >= k) st[id] = true;
    }

    for(int i = 1; i <= 100000; i++){
        if(st[i]) printf("%d\n", i);
    }
    return 0;
}



#include<iostream>

using namespace std;

const int N = 100010;

int a[N], tr[N];
int n, m;

// 获取最后一位1 
int lowbit(int x){
    return x & -x;    
}

// 单点修改
void add(int x, int v){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

// 区间查询
int query(int x){
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) add(i, a[i]);
    while(m--){
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if(k) add(x, y);
        else printf("%d\n", query(y) - query(x - 1));
    }

    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

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


int main(){
    int n;
    scanf("%d", &n);
    set<int> s;
    while(n--){
        char op[2];
        int a;
        scanf("%s%d",op, &a);
        if(op[0] == 'I') s.insert(a);
        else {
            if(s.find(a) != s.end()) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}


活动打卡代码 AcWing 797. 差分

#include<iostream>

using namespace std;

const int N = 100010;
int a[N], b[N];

void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int c;
        scanf("%d", &c);
        insert(i, i, c);
    }
    while(m--){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for(int i = 1; i <= n; i++){
        a[i] = a[i - 1] + b[i];
        printf("%d ", a[i]);
    }

    return 0;
}



#include<iostream>

using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;

LL qmi(int a, int b, int c){
    LL res = 1;
    while(b){
        if(b&1) res = (LL) res * a % mod;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}
int main(){
    scanf("%d", &n);
    int a = 2 * n, b = n;
    LL res = 1;
    for(int i = a; i > a - b; i--) res = (LL)res * i % mod;
    for(int i = 1; i <= b; i++) res = (LL)res * qmi(i, mod - 2, mod) % mod;

    printf("%d", (LL)res * qmi(n + 1, mod - 2, mod) % mod);

    return 0;
}