头像

柚恩不加糖




离线:5小时前


最近来访(98)
用户头像
linzy_3
用户头像
蜉蝣
用户头像
North_Pole
用户头像
平沢唯
用户头像
._6372
用户头像
用户头像
AIC
用户头像
烙饼
用户头像
蒟蒻果冻
用户头像
从前
用户头像
等三人
用户头像
novice_7
用户头像
封禁用户
用户头像
slight
用户头像
神经蛙_274
用户头像
wdyf
用户头像
mei_24
用户头像
PekingOpera
用户头像
K777
用户头像
小胖熊

活动打卡代码 AcWing 281. 硬币

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 105, M = 100005;
int n, m;
int a[N], c[N];
int f[M], used[M]; //j是否能被拼成,used表示拼到j用了多少个第i个物品,只枚举倍数

void init()
{
    rep(i, 0, m + 1)
        f[i] = 0;
}

int main()
{
    while(scanf("%d%d", &n, &m))
    {
        if(!n && !m)    break;
        init();

        rep(i, 1, n + 1)
            scanf("%d", &a[i]);
        rep(i, 1, n + 1)    
            scanf("%d", &c[i]);

        f[0] = 1;
        rep(i, 1, n + 1)
        {
            rep(j, 0, m + 1)
                used[j] = 0;
            rep(j, a[i], m + 1)
                if(!f[j] && f[j - a[i]] && used[j - a[i]] < c[i]) //类单调队列优化
                    f[j] = 1, used[j] = used[j - a[i]] + 1;
        }
        int res = 0;
        rep(i, 1, m + 1)
            if(f[i])
                res ++;
        cout << res << '\n';
    }
}


活动打卡代码 AcWing 287. 积蓄程度

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 200005;
int n;
int flow[N]; //以i为根节点的整个子树的流量
int f[N]; //以i为根节点的整个子树的最大流量
vector<PII> g[N];
int deg[N]; //每个点的度数

void dp1(int u, int fa)
{
    flow[u] = 0;
    for(PII x : g[u])
    {
        int v = x.first, w = x.second;
        if(v == fa)  continue;
        dp1(v, u);
        if(deg[v] == 1) flow[u] += w;
        else flow[u] += min(w, flow[v]);
    }
}

void dp2(int u, int fa)
{
    for(PII x : g[u])
    {
        int v = x.first, w = x.second;
        if(v == fa) continue;
        if(deg[u] == 1) 
            f[v] = flow[v] + w; //如果父亲是汇点,那么制约的就只有w了
        else if(deg[v] == 1)
            f[v] = min(w, flow[u] - w); //如果当前点为汇点,他以自身为子树为0,另一部分是父亲总流量-边和边的最小值
        else
            f[v] = flow[v] + min(f[u] - min(w, flow[v]), w); //如果都不是,那么他首先拥有自己的子树,还要加上来自父亲那边的总流量-父亲分过来的流量
        dp2(v, u);
    }
}

void init()
{
    rep(i, 1, n + 1)
        g[i].clear(), deg[i] = 0;
}

void solve()
{
    cin >> n;
    init();

    for(int i = 1; i < n; i ++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({v, c}); g[v].pb({u, c});
        deg[v] ++; deg[u] ++; //统计度数
    }

    dp1(1, -1);
    f[1] = flow[1];
    dp2(1, -1);
    int res = 0;
    rep(i, 1, n + 1)
        res = max(res, f[i]);
    cout << res << '\n';
}

signed main()
{
    int _ = 1;
    cin >> _;
    while(_--)
        solve();
}


活动打卡代码 AcWing 286. 选课

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 305;
int n, m;
int f[N][N]; //以i为根的子树下,选择了j门课的方案的最大值
int a[N];
vector<int> g[N];
int rt = 0;

