Educational Codeforces Round 109 (Rated for Div. 2)C. Robot Collisions D. Armchairs题解

先说D
本来打算找一道前缀和优化$dp$的例题的，一直找不好简单的太简单，难的太难。今天打开$div$，哟吼，这例题不就来了。
题目的意思是有$n$个座位$m$个人$（m<n/2）$坐在一些位置上，现在要求原来这些坐着人的位置都空出来，让这些人坐在其他座位上，问移动距离总和的最小值。
这题的状态就很肌肉记忆了，$dp[i][j]$表示第i个人坐到第j个原来空着的位置，并且前i个人完全匹配的最小移动距离。
我们来考虑转移
$$dp[i][j]=mi{n}_{k=1,2,..,j-1}(dp[i-1][k])+abs(dis1[i]-dis0[j])$$
我们想到了一个O(n^3)的dp，然后我们发现$mi{n}_{k=1,2,..,j-1}(dp[i-1][k])$
是可以$O(n)$预处理的，那么这个$dp$就被优化掉了一维，变成了$O(n^2)$，我们就美美的A掉了D题。

    #include<bits/stdc++.h>
    using namespace std;
    int cnt1=0,cnt0=0;
    int dis1[5005],dis0[5005];
    int dp[5005][5005];
    int minn[5005];
    int main()
    {
        int n;
        scanf("%d",&n);
     
        for(int i=1;i<=n;i++)
        {
            int t;
            scanf("%d",&t);
            if(t==1)dis1[++cnt1]=i;
            if(t==0)dis0[++cnt0]=i;
        }
        for(int i=0;i<=cnt1;i++)
        for(int j=0;j<=cnt0;j++)
        dp[i][j]=1e9;
     
     
        for(int i=1;i<=cnt0;i++)dp[1][i]=abs(dis1[1]-dis0[i]);
        for(int j=0;j<=cnt0;j++)minn[j]=1e9;
        for(int j=1;j<=cnt0;j++)minn[j]=min(minn[j-1],dp[1][j]);
     
        for(int i=2;i<=cnt1;i++)
        {
     
            for(int j=i;j<=cnt0;j++)if(minn[j-1]!=1e9)dp[i][j]=minn[j-1]+abs(dis1[i]-dis0[j]);
            for(int j=0;j<=cnt0;j++)minn[j]=1e9;
            for(int j=1;j<=cnt0;j++)minn[j]=min(minn[j-1],dp[i][j]);
     
        }
     
        int minn=1e9;
     
        if(cnt1==0)printf("0\n");
        else
        {
            for(int i=1;i<=cnt0;i++)
            {
                minn=min(minn,dp[cnt1][i]);
     
            }
     
            printf("%d\n",minn);
        }
        return 0;
    }
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

再说C
C就类似蚂蚁走路的问题，走到两个边界会反弹，两只蚂蚁在整点碰撞会死，求每只蚂蚁死的时间。
首先有一个小结论，两只蚂蚁会在整点碰撞当且仅当它们的奇偶性相同。
所以我们可以把奇数位置的蚂蚁和偶数位置的蚂蚁分开来看。
我们从数轴从左往右看，我们知道最左边的
$<-<-$
他们肯定是和彼此相撞的，我们可以把他们去掉
所以最左边就变成了这样
$->$
或者这样$<-->$
然后我们发现如果有两只相邻的蚂蚁是相向而行的，他们肯定和彼此相撞，所以我们就用一个单调栈来维护这种关系，如果栈顶和我都是左，那么消掉，如果都是右，那么入栈，如果相向，那么消掉。这样就得到了一个单调的栈，然后我们再反向进行一次操作，就做完了，这题思维上面其实我觉得只有1500分，所以放在C也无可厚非，但是出题人可能高估了大家的代码能力，所以导致C过得太少了。

    #include<bits/stdc++.h>
    using namespace std;
    struct edge
    {
        int id,dis,dir;
        bool operator < (const edge &ths)const
        {
            return dis<ths.dis;
        };
    }a[300005];
    stack<edge>q0,q1;
    int ans[300005];
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n,m;
            while(!q0.empty())q0.pop();
            while(!q1.empty())q1.pop();
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i].dis);
                a[i].id=i;
            }
            for(int i=1;i<=n;i++)
            {
                char c[2];
                scanf("%s",c);
                if(c[0]=='L')a[i].dir=1;
                if(c[0]=='R')a[i].dir=0;
            }
     
            sort(a+1,a+1+n);
            memset(ans,-1,sizeof(ans));
     
            for(int i=1;i<=n;i++)
            {
                if(a[i].dis%2==0)
                {
                    if(q0.empty())q0.push(a[i]);
                    else
                    {
                        edge p=q0.top();
                        if(p.dir==1&&a[i].dir==1)
                        {
                            q0.pop();
                            ans[p.id]=p.dis+abs(p.dis-a[i].dis)/2;
                            ans[a[i].id]=ans[p.id];
                        }
                        else if(p.dir==0&&a[i].dir==1)
                        {
                            q0.pop();
                            ans[p.id]=abs(p.dis-a[i].dis)/2;
                            ans[a[i].id]=ans[p.id];
                        }
                        else
                        {
                            q0.push(a[i]);
                        }
                    }
                }
                if(a[i].dis%2==1)
                {
                    if(q1.empty())q1.push(a[i]);
                    else
                    {
                        edge p=q1.top();
                        if(p.dir==1&&a[i].dir==1)
                        {
                            q1.pop();
                            ans[p.id]=p.dis+abs(p.dis-a[i].dis)/2;
                            ans[a[i].id]=ans[p.id];
                        }
                        else if(p.dir==0&&a[i].dir==1)
                        {
                            q1.pop();
                            ans[p.id]=abs(p.dis-a[i].dis)/2;
                            ans[a[i].id]=ans[p.id];
                        }
                        else
                        {
                            q1.push(a[i]);
                        }
                    }
                }
    //            printf("1\n");
            }
            while(q0.size()>=2)
            {
                edge p2=q0.top();
                q0.pop();
                edge p1=q0.top();
                q0.pop();
    //            printf("p1 %d p2 %d %d %d\n\n",p1.dis,p2.dis,p1.dir,p2.dir);
                if(p1.dir==0&&p2.dir==0)
                {
                    ans[p1.id]=(m-p2.dis)+abs(p1.dis-p2.dis)/2;
                    ans[p2.id]=ans[p1.id];
                }
                else if(p1.dir==1&&p2.dir==0)
                {
                    ans[p1.id]=((m-p2.dis)+p1.dis+m)/2;
                    ans[p2.id]=ans[p1.id];
                }
            }
     
            while(q1.size()>=2)
            {
                edge p2=q1.top();
                q1.pop();
                edge p1=q1.top();
                q1.pop();
    //            printf("p1 %d p2 %d %d %d\n\n",p1.dis,p2.dis,p1.dir,p2.dir);
                if(p1.dir==0&&p2.dir==0)
                {
                    ans[p1.id]=(m-p2.dis)+abs(p1.dis-p2.dis)/2;
                    ans[p2.id]=ans[p1.id];
                }
                else if(p1.dir==1&&p2.dir==0)
                {
                    ans[p1.id]=((m-p2.dis)+p1.dis+m)/2;
                    ans[p2.id]=ans[p1.id];
                }
            }
            for(int i=1;i<=n;i++)printf("%d ",ans[i]);
            printf("\n");
     
        }
        return 0;
    }
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