头像

朴小明




离线:3小时前


最近来访(37)
用户头像
啦啦啦啦啦啦啦啦啦啦啦
用户头像
jelly_07
用户头像
鲶鱼饭
用户头像
JesseChan
用户头像
SolitudeFate
用户头像
CodeEcho
用户头像
Leonard7
用户头像
Panzer_Jack
用户头像
老坛算粉
用户头像
DPH
用户头像
向前进
用户头像
Wyattaa
用户头像
忘打周赛
用户头像
殷文博
用户头像
itdef
用户头像
Apprentice_lb
用户头像
karuya
用户头像
MrLuo
用户头像
_wyp_


最近学会了dfs的记忆化形式的数位dp,来贴一贴例题和代码,注释也有很多,方便以后自己忘了回来看。

和与或

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10 + 5, mod = 1e9 + 9;
int f[65][1ll << 10];
int a[N];
int n;
int dfs(int pos, int lim)
{
    if (pos < 0) return 1;
    if (f[pos][lim] != -1) return f[pos][lim];

    f[pos][lim] = 0;
    int s = 0;
    for (int i = 0; i < n; i++)   //全部填0,计算一下下面的lim & s
    {
        int k; //k是这一位最高能填0还是1
        if ((lim >> i) & 1) k = (a[i] >> pos) & 1;
        else k = 1;
        s |= (0 == k) << i;  //这一位填的数是0
    }
    //对于没压缩的来说,lim & (填的数 == (a[i] >> pos) & 1) ,看是不是填了最高位
    f[pos][lim] += dfs(pos - 1, lim & s);
    f[pos][lim] %= mod;

    for (int i = 0; i < n; i++)  //因为只能填一个1,枚举他能填在哪里
    {
        //先判这位是否能填1,(a[i] >> pos) & 1本身是1,那一定可填;否则要看lim的第i位是否有限制
        if (!((a[i] >> pos) & 1) && (lim >> i) & 1) continue;
        int p = (s | (1ll << i)) ^ (1ll << i); //把s的这一位变0
        int k;
        if ((lim >> i) & 1) k = (a[i] >> pos) & 1;
        else k = 1;
        p |= (1 == k) << i; //这一位填的数是1
        f[pos][lim] += dfs(pos - 1, lim & p);
        f[pos][lim] %= mod;
    }
    return f[pos][lim];
}
void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    memset(f, -1, sizeof(f));
    cout << dfs(63, (1ll << n) - 1);  //1表示有限制,0表示无限制
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

dh的帽子

