Liveddd's Blog

愛にできることはまだあるかい

The 2024 ICPC Asia Shenyang Regional Contest

发表于 更新于 分类于
本文字数： 16k 阅读时长 ≈ 35 分钟

唉，状态太差了，被打爆了。

A. Safety First

很棒的根号分治 DP，应该意识到的。

考虑一种 DP，设计 $f(i,j)$ 表示当前有 $i$ 个，总高度为 $j$，当前长度为 $k$，枚举前一个长度 $l$。状态转移方程为：

用前缀和优化即可做到 $\mathcal O(nm^2)$。但我们更好的实现方法是直接每次先从大到小枚举是否加入长度为 $l$ 的梯子，这样的话状态就只有 $\mathcal O(nm)$ （但是时间复杂度并没有什么区别）。

想到就没希望了，毕竟状态数就是 $\mathcal O(nm^2)$ 的了。$\sum a_i =k$ 一定的题目，给人一种相当熟悉的预感：显然，产生贡献的大于 $\sqrt m$ 的段数小于 $\sqrt{m}$ 个。但是我们发现单纯沿用上面的 DP 没法很好地利用这一点，因为我们没有记录当前是否对总长度产生贡献。

对于这种类型我们容易想到了另外一种 DP，设计 $f(i,j,k)$ 表示考虑当前有 $i$ 个，能够产生贡献的有 $j$ 个，当前总高度为 $k$，考虑两种转移：1. 新加一个；2. 把前面的全部 +1。

仔细观察两种算法的利弊，我们考虑把二者结合起来。对于前 $\ge\sqrt {m}$ 段，我们使用算法二，每次都加入长度 $\sqrt{m}$ 的产生贡献的段（而非 $1$），时间复杂度为 $\mathcal O(nm\sqrt{m})$；对于剩下的$\le \sqrt{m}$ 段，我们使用算法一，所以时间复杂度也为 $\mathcal O(nm\sqrt{m})$。

Code
 
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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e3+10,M=50,mod=998244353;
template<class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n=2000,m=2000,B=46;
int f[N][N],g[N][N];

inline void adj(int &x){x+=x>>31&mod;}
inline void solve()
{
    read(n,m);
    printf("%d\n",g[n][m]);
}
int main()  
{
    f[0][0]=g[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=B;j;j--)
            for(int k=m;k>=B;k--)
                adj(f[j][k]+=f[j-1][k-B]-mod);
        f[0][0]=0;
        for(int j=1;j<=B;j++)
            for(int k=j;k<=m;k++)
                adj(f[j][k]+=f[j][k-j]-mod);
        for(int j=1;j<=B;j++)
            for(int k=1;k<=m;k++)
                adj(g[i][k]+=f[j][k]-mod);
    }
    for(int i=B-1;i;i--)
        for(int j=1;j<=n;j++)
        {
            for(int k=i;k<=m;k++)
                adj(g[j][k]+=g[j-1][k-i]-mod);
            if(j>1)
                for(int k=1;k<=m;k++)
                    adj(g[j][k]+=g[j-1][k]-mod);
        }
    int T;
    read(T);
    while(T--)solve();
    return 0;
}

B. Magical Palette

神秘智慧构造，被打爆了。需要一点思考。

I. Growing Tree

其实也并没有很难。

显然对于越浅的边，限制越小。我们于是尝试从深到浅进行考虑。容易发现，只要我们对一条边进行处理，那么这条边下面的子树看可以和其他部分不存在相同（因为可以加上一个任意的数），相当于去掉该边，得到两个互不相同的两部分。

对于节点 $x$，若它的两棵子树之间存在相同的（考虑子树内部相同的已经被处理掉了），那么我们需要决定更改两条边中的哪一条。这个不好考虑，于是直接尝试爆搜，分别搜更改两条边的情况。因为最多操作 $n$ 次，故状态数为 $\mathcal O(2^n)$，而每次采用归并的方式合并子树并找相同的，这一部分每一次总的复杂度为 $\mathcal O(n2^n)$，所以最终复杂度为 $\mathcal O(n4^n)$。

Code
 
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
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;
const int N=11,M=(1<<N+1)+10;
template<class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T,n;
int ans;
int d[M],Log[M];
vector<int>v[M];