void dp(int u)
{
    f[u][0] = 0;
    for(int v : g[u])
    {
        dp(v);
        //for(int v : g[u])
        for(int j = m; j >= 0; j --) //当前以i为根的子树能选的数量
            for(int k = 0; k <= j; k ++) //组内的物品
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
        //分组背包
    }
    if(u != 0) //如果u不为0,那么我们最多选j-1节课,为了避免分类讨论所以写在外卖
        for(int j = m; j > 0; j --)
            f[u][j] = f[u][j - 1] + a[u];
}

signed main()
{
    cin >> n >> m;
    rep(i, 1, n + 1)
    {
        int fa;
        cin >> fa >> a[i];
        g[fa].pb(i);
    }

    dp(0);
    cout << f[0][m] << '\n';
}


活动打卡代码 AcWing 284. 金字塔

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 305;
const int mod = 1e9;
char s[N];
int f[N][N];
int n;

signed main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);

    rep(len, 1, n + 1)
    rep(l, 1, n - len + 2)
    {
        int r = l + len - 1;
        if(len == 1)    f[l][r] = 1;
        else
        {
            if(s[l] == s[r])
            {
                for(int k = l + 2; k <= r; k ++)        
                    if(s[l] == s[k]) //[l + 1, k - 1]是s[l]和s[k]夹着的子树
                        f[l][r] = (f[l][r] + 1ll * f[l + 1][k - 1] * f[k][r]) % mod;
            }
        }
    }
    cout << f[1][n] << '\n';
}


活动打卡代码 AcWing 367. 学校网络

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 105;
int n;
vector<int> g[N];
int dfn[N], low[N];
int block[N];
int scc, timer;
int instk[N];
vector<int> stk;

vector<int> dag[N];
int in[N], out[N];
bool flag[N][N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timer;
    stk.pb(u);
    instk[u] = 1;
    for(int v : g[u])
    {
        if(!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if(instk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        scc ++;
        int top = -1;
        do
        {
            top = stk.back();
            stk.pop_back();
            block[top] = scc;
            instk[top] = 0;
        } while(top != u);
    }
}

signed main()
{
    cin >> n;
    rep(i, 1, n + 1)
    {
        int v;
        while(cin >> v)
        {
            if(!v)  break;
            g[i].pb(v);
        }
    }

    rep(i, 1, n + 1)
        if(!dfn[i])
            tarjan(i);

    rep(i, 1, n + 1)
        for(int j : g[i])
        {
            int u = block[i], v = block[j];
            if(u == v)  continue;
            dag[u].pb(v), out[u] ++, in[v] ++;
        }       
    int tot_in0 = 0, tot_out0 = 0;
    rep(i, 1, scc + 1)
    {
        tot_in0 += (in[i] == 0 ? 1 : 0);
        tot_out0 += (out[i] == 0 ? 1 : 0);
    }
    cout << tot_in0 << '\n';
    if(scc == 1) //特判一下
        cout << "0\n";
    else
        cout << max(tot_in0, tot_out0) << '\n';
}



#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 6005;
int n;
int a[N];
int father[N];
vector<int> g[N];
int f[N][2]; //以i为根的子树,i是去还是不去的最大价值

void dfs(int u, int fa)
{
    f[u][1] = a[u];
    for(auto v : g[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][1], f[v][0]);
    }
}

signed main()
{
    cin >> n;
    rep(i, 1, n + 1)
        cin >> a[i];
    rep(i, 2, n + 1)
    {
        int u, v;
        cin >> v >> u;
        g[u].pb(v); g[v].pb(u);
        father[v] = 1;
    }
    int rt = -1;
    rep(i, 1, n + 1)
        if(!father[i]) 
            {rt = i; break;}

    dfs(rt, - 1);
    cout << max(f[rt][0], f[rt][1]) << '\n';
}


活动打卡代码 AcWing 280. 陪审团

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

int n, m;
int f[205][25][805]; //从前i个人里选j个人,且差值为k的方案集合,属性:和的最大值
int p[205], d[205];
int base = 400;
int ans[205];

signed main()
{
    int no = 1;
    while(scanf("%d%d", &n, &m))
    {
        if(!n && !m)    break;
        rep(i, 1, n + 1)
            scanf("%d%d", &p[i], &d[i]);
        memset(f, -0x3f, sizeof f);
        f[0][0][base] = 0;

        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= m; j ++)
                for(int k = 0; k <= 800; k ++)
                {
                    f[i][j][k] = f[i - 1][j][k];
                    int dis = k - (d[i] - p[i]);
                    if(dis < 0 || dis > 805)   continue;
                    if(j == 0)   continue;
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][dis] + (d[i] + p[i]));
                }

        int v = 0;
        while(f[n][m][base - v] < 0 && f[n][m][base + v] < 0)   v ++;

        if(f[n][m][base - v] > f[n][m][base + v])   v = base - v;
        else v = base + v;

        vector<int> res;
        int i = n, j = m, k = v;
        while(j)
        {
            if(f[i][j][k] == f[i - 1][j][k])    i --;
            else
            {
                res.pb(i);
                k -= (d[i] - p[i]), i --, j --;
            }
        }

        int totp = 0, totd = 0;
        for(auto x : res)
            totp += p[x], totd += d[x];
        printf("Jury #%d\n", no ++);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", totp, totd);
        sort(res.begin(), res.end());
        for(auto x : res)
            printf(" %d", x);
        puts("\n");
    }
    return 0;
}


