//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 510, M = 5210;
int h[N], e[M], ne[M], w[M], idx;
int n, m1, m2;
int dist[N], cnt[N];
bool st[N];
inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
inline bool spfa()
{
    queue<int> q;
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
inline void solve()
{
    idx = 0;
    cin >> n >> m1 >> m2;
    memset(h, -1, sizeof h);
    while (m1 -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    while (m2 -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, -c);
    }
    if (spfa()) cout << "YES" << endl;
    else cout << "NO" << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t -- ) solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 240;
int h[N], e[N], ne[N], idx;
double r[N], c[N];
int cnt[N];
int n, m, s;
double v;
double dist[N];
bool st[N];
inline void add(int a, int b, double x, double y)
{
    e[idx] = b, r[idx] = x, c[idx] = y, ne[idx] = h[a], h[a] = idx ++;
}
inline bool spfa()
{
    queue<int> q;
    q.push(s);
    dist[s] = v;
    st[1] = true;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < (dist[t] - c[i]) * r[i])
            {
                dist[j] = (dist[t] - c[i]) * r[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
inline void solve()
{
    cin >> n >> m >> s >> v;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        double x1, y1, x2, y2;
        cin >> a >> b >> x1 >> y1 >> x2 >> y2;
        add(a, b, x1, y1), add(b, a, x2, y2);
    }
    if (spfa()) puts("YES");
    else puts("NO");
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

spfa

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 240;
int h[N], e[N], ne[N], idx;
double r[N], c[N];
int cnt[N];
int n, m, s;
double v;
double dist[N];
bool st[N];
inline void add(int a, int b, double x, double y)
{
    e[idx] = b, r[idx] = x, c[idx] = y, ne[idx] = h[a], h[a] = idx ++;
}
inline bool spfa()
{
    queue<int> q;
    q.push(s);
    dist[s] = v;
    st[1] = true;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < (dist[t] - c[i]) * r[i])
            {
                dist[j] = (dist[t] - c[i]) * r[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
inline void solve()
{
    cin >> n >> m >> s >> v;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        double x1, y1, x2, y2;
        cin >> a >> b >> x1 >> y1 >> x2 >> y2;
        add(a, b, x1, y1), add(b, a, x2, y2);
    }
    if (spfa()) puts("YES");
    else puts("NO");
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
#define  endl '\n'
using namespace std;
const int N = 5e5 + 10, M = 150;
struct node
{
    int p, s;
}factor[N];
int primes[N], cnt;
bool st[N];
int cntf, divide[N], cntd;
inline int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
inline void get(int x)
{
    for (int i = 2; i <= x; i ++ )
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= x; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
inline void dfs(int u, int p)
{
    if (u > cntf)
    {
        divide[cntd ++] = p;
        return;
    }
    for (int i = 0; i <= factor[u].s; i ++ )
    {
        dfs(u + 1, p);
        p *= factor[u].p;
    }
}
inline void solve()
{
    int n;
    cin >> n;
    while (n --)
    {
        int a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;
        int d = b1;
        cntf = 0;
        for (int i = 0; primes[i] <= d / primes[i]; i ++ )
        {
            int p = primes[i];
            if (d % p == 0)
            {
                int s = 0;
                while (d % p == 0) d /= p, s ++;
                factor[++ cntf] = {p, s};
            }
        }
        if (d > 1) factor[++ cntf] = {d, 1};
        cntd = 0;
        dfs(1, 1);
        int res = 0;
        for (int i = 0; i < cntd; i ++ )
        {
            int x = divide[i];
            if (gcd(x, a0) == a1 && (long long) x * b0 / gcd(x, b0) == b1) res ++;
        }
        cout << res << endl;
    }
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    get(N);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
int primes[N], st[N];
int n, cnt;
inline void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
inline void solve()
{
    cin >> n;
    init(n);
    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i], c = 0;
        for (int j = n; j; j /= p ) c += j / p;
        cout << p << " " << c << endl;
    }
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int w[N], q[N];
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i];
    int res = 0, hh = 0, tt = -1;
    int len = n / 2;
    for (int i = 1; i <= n * 2; i ++ )
    {
        if (hh <= tt && i - len > q[hh]) hh ++;
        if (res < i - q[hh] + w[q[hh]] + w[i])
            res = i - q[hh] + w[q[hh]] + w[i];
        while (hh <= tt && w[q[tt]] - q[tt] <= w[i] - i) tt --;
        q[ ++ tt] = i;
    }
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

滑动窗口 + 优化

不难发现如果 i - j > n / 2，由于 n - (i - j) = n + j - i <= n / 2，因此可以对应成在 i 和 j + n 之间运送货物，
代价为 a[i] + a[j] + n + j - i
可是O(n ^ 2)必然超时
不难发现他是维护一个区间内的最大值，答案取决于a[j] - j

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int w[N], q[N];
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i];
    int res = 0, hh = 0, tt = -1;
    int len = n / 2;
    for (int i = 1; i <= n * 2; i ++ )
    {
        if (hh <= tt && i - len > q[hh]) hh ++;
        if (res < i - q[hh] + w[q[hh]] + w[i])
            res = i - q[hh] + w[q[hh]] + w[i];
        while (hh <= tt && w[q[tt]] - q[tt] <= w[i] - i) tt --;
        q[ ++ tt] = i;
    }
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 3850;
int f[2][N][2], w[N];
int n, m;
inline void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    memset(f, -0x3f, sizeof f);
    f[1][1][1] = f[1][0][0] = 0;
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
            if (j >= 1) 
            f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][1] + w[i], f[i - 1 & 1][j - 1][0]);
        }
    int res = f[n & 1][m][0];
    memset(f, -0x3f, sizeof f);
    f[1][0][0] = 0; f[1][1][1] = w[1];
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
            if (j >= 1) 
            f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][1] + w[i], f[i - 1 & 1][j - 1][0]);
        }
    if (res < f[n & 1][m][1]) cout << f[n & 1][m][1] << endl;
    else cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