void dfs(int x,int res)
{
    if(res>=ans)return ;
    if(!x)return ans=res,void();
    v[x].clear();
    if(x>=(1<<(n-1)))return v[x].push_back(d[x]),dfs(x-1,res);
    bool flag=0;
    auto i=v[x<<1].begin(),j=v[x<<1|1].begin();
    while(i!=v[x<<1].end()&&j!=v[x<<1|1].end())
    {
        if(*i<*j)v[x].push_back(*i),i++;
        else if(*i>*j)v[x].push_back(*j),j++;
        else
        {
            flag=1;
            break;
        }
    }
    if(flag)
    {
        if(res+1>=n-Log[x])return;
        v[x]=v[x<<1],dfs(x-1,res+1);
        v[x]=v[x<<1|1],dfs(x-1,res+1);
    }
    else
    {
        while(i!=v[x<<1].end())v[x].push_back(*i),i++;
        while(j!=v[x<<1|1].end())v[x].push_back(*j),j++;
        dfs(x-1,res);
    }
}
void solve()
{
    read(n);
    n++;
    for(int i=2;i<(1<<n);i++)read(d[i]),d[i]+=d[i>>1],Log[i]=Log[i>>1]+1;
    ans=n+1;
    dfs((1<<n)-1,0);
    if(ans>n)puts("-1");
    else printf("%d\n",ans);
}

int main()
{
    read(T);
    while(T--)solve();
    return 0;
}

D. Dot Product Game

容易转化为逆序对相关的问题，不说了。

E. Light Up the Grid

小水题，但是犯唐看错题了。

考虑按照什么样的顺序操作这 $m$ 个矩阵，但注意到 $m\le 16$（因为一共只有 $16$ 种矩阵状态），我们是可以直接状压 DP 的。不过我们需要提前预处理可能的操作的花费，在最短路上跑就行了。然后状压 $16$ 种状态已经达成了哪些，DP 预处理出，时间复杂度为 $\mathcal O(m^22^m)$。最后直接输出答案即可。

Code
 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long 
using namespace std;
const int N=16,M=(1<<N)+10,INF=1e9;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T;
int c[4];
int trans[9],e[9];
int dis[N];
bool vis[N];
int f[N][M],ans[M];
struct Node
{
    int id,d;
    bool operator<(const Node &t)const{return d>t.d;}
};
void Dijkstra()
{
    priority_queue<Node>q;
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    q.push({0,0});
    while(!q.empty())
    {
        int x=q.top().id;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=0;i<9;i++)
        {
            int y=x^trans[i];
            if(dis[y]>dis[x]+e[i])
            {
                dis[y]=dis[x]+e[i];
                q.push({y,dis[y]});
            }
        }
        if(x==0)dis[0]=INF;
    }
}
void solve()
{
    int n,sta=0;
    read(n);
    for(int i=0;i<n;i++)
    {
        int now=0;
        for(int j=0,x;j<4;j++)
        {
            scanf("%1d",&x);
            now=now<<1|(x^1);
        }
        sta|=1<<now;
    }
    printf("%d\n",ans[sta]);
}

int main()
{
    read(T);
    for(int i=0;i<4;i++)read(c[i]);
    for(int i=0;i<4;i++)trans[i]=1<<i,e[i]=c[0];
    trans[4]=3,e[4]=c[1];//0011
    trans[5]=12,e[5]=c[1];//1100
    trans[6]=5,e[6]=c[2];//0101
    trans[7]=10,e[7]=c[2];//1010
    trans[8]=15,e[8]=c[3];//1111
    Dijkstra();

    int n=16,all=1<<n;
    for(int i=0;i<n;i++)for(int sta=0;sta<all;sta++)f[i][sta]=INF;
    for(int i=0;i<n;i++)f[i][1<<i]=dis[i];
    for(int sta=1;sta<all;sta++)
    {
        vector<int>x,y;
        for(int i=0;i<n;i++)
            if(sta>>i&1)x.push_back(i);
            else y.push_back(i);
        for(auto i:x)
            for(auto j:y)
            {
                int now=sta^(1<<j);
                f[j][now]=min(f[j][now],f[i][sta]+dis[i^j]);
            }
    }
    for(int sta=1;sta<all;sta++)
    {
        ans[sta]=INF;
        for(int i=0;i<n;i++)ans[sta]=min(ans[sta],f[i][sta]);
    }
    while(T--)solve();
    return 0;
}

