2026春季W3(3.16~3.22)

HDU春季热身赛1005

为什么又是一道 \(dp\) \ll
观察到 \(k\) 一定小于25，可以作为数组的第二维，于是我们令 \(dp_{i, j}\) 为在位置 \(i\) 时，剩余 \(j\) 个位置拥有"时空回溯副作用" 时可以得到的最多碎片。
我们考虑三个规则：

1. 直接收集， \(j\) 在不等于0时得到的是 \(a_i / 2\) ，且添加后 \(j\) 会 \(-1\) 。\(dp_{i+1,max(0,j-1)} = max(...,dp_{i,j}+v)\)
2. 时空回溯，只能当 \(j =0\) 时使用，使用后 \(j = k\) 。\(dp_{i+1,k} = max(...,dp_{i,0}+2 \cdot a_i)\)
3. 时空跳跃，直接转移即可， \(i\) 到 \(i+m\) 的所有碎片用前缀和处理。\(dp_{i+m+1,max(0,j-m-1)} = max(...,dp_{i,j}+pre_{i+m}-pre_{i-1})\)
   最后记得处理答案的时候将 \(dp\) 数组的 \(n\) 到 \(n+m+1\) 全遍历一遍求最大即可，如果只到 \(n+m\) 为错误。

HDU春季联赛第一场

1009

本题需通过 \(bfs\) 搜索答案，在设置边界条件时，有结论：若最后存在一个方案，则图中向量和的两个维度不会超出一个区间(即如果某个分支跑的离原点很远了就可以直接剪枝)。在设置坐标时设置偏移量(因为坐标会存在负数但数组下标不行)。

const int C = 255;
int n;
int dis[590][590];
void LonelyLunar_solve(){
    cin>>n;
    vector<pii> usd;
    vector<pii> a;
    queue<pii> q;
    for(int i = 1;i <= n; i++){
        int x,y;cin>>x>>y;
        if(dis[x+C][y+C]==2e9){
            dis[x+C][y+C] = 1;
            a.push_back({x,y});
            usd.push_back({x,y});
            q.push({x,y});
        }
    }
    if(dis[C][C]==1){
        cout<<"1"<<endl;
        for(auto i : usd) dis[i.first+C][i.second+C] = 2e9;
        return;
    }
    while(!q.empty()){
        int x = q.front().first,y = q.front().second;
        q.pop();
        for(auto [tx, ty] : a){
            int xx = x+tx;
            int yy = y+ty;
            if(xx==0&&yy==0){
                cout<<dis[x+C][y+C]+1<<endl;
                for(auto i : usd) dis[i.first+C][i.second+C] = 2e9;
                return;
            }
            if(xx>C||xx<-C||yy>C||yy<-C||dis[xx+C][yy+C]!=2e9) continue;
            usd.push_back({xx,yy});
            q.push({xx,yy});
            dis[xx+C][yy+C] = dis[x+C][y+C]+1;
        }
    }
    cout<<"-1"<<endl;
}

1001

根据游戏规则可以发现是巴什博弈，有结论：若石头总数是(可以拿的最多数量+1)的整数倍，则先手必败，否则先手必胜。此时我们要解决的问题是先手在哪些情况下会赢。
由于我们知道石头总数 \(N = f(i,j,k) = a_i \cdot k^{a_i + a_j} + a_j\) ，所以本问题转化为： \(N = f(i,j,k) = a_i \cdot k^{a_i + a_j} + a_j\) 什么时候是 \(k+1\) 的倍数？

由 \(k \equiv -1 \pmod{k+1}\) ，上述公式中的 \(k\) 可被替换成 \(-1\) ，转化为\(a_i \cdot (-1)^{a_i + a_j} + a_j\) 。对该公式分类讨论：

