首页 > 其他分享 >HDU多校 2024R1

HDU多校 2024R1

时间：2024-07-21 22:18:23浏览次数：18  
标签：HDU tc int 多校 long 4005 include 2024R1 dp

T1

把 \(A\) 的所有循环位移哈希一下扔 set 里，拿 \(B\) 的所有长为 \(|A|\) 的子串查一遍即可。

代码 
#include <iostream>
#include <set>
using namespace std;
set<unsigned long long> st;
const int B = 2333;
unsigned long long pw[2000005];
int main() {
    int tc;
    cin >> tc;
    pw[0] = 1;
    for (int i = 1; i <= 2000000; i++) pw[i] = pw[i - 1] * B;
    while (tc--) {
        st.clear();
        string a, b;
        cin >> a >> b;
        int n = a.size();
        a = a + a;
        int m = b.size();
        a = ' ' + a, b = ' ' + b;
        int tmp = 0;
        for (int i = 1; i < n; i++) tmp = tmp * B + a[i] - 'A' + 1;
        for (int i = 1; i <= n; i++) {
            int t = i + n - 1;
            tmp = tmp * B + a[t] - 'A' + 1;
            st.insert(tmp);
            tmp -= pw[n - 1] * (a[i] - 'A' + 1);
        }
        tmp = 0;
        int ans = 0;
        for (int i = 1; i < n; i++) tmp = tmp * B + b[i] - 'A' + 1;
        for (int i = 1; i + n - 1 <= m; i++) {
            int t = i + n - 1;
            tmp = tmp * B + b[t] - 'A' + 1;
            ans += st.count(tmp);
            tmp -= pw[n - 1] * (b[i] - 'A' + 1);
        }
        cout << ans << "\n";
    }
    return 0;
}

T2

背包即可。

代码 
#include <iostream>
#define int long long
using namespace std;
const int inf = 0x7ffffffffffffff;
int dp[1005][4005];
int a[1005];
int b[1005];
int c[1005];
int d[1005];
signed main() {
    int tc;
    cin >> tc;
    while (tc--) {
        int n, k;
        cin >> n >> k;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) 
                dp[i][j] = inf;
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 4000; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j) 
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + a[i]);
                if (j > 1) 
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 2] + b[i]);
                if (j > 2) 
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 3] + c[i]);
                if (j > 3) 
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 4] + d[i]);
            }
        }
        cout << dp[n][k] << "\n";
    }
    return 0;
}

T3

又有 \(\max\) 又有绝对值，看起来很不爽。分讨一下拆式子，发现只需要对每个值 \(x\) 记录小于 \(x\) 的个数，小于 \(x\) 的所有数的和，大于 \(x\) 的所有数的和以及大于 \(x\) 的所有数的平方和即可完成 \(\mathcal{O}(1)\) 时间内加入 / 删除一个数并维护答案。使用 dsu on tree 加上树状数组即可做到 \(\mathcal{O}(n \log^2n)\)。

代码 
#include <iostream>
#define int long long
#define lowbit(x) ((x) & (-(x)))
using namespace std;
#define nnc getchar
inline int read() {
    int ret = 0;
    char c = nnc();
    while (c < '0' || c > '9') c = nnc();
    while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nnc();
    return ret;
}
int n;
unsigned long long a[500005];
int head[500005], nxt[1000005], to[1000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int sz[500005], son[500005];
int dfn[500005], _dfn[500005], ncnt;
void dfs1(int x, int fa) {
    sz[x] = 1;
    _dfn[dfn[x] = ++ncnt] = x;
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa) {
            dfs1(v, x);
            sz[x] += sz[v];
            if (sz[v] > sz[son[x]]) 
                son[x] = v;
        }
    }
}
struct BIT {
    pair<unsigned long long, unsigned long long> pbit[1000005], sbit[1000005];
    pair<unsigned long long, unsigned long long> pquery(int x) {
        pair<unsigned long long, unsigned long long> ret(0, 0);
        for (; x; x -= lowbit(x)) ret.first += pbit[x].first, ret.second += pbit[x].second;
        return ret;
    }
    pair<unsigned long long, unsigned long long> squery(int x) {
        pair<unsigned long long, unsigned long long> ret(0, 0);
        for (; x <= 1000000; x += lowbit(x)) ret.first += sbit[x].first, ret.second += sbit[x].second;
        return ret;
    }
    void add(int x, unsigned long long y) {
        unsigned long long tx = x;
        for (; x <= 1000000; x += lowbit(x)) pbit[x].first += y, pbit[x].second += tx * y;
        for (x = tx; x; x -= lowbit(x)) sbit[x].first += y * tx, sbit[x].second += tx * tx * y;
    }
} bit;
unsigned long long cur, Ans;
void addd(unsigned long long x, int v = 1) {
    x = a[x];
    pair<int, int> qp, qs;
    qp = bit.pquery(x - 1), qs = bit.squery(x + 1);
    cur += v * (x * (x * qp.first - qp.second) + qs.second - x * qs.first);
    bit.add(x, (unsigned long long)v);
}
void Add(int x) {
    for (int i = dfn[x]; i < dfn[x] + sz[x]; i++) addd(_dfn[i]);
}
void Del(int x) {
    for (int i = dfn[x]; i < dfn[x] + sz[x]; i++) addd(_dfn[i], -1);
}
void dfs2(int x, int fa) {
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa && v != son[x]) 
            dfs2(v, x), Del(v);
    }
    if (son[x]) 
        dfs2(son[x], x);
    addd(x);
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa && v != son[x]) 
            Add(v);
    }
    Ans ^= cur * 2;
}
signed main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u, v;
        u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) a[i] = read();
    dfs1(1, 0);
    dfs2(1, 0);
    cout << Ans << "\n";
    return 0;
}

