#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, m;
        cin >> n >> m;
        int res = 0, cur = 0;
        while (n -- )
        {
            int x;
            cin >> x;
            if (cur + x > m) res ++ , cur = 0;
            cur += x;
        }
        if (cur) res ++ ;
        cout << res << endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
int w[N];
LL l[N], r[N];
int stk[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    int tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (tt && w[stk[tt]] >= w[i]) tt -- ;
        l[i] = l[stk[tt]] + (LL)(i - stk[tt]) * w[i];
        stk[ ++ tt] = i;
    }

    tt = 0;
    stk[0] = n + 1;
    for (int i = n; i; i -- )
    {
        while (tt && w[stk[tt]] >= w[i]) tt -- ;
        r[i] = r[stk[tt]] + (LL)(stk[tt] - i) * w[i];
        stk[ ++ tt] = i;
    }

    LL res = 0, k = 0;
    for (int i = 1; i <= n; i ++ )
    {
        LL t = l[i] + r[i + 1];
        if (t > res) res = t, k = i;
    }

    for (int i = k - 1; i; i -- )
        w[i] = min(w[i], w[i + 1]);
    for (int i = k + 2; i <= n; i ++ )
        w[i] = min(w[i], w[i - 1]);

    for (int i = 1; i <= n; i ++ )
        printf("%d ", w[i]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int w[N];

int main()
{
    int m;
    scanf("%d", &m);

    unordered_map<int, PII> S;
    for (int i = 1; i <= m; i ++ )
    {
        int n, sum = 0;
        scanf("%d", &n);
        for (int j = 1; j <= n; j ++ )
        {
            scanf("%d", &w[j]);
            sum += w[j];
        }
        for (int j = 1; j <= n; j ++ )
        {
            int t = sum - w[j];
            if (S.count(t) && S[t].x != i)
            {
                puts("YES");
                printf("%d %d\n", S[t].x, S[t].y);
                printf("%d %d\n", i, j);
                return 0;
            }
            S[t] = {i, j};
        }
    }

    puts("NO");
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n;
        cin >> n;
        cout << n << endl;
        for (int i = 1; i <= n; i ++ )
            cout << i << ' ';
        cout << endl;
    }

    return 0;
}

基于宽搜的拓扑排序

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 100010;

int n, m;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int d[N], q[N];

void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (auto p = head[t]; p; p = p->next)
            if ( -- d[p->id] == 0)
                q[ ++ tt] = p->id;
    }

    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d[b] ++ ;
        add(a, b);
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ )
            printf("%d ", q[i]);
    }

    return 0;
}

基于深搜的拓扑排序

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 100010;

int n, m;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int st[N], q[N], top;

void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool dfs(int u)
{
    st[u] = 1;

    for (auto p = head[u]; p; p = p->next)
    {
        int j = p->id;
        if (!st[j])
        {
            if (!dfs(j)) return false;
        }
        else if (st[j] == 1) return false;
    }

    q[top ++ ] = u;

    st[u] = 2;
    return true;
}

bool topsort()
{
    for (int i = 1; i <= n; i ++ )
        if (!st[i] && !dfs(i))
            return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = n - 1; i >= 0; i -- )
            printf("%d ", q[i]);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n;

void update(char& c)
{
    if (c == 'W') c = 'B';
    else c = 'W';
}

bool check(string s, char c)
{
    vector<int> res;
    for (int i = 0; i + 1 < n; i ++ )
    {
        if (s[i] != c)
        {
            update(s[i]);
            update(s[i + 1]);
            res.push_back(i);
        }
    }
    if (s.back() != s[0]) return false;

    cout << res.size() << endl;
    for (auto x: res) cout << x + 1 << ' ';
    if (res.size()) cout << endl;

    return true;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        string s;
        cin >> n >> s;
        if (!check(s, 'W') && !check(s, 'B')) puts("-1");
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int a, b, c, d, e, f;
        cin >> a >> b >> c >> d >> e >> f;
        if (e >= f)
        {
            int x = min(a, d);
            int y = min({b, c, d - x});
            cout << x * e + y * f << endl;
        }
        else
        {
            int y = min({b, c, d});
            int x = min(a, d - y);
            cout << x * e + y * f << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n;
int p[N], q[N];
bool st[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(q, 0, sizeof q);
        memset(st, 0, sizeof st);
        for (int i = 1; i <= n; i ++ )
        {
            scanf("%d", &p[i]);
            q[p[i]] = i;
        }

        bool flag = false;
        for (int i = 1; i <= n; i ++ )
        {
            if (st[i] || !p[i]) continue;
            st[i] = true;
            int x = i, y = i;
            while (p[x] && !st[p[x]])
            {
                x = p[x];
                st[x] = true;
            }
            while (q[y] && !st[q[y]])
            {
                y = q[y];
                st[y] = true;
            }

            if (p[x] == y) continue;
            if (!flag)
            {
                flag = true;

                for (int j = 1; j <= n; j ++ )
                    if (!p[j] && !q[j])
                    {
                        st[j] = true;
                        p[x] = j;
                        x = j;
                    }
            }
            p[x] = y;
        }

        if (!flag)
        {
            int x = 0, y = 0;
            for (int i = 1; i <= n; i ++ )
                if (!p[i])
                {
                    if (!x && !y) x = y = i;
                    else
                    {
                        p[x] = i;
                        x = i;
                    }
                }
            p[x] = y;
        }

        for (int i = 1; i <= n; i ++ )
            printf("%d ", p[i]);
        puts("");
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s1[N], s2[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        a[ ++ n] = m;
        s1[n] = s2[n] = 0;
        for (int i = n - 1; i >= 0; i -- )
        {
            s1[i] = s1[i + 1], s2[i] = s2[i + 1];
            if (i % 2 == 0) s1[i] += a[i + 1] - a[i];
            else s2[i] += a[i + 1] - a[i];
        }

        int res = s1[0];
        for (int i = 0; i < n; i ++ )
        {
            int t = a[i + 1] - a[i];
            if (t == 1) continue;
            res = max(res, s1[0] - s1[i] + s2[i + 1] + t - 1);
        }
        printf("%d\n", res);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n, x;
        scanf("%d%d", &n, &x);
        bool flag = false;
        int a = 0;
        while (n -- )
        {
            int t;
            scanf("%d", &t);
            if (t == x) flag = true;
            a = max(a, t);
        }
        if (flag) puts("1");
        else if (x < a) puts("2");
        else printf("%d\n", (x + a - 1) / a);
    }

    return 0;
}