1004 智能车

Description

看是否存在若干中方案使得 \(p_{x_{1}}+p_{x_{2}}+p_{x_{3}}+\dots=c\) ## Input 一共 \(T\) 组数据，对于每一组数据： \(\boxed{\begin{array}&n&c\\p_{1}&p_{2}&p_{3}&\dots&p_{n}\end{array}}\) 数据范围： - \(1\leq T\leq 10\) - \(1\leq n\leq 5\times 10^4\) - \(1\leq c\leq 500\) - \(1\leq p_{i}\leq c\) ## Output 找出一个方案满足最大值和最小值相差最小，求出最小的差值。如果不存在满足条件的方案，输出−1。 ## Sample Input

1
2
3

1
4 10
3 7 2 5

## Sample Output

## Hint 样例中，一种可行的方案是 \([3,2,5]\)，差值为 \(3\)。可以证明不存在差值更小的方案。 # 1008 大雪球 ## Description 把两个不同的数合成一个更大的数扔出去例如两个数的大小分别为 \(x,y\) 可以合成一个 \(x+y\) 的大数。求出在所有的合成方案中，第 \(k\) 小的大数的大小。两个合成方案不同当且仅当至少一个数的序号不同。 ## input 有 \(T\) 组数据，对于每组数据; \(\boxed{\begin{array}&n\\v_{1}&v_{2}&v_{3}&\dots&v_{n}\\k\end{array}}\) 数据范围： - \(1\leq T\leq 10,2\leq n\leq 1\times10^5,1\leq v_{i}\leq 10^9,1\leq k\leq \frac{n\times(n-1)}{2}\) ## Output 输出第 \(k\) 小的大数的大小。

Sample Input

Sample Output

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

1009 序列

求 \(\sum\limits_{l=1}^n\sum\limits_{r=l}^n(a_{l}\oplus a_{l+1}\oplus\dots \oplus a_{r})\times \min_{l\leq i\leq r}a_{i}\) 对 \(998244353\) 取模的值。输入 \(\boxed{\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

输出样例

1
2

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

![[../../../../images/Z-attachment/Pasted image 20231230174217.png]]

#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 ![[../../../../images/Z-attachment/Pasted image 20231230174200.png]]

#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

![[../../../../images/Z-attachment/Pasted image 20231230174109.png]]

#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

![[../../../../images/Z-attachment/Pasted image 20231230174412.png]]

1002

![[../../../../images/Z-attachment/Pasted image 20231230174703.png]]

FXJFXJ

HDU新生赛