状态转移

设f[i][j][0/1]表示在第i个小时睡或不睡，睡j个小时的恢复的最大体力值
不难得出
f[i][j][0] = max(f[i-1][j][1], f[i-1][j][0])
f[i][j][1] = max(f[i-1][j-1][1] + w[i], f[i-1][j-1][0])
关于状态初始化的时候分类讨论下当天最后一小时睡与不睡，即：
第n小时不睡觉
memset(f, -0x3f, sizeof f);
f[1][0][0] = f[1][1][1] = 0;

第n小时睡觉
memset(f, -0x3f, sizeof f);
f[1][0][0] = 0; f[1][1][1] = w[1];

但是经过计算，该数组内存会超限
64mb = 1.6 * 10 ^ 7
数组占用内存 3.2 * 10 ^ 7

不难发现，当前状态与最近两层有关系，所以再用滚动数组优化

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3850;
int f[2][N][2], w[N];
int n, m;
inline void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    memset(f, -0x3f, sizeof f);
    f[1][1][1] = f[1][0][0] = 0;
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
            if (j >= 1) 
            f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][1] + w[i], f[i - 1 & 1][j - 1][0]);
        }
    int res = f[n & 1][m][0];
    memset(f, -0x3f, sizeof f);
    f[1][0][0] = 0; f[1][1][1] = w[1];
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
            if (j >= 1) 
            f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][1] + w[i], f[i - 1 & 1][j - 1][0]);
        }
    if (res < f[n & 1][m][1]) cout << f[n & 1][m][1] << endl;
    else cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 2510;
bool st[N];
int n, m, s, e;
int g[N][N];
int dist[N];
inline int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for (int i = 1; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j])) 
                t = j;
        st[t] = true;
        for (int j = 1; j <= n ; j ++ )
            if (dist[j] > dist[t] + g[t][j])
                dist[j] = dist[t] + g[t][j];
    }
    return dist[e];
}
inline void solve()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m >> s >> e;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        int cnt = c < g[a][b] ? c : g[a][b];
        g[a][b] = g[b][a] = cnt;
    }
    cout << dijkstra() << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~