1. \(a_i\) 和 \(a_j\) 奇偶性不同,那么 \(a_i + a_j\) 是奇数，\((-1)\) 的奇数次方还是 \(-1\)。 式子变成：\(-a_i + a_j\)，也就是 \(a_j - a_i\)。 因为 \(k\) 是区间最大值，所以 a_i 和 a_j 都小于等于 \(k\)。它们的差值 \(a_j - a_i\) 的范围在 \((-k,\ k)\)。在这个范围里，只有 0 是 \(k+1\) 的倍数，也就是要求 \(a_i = a_j\)。但这又和“奇偶性不同”矛盾。 结论：这种情况小远永远不可能输（必胜）。
2. \(a_i\) 和 \(a_j\) 奇偶性相同，式子变成：\(a_i + a_j\) 。因为 \(a_i\) 和 \(a_j\) 都小于 \(k\)，所以它们的和最大不到 \(2k\)。要使其变成 \((k+1)\) 的倍数，唯一可能只能为 \(k+1\) 。
   以上，得出小远必败的条件：\(a_{i}+a_{j}=k+1\) 且 \(k+1\) 为偶数。
   对原题，转化为：找出多少对 \((i,\ j)\) 让小远必输，然后用总方案数相减。
   显然不能暴力，因此把数组里的每一个数当作最大值 k。利用单调栈可以快速找到每个数能“管辖”的范围（在这个区间内，它就是最大的），当查询的 \(k\) 为偶数时直接跳过即可。
   对于一个奇数 \(k\) ，假设它的管辖区间是 \([L,\ R]\)，它自己在位置 \(m\)。 现在 \(m\) 把区间分成了左右两半。我们要在左边找一个 \(a_i\) ，右边找一个 \(a_j\) ，使得 \(a_i + a_j = k + 1\) 。为了快，我们只遍历左右两边比较短的那一半。假设左边短，我们就遍历左边的每一个数 \(x\) ，此时我们需要在右半区间里存下标二分查找有没有哪个数等于 \((k + 1) - x\)。

int n;
int a[mxn];
void LonelyLunar_solve(){
    cin>>n;
    vector<int> L(n+1,0);
    vector<int> R(n+1,0);
    vector<int> val;
    for(int i = 1;i <= n; i++){
        cin>>a[i];
        val.push_back(a[i]);
        L[i] = R[i] = 0;
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    vector<vector<int>> pos(val.size());
    //pos[id]存储离散化后第id大的元素在原数组中出现的所有下标
    for(int i = 1;i <= n; i++){
        int id = lower_bound(val.begin(),val.end(),a[i])-val.begin();
        pos[id].push_back(i);
    }
    //单调栈求 L[i]：左侧第一个【严格大于】a[i] 的位置
    //使用“严格大于”和右侧的“大于等于”配合，避免多个相同最大值时的重复统计
    vector<int> s;
    for(int i =1 ;i <= n; i++){
        while(!s.empty()&&a[s.back()]<=a[i]) s.pop_back();
        L[i] = s.empty()?0:s.back();
        s.push_back(i);
    }
    s.clear();
    for(int i = n;i >= 1; i--){
        while(!s.empty()&&a[s.back()]<a[i]) s.pop_back();
        R[i] = s.empty()?n+1:s.back();
        s.push_back(i);
    }
    auto get = [&](int v,int ql,int qr) -> int{
        if(v<0) return 0;
        auto it = lower_bound(val.begin(),val.end(),v);
        if(it==val.end()||*it!=v) return 0;
        int id = distance(val.begin(), it);
        auto it1 = lower_bound(pos[id].begin(),pos[id].end(),ql);
        auto it2 = upper_bound(pos[id].begin(),pos[id].end(),qr);
        return distance(it1, it2);
    };
    ll lsc = 0;
    for(int p = 1;p <= n; p++){
        if(a[p]%2==0) continue;
        int lp = p-L[p],rp = R[p]-p;
        int target = a[p]+1;//a[i] + a[j] = k + 1
        if(lp<=rp){
            for(int x = L[p]+1;x <= p; x++){
                int req = target-a[x];
                lsc+=get(req, p, R[p]-1);
            }
        }
        else{
            for(int x = p;x < R[p]; x++){
                int res = target-a[x];
                lsc+=get(res, L[p]+1, p);
            }
        }
    }
    cout<<(ll)n*n-2ll*lsc<<endl;
}

本周专题：最短路

洛谷P2865P2865 [USACO06NOV] Roadblocks G - 洛谷

在求次短路时，不能使用局部贪心代替最短路，而是需要设置一个 \(cmindis\) 数组，在求最短路的过程中顺手把次短路求出来，以及在当前的行进距离小于当前点记录的最短距离时，不止是记录最短路和次短路长度，还需要将两种路径都压入队列中。

洛谷P6464P6464 [传智杯 #2 决赛] 传送门 - 洛谷

显然暴力不行且为 \(Floyd\) 求最短路，在每次枚举两个点之间做传送门的时候只需要将与这两个点相关的边重新判一遍即可(即只需要枚举一遍中间点 \(k\) )。