要枚举三个数的上限和下限,直接压缩成两个limit,方便。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10 + 5, mod = 1e9 + 9;
int f[20][1ll << 3][1ll << 3];
int l, r;
int dfs(int pos, int lim1, int lim2)
{
    if (pos < 0) return 1;
    if (f[pos][lim1][lim2] != -1) return f[pos][lim1][lim2];

    f[pos][lim1][lim2] = 0;

    int a[3], b[3];
    for (int i = 0; i < 3; i++)
    {
        if ((lim1 >> i) & 1) a[i] = (l >> pos) & 1;
        else a[i] = 0;
        if ((lim2 >> i) & 1) b[i] = (r >> pos) & 1;
        else b[i] = 1;
    }
    for (int i = a[0]; i <= b[0]; i++)
    for (int j = a[1]; j <= b[1]; j++)
    for (int k = a[2]; k <= b[2]; k++)
    {
        if ((i ^ j ^ k) != (i | j | k)) continue;
        int s1 = (i == a[0]) | ((j == a[1]) << 1) | ((k == a[2]) << 2);
        int s2 = (i == b[0]) | ((j == b[1]) << 1) | ((k == b[2]) << 2);
        f[pos][lim1][lim2] += dfs(pos - 1, s1 & lim1, s2 & lim2);
    }
    return f[pos][lim1][lim2];
}
void solve()
{
    cin >> l >> r;
    memset(f, -1, sizeof(f));
    int ans = dfs(17, (1ll << 3) - 1, (1ll << 3) - 1);
    cout << ans;
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

D. Little Girl and Maximum XOR

这题返回的不是数数,而是最大值,和上一题的代码很相似,随便改改就行了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10 + 5, mod = 1e9 + 9;
int f[65][1ll << 3][1ll << 3];
int l, r;
int dfs(int pos, int lim1, int lim2)
{
    if (pos < 0) return 0;
    if (f[pos][lim1][lim2] != -1) return f[pos][lim1][lim2];

    f[pos][lim1][lim2] = 0;

    int a[2], b[2];
    for (int i = 0; i < 2; i++)
    {
        if ((lim1 >> i) & 1) a[i] = (l >> pos) & 1;
        else a[i] = 0;
        if ((lim2 >> i) & 1) b[i] = (r >> pos) & 1;
        else b[i] = 1;
    }
    for (int i = a[0]; i <= b[0]; i++)
    for (int j = a[1]; j <= b[1]; j++)
    {
        int s1 = (i == a[0]) | ((j == a[1]) << 1);
        int s2 = (i == b[0]) | ((j == b[1]) << 1);
        f[pos][lim1][lim2] = max(((i ^ j) << pos) + dfs(pos - 1, s1 & lim1, s2 & lim2), f[pos][lim1][lim2]);
    }
    return f[pos][lim1][lim2];
}
void solve()
{
    cin >> l >> r;
    memset(f, -1, sizeof(f));
    int ans = dfs(63, (1ll << 2) - 1, (1ll << 2) - 1);
    cout << ans;
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

P4317 花神的数论题

就三种状态表示,第几位,限制,有几个1,注意边界的时候的返回条件就好了。
如果cnt == 0,那就是数字0,所以return 1;
如果pos < 0了,那只有cnt == 0的时候才合法吧应该.....这里我也不是很懂。。。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10 + 5, mod = 10000007;
int f[65][2][60];
int n;
int dfs(int pos, int lim, int cnt)
{
    if (pos < 0) return cnt == 0;
    if (cnt == 0) return 1;
    if (f[pos][lim][cnt] != -1) return f[pos][lim][cnt];

    f[pos][lim][cnt] = 0;

    int k;
    if (lim) k = (n >> pos) & 1;
    else k = 1;

    for (int i = 0; i <= k; i++)
    {
        if (i == 0) f[pos][lim][cnt] += dfs(pos - 1, lim & (i == k), cnt);
        else f[pos][lim][cnt] += dfs(pos - 1, lim & (i == k), cnt - 1);
    }
    return f[pos][lim][cnt];
}
int qpow (int x, int n)
{
    int ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % mod;
        x = x* x % mod;
        n >>= 1;
    }
    return ret;
}
void solve()
{
    cin >> n;
    memset(f, -1, sizeof(f));
    int ans = 1;
    for (int i = 1; i <= 55; i++)
    {
        int ret = dfs(63, 1, i);
        ans = ans * qpow(i, ret) % mod;
        // cout << dfs(63, 1, i) << " ";
    }
    cout << ans;
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

Round Numbers

晚上问了下队友,他直接口胡出做法了,我就码了一下,直接过了。。这个状态表示也很简单,不用记录前导0,直接记录1有多少个,0有多少个。
边界条件是 return zero >= one,转移的时候是one + (i == 1), zero + (i == 0 && one)。然后这题就做完了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 60 + 5, mod = 10000007;
int f[N][2][N][N];
int x;
int dfs(int pos, int lim, int one, int zero)
{
    if (pos < 0) return zero >= one;
    if (f[pos][lim][one][zero] != -1) return f[pos][lim][one][zero];
    f[pos][lim][one][zero] = 0;
    int k;
    if (lim) k = (x >> pos) & 1;
    else k = 1;

    for (int i = 0; i <= k; i++)
    {
        f[pos][lim][one][zero] += dfs(pos - 1, lim & (i == k), one + (i == 1), zero + (i == 0 && one));
    }

    return f[pos][lim][one][zero];
}
int calc(int n)
{
    int ret = 0;
    x = n;
    memset(f, -1, sizeof(f));
    ret = dfs(63, 1, 0, 0);
    return ret;
}
void solve()
{
    int l, r;
    cin >> l >> r;
    // cout << calc(r) << " " << calc(l - 1);
    cout << calc(r) - calc(l - 1);
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}



链接:D. Chip Move

题意:

一开始处于坐标轴的原点,给定了数字K,第一次跳K的倍数步,第二次K + 1的倍数步,....一直这样跳下去。

问点1~n,到达这些位置的走法分别是多少。

做法:

一、(会MLE,然后显然也是TLE的…)
f[i][j]表示到达第i个点的时候,一共走了j步,这样的dp方程的转移非常好想,直接考虑j - 1步的时候能从哪些位置转移过来就好了。直接上代码。

其中b数组的意思是到这个点最多可以跳b[i]步。

可以看到最内层就是枚举步长的倍数,进行一个非常暴力的转移了。

int a[N], b[N];
int f[N][632], ans[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = k, j = 1; i <= n; i += k + j, j++) b[i] = b[i - k - j + 1] + 1;
    for (int i = 1; i <= n; i++) b[i] = max(b[i], b[i - 1]);  //b[200000] = 631
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= b[i]; j++)
        {
            for (int s = 1; i - s * (k + j - 1) >= 0; s++)
            {
                f[i][j] += f[i - s * (k + j - 1)][j - 1];
                f[i][j] %= mod;
            }
            ans[i] = (ans[i] + f[i][j]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}

二、

考虑优化最内层的枚举倍数的循环,可以用调和级数,但还是会MLE和TLE,这里就不展开代码了。

三、(不会TLE,但会MLE)

这次彻底优化时间复杂度,最内层的枚举倍数,设step = s * (k + j - 1),tle代码会去找 i - 1 * step,i - 2 * step…,然后是从j - 1步转移而来。但是这样是有大量的重复计算了,这些里面有相当一部分,被f[i - 1* step] [j]也进行过计算,所以可以这样优化了:

很像完全背包的转移方程的优化,关于完全背包,依稀记得他的n3优化到n2的推理,在白书上有,进阶指南没写这部分优化,有点子可惜。。

int a[N], b[N];
int f[N][632], ans[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = k, j = 1; i <= n; i += k + j, j++) b[i] = b[i - k - j + 1] + 1;
    for (int i = 1; i <= n; i++) b[i] = max(b[i], b[i - 1]);  //b[200000] = 631
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= b[i]; j++)
        {
            // for (int s = 1; i - s * (k + j - 1) >= 0; s++)  //这是没有优化时间复杂度的
            // {
            //     f[i][j] += f[i - s * (k + j - 1)][j - 1];
            //     f[i][j] %= mod;
            // }
            int from = i - (k + j - 1);
            if (from < 0) continue;
            f[i][j] = (f[from][j] + f[from][j - 1]) % mod;   //优化时间复杂度后可以这样转移
            ans[i] = (ans[i] + f[i][j]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}

四、(成功AC)

考虑优化空间了,这里注意到f[i][j] = (f[from][j] + f[from][j - 1]) % mod;,第二维只会从j和j-1,那就考虑优化他们了。

首先说一下代码里的两层循环为什么可以互换位置,循环换一下顺序,不影响结果,是因为只要保证计算某个状态时候,被转移的状态全部计算过了就行,这个题目,换一下两维枚举顺序,显然可以保证这一点。

然后再说一下为什么第16行要进行一个清0,因为待会儿会被累加进ans数组,而上一次的结果是不能留在这一次的。

快乐上代码了:

int a[N], b[N];
int f[N][2], ans[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = k, j = 1; i <= n; i += k + j, j++) b[i] = b[i - k - j + 1] + 1;
    for (int i = 1; i <= n; i++) b[i] = max(b[i], b[i - 1]);
    f[0][0] = 1;
    for (int j = 1; j <= b[n]; j++)
    {
        for (int i = 0; i <= n; i++) f[i][j & 1] = 0;
        for (int i = 1; i <= n; i++)
        {
            int from = i - (k + j - 1);
            if (from < 0) continue;
            f[i][j & 1] = (f[from][j & 1] + f[from][!(j & 1)]) % mod;
            ans[i] = (ans[i] + f[i][j & 1]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}



还没懂dfs的数位dp,暂时只会预处理和枚举数位。

预处理的dp是从低位到高位的,

需要前导0是f[0][0] = 1;
不需要的是前导0for (int j = 1; j <= 9; j++) g[1][j] = 1;

对于一个查询x,从x的高位枚举到低位就能做下去了。

分享一道需要前导0和不需要前导0的好题: 22数

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int f[11][11 * 9], g[11][11 * 9];
int a[11];
int get(int x)
{
    x++;
    int cnt = 0;
    while(x)
    {
        a[++cnt] = x % 10;
        x /= 10;
    }

    int ret = 0;
    for (int i = cnt - 1; i >= 1; i--) 
    {
        ret += g[i][i * 2]; //这里不需要前导0
    }
    // cout << ret << "\n";
    int sum = 0;
    for (int i = cnt; i >= 1; i--)
    {
        for (int j = 0 + (i == cnt); j < a[i]; j++)
        {
            if (cnt * 2 - sum - j < 0) continue;
            ret += f[i - 1][cnt * 2 - sum - j]; //这里需要前导9
        }
        sum += a[i];
    }
    return ret;
}
void solve()
{
    f[0][0] = 1;
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 0; j <= i * 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                if (j < k) continue;
                f[i][j] += f[i - 1][j - k];
            }
        }
    }


    for (int j = 1; j <= 9; j++) g[1][j] = 1;
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 0; j <= i * 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                if (j < k) continue;
                g[i][j] += g[i - 1][j - k];
            }
        }
    }

    int n;
    cin >> n;
    cout << get(n);
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}