活动打卡代码 AcWing 350. 巡逻

思路:已知题目是让你找k条最长的直径将其头尾相连成环,若最长和次长有重叠时,情况比较复杂。
1.如果一条边仅在第二个环出现过,只用走一次。
2.如果一条边在两个环都出现过,要走两次。
3.如果一条边在两个环都没出现过,要走两次。

第二条也是连接直径(第二大), 那问题来了, 如何消除已经连过的直径?
将所连过的直径权值又1改-1, 即可
相当于你在算这条边为直径时, 贡献值为-1
那为什么不应该是贡献值为 0 呢?
本来一条直径对答案的帮助为res - len + 1
现在我本来对res有-1的贡献,但是因为连了第二条边我又要多走一次,那就是res + 1相互抵消,因此将其贡献修改为-1是合理的
其实是, 当你第一次连接直径时, 原本要原路返回, 这条边会走两次, 你连接之后直走一次
第二次连接时, 这条边会由于你的连线非但没少走, 还会多走一边故, 贡献从 1 变为 -1 (新建的边必须走一次)

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 100005, M = 2 * N;
int h[N], e[M], w[M], nex[M], idx;
void add(int a, int b)
{
    e[idx] = b;
    w[idx] = 1;
    nex[idx] = h[a];
    h[a] = idx ++;
}

int n, k, d2; //次直径
int dis[N], path[N];

int bfs(int u)
{
    memset(dis, -1, sizeof dis);
    queue<int> q;
    q.push(u);
    dis[u] = 0;

    while(q.size())
    {
        int t = q.front();
        q.pop();

        for(int i = h[t]; i != -1; i = nex[i])
        {
            int v = e[i];

            if(dis[v] != -1)    continue;
            dis[v] = dis[t] + 1;
            path[v] = i;// 记录路径
            q.push(v);
        }
    }

    int p = u;
    for(int i = 1; i <= n; i ++)
        if(dis[i] > dis[p])
            p = i;
    return p;
}

void update(int ed, int st)
{
    while(ed != st)
    {
        w[path[ed]] = -1; //正边
        w[path[ed] ^ 1] = -1; //神来之笔,因为存入的时候是连续的 所以idx和idx^1一奇一偶正好一起改变了
        ed = e[path[ed] ^ 1]; //反边
    }
}

