Eous的小站
日记

日记

Sun Dec 08 2024
8 分钟
life 日记
1246 字

上午#

切了一题

CF2027D1 The Endspeaker (Easy Version)#

还是那句话：既然出现在dp专题里，那肯定就是dp咯
我们设 dpk,i,jdp_{k,i,j} 表示在 ak=bi,ja_k = b_{i,j} 时能否获胜。我们发现，正着推好像不大行，那么，正难则反。
我们考虑从 l→1,(i,j)→(1,1)l \rightarrow 1,(i,j) \rightarrow (1,1) ，反着推。那么有明显的转移：dpk,i,j=[(∑x=i+1n∑y=j+1mdpk+1,x,y)=0]dp_{k,i,j} = \left[\left(\sum\limits_{x = i + 1}^{n}\sum\limits_{y = j + 1}^{m}dp_{k + 1,x,y}\right) = 0\right] 。但是，枚举状态就有 O(knm)\mathcal{O}(knm) 的复杂度了，转移还有 O(nm)\mathcal{O}(nm) 。合起来就是 O(kn2m2)\mathcal{O}(kn^2m^2) 。这不给你T飞起来。
我们考虑怎么 O(1)\mathcal{O}(1) 转移。我们发现，(∑x=i+1n∑y=j+1mdpk+1,x,y)\left(\sum\limits_{x = i + 1}^{n}\sum\limits_{y = j + 1}^{m}dp_{k + 1,x,y}\right) 可以用二维后缀和维护。那么最外面的循环枚举 kk （本该如此），然后里面是 O(nm)\mathcal{O}(nm) 的转移，等它转移完了，我们再 O(nm)\mathcal{O}(nm) 维护一下二维后缀和，这样就达到的 O(1)\mathcal{O}(1) 转移的效果，总复杂度 O(knm)\mathcal{O}(knm) ，就可以了。

中午 & 下午#

打了一下午游戏，在打游戏的时候尝试切一道线段树，但是失败了。

晚上#

今天晚上又有 arc 又有 codeforces 的，本来都不想来，但是还是来学校打了。顺便把之前没写完的日记补了。

CF2027D The Endspeaker solution#

我们先来看 easy version 。这一看就很有dp的感觉啊，于是我们就设 dpi,jdp_{i,j} 表示当 k=ik = i ，剩的第一个元素下标为 jj 的时候的最小代价。初始化时 dp1,1=0dp_{1,1} = 0 。然后我们就可以考虑如何转移：

  • 第一种操作时，我们从 jj 开始找到第一个位置 cc 使得 ∑x=jc>bi\sum\limits_{x = j}^{c} > b_i ，然后就可以转移：dpi,c=min⁡(dpi,c,dpi,j+m−i)dp_{i,c} = \min(dp_{i,c},dp_{i,j} + m - i) 。
  • 第二种操作时，有显然的转移：dpi+1,j=min⁡(dpi+1,j,dpi,j)dp_{i + 1,j} = \min(dp_{i + 1,j},dp_{i,j}) 。

然后怎么统计答案呢？我们想：要把 aa 数组去完，那么答案肯定是某个 dpx,n+1dp_{x,n + 1} （ xx 我们还不知道），然后，我们又发现，其实这个 xx 是多少无关紧要，那么我们就有答案：ans=min⁡i=1mdpi,n+1ans = \min\limits_{i = 1}^{m}dp_{i,n + 1} 。

这是 easy version 啊，现在我们来看 easy version 的 hard version （ yzp 名言）
我们看 hard version 它 hard 在哪里。我们看：它不仅让我们求最小的代价是多少，他还让我们求有多少种方案能够达到最小的代价。我们发现，对于 ∀p∈(j+1,c]\forall p \in (j + 1,c] ，都可以从 dpi,jdp_{i,j} 转移：dpi,p=min⁡(dpi,p,dpi,j+m−i)dp_{i,p} = \min(dp_{i,p},dp_{i,j} + m - i) 。在简单版中不这么做是因为答案不会更优还浪费时间复杂度，而现在要统计方案数了，那么就要考虑一下了。而我们看要更新 (j+1,c](j + 1,c] 这个区间，那么我们就想到线段树。
因为实现实在是太美所以就放一下代码：

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/extc++.h>
#define int long long
#define inf 0x7f7f7f7f7f7f7f7f
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
void operator+=(pii &x,pii &y)//这里就类似统计答案
{
    if(x.first != y.first)//如果方案更优就更新方案
    {
        if(x.first > y.first)
            x = y;
    }//这里一定一定要打大括号
    else//如果方案相同就更新方案数
        x.second = (x.second + y.second) % mod;
}
int n,m;
int a[maxn],b[maxn];
int pre[maxn];
struct Rukkhadevata//又好用码量又大的树：大慈树
{
    int l,r;
    pii val;
}tree[maxn << 2];
void push_down(int rt)
{
    if (tree[rt].val.first == inf)
        return;
    tree[rt << 1].val += tree[rt].val;
    tree[rt << 1 | 1].val += tree[rt].val;
    tree[rt].val = mkp(inf,0);
}//lazy下放
//为何直接拿val当lazy:因为不用维护区间查询，所以对于非叶子节点的val没有意义，就拿来当lazy
void build(int l,int r,int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].val = mkp(inf,0);
    if (l == r)
    {
        if (l == 1)
            tree[rt].val = mkp(0,1);
        return;
    }
    int mid = l + r >> 1;
    build(l,mid,rt << 1);
    build(mid + 1,r,rt << 1 | 1);
}
void upd(int ql,int qr,pii x,int rt)
{
    int l = tree[rt].l;
    int r = tree[rt].r;
    if (ql <= l && r <= qr)
    {
        tree[rt].val += x;
        return;
    }
    push_down(rt);
    int mid = l + r >> 1;
    if (ql <= mid)
        upd(ql,qr,x,rt << 1);
    if (qr > mid)
        upd(ql,qr,x,rt << 1 | 1);
}
pii que(int x,int rt)
{
    int l = tree[rt].l;
    int r = tree[rt].r;
    if (l == r)
        return tree[rt].val;
    push_down(rt);
    int mid = l + r >> 1;
    if (x <= mid)
        return que(x,rt << 1);
    else
        return que(x,rt << 1 | 1);
}
void solve()
{
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld",a + i);
        pre[i] = pre[i - 1] + a[i];
    }
    for (int j = 1; j <= m; j++)
        scanf("%lld",b + j);
    build(1,n,1);
    pii ans = mkp(inf,0);
    for (int j = 1; j <= m; j++)
    {
        pii tmp1 = mkp(inf,0);
        for (int i = 1; i <= n; i++)
        {
            int pos = upper_bound(pre + i,pre + n + 1,b[j] + pre[i - 1]) - pre;//找到c
            if (i < pos)
            {
                pii tmp2 = que(i,1);
                tmp2.first += m - j;
                if (pos == n + 1)
                {
                    tmp1 += tmp2;
                    pos --;
                }
                if (i < pos)
                    upd(i + 1,pos,tmp2,1);//转移
            }
        }
        ans += tmp1;//记录答案
    }
    if (ans.first != inf)
        printf("%lld %lld\n",ans.first,ans.second);
    else
        puts("-1");
}
signed main()
{
    int t;
    scanf("%lld",&t);
    while (t--)
        solve();
    return 0;
}