G. Guess the Polygon

噢谢，还是很简单的交互。

设 $f(x)$ 为横坐标为 $x$ 对应的长度，相当与询问 $(x,f(x))$，求出 $\int f(x)$。容易发现 $f(x)$ 是一个线性并且按照每个顶点横坐标分段的函数。

容易发现，如果顶点横坐标 $x$ 互不相同，那么 $f(x)$ 显然是连续的； 否则 $f(x)$ 就可能存在断点。于是我们分两种情况讨论：

  1. 横坐标 $x$ 互不相同，因为 $f(x)$ 为连续的 $x-1$ 段函数，所以直接询问 $n-2$ 个断点即可。
  2. 存在横坐标 $x$ 相同，那么 $f(x)$ 最多有 $x-2$ 段，所以直接询问 $n-2$ 段的中点即可。

时间复杂度瓶颈为排序的 $\mathcal O(n\log n)$。

但需要注意的是对于分数的处理。注意到交互器返回的分数可能很大。一个处理方式是：对其去模，并将除法转为逆元，我们选取大于 $2\times 10^6$ 的质数作为模数：因为注意到面积的二倍一定是整数，其余乘上的分母一定会消掉。另一种是直接使用了 long double，据说精度也是够用的。

Code
 
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=1e3+10,mod=998244353;
inline void adj(int &x){x+=x>>31&mod;}
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=((x<<1)+(x<<3)+(ch^48))%mod,ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int gcd(int x,int y)
{
    if(x>y)swap(x,y);
    if(x==0)return y;
    return gcd(y%x,x);
}
int T,n;
int a[N];
int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
int query(int p,int q)
{
    int g=gcd(p,q);
    printf("? %d %d\n",p/=g,q/=g);
    fflush(stdout);
    ll x,y;
    read(x,y);
    return 1ll*x*qpow(y)%mod;
}
void solve()
{
    read(n);
    for(int i=1,y;i<=n;i++)read(a[i],y);
    sort(a+1,a+1+n);
    int tot=unique(a+1,a+1+n)-a-1;
    int ans=0,res=0;
    if(tot==n)
    {
        for(int i=2;i<n;i++)
        {
            int now=query(a[i],1);
            adj(ans+=1ll*(res+now)*(a[i]-a[i-1])%mod-mod);
            res=now;
        }
        adj(ans+=1ll*res*(a[n]-a[n-1])%mod-mod);
    }
    else
    {
        n=tot;
        for(int i=2;i<=n;i++)adj(ans+=2ll*query(a[i]+a[i-1],2)*(a[i]-a[i-1])%mod-mod);
    }
    if(ans&1)printf("! %d 2\n",ans);
    else printf("! %d 1\n",ans>>1);
    fflush(stdout);
}
int main()
{
    read(T);
    while(T--)solve();
    return 0;
}

H. Guide Map

出的挺不错的一题。

考虑初始的两棵树为 $T_1,T_2$（设 $T_1$ 为根）。容易发现，在 dfs 树上横叉边是不允许存在的。容易想到将 $T_1,T_2$ 分别求出可以随便选的边，再乘起来即可得到答案。

对于有根的 $T_1$，我们直接用树状数组进行统计即可。注意还有考虑每个点加上 $T_2$ 作为子树的贡献，统计一下即可。

但是对于 $T_2$，我们对所有点作为根求一遍。考虑换根，我们在 $x$ 上记录其对父亲的贡献就行了。时间复杂度为 $\mathcal O(n\log n)$。

注意特判 $|T_2|=1$ 的情况。

Code
 
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<iostream>
#include<cstdio>
#define lowbit(x) (x&(-x))
using namespace std;
using ll=long long;
const int N=2e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n; 
int tot,head[N],ver[N<<1],ne[N<<1];
bool vis[N];
int suf[N];
ll s;
int lans,rans;