int dp(int u, int fa)
{
    int dis1 = 0, dis2 = 0;
    for(int i = h[u]; i != -1; i = nex[i])
    {
        int v = e[i], val = w[i];
        if(v == fa) continue;
        int t = dp(v, u) + val;
        if(t >= dis1)
            dis2 = dis1, dis1 = t;
        else if(t > dis2)
            dis2 = t;
    }
    d2 = max(d2, dis1 + dis2);
    return dis1;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> k;
    for(int i = 2; i <= n; i ++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    int st = bfs(1);
    int ed = bfs(st);

    //若K = 1的时候,连接直径的两端点为最佳方案。K = 2的时候,应该找到最大直径和次大直径
    int res = 2 * (n - 1) - dis[ed] + 1;

    if(k == 2)
    {
        update(ed, st);
        memset(dis, 0, sizeof dis);
        dp(1, -1);
        res = res - d2 + 1;
    }

    cout << res << '\n';
}


活动打卡代码 AcWing 277. 饼干

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define per(i, n, a) for(int i = n; i >= a; i--)
#define fi first
#define se second
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
#define ms(x, y)    memset(x, y, sizeof x)
#define debug(x)    cout << x << endl;
typedef double db;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;

#define int long long
const int N = 35;
int n, m;
PII g[N];
int f[N][5005]; //表示将j块饼干分配给前i个人,且分配的饼干数单调不升 属性:Min
int s[N]; //前缀和
int res[N];

int cmp(PII a, PII b)   {return a.first > b.first;}

void solve()
{
    cin >> n >> m;
    rep(i, 1, n + 1)
        cin >> g[i].first, g[i].second = i;
    sort(g + 1, g + n + 1, cmp); //贪心 a[i]越大,分的饼干应该越多 通过交换邻项法证明

    rep(i, 1, n + 1)    s[i] = s[i - 1] + g[i].first;

    ms(f, 0x3f);
    f[0][0] = 0;
    for(int i = 1; i <= n; i ++)
    for(int j = i; j <= m; j ++) //满足j - i >= 0 --> j >= i
    {
        f[i][j] = f[i][j - i];
        for(int k = 1; k <= i; k ++) // i - k >= 0  
            f[i][j] = min(f[i][j], f[i - k][j - k] + (s[i] - s[i - k]) * (i - k)); //结尾k个人都分到饼干1
    }

    cout << f[n][m] << '\n';

    //倒推DP的过程
    int i = n, j = m, h = 0;
    while(i) //DP转移过程中已保证i <= j
    {
        if(f[i][j] == f[i][j - i])  j -= i, h ++; //整体下降的高度是多少
        else 
        {
            for(int k = 1; k <= i; k ++)
            {
                if(f[i][j] == f[i - k][j - k] + (s[i] - s[i - k]) * (i - k)) //找到连续的一段的1
                {
                    for(int l = i - k + 1; l <= i; l ++)
                        res[g[l].second] = h + 1;
                    i -= k, j -= k;
                    break;
                }
            }
        }
    }

    for(int i = 1; i <= n; i ++)
        cout << res[i] << ' ';
    cout << '\n';
}

signed main()
{
    solve();
}


活动打卡代码 AcWing 275. 传纸条

#include <bits/stdc++.h>

using namespace std;
int n, m;
int g[55][55];
int f[55 << 1][55][55]; //两人一起走的第n + m步, 当前分别位于(i, k - i), (j, k - j)

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> g[i][j];

    for(int k = 2; k <= n + m; k ++)
        for(int i = 1; i < k; i ++)
            for(int j = 1; j < k; j ++)
            {
                int t = g[i][k - i];
                if(i != j)  t += g[j][k - j];
                for(int a = 0; a <= 1; a ++)
                for(int b = 0; b <= 1; b ++)
                    f[k][i][j] = max(f[k - 1][i - a][j - b], f[k][i][j]);
                f[k][i][j] += t;
            }
    cout << f[n + m][n][n];
}