头像

醒来




离线:6小时前


活动打卡代码 AcWing 2816. 判断子序列

醒来
22天前
#include<iostream>
using namespace std;

const int N = 100010;

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

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    for(int i = 0; i < m; i ++ ) cin >> b[i];
    int i, j;
    for(i = 0, j = 0; i < n && j < m; ){
        if(a[i] == b[j]) i ++ , j ++ ;
        else j ++ ;
    }
    if(i == n) puts("Yes");
    else puts("No");
}



醒来
22天前
#include<iostream>
#include<cstring>
using namespace std;

const int N = 6010;

int h[N], e[N], ne[N], idx;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int happy[N], n;
int ind[N];

typedef pair<int, int> PII;
PII dfs(int u){
    int a = 0, b = happy[u];
    for(int i = h[u]; i != -1; i = ne[i]){
        int v = e[i];
        auto t = dfs(v);
        a += max(t.first, t.second);
        b += t.first;
    }
    return {a, b};
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> happy[i];
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++ ){
        int a, b;
        cin >> a >> b;
        add(b, a);
        ind[a] ++ ;
    }
    int root = 1;
    while(ind[root]) root ++ ;
    auto t = dfs(root);
    cout << max(t.first, t.second) << endl;
}




活动打卡代码 AcWing 91. 最短Hamilton路径

醒来
22天前
#include<iostream>
#include<cstring>
using namespace std;

const int N = 20, M = 1 << N, INF = 0x3f3f3f3f;

int f[N][M];
int g[N][N], n;

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            cin >> g[i][j];
    memset(f, INF, sizeof f);
    f[0][1] = 0;
    for(int i = 0; i < (1 << n); i ++ )
        for(int j = 0; j < n; j ++ )
            for(int k = 0; k < n; k ++ )
                if(j != k && ((i >> j) & 1) && ((i >> k) & 1))
                    f[j][i] = min(f[j][i], f[k][i - (1 << j)] + g[k][j]);
    cout << f[n - 1][(1 << n) - 1] << endl;
}



醒来
22天前
#include<iostream>
using namespace std;

const int N = 12, M = 1 << N;

long long f[N][M], n, m;
bool st[M];

int main(){
    while(cin >> n >> m, n || m){
        for(int i = 0; i < (1 << n); i ++ ){
            st[i] = true;
            int cnt = 0;
            for(int j = 0; j < n; j ++ )
                if((i >> j) & 1){
                    if(cnt % 2) break;
                    cnt = 0;
                }else cnt ++ ;
            if(cnt % 2) st[i] = false;
        }

        for(int i = 0; i <= m; i ++ )
            for(int j = 0; j < (1 << n); j ++ )
                f[i][j] = 0;
        f[0][0] = 1;
        for(int i = 1; i <= m; i ++ )
            for(int j = 0; j < (1 << n); j ++ )
                for(int k = 0; k < (1 << n); k ++ )
                    if(!(j & k)&& st[k | j])
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }
}


活动打卡代码 AcWing 338. 计数问题

醒来
22天前
#include<iostream>
#include<vector>
using namespace std;

int count(int x, int d){
    vector<int> num;
    while(x){
        num.push_back(x % 10); 
        x /= 10;
    }
    int n = num.size(), res = 0;
    for(int i = 0; i < n - !d; i ++ ){
        int left = 0, right = 0, power = 1;
        for(int j = i - 1; j >= 0; j -- ) left = left * 10 + num[j], power *= 10;
        for(int j = n - 1; j > i; j -- ) right = right * 10 + num[j];
        res += (right - !d) * power;
        if(num[i] == d) res += left + 1;
        else if(num[i] > d) res += power;
    }
    return res;
}

int main(){
    int a, b;
    while(cin >> a >> b, a || b){
        if(a > b) swap(a, b);
        for(int i = 0; i < 10; i ++ )
            cout << count(b, i) - count(a - 1, i) << " ";
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 458. 比例简化

醒来
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 425. 明明的随机数

醒来
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 417. 不高兴的津津

醒来
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 421. 陶陶摘苹果

醒来
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 428. 数列

醒来
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~