活动打卡代码 AcWing 4484. 有限小数

朴小明
1个月前

类似计组的分数转二进制,一直乘以2,直到分母变1,这里就是约分后乘以k
AcWing居然也可int128,爱了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000 + 5, mod = 1e9 + 7;
void solve()
{
    int x, y, k;
    cin >> x >> y >> k;
    int gcd = __gcd(x, y);
    x /= gcd;
    y /= gcd;
    __int128 p = k;
    for (int i = 1; i <= 65; i++)
    {
        p = p * p % y;
        if (p == 0)
        {
            puts("YES");
            return;
        }
    }
    puts("NO");
}
signed main()
{
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}


活动打卡代码 AcWing 4427. 树中节点和

朴小明
2个月前

简简单单思维题,偶数节点尽量大,但是有限制

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
vector<int> v[N];
int s[N], a[N];
void dfs(int x, int fa, int dep)
{
    int ma = 1e18;
    for (auto i : v[x])
    {
        int y = i;
        if (y == fa) continue;
        ma = min(s[y] - s[fa], ma);
        // dfs(y, x, dep + 1);
    }
    if (dep % 2 == 0) 
    {
        if (v[x].empty()) return;
        a[x] = ma;
        s[x] = s[fa] + a[x];
    }
    else a[x] = s[x] - s[fa];

    for (auto i : v[x])
    {
        int y = i;
        if (y == fa) continue;
        dfs(y, x, dep + 1);
    }
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) 
    {
        int u;
        cin >> u;
        v[u].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> s[i];
    dfs(1, 0, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) 
    {
        ans += a[i];
        // cout << a[i] << " ";
        if (a[i] < 0)
        {
            cout << -1;
            return;
        }
    }
    cout << ans;
}
signed main()
{
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}


