军训

Description

起点 (0,0)(0,0) ，每次只能走恰好曼哈顿距离为 kk 的点，构造一种到达 (x,y)(x,y) 且步数最小的方案，无解输出 -1。

Input

一行三个整数 k,x,yk, x, y 。

Output

若无解，一行一个整数 -1。

否则第一行一个整数 ss, 代表最小操作次数。

接下来 ss 行，第 ii 行两个整数 xi,yix_i, y_i, 表示第 ii 次操作后的坐标，若多组解任意输出一组。

Hint

1≤k≤109,−105≤x,y≤105,(x,y)≠(0,0)1 \le k \le 10^9, -10^5 \le x,y \le 10^5, (x,y) \not = (0,0)

Solution

因为 x,yx,y 可正可负，不如先将 x,yx,y 取绝对值，输出时判符号。

如果 kk 是奇数，那么所有坐标都可达(存在一种方案从 (x,y)(x,y) 走到 (x+1,y)(x+1,y) )。

如果 kk 是偶数，那么 x+y≡1(mod2)x+y \equiv 1 \pmod 2 的所有坐标都不可达，其他坐标都可达(存在一种方案从 (x,y)(x,y) 走到 (x+1,y+1)(x+1,y+1) )

如果 x+y>2kx+y > 2k ，那么直接向 (x,y)(x,y) 的方向走即可。

如果 x+y≤2kx+y \le 2k ，此时一定有 2k−x−y mod 2=02k-x-y \bmod 2 = 0，设 x+y+2t=2kx+y+2t = 2k，则 t=k−⌊x+y2⌋t = k-\lfloor \frac{x+y}{2} \rfloor，然后我们分两步走，每步在其中一个反方向走 tt，这样两次走的反方向就是 2t2t ，走过的距离就是 x+y+2t=kx+y+2t=k ，正好能从 (x,y)(x,y) 走到 (0,0)(0,0)

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

typedef pair<int,int> pir;

int k, x, y;

stack<pir,vector<pir>> st;

pir f(int x, int y);

int main()
{
    cin >> k >> x >> y;
    if(k%2 == 0 and (x+y)%2 != 0)
        return cout << "-1", 0;
    st.emplace(x, y);
    while(x != 0 or y != 0)
    {
        st.emplace(f(x, y));
        x = st.top().first;
        y = st.top().second;
    }
    
    st.pop();
    
    cout << st.size() << "\n";
    while(!st.empty())
    {
        cout << st.top().first << " " << st.top().second << "\n";
        st.pop();
    }
}

pir f(int x, int y)
{
    if(x > y)
    {
        pir tmp = f(y, x);
        return {tmp.second, tmp.first};
    }
    if(x < 0)
    {
        pir tmp = f(-x, y);
        return {-tmp.first, tmp.second};
    }
    if(x+y >= k*2) return {x, y-k};
    if(x+y == k) return {0, 0};
    int t = k - (x+y)/2;
    return {-t, x+y-(k-t)};
}

命题规范

Description

有 nn 种需要满足的命题规范，mm 个出题人，提供 ai,ja_{i,j} 个大样例可以让第 jj 个出题人满足第 ii 个规范，在找到第 ii 个出题人满足规范之前，需要先提供 bib_i 个大样例。

求满足所有命题规范最少提供多少大样例。

Input

第一行两个整数 n,mn,m

接下来 nn 行，第 ii 行 mm 个整数 ai,1,ai,2,⋯ ,ai,ma_{i,1},a_{i,2},\cdots,a_{i,m}。

接下来一行 mm 个整数 b1,b2,⋯ ,bmb_1, b_2, \cdots, b_m

Output

一行一个整数表示答案

Hint

1≤n≤105,1≤m≤25,1≤ai,j,bi≤1091 \le n \le 10^5, 1 \le m \le 25, 1 \le a_{i,j},b_i \le 10^9

Solution

直接暴力是 O(nm2m)O(nm2^m) 的，首先 2m2^m 没办法省掉，那么需要避免每次枚举 nmnm 来计算答案。

如果还是保留暴力的取 min⁡\min ，是没办法降低时间复杂度的，因为取 min⁡\min 无法继承贡献。

考虑出题人选定时每道题的贡献: 最小的出现在出题人集合里的数。

一个小 trick: 差分数组的前缀和是原数，这样的话我们可以把取 min⁡\min 变成求和操作，方便继承贡献。

对于一道题 ii ，设 ai,p1≤ai,p2≤⋯≤ai,pma_{i,p_1} \le a_{i,p_2} \le \cdots \le a_{i,p_m}，设选择的出题人集合为 SS ，对于 1≤j≤m1 \le j \le m，若 {p1,p2,⋯ ,pj−1}⊆{1,2,⋯ ,m}∖S\{p_1, p_2, \cdots, p_{j-1}\} \subseteq \{1,2,\cdots,m\} \setminus S ，则答案需要加上 ai,pj−ai,pj−1a_{i,p_j}-a_{i,p_{j-1}}，我们将这个数作为集合 {p1,p2,⋯ ,pj−1}\{p_1, p_2, \cdots, p_{j-1}\} 的贡献。

