1004 智能车

Description

看是否存在若干中方案使得 $p_{x_1}+p_{x_2}+p_{x_3}+\cdots =c$

Input

一共 $T$ 组数据，对于每一组数据：
$\boxed{{\displaystyle \begin{array}{}n& c\\ p_1& p_2& p_3& \dots & p_n\end{array}}}$
数据范围：

• $1\le T\le 10$
• $1\le n\le 5\times {10}^4$
• $1\le c\le 500$
• $1\le p_i\le c$

Output

找出一个方案满足最大值和最小值相差最小，求出最小的差值。如果不存在满足条件的方案，输出−1。

Sample Input

1
4 10
3 7 2 5

Sample Output

3

Hint

样例中，一种可行的方案是 $[3,2,5]$，差值为 $3$。可以证明不存在差值更小的方案。

1008 大雪球

Description

把两个不同的数合成一个更大的数扔出去
例如两个数的大小分别为 $x,y$ 可以合成一个 $x+y$ 的大数。
求出在所有的合成方案中，第 $k$ 小的大数的大小。
两个合成方案不同当且仅当至少一个数的序号不同。

input

有 $T$ 组数据，对于每组数据;
$\boxed{{\displaystyle \begin{array}{}n\\ v_1& v_2& v_3& \dots & v_n\\ k\end{array}}}$
数据范围：

• $1\le T\le 10,2\le n\le 1\times {10}^5,1\le v_i\le {10}^9,1\le k\le \frac{n\times (n-1)}{2}$

Output

输出第 $k$ 小的大数的大小。

Sample Input

1
4
2 3 4 5
3

Sample Output

7

Hint

样例中，可以合成 $6$ 种不同的大雪球，按体积排序后为 $[5,6,7,7,8,9]$，因此体积第 $3$ 小的大雪球的体积为 7。

1009 序列

求 $\sum _{l=1}^n\sum _{r=l}^n(a_l\oplus a_{l+1}\oplus \cdots \oplus a_r)\times \underset{l\le i\le r}{min}{a}_i$ 对 $998244353$ 取模的值。
输入
$\boxed{{\displaystyle \begin{array}{}T\\ n\\ a_1& a_2& a_3& \dots & a_n\end{array}}}$
输出答案
输入样例

2
3
2 3 4
5
5 12 18 8 17

输出样例

62
2219

代码(不确定正确性)

#include<bits/stdc++.h>
#define MOD 998244353
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    long long ans = 0;
    for (int l = 0; l < n; l++)
    {
        int prefixXOR = 0;
        int minVal = a[l];
        for (int r = l; r < n; r++)
        {
            prefixXOR ^= a[r];
            minVal = min(minVal, a[r]);
            ans = (ans + (prefixXOR * minVal) % MOD) % MOD;
        }
    }
    cout << ans << endl;
}
int main()
{
    int _;
    cin >> _;
    while(_--)
        solve();
}

1003

#include<bits/stdc++.h>
#define MOD 998244353
using namespace std;

int dfs(int node, int k, vector<vector<int>> &graph, vector<int> &evilValue, vector<vector<int>> &dp)
{
    if (dp[node][k] != -1)
        return dp[node][k];
    int result = (evilValue[node] <= k);
    for (int neighbor : graph[node])
        if (k >= evilValue[node])
            result = (result + dfs(neighbor, k / evilValue[node], graph, evilValue, dp)) % MOD;
    dp[node][k] = result;
    return result;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> evilValue(n);
        for (int i = 0; i < n; i++)
            cin >> evilValue[i];

        vector<vector<int>> graph(n);
        for (int i = 0; i < m; i++)
        {
            int u, v;
            cin >> u >> v;
            graph[u - 1].push_back(v - 1);
        }

        vector<vector<int>> dp(n, vector<int>(k + 1, -1));

        int totalPaths = 0;
        for (int i = 0; i < n; i++)
            totalPaths = (totalPaths + dfs(i, k, graph, evilValue, dp)) % MOD;

        cout << totalPaths << endl;
    }

}

1007

#include<bits/stdc++.h> 
using namespace std;

const int MAXN = 1005;
const int MAXK = 6;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

struct State
{
    int x, y, t;
};

char grid[MAXK][MAXN][MAXN];
bool visited[MAXK][MAXN][MAXN];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(visited, 0, sizeof(visited));
        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int l = 0; l < m; l++)
                {
                    cin >> grid[i][j][l];
                }
            }
        }
        int h, ex, ey;
        cin >> h >> ex >> ey;

        queue<State> q;
        q.push({n, m, 0});
        visited[0][n][m] = true;

        while (!q.empty())
        {
            State cur = q.front();
            q.pop();

            if (cur.x == ex && cur.y == ey)
            {
                cout << cur.t << endl;
                break;
            }

            for (int i = 0; i < 4; i++)
            {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                if (grid[(cur.t + 1) % k][nx][ny] == '*')
                    continue;
                for (int j = 0; j <= h; j++)
                {
                    int tx = nx - j;
                    if (tx <= 0)
                        break;
                    if (grid[(cur.t + 1) % k][tx][ny] == '*')
                        break;
                    if (visited[(cur.t + 1) % k][tx][ny])
                        continue;
                    visited[(cur.t + 1) % k][tx][ny] = true;
                    q.push({tx, ny, cur.t + 1});
                }
            }
        }
    }
}

1005

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<int> depth;
vector<int> xorValues;
vector<vector<int>> weight;
void dfs(int node, int parent, int xorVal, int d)
{
    depth[node] = d;
    xorValues[node] = xorVal;

    for (int child : tree[node])
        if (child != parent)
            dfs(child, node, xorVal ^ weight[node][child], d + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--)
    {
        int n;
        cin >> n;

        tree.resize(n + 1);
        depth.resize(n + 1);
        xorValues.resize(n + 1);
        weight.assign(n + 1, vector<int>(n + 1, 0));

        for (int i = 0; i < n - 1; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            tree[u].push_back(v);
            tree[v].push_back(u);
            weight[u][v] = w;
            weight[v][u] = w;
        }

        dfs(1, 0, 0, 0);

        int q;
        cin >> q;

        for (int i = 0; i < q; i++)
        {
            int l, r, x;
            cin >> l >> r >> x;

            int result = 0;
            for (int j = l; j <= r; j++)
                result += xorValues[j] ^ xorValues[x];
            cout << result << endl;
        }
        tree.clear();
        depth.clear();
        xorValues.clear();
        weight.clear();
    }
}

1006

1002