T4

线段树分治一下，发现需要在可撤销并查集中支持给某集合中每个数加上一个给定数。考虑使用懒标记，当一个点 \(x\) 被从 \(y\) 断开时，将 \(y\) 的懒标记传到 \(x\) 上。但是这样会使新加入的数的答案多算，于是当 \(x\) 被接到 \(y\) 上时，把 \(y\) 的懒标记从 \(x\) 中减去。这样就没有问题了。

T6

转化为从三个相同的序列中分别选出一个子序列使得全部相同的方案数。\(f[i][j][k]\) 表示分别匹配到 \(i, j, k\)，三维前缀和优化即可。

代码 
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
int n;
int dp[255][255][255];
int a[255];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] + dp[i][j][k - 1] - dp[i - 1][j - 1][k] - dp[i - 1][j][k - 1] - dp[i][j - 1][k - 1] + dp[i - 1][j - 1][k - 1];
                if (a[i] == a[j] && a[j] == a[k]) 
                    dp[i][j][k] += dp[i - 1][j - 1][k - 1] + 1;
                dp[i][j][k] = (dp[i][j][k] % P + P) % P;
            }
        }
    }
    cout << dp[n][n][n] << "\n";
    return 0;
}

T7

正难则反，考虑若三个点不成环，当且仅当三个点中存在一个点有两个入度。先把所有三元组计入答案，再减去不成环的三元组即可。每个不成环的三元组在其中有两个入度的点计算其贡献，统计入度三维偏序一下即可。

代码

T8

位运算按位独立，对每一位分别考虑，对于 \(n\) 的每一位，若为 \(0\) 则有 \(4\) 种方案，否则有 \(12\) 中。每一位的方案数乘起来即可。

代码 
#include <iostream>
using namespace std;
int main() {
    int tc;
    cin >> tc;
    while (tc--) {
        int n, k;
        cin >> n >> k;
        long long ans = 1;
        while (k--) {
            if (n & 1) 
                ans *= 12;
            else 
                ans *= 4;
            n >>= 1;
        }
        cout << ans << "\n";
    }
    return 0;
}

T12

离散化，对每个区域计算其贡献。很显然被覆盖次数相同的区域对所有答案的贡献系数都相同，因此直接合并。然后 \(n^2\) 枚举覆盖次数和 \(k\) 算贡献即可。

代码 
#include <iostream>
#include <algorithm>
#include <map>
#define int long long
using namespace std;
const int P = 998244353;
int n;
int x1[2005], yy1[2005], x2[2005], y2[2005];
int d[4005], dcnt;
int nx, ny;
int _mpx[4005], _mpy[4005];
int cov[4005][4005];
int fac[4005], inv[4005], ifac[4005];
void Cpre(int x) {
    fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
    for (int i=  2; i <= x; i++) {
        fac[i] = fac[i - 1] * i % P;
        inv[i] = (P - P / i) * inv[P % i] % P;
        ifac[i] = ifac[i - 1] * inv[i] % P;
    }
}
int s[2005];
map<int, int> mp;
signed main() {
    Cpre(4000);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x1[i] >> yy1[i] >> x2[i] >> y2[i];
    for (int i = 1; i <= n; i++) d[++dcnt] = x1[i], d[++dcnt] = x2[i];
    sort(d + 1, d + dcnt + 1);
    for (int i = 1; i <= dcnt; i++) (d[i] != d[i - 1]) ? (_mpx[mp[d[i]] = mp[d[i - 1]] + 1] = d[i]) : 0;
    for (int i = 1; i <= n; i++) x1[i] = mp[x1[i]], x2[i] = mp[x2[i]];
    nx = mp[d[dcnt]];
    dcnt = 0, mp.clear();
    for (int i = 1; i <= n; i++) d[++dcnt] = yy1[i], d[++dcnt] = y2[i];
    sort(d + 1, d + dcnt + 1);
    for (int i = 1; i <= dcnt; i++) (d[i] != d[i - 1]) ? (_mpy[mp[d[i]] = mp[d[i - 1]] + 1] = d[i]) : 0;
    for (int i = 1; i <= n; i++) yy1[i] = mp[yy1[i]], y2[i] = mp[y2[i]];
    ny = mp[d[dcnt]];
    for (int i = 1; i <= n; i++) {
        cov[x1[i]][yy1[i]]++;
        cov[x2[i]][yy1[i]]--;
        cov[x1[i]][y2[i]]--;
        cov[x2[i]][y2[i]]++;
    }
    for (int i = 1; i <= nx; i++) {
        for (int j = 1; j <= ny; j++) 
            cov[i][j] += cov[i - 1][j] + cov[i][j - 1] - cov[i - 1][j - 1];
    }
    for (int i = 1; i < nx; i++) {
        for (int j = 1; j < ny; j++) {
            int S = (_mpx[i + 1] - _mpx[i]) * (_mpy[j + 1] - _mpy[j]);
            s[cov[i][j]] += S;
        }
    }
    for (int k = 1; k <= n; k++) {
        int ans = 0;
        for (int x = 1; x <= n - k; x++) 
            ans += s[x] % P * (P + 1 - fac[n - x] * fac[n - k] % P * ifac[n] % P * ifac[n - x - k] % P) % P;
        for (int x = n - k + 1; x <= n; x++) ans = (ans + s[x]) % P;
        cout << ans % P << "\n";
    }
    return 0;
}