出题人集合 SS 的答案即为 {1,2,⋯ ,m}∖S\{1,2,\cdots,m\} \setminus S 的子集和。

时间复杂度 O(nmlog⁡m+m2m)O(nm \log m + m2^m)。

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

typedef long long ll;
const int N = 1e5+10;
const int M = 25;

int n, m;
int p[M+1];
ll a[N][M+1], b[M+1];
ll f[1<<M], g[1<<M];

#define pos(i) (1<<(i-1))

int main()
{
    read(n, m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            read(a[i][j]);
    for(int i = 1; i <= m; i++)
        read(b[i]);
    
    for(int i = 1; i < (1<<m); i++)
    {
        int l = __builtin_ctz(i);
        g[i] = g[i^(1<<l)]+b[l+1];
    }
    
    iota(p+1, p+m+1, 1);
    
    for(int i = 1; i <= n; i++)
    {
        sort(p+1, p+m+1, [&](int x, int y){
            return a[i][x] < a[i][y];
        });
        int st = 0;
        for(int j = 1; j <= m; j++)
        {
            f[st] += a[i][p[j]]-a[i][p[j-1]];
            st |= pos(p[j]);
        }
    }
    
    for(int i = 1; i <= m; i++)
        for(int j = 0; j < (1<<m); j += 1<<i)
            for(int k = 0; k < pos(i); k++)
                f[j|pos(i)|k] += f[j|k];
    
    ll ans = LLONG_MAX;
    for(int i = 1; i < (1<<m); i++)
        ans = min(ans, g[i]+f[((1<<m)-1)^i]);
    
    print(ans, '\n');
}

前置知识

Description

给定两个长度为 nn 的序列 a,ba,b，求一个 11 到 nn 的排列 cc ，最小化:

∑i=1n⌈max⁡(bi−aci,0)k⌉\sum_{i=1}^{n} \left\lceil \frac{\max(b_i-a_{c_i}, 0)}{k} \right\rceil

Input

第一行两个整数 n,kn, k。

第二行 nn 个整数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n。

第三行 nn 个整数 b1,b2,⋯ ,bnb_1, b_2, \cdots, b_n。

Output

第一行一个整数表示答案。

第二行 nn 个整数 c1,c2,⋯ ,cnc_1, c_2, \cdots, c_n。

若有多组解任意输出一组即可。

Hint

1≤n≤105,1≤ai,bi,k≤1091 \le n \le 10^5, 1 \le a_i,b_i,k \le 10^9

Solution

考虑一个贪心。

首先问题可以看成每次操作把某个 bib_i 减去 kk ，求最少次数使得存在排列 cc 满足 bi≤acib_i \le a_{c_i}。

对比当前 a,ba,b 中最大值，如果 max⁡{a}≥max⁡{b}\max\{a\} \ge \max\{b\}，那么直接把这两个数配成一对即可，否则把 bb 种的最大值减去 kk。

用 map 和 set 加速贪心过程即可，具体就是把 ⌊bik⌋\lfloor \frac{b_i}{k} \rfloor 相同的 bib_i 一起处理，时间复杂度 nlog⁡2nn \log^2 n。

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

typedef long long ll;
const int N = 1e5+10;

struct node {
    int val, id;
};
bool operator < (const node &a, const node &b) {
    return a.val != b.val ? a.val < b.val : a.id < b.id;
}
bool operator > (const node &a, const node &b) {
    return b < a;
}

int n, k;
node a[N]; int ans[N];
map<int, set<node>> mp;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i].val, a[i].id = i;
    for(int i = 1; i <= n; i++)
    {
        int b; cin >> b;
        mp[b/k].insert({b%k, i});
    }
    
    sort(a+1, a+n+1, greater<node>());
    
    ll sum = 0;
    for(int i = 1; i <= n; i++)
    {
        while(!mp.empty())
        {
            int t = mp.rbegin()->first;
            auto& s = mp.rbegin()->second;
            if(s.empty()) { mp.erase(--mp.end()); continue; }
            if(a[i].val >= t*k + s.begin()->val)
            {
                auto p = --s.upper_bound({a[i].val-t*k, INT_MAX});
                ans[p->id] = a[i].id; s.erase(p); break;
            }
            int delta = max(1, t-a[i].val/k);
            sum += delta*s.size();
            auto& ss = mp[t-delta];
            if(s.size() > ss.size()) swap(s, ss);
            ss.insert(s.begin(), s.end());
            mp.erase(--mp.end());
        }
    }
    
    cout << sum << "\n";
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " ";
}