活动打卡代码 AcWing 4426. 整除子串

朴小明
2个月前

很简单的dp,还不用考虑子序列,更简单了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
char s[N];
int f[N][4];
void solve()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    // f[0][0] = f[0][1] = f[0][2] = f[0][3] =  1;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i][(s[i] - '0') % 4] = 1;
        for (int j = 0; j < 4; j++)
        {
            // f[i][j] += f[i - 1][((j - s[i] + '0') % 4 + 4) % 4];
            f[i][(j * 10 + s[i] - '0')%4] += f[i - 1][j];
        }
        ans += f[i][0];
    }
    cout << ans;
}
signed main()
{
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}


活动打卡代码 AcWing 259. 真正的骗子

朴小明
3个月前

写麻了,过了样例就ac,还行吧。。dp还原真恶心

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000 + 5, mod = 1e9 + 7;
int m, p1, p2;
int fa[N], f[N][N], siz[N];
char s[10];
int getf(int k)
{
    if (fa[k] == k) return k;
    return fa[k] = getf(fa[k]);
}
int a[N], b[N];
bool vis[N][2];
int book[N];
void dp(int cnt)
{
    f[0][0] = 1;
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = 0; j <= p1; j++)
        {
            if (j >= a[i]) f[i][j] += f[i - 1][j - a[i]];
            if (j >= b[i]) f[i][j] += f[i - 1][j - b[i]];
        }
    }
    if (f[cnt][p1] != 1) 
    {
        puts("no");
        return;
    }
    int p = p1;
    for (int i = cnt; i >= 1; i--)
    {
        if (p - a[i] >= 0 && f[i - 1][p - a[i]]) 
        {
            vis[i][0] = 1;
            p -= a[i];
        }
        else /* (p - b[i] >= 0 && f[i - 1][p - b[i]])  */
        {
            vis[i][1] = 1;
            p -= b[i];
        }
        // cout << vis[i][0] << " " << vis[i][1] << "\n";
    }
    for (int i = 1; i <= p1 + p2; i++)
    {
        int father = getf(i);
        if (father <= p1 + p2)
        {
            if (vis[book[father]][0]) cout << i << "\n";
        }
        else
        {
            if (vis[book[getf(i + p1 + p2)]][1]) cout << i << "\n";
        }
    }
    puts("end");
}
void merge(int x, int y)
{
    x = getf(x), y = getf(y);
    if (x == y) return;
    fa[y] = x;
    siz[x] += siz[y];
}
void solve()
{
    for (int i = 1; i <= p1 + p2; i++) 
    {
        fa[i] = i;
        siz[i] = 1;
        siz[i + p1 + p2] = 1;
        fa[i + p1 + p2] = i + p1 + p2;
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%lld%lld%s", &x, &y, s + 1);
        if (s[1] == 'y')
        {
            merge(x, y);
            merge(x + p1 + p2, y + p1 + p2);
        }
        else
        {
            merge(x, y + p1 + p2);
            merge(x + p1 + p2, y);
        }
    }


    int cnt = 0;
    for (int i = 1; i <= p1 + p2; i++)
    {
        int father = getf(i);
        if (father <= p1 + p2)
        {
            if (!book[father]) book[father] = ++cnt;
            a[book[father]]++;
            b[book[father]] = siz[father] - a[book[father]];
        }
        /* else
        {
            if (!book[father]) book[father] = ++cnt;
            b[book[father]]++;
            a[book[father]] = siz[father] - b[book[father]];
        } */
    }
    dp(cnt);
    for (int i = 1; i <= cnt; i++)
    {
        // cout << a[i] << " " << b[i] << "\n";
        for (int j = 0; j <= p1 + p2; j++) f[i][j] = 0;
    }
    for (int i = 1; i <= p1 + p2; i++)
    {
        vis[i][0] = vis[i][1] = 0;
        book[i] = 0;
        a[i] = b[i] = 0;
    }
}
void input()
{
    while(cin >> m >> p1 >> p2, m + p1 + p2)
    {
        solve();
    }
}
signed main()
{
    int tt = 1;
    // cin >> tt;
    while (tt--) input();
    return 0;
}