标签：HDU,tc,int,多校,long,4005,include,2024R1,dp
From： https://www.cnblogs.com/forgotmyhandle/p/18315049

相关文章

  • A Bit More Common (2024牛客多校1 B)
    进入博客阅读体验更佳：ABitMoreCommon(2024牛客多校1B)|付诺の小站(funuo0728.github.io)ABitMoreCommon题目大意给定两个整数n和m(1\len,m\le5000)，在所有长度为n且元素取值范围为[0,2^m)的序列中，计算存在两个合法子序列的序列个数。其中，合法子序列是指......
  • 2024牛客多校1
    2024牛客多校12024年第一场多校赛，打的很一般，多校之前vp的几场多校成绩还不错，一场比赛直接打回原形。赛时队友做的签到题C、H，吃了两发罚时，我自己推的A，出的很快，可惜没注意取模，吃了发罚时，长个记性吧。A给定n，m，p，问长度为n，并且都由小于\(2^m\)的数组成，存在一个子序列的按位且等......
  • 2024牛客暑期多校训练营2 解题报告
    B-MST对于整个序列进行一次kruskal对于序列中如果需要访问的点数小于300那么将所有的点的边存入序列中进行kruskal如果大于300那么直接对于所有的点进行kruskal点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineall(x)x.begin(),x.end()#defineral......
  • 2024牛客暑期多校训练营2 HI
    2024牛客暑期多校训练营2H.InstructionsSubstring题意：有一个字符串序列，有WSAD四种操作，可以上下左右移动。可以选取一段连续的子序列，从（0,0）出发，经过连续子序列操作后可以经过点(x,y)，问这样的子序列有多少个思路：若一个子序列能够实现到达点（x,y），那么在这个子序列后面加任意字符都......
  • 2024牛客暑期多校训练营2
    H.InstructionsSubstring题目大意：给出一段长为\(n\)的字符串，其中WASD分别代表向上下左右走，给出目的地\((x,y)\)，选择一段连续子序列使得从\((0,0)\)出发可以经过目的地，求这样的子序列的总数。思路：用前缀和记录到\(i\)为止到达的位置，从前往后遍历右端点\(r\)，找到恰好到......
  • 2024牛客暑期多校训练营1
    A:ABitCommon题目大意：建立一个长度为n且每个数严格小于\(2^m\)的非空序列A使其存在一个非空子序列B，B中所有元素的与运算结果为1，输出合法A序列的个数。思路：存在子序列合法即该序列合法，其他元素无要求。即可以枚举合法子序列的长度，其他元素均为必定非合法整数。又因为需要结果为......
  • 航电多校 2024 笔记
    01写点赛时不会的。难绷场，可能因为是01所以比较水，就只有最后一个能放省选模拟T1，以及一堆原神题。T5hdu7434博弈小马给出了一个可重小写字符集合 \(S\)。Alice初始时有空串 \(A\)，Bob初始时有空串 \(B\)。两人轮流等概率取出集合 \(S\) 中的一个字符 \(c\)，将它拼接......
  • 多校联合暑假训练赛第一场
    B.对数组的最小操作次数Code:#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;intdp[N][8],n,k,a[N];intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(inti=1;i......
  • 2024牛客暑期多校训练营1 解题报告
    A-ABitCommon通过该题的性质可以知道偶数的关系不影响能够成立的序列我们只讨论最后一位为1的数这些数才能对该序列造成影响又因为对于每个特殊序列中每位必定有一个0所以特殊序列的个数为C(n,k)*2((m-1)*(m-n))*(2(m-1)-1)^(n-k)点击查看代码#include<bits/stdc++.h>......
  • 杭电多校补题
    1001.循环位移#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;constintN=1048580*2;constintP=131;ullp[N],h1[N],h2[N];voidsolve(){stringa,b;cin>>a>>b;intn=a.size()......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99