Skip to content

AGC007 做题记录

A

结论题，棋子只向下或右移动并且到达右下角当且仅当 '#' 字的数量是 \(H+W-1\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
char a[10][10];
int main(){
    int h=read(),w=read(),cnt=0;
    rep(i,1,h){
        scanf("%s",a[i]+1);
        rep(j,1,w)cnt+=(a[i][j]=='#');
    }
    puts(cnt==h+w-1?"Possible":"Impossible");
    return 0;
}

B

构造题。先思考如何让 \(a_{p_i}+b_{p_i}\) 为定值，考虑到递增和递减的性质，不难发现 \(a_i=i,b_i=n-i\) 即满足要求。

下面让 \(a_{p_i}+b_{p_i}\) 递增即可，把 \(b_{p_i}\) 加上 \(i\) 就行了，但这会破坏我们 \(b_i\) 的递增性质。注意到两个数组同时乘以一个大数 \(k\) 后仍满足原性质，所以可以设 \(a_i=ki,b_i=k(n-i)\) 再把 \(b_{p_i}\) 加上 \(i\) 即可。只要 \(k\ge n\) 即满足要求，且 \(a_i,b_i\le 10^9\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e4+5;
int a[N],b[N],n,p;
int main(){
    n=read();
    rep(i,1,n)a[i]=i*N,b[i]=(n-i)*N;
    rep(i,1,n)p=read(),b[p]+=i;
    rep(i,1,n)printf("%d ",a[i]);
    puts("");
    rep(i,1,n)printf("%d ",b[i]);
    return 0;
}

C

神仙题。

每次滚完少一个球一个坑，留下的会是 \(n-1\) 个球 \(n\) 个坑的情况，不妨考虑新序列的期望长度和原序列的关系。我们枚举第一个球的所有可能性，计算新的距离序列的期望值。观察发现仍然是一个等差数列！很多题解都提到了这一点，这里提供一种证明方法：

一共有 \(2n\) 种滚球的可能，考虑对第 \(i\) 段距离，有哪些情况能对其期望长度的增加产生贡献：

  • 原来的前 \(i\) 段距离被滚过（也就是第 \(i\) 段距离之前的球滚完了），使原第 \(i+2\) 段距离代替了第 \(i\) 段。
  • 原来的第 \(i+1\) 段距离被滚过，使原第 \(i,i+2,i+3\) 段代替了第 \(i\) 段。

设新的距离序列为 \(d'_i\) ，那么有： 这构成一个新的等差数列，而对每个 \(d,x\) 我们推一次球的期望距离为数列的中位数，递推到最后即可。

时间复杂度：\(O(n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
int main(){
    int n;double d,x,ans=0;
    scanf("%d%lf%lf",&n,&d,&x);
    while(n){
        ans+=d+x*(2*n-1)/2;
        double dd=d+(2*d+5*x)/(2*n),xx=x+2*x/n;
        d=dd,x=xx;n--;
    }
    printf("%.10lf\n",ans);
    return 0;
}

D

首先观察到 Shik 行走的路线可以被表示成往数轴正方向和反方向的运动以及原地等候，且最终运动到终点。到关键点有两个原因：

  • 第一次到达，开始生成金币。
  • 第二次到达，捡金币。

注意到折返和前进显然都要到一个关键点，否则没有意义。不妨设从当前位置 \(pos\) 点折返最远到 \(i\) 号点再前进，如果能在 \(i\) 号点拿到金币，那么 \(i+1,i+2,\dots,pos\) 等节点此时必然也生成了金币。这说明每次折返都会拿到这段区间的金币。下面设 \(f_i\) 为捡到了前 \(i\) 个点的金币时花费的最小时间，显然当时在 \(i\) 号点。从 \(f_j\) 转移时，需要先走一段 \(x_i-x_j\) 的距离，再取往返时间和 \(i\) 号金币出现的时间的最大值，我们有： 提取 \(x_i-x_j\) 项到括号外面，发现求和后为 \(x_n\) 。考虑如何优化括号内的求值，

  • \(2(x_i-x_{j+1})\le T\Longrightarrow f_i=\min_j\{f_j\}\)
  • \(2(x_i-x_{j+1})>T\Longrightarrow f_i=2x_i+\min_j\{f_j-2x_{j+1}\}\)

由于 \(x_i-x_{j+1}\) 随 \(j\) 单调递减，这可以用单调队列优化到 \(O(n)\) 。

时间复杂度：\(O(n)\)

 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
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5;
int q[N],h,t;
ll n,E,T,x[N],f[N],minn=1e18;
int main(){
    n=read(),E=read(),T=read();
    rep(i,1,n)x[i]=read();
    f[0]=0;
    rep(i,1,n){
        while(h<=t&&2*(x[i]-x[q[h]+1])>T){
            minn=min(minn,f[q[h]]-2*x[q[h]+1]);
            ++h;
        }
        f[i]=min(f[q[h]]+T,minn+2*x[i]);
        q[++t]=i;
    }
    printf("%lld\n",f[n]+E);
    return 0;
}

E

神仙树形dp。

要求最小化所有路径权值的最大值，这显然想到二分。下面考虑对于最大权值 \(V\) 如何计算是否有可行解，由题意得每个子树都要走完才能去另一个子树，于是可以想到这样的 \(dp\) ：

设 \(f_u(a,b)\) 为在 \(u\) 子树内存在满足条件的构造，且根到第一个叶子和最后一个叶子的距离分别为 \(a,b\) 。可以理解 \(f_u\) 为子树 \(u\) 中所有可行解的解集。记 \(u\) 的左右儿子为 \(l,r\) ，那么转移就是： 暴力合并左右儿子的状态时间复杂度超标，考虑优化。我们可以贪心地筛选集合内的元素，也就是如果有 \(a_1\le a_2,b_1\le b_2\) 那么 \((a_1,b_1)\) 显然更优，可以排序后筛掉形如 \((a_2,b_2)\) 的元素。于是剩下的元素满足 \(a\) 升序排列，\(b\) 降序排列，于是在合并时可以使用 \(two-pointers\) 优化。注意到每次合并增加的状态数为 \(2\times\min(|f_l|,|f_r|)\) ，不难发现总状态数是 \(O(n\log n)\) 的，可以通过本题。

时间复杂度：\(O(n\log^2 n)\) 

 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
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,ch[N][2];
ll w[N][2];
vector <pii> Ans[N];
void dfs(int u,ll V){
    Ans[u].clear();
    if(!ch[u][0]){
        Ans[u].pb({0,0});
        return;
    }
    rep(i,0,1)if(ch[u][i])dfs(ch[u][i],V);
    vector <pii> vec;
    rep(t,0,1){
        int ls=ch[u][t],rs=ch[u][t^1];
        ll Max=V-w[u][0]-w[u][1];
        for(int i=0,j=0;i<Ans[ls].size();++i){
            while(j+1<Ans[rs].size()&&Ans[rs][j+1].fi+Ans[ls][i].se<=Max) ++j;
            if(j>=Ans[rs].size()||Ans[rs][j].fi+Ans[ls][i].se>Max) continue;
            vec.pb({Ans[ls][i].fi+w[u][t],Ans[rs][j].se+w[u][t^1]});
        }
    }
    sort(vec.begin(),vec.end());
    rep(i,0,(int)vec.size()-1){
        if(!Ans[u].empty()&&Ans[u].back().se<=vec[i].se)continue;
        Ans[u].pb(vec[i]);
    }
}
inline bool check(ll mid){
    dfs(1,mid);
    return Ans[1].size()>=1;
}
int main(){
    n=read();
    ll l=0,r=0,ans;
    rep(i,2,n){
        int fa=read(),val=read();
        r+=val;
        if(ch[fa][0])ch[fa][1]=i,w[fa][1]=val;
        else ch[fa][0]=i,w[fa][0]=val;
    }
    while(l<=r){
        ll mid=(l+r)/2;
        if(check(mid)){
            r=mid-1;ans=mid;
        }else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

F

设最少变换 \(m-1\) 次，把这 \(m-1\) 次的串与初始串从上至下放在一起成一个 \(n\times m\) 的方阵。由题意得 \(S_{i,j}=S_{i-1,j}\) 或 \(S_{i,j}=S_{i,j-1}\) ，即当前位置从上面或左边一格转移而来，观察原串 \(n\) 个字符转移的路径会在方阵里成多条折线，如下图。

不难发现每条折线尽量靠右最优，因为这样可以让该折线不影响前面的线，以及使原串还可以引出折线的字母尽量多。如果当前行画不下就加一行，下面考虑如何维护这样的贪心。如果有 \(S_0=T\) 直接输出 \(0\) 。

首先找出 \(T\) 最长的由相同字符 \(c\) 组成的后缀，在 \(S\) 中找到剩余字符中最右的 \(c\) ，记这两个位置为 \(S_i,T_j\) 。可以用队列维护所有拐点：先把所有横坐标在 \(j\) 后面的点出队，由贪心策略得剩下的拐点往左下移动一格。由于拐点不出现在 \(T\) 串，答案则是最下面的拐点的纵坐标 \(+1\) 。

时间复杂度：\(O(n)\)

 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
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e6+5;
int n,ans,m;
char S[N],T[N];
bool flg;
queue <int> q;
int main(){
    n=read();scanf("%s%s",S+1,T+1);
    rep(i,1,n)if(S[i]!=T[i])flg=1;
    if(!flg)return puts("0"),0;
    int m=n;
    while(m){
        while(m>1&&T[m]==T[m-1])m--;
        while(n&&(n>m||S[n]!=T[m]))--n;
        if(!n)return puts("-1"),0;
        while(!q.empty()&&q.front()-q.size()>=m)q.pop();
        if(n!=m)q.push(n);
        ans=max(ans,(int)q.size()+1);
        --m;
    }
    printf("%d\n",ans);
    return 0;
}

Comments