朴小明
5个月前

第84行和85行,这应该没区别吧?这wa的莫名其妙了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 25000 + 5, INF = 0x3f3f3f3f;
struct node{
    int val, v;
    bool operator < (const node &k) const{
        return val > k.val;
    }
};
vector<node> v[N];
queue<int> tp;
int f[N];
int cnt;
int n;
int in[N], d[N];
bitset<N> t;
void dfs(int k, int x)
{
    f[k] = x;
    for (auto i : v[k]){
        if (f[i.v] == 0) dfs(i.v, x);
    }
}
void fenkuai()
{
    for (int i = 1; i <= n; i++) {
        if (f[i] == 0) {
            dfs(i, ++cnt);
        }
    }
}
void disjktra(int s)
{
    priority_queue<node> q;
    for (int i = 1; i <= n; i++) {
        if (f[i] == s) q.push(node{d[i], i});
    }
    while(!q.empty())
    {
        int x = q.top().v;
        q.pop();
        if (t[x]) continue;
        t[x] = 1;
        for (auto i : v[x]){
            int y = i.v, val = i.val;
            if (d[y] > d[x] + val) {
                d[y] = d[x] + val;
                if (f[x] == f[y]) q.push(node{d[y], y});
            }
            if (f[y] != f[x]){
                in[f[y]]--;
                if (in[f[y]] == 0){
                    tp.push(f[y]);
                }
            }
        }
    }
}
signed main()
{
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    int m1, m2, st;
    cin >> n >> m1 >> m2 >> st;
    for (int i = 1; i <= m1; i++) {
        int x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        v[x].push_back(node{z, y});
        v[y].push_back(node{z, x});
    }
    fenkuai();


    for (int i = 1; i <= m2; i++) {
        int x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        in[f[y]]++;
        v[x].push_back(node{z, y});
    }
    memset(d, INF, sizeof(d));
    // for (int i = 0; i <= N - 1; i++) d[i] = INF;


    tp.push(f[st]);
    for (int i = 1; i <= cnt; i++) {
        if (in[i] == 0) tp.push(i);
    }
    d[st] = 0;
    while(!tp.empty()){
        int x = tp.front();
        tp.pop();
        disjktra(x);
    }


    for (int i = 1; i <= n; i++){
        if (d[i] >= INF) puts("NO PATH");
        else printf("%lld\n", d[i]);
    }
    return 0;
}