struct BIT
{
    int n,c[N];
    void clear()
    {
        for(int i=1;i<=n;i++)c[i]=0;
    }
    void add(int x,int k)
    {
        for(;x<=n;x+=lowbit(x))c[x]+=k;
    }
    int ask(int x)
    {
        int res=0;
        for(;x;x-=lowbit(x))res+=c[x];
        return res;
    }
    int query(int l,int r)
    {
        return ask(r)-ask(l-1);
    }
}T;

inline void adj(int &x){x+=x>>31&mod;}
inline int qpow(int x,ll k)
{
    int res=1;
    k%=mod-1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
//part1
void dfs1(int x,int fa)
{
    if(fa)s-=T.query(x+1,n);
    vis[x]=1;
    T.add(x,1);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs1(y,x);
    }
    if(fa)s+=T.query(x+1,n);
}
void dfs2(int x,int fa,int cnt)
{
    if(fa)cnt+=suf[x];
    adj(lans+=qpow(2,s+cnt)-mod);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs2(y,x,cnt);
    }
}
//part2
int f[N],g[N];
void dfs3(int x,int fa)
{
    f[x]-=T.query(x+1,n);
    T.add(x,1);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        g[y]-=T.query(x+1,n);
        dfs3(y,x);
        g[y]+=T.query(x+1,n);
    }
    f[x]+=T.query(x+1,n);
    s+=f[x];
}
void dfs4(int x,int fa)
{
    if(fa)s+=suf[x+1]-f[x];
    adj(rans+=qpow(2,s)-mod);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        s-=g[y];
        dfs4(y,x);
        s+=g[y];
    }
    if(fa)s-=suf[x+1]-f[x];
}
int main()
{
    read(n);
    for(int i=1,u,v;i<=n-2;i++)read(u,v),add(u,v),add(v,u);
    T.n=n;
    dfs1(1,0);
    int rt;
    for(int i=n;i;i--)
    {
        suf[i]=suf[i+1];
        if(!vis[i])rt=i,suf[i]++;
    }
    if(suf[1]==1)lans=qpow(2,s);
    dfs2(1,0,0);
    s=0,T.clear();
    dfs3(rt,0);
    dfs4(rt,0);
    printf("%d\n",1ll*lans*rans%mod);
    return 0;
}

M. Obliviate, Then Reincarnate

尼玛这题这么简单，我赛时到底在干嘛？？？

考虑转化为图，对于每个 $x\pmod n$ 的类建一个点。对于搬迁指令 $(a,b)$ 建边 $(a\pmod n,(a+b)\pmod n,b)$。容易发现能够抵达无穷个的条件是能够走到一个环上。那么很容易想到用 Tarjan 求出强连通分量后缩点得到 DAG，在拓扑序上求出即可。但注意到 我们需要保证走一遍之后 $x$ 的值发生变化（也就是环上的权值和不为 $0$）。时间复杂度为 $\mathcal O(n+m+q)$。

Code
 
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
#include<iostream>
#include<cstdio>
using namespace std;
using ll=long long;
const int N=5e5+10,M=5e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,q;
int tot,head[N],ver[M],e[M],ne[M];
ll d[N];
int dfncnt,dfn[N],low[N];
int top,sta[N];
bool vis[N],ans[N];

int id(int x){return (x%n+n)%n;}
inline void add(int u,int v,int w)
{
    ver[++tot]=v;
    e[tot]=w;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x)
{
    dfn[x]=low[x]=++dfncnt;
    sta[++top]=x,vis[x]=1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i],z=e[i];
        if(!dfn[y])
        {
            d[y]=d[x]+z;
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y])
        {
            if(d[x]+z!=d[y])ans[x]=1;
            low[x]=min(low[x],dfn[y]);
        }
        ans[x]|=ans[y];
    }
    if(dfn[x]==low[x])
    {
        int y;
        do
        {
            y=sta[top--],vis[y]=0;
            ans[y]=ans[x];
        }while(x!=y);
    }
}
int main()
{
    read(n,m,q);
    for(int i=1,a,b;i<=m;i++)read(a,b),add(id(a),id(a+b),b);
    for(int i=0;i<n;i++)if(!dfn[i])dfs(i);
    for(int x;q;q--)read(x),puts(ans[id(x)]?"Yes":"No");
    return 0;
}