头像

由比滨结衣




离线:17小时前



#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int e = 0;
    for(int i = n - 1; i >= 0; i--){
        if((e + a[i]) & 1) e = e + a[i] + 1 >> 1;
        else e = e + a[i] >> 1;
    }
    cout << e << endl;
    return 0;
}


活动打卡代码 AcWing 3215. 网络延时

两次DFS

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

const int N = 2e4 + 10;
int h[N], ne[N * 2], e[N * 2], idx, ans;
int maxu;

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

void dfs(int u, int fa, int w){
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u, w + 1);
    }
    if(w > ans){
        ans = w;
        maxu = u;
    }
}

int main(){
    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;
    for(int i = 2; i <= n; i++){
        int f;
        cin >> f;
        add(i, f);
        add(f, i);
    }
    for(int i = 1; i <= m; i++){
        int f;
        cin >> f;
        add(n + i, f);
        add(f, n + i);
    }
    dfs(1, -1, 0);
    dfs(maxu, -1, 0);
    cout << ans;
    return 0;
}

树形DP

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

const int N = 2e4 + 10;
int h[N], ne[N * 2], e[N * 2], d[N], idx, ans;
bool st[N];

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

void tree_dp(int u, int w){
    st[u] = true;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(st[j]) continue;
        tree_dp(j, w + 1);
        ans = max(ans, d[u] + d[j] + 1);
        d[u] = max(d[u], d[j] + 1);
    }
}

int main(){
    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;
    for(int i = 2; i <= n; i++){
        int f;
        cin >> f;
        add(i, f);
        add(f, i);
    }
    for(int i = 1; i <= m; i++){
        int f;
        cin >> f;
        add(n + i, f);
        add(f, n + i);
    }
    tree_dp(1, 0);
    cout << ans;
    return 0;
}



例题网址:

https://www.acwing.com/problem/content/description/1209/

树形DP

用数组模拟

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

const int N = 1e5 + 10;
int h[N], ne[N * 2], e[N * 2], v[N * 2], idx;//无向图,开二倍空间
int d[N];
bool vis[N];
int ans;

void tree_dp(int x){
    vis[x] = true;
    for(int i = h[x]; ~i; i = ne[i]){
        int y = v[i];
        if(vis[y]) continue;
        tree_dp(y);
        ans = max(ans, d[x] + d[y] + e[i]);
        d[x] = max(d[x], d[y] + e[i]);
    }
}

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

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }
    tree_dp(1);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}

用vector模拟

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

typedef pair<int, long long> pii;

const int N = 1e5 + 10;
long long d[N];
bool vis[N];
long long ans;
vector<pii> city[N];

void tree_dp(int x){
    vis[x] = true;
    for(int i = 0; i < city[x].size(); i++){
        int y = city[x][i].first;
        if(vis[y]) continue;
        tree_dp(y);
        ans = max(ans, d[x] + d[y] + city[x][i].second);
        d[x] = max(d[x], d[y] + city[x][i].second);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        city[a].push_back({b, w});
        city[b].push_back({a, w});
    }
    tree_dp(1);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}

两次DFS用结构体存(速度会慢)(还不如用Vector)

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

const int N = 1e5 + 10;
int h[N], idx;//无向图,开二倍空间
int d[N];
bool vis[N];
int ans, maxu;

struct edge{
    int to;
    int ne;
    int w;
}e[N * 2];


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

void dfs(int u, int fa, int w){
    for(int i = h[u]; ~i; i = e[i].ne){
        int j = e[i].to;
        if(j != fa)
            dfs(j, u, w + e[i].w);
    }
    if(ans < w){
        maxu = u;
        ans = w;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }
    dfs(1, -1, 0);
    dfs(maxu, -1, 0);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}

两次DFS用多个数组存(速度更快)

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

const int N = 1e5 + 10;
int h[N], ne[N * 2], e[N * 2], v[N * 2], idx;//无向图,开二倍空间
int d[N];
bool vis[N];
int ans, maxu;

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

void dfs(int u, int fa, int w){
    for(int i = h[u]; ~i; i = ne[i]){
        int j = v[i];
        if(j != fa)
            dfs(j, u, w + e[i]);
    }
    if(ans < w){
        maxu = u;
        ans = w;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }
    dfs(1, -1, 0);
    dfs(maxu, -1, 0);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}


活动打卡代码 AcWing 3250. 通信网络

用数组模拟

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

const int N = 1e3 + 10, M = 2e4 + 10;
int n, m;
int h1[N], h2[N], ne[M], e[M], idx;
bool st1[N], st2[N];

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

void dfs(int u, int h[], bool st[]){
    st[u] = true;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(!st[j]) dfs(j, h, st);
    }
}