活动打卡代码 AcWing 1726. 挤奶顺序

朴小明
6个月前
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500 + 5, mod = 1e9 + 7;
int a[N], b[N], c[N], p[N];
bitset<N> f;
signed main ()
{
    int n, m, k;
    cin >> n >> m >> k;
    bool ck = 0;
    for (int i = 1; i <= m; i++){
        cin >> a[i];
        if (a[i] == 1) ck = 1;
    }
    for (int i = 1; i <= k; i++) {
        int x;
        cin >> c[i] >> x;
        if (c[i] == 1) {
            cout << x;
            return 0;
        }
        p[c[i]] = x;
        f[x] = 1;
    }
    if (ck == 0){
        for (int i = m; i >= 1; i--) {
            if (p[a[i]]) continue;
            int pos = n;
            for (int j = i + 1; j <= m; j++){ 
                pos = min(pos, p[a[j]]);
            }
            for (int j = pos; j >= 1; j--){
                if (f[j] == 0){
                    f[j] = 1;
                    p[a[i]] = j;
                    break;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (f[i] == 0){
                cout << i << endl;
                return 0;
            }
            // cout << p[i] << " ";
        }
    }
    else {
        for (int i = 1; i <= m; i++){
            if (p[a[i]]) continue;
            int pos = 1;
            for (int j = 1; j <= i - 1; j++){
                pos = max(pos, p[a[j]]);
            }
            for (int j = pos; j <= n; j++){
                if (f[j] == 0){
                    f[j] = 1;
                    p[a[i]] = j;
                    break;
                }
            }
        }
        cout << p[1] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1855. 愤怒的奶牛

朴小明
6个月前

include [HTML_REMOVED]

using namespace std;

define int long long

const int N = 1e6 + 5, mod = 1000000007;
int a[N];
int n;
int get(int st)
{
int z = 1;
int ret = 1;
for (int i = st; i <= n; i){
int j = i;
while(j + 1 <= n && a[j + 1] - a[i] <= z) {
j
;
ret;
}
if (i == j) break;
i = j;
i–;
z
;
}
z = 1;
for (int i = st; i >= 1; i–){
int j = i;
while(j - 1 >= 1 && a[i] - a[j - 1] <= z) {
j–;
ret;
}
if (i == j) break;
i = j;
i
;
z;
}
return ret;
}
signed main()
{
// int n;
cin >> n;
for (int i = 1; i <= n; i
) cin>>a[i];
sort(a + 1, a + 1 + n);
// for (int i = 1; i <= n; i) cout<<a[i]<<” “;
// cout << endl;
// for (int i = 1; i <= n; i
) cout<<get(i)<<” “;
// cout << endl;
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, get(i));
cout << ans;
return 0;
}