int main(){
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        add(h1, a, b);
        add(h2, b, a);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        memset(st1, 0, sizeof st1);
        memset(st2, 0, sizeof st2);
        dfs(i, h1, st1);
        dfs(i, h2, st2);
        int s = 0;
        for(int j = 1; j <= n; j++)
            if(st1[j] || st2[j])
                s++;
        if(s == n) ans++;
    }
    cout << ans;
    return 0;
}

用结构体数组模拟

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

const int N = 1e3 + 10, M = 2e4 + 10;
int n, m;
int h1[N], h2[N], idx;
bool st1[N], st2[N];

struct edge{
    int to;
    int ne;
}e[M];

void add_edge(int h[], int a, int b){
    e[idx].to = b;
    e[idx].ne = h[a];
    h[a] = idx++;
}

void dfs(int u, int h[], bool st[]){
    st[u] = true;
    for(int i = h[u]; ~i; i = e[i].ne){
        int j = e[i].to;
        if(!st[j]) dfs(j, h, st);
    }
}

int main(){
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        add_edge(h1, a, b);
        add_edge(h2, b, a);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        memset(st1, 0, sizeof st1);
        memset(st2, 0, sizeof st2);
        dfs(i, h1, st1);
        dfs(i, h2, st2);
        int s = 0;
        for(int j = 1; j <= n; j++)
            if(st1[j] || st2[j])
                s++;
        if(s == n) ans++;
    }
    cout << ans;
    return 0;
}

用Vector模拟

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

const int N = 1e3 + 10;
int n, m;
vector<int> v1[N], v2[N];
bool st1[N], st2[N];

void dfs(int u, vector<int> v[], bool st[]){
    st[u] = true;
    for(int i = 0; i < v[u].size(); i++){
        int j = v[u][i];
        if(!st[j]) dfs(j, v, st);
    }
}

int main(){
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        v1[a].push_back(b);
        v2[b].push_back(a);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        memset(st1, 0, sizeof st1);
        memset(st2, 0, sizeof st2);
        dfs(i, v1, st1);
        dfs(i, v2, st2);
        int s = 0;
        for(int j = 1; j <= n; j++)
            if(st1[j] || st2[j])
                s++;
        if(s == n) ans++;
    }
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 3257. 跳一跳

#include <iostream>
using namespace std;

int main(){

    int flag, prev = 0, ans = 0;

    while(cin >> flag, flag != 0){

        if (flag == 2) {
            if(prev == 1) prev = 0;
            prev += 2;
        } else prev = 1;

        ans += prev;
    }

    cout << ans;

    return 0;
}



随便写写

#include <iostream>
using namespace std;

int main(){

    int flag, prev = 0, ans = 0;

    while(cin >> flag, flag != 0){

        if (flag == 2) {
            if(prev == 1) prev = 0;
            prev += 2;
        } else prev = 1;

        ans += prev;
    }

    cout << ans;

    return 0;
}


活动打卡代码 AcWing 3257. 跳一跳

#include <iostream>
using namespace std;

int main(){
    int flag, prev = 0, pre_sum = 0;
    int ans = 0;
    while(cin >> flag, flag != 0){
        if(flag == 2) {
            if(prev == 1) pre_sum = 0;
            prev = 2, pre_sum += 2, ans += pre_sum;
        }
        else prev = pre_sum = 1, ans++;
    }
    cout << ans;
    return 0;
}



话不多说直接上代码吧

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

int main(){

    bool flag = false;
    string a, b;

    cin >> a >> b;

    if(a.size() < b.size()) swap(a, b);//保证b为子串

    //先从a开始找到与b的第一个字符相同的下标
    for(int i = 0; i < a.size(); i++){
        int k = 0;
        for(int j = 0, u = i; j < b.size(); j++, u++){    //记录a的下标为u,b的下标为j,此时为0
            if(u == a.size()) u = 0;                      //之后u++,j++
            if(a[u] != b[j]) break;                       //如果下标对应的字符不相等,则直接跳出循环
            k++;                                          //重新开始从a中找与b的第一个字符相同的下标
        }                                                 //需要注意的点是u可能会越界,记得将其重置
        if(k == b.size()){
            flag = true;
            break;
        }
    }
    if(flag) puts("true");
    else puts("false");
    return 0;
}

另类写法……

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

int main(){
    string a, b;
    cin >> a >> b;
    if(a.size() < b.size()) swap(a, b);
    a += a;
    if(a.find(b) != string :: npos) puts("true");
    else puts("false");
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int main()
{
    ll a,b,p,res;
    cin>>a>>b>>p;
    res=0;
    while(b)
    {
        if(b&1)
            res=(res+a)%p;
        b>>=1;
        a=2*a%p;
    }
    cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 89. a^b

#include<iostream>
using namespace std;

typedef long long ll;

int main(){
    ll a, b, p, ans = 1;
    cin >> a >> b >> p;
    while(b){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    cout << ans % p;
    return 0;
}