AtCoder Beginner Contest 245 A~E 题解

[A - Good morning](https://atcoder.jp/contests/abc245/tasks/abc245_a)

题目大意输入格式输出格式样例分析代码 [B - Mex](https://atcoder.jp/contests/abc245/tasks/abc245_b)

题目大意输入格式输出格式样例分析代码 [C - Choose Elements](https://atcoder.jp/contests/abc245/tasks/abc245_c)

题目大意输入格式输出格式样例分析代码 [D - Polynomial division](https://atcoder.jp/contests/abc245/tasks/abc245_d)

题目大意输入格式输出格式样例分析代码 [E - Wrapping Chocolate](https://atcoder.jp/contests/abc245/tasks/abc245_e)

题目大意输入格式输出格式分析代码

在同一天里，Takahashi在 A A A时 B B B分起床，Aoki在 C C C时 D D D分 1 1 1秒起床，请问谁起床更早？

0 ≤ A , C < 24 0le A,C<24 0≤A,C<24
0 ≤ B , D < 60 0le B,D<60 0≤B,D<60

A   B   C   D A~B~C~D A B C D

输出起得更早的人的名字（Takahashi或Aoki）。

思路很明显，直接判断 ( A , B ) ≤ ( C , D ) (A,B)le(C,D) (A,B)≤(C,D)是否成立即可。

#include 
using namespace std;

int main()
{
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	puts((a == c? b <= d: a < c)? "Takahashi": "Aoki");
	return 0;
}

给定整数序列 A = ( A 1 , … , A N ) A=(A_1,dots,A_N) A=(A1​,…,AN​)。求最小的不在 A A A中的自然数。

1 ≤ N ≤ 2000 1le Nle 2000 1≤N≤2000
0 ≤ A i ≤ 2000 0le A_ile 2000 0≤Ai​≤2000

N N N
A 1   …   A N A_1~dots~A_N A1​ … AN​

输出一行，即最小的不在 A A A中的自然数。

略，请自行前往AtCoder查看

由于题面中有限制 0 ≤ A i ≤ 2000 0le A_ile 2000 0≤Ai​≤2000，所以我们直接开一个数组记录 [ 0 , 2001 ] [0,2001] [0,2001]中每个数是否出现过即可。
本题方法很多，这里介绍的是最快的算法，时间复杂度 O ( N ) mathcal O(N) O(N)。

#include 
using namespace std;

bool used[2005];

int main()
{
	int n;
	scanf("%d", &n);
	while(n--)
	{
		int a;
		scanf("%d", &a);
		used[a] = true;
	}
	int i = -1;
	while(used[++i]);
	printf("%dn", i);
	return 0;
}

给定两个长度为 N N N的整数序列 A = ( A 1 , … , A N ) A=(A_1,dots,A_N) A=(A1​,…,AN​)和 B = ( B 1 , … , B N ) B=(B_1,dots,B_N) B=(B1​,…,BN​)。
问是否存在序列 X = ( X 1 , … , X N ) X=(X_1,dots,X_N) X=(X1​,…,XN​)，满足如下条件：

X i = A i X_i=A_i Xi​=Ai​或 X i = B i X_i=B_i Xi​=Bi​ ∣ X i − X i + 1 ∣ ≤ K |X_i-X_{i+1}|le K ∣Xi​−Xi+1​∣≤K，其中 1 ≤ i < N 1le i 1 ≤ N ≤ 2 × 1 0 5 1le Nle 2times 10^5 1≤N≤2×105
1 ≤ K ≤ 1 0 9 1le Kle 10^9 1≤K≤109
1 ≤ A i , B i ≤ 1 0 9 1le A_i,B_ile 10^9 1≤Ai​,Bi​≤109

N   K N~K N K
A 1   …   A N A_1~dots~A_N A1​ … AN​
B 1   …   B N B_1~dots~B_N B1​ … BN​

如果存在符合全部条件的 X X X，输出Yes；否则，输出No。

略，请自行前往AtCoder查看

好家伙，C题都要用dp……
本题普通的方法貌似不太好做，因此我们考虑 DP text{DP} DP。
令 f ( i ) = X i f(i)=X_i f(i)=Xi​选择能否等于 A i A_i Ai​， g ( i ) = X i g(i)=X_i g(i)=Xi​能否等于 B i B_i Bi​。
然后状态转移方程就简单了，详见代码。

#include 
#define maxn 200005
using namespace std;

int a[maxn], b[maxn];
bool f[maxn], g[maxn];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i=0; i 
注：本题还有一种很奇怪的解法，就是直接判断相邻的四种连接方式是否有至少一种能连通，比如#30453703，如果有大佬能证明这种方法的正确性，欢迎在评论区留言告诉我，谢谢！
 
 
D - Polynomial division 
题目大意 
我们有三个多项式
 
     
      
       
        
         A
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           0
          
         
         
          N
         
        
        
         
          A
         
         
          i
         
        
        
         
          X
         
         
          i
         
        
        
        
         B
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           0
          
         
         
          M
         
        
        
         
          B
         
         
          i
         
        
        
         
          X
         
         
          i
         
        
        
        
         C
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           0
          
         
         
          
           N
          
          
           +
          
          
           M
          
         
        
        
         
          B
         
         
          i
         
        
        
         
          X
         
         
          i
         
        
       
       
         A(x)=sum_{i=0}^N A_iX^i\ B(x)=sum_{i=0}^M B_iX^i\ C(x)=sum_{i=0}^{N+M} B_iX^i 
       
      
     A(x)=i=0∑N​Ai​XiB(x)=i=0∑M​Bi​XiC(x)=i=0∑N+M​Bi​Xi
 已知
    
     
      
       
        
         A
        
        
         0
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         A
        
        
         N
        
       
      
      
       A_0,dots,A_N
      
     
    A0​,…,AN​和
    
     
      
       
        
         C
        
        
         0
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         C
        
        
         N
        
       
      
      
       C_0,dots,C_N
      
     
    C0​,…,CN​且
    
     
      
       
        A
       
       
        (
       
       
        x
       
       
        )
       
       
        ×
       
       
        B
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        C
       
       
        (
       
       
        x
       
       
        )
       
      
      
       A(x)times B(x)=C(x)
      
     
    A(x)×B(x)=C(x)（
    
     
      
       
        x
       
       
        ∈
       
       
        R
       
      
      
       xin R
      
     
    x∈R），求
    
     
      
       
        
         B
        
        
         0
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         B
        
        
         M
        
       
      
      
       B_0,dots,B_M
      
     
    B0​,…,BM​。
 换句话说，给定多项式
    
     
      
       
        A
       
      
      
       A
      
     
    A和
    
     
      
       
        C
       
      
      
       C
      
     
    C每一项的系数，求多项式
    
     
      
       
        B
       
       
        =
       
       
        
         C
        
        
         A
        
       
      
      
       B=frac C A
      
     
    B=AC​。
 

    
     
      
       
        1
       
       
        ≤
       
       
        N
       
       
        ,
       
       
        M
       
       
        <
       
       
        100
       
      
      
       1le N,M<100
      
     
    1≤N,M<100
 
    
     
      
       
        ∣
       
       
        
         A
        
        
         i
        
       
       
        ∣
       
       
        ≤
       
       
        100
       
      
      
       |A_i|le 100
      
     
    ∣Ai​∣≤100
 
    
     
      
       
        ∣
       
       
        
         C
        
        
         i
        
       
       
        ∣
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         6
        
       
      
      
       |C_i|le 10^6
      
     
    ∣Ci​∣≤106
 
    
     
      
       
        
         A
        
        
         N
        
       
       
        ≠
       
       
        0
       
       
        ,
       
       
        
         C
        
        
         
          N
         
         
          +
         
         
          M
         
        
       
       
        ≠
       
       
        0
       
      
      
       A_Nne0,C_{N+M}ne0
      
     
    AN​​=0,CN+M​​=0
 题目保证存在合法的
    
     
      
       
        (
       
       
        
         B
        
        
         0
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         B
        
        
         M
        
       
       
        )
       
      
      
       (B_0,dots,B_M)
      
     
    (B0​,…,BM​)。
 
输入格式 

    
     
      
       
        N
       
       
         
       
       
        M
       
      
      
       N~M
      
     
    N M
 
    
     
      
       
        
         A
        
        
         0
        
       
       
         
       
       
        …
       
       
         
       
       
        
         A
        
        
         N
        
       
      
      
       A_0~dots~A_N
      
     
    A0​ … AN​
 
    
     
      
       
        
         C
        
        
         0
        
       
       
         
       
       
        …
       
       
         
       
       
        
         C
        
        
         
          N
         
         
          +
         
         
          M
         
        
       
      
      
       C_0~dots~C_{N+M}
      
     
    C0​ … CN+M​
 
输出格式 
输出
    
     
      
       
        
         B
        
        
         0
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         B
        
        
         M
        
       
      
      
       B_0,dots,B_M
      
     
    B0​,…,BM​，用空格分隔。
 
样例 
略，请自行前往AtCoder查看
 
分析 
本题可以直接模拟多项式的大除法运算，运算时只需记录系数即可。
 
代码 
#include 
#define maxn 105
using namespace std;

int a[maxn], b[maxn], c[maxn << 1];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<=n; i++) scanf("%d", a + i);
	for(int i=0; i<=n+m; i++) scanf("%d", c + i);
	for(int i=m; i>=0; i--) // NOTE: 必须倒推！
	{
		b[i] = c[n + i] / a[n];
		for(int j=0; j<=n; j++)
			c[i + j] -= a[j] * b[i];
	}
	for(int i=0; i<=m; i++)
		printf("%d ", b[i]);
	return 0;
}
 
 
E - Wrapping Chocolate 
题目大意 
我们有
    
     
      
       
        N
       
      
      
       N
      
     
    N块巧克力和
    
     
      
       
        M
       
      
      
       M
      
     
    M个盒子。第
    
     
      
       
        i
       
      
      
       i
      
     
    i块巧克力长
    
     
      
       
        
         A
        
        
         i
        
       
      
      
       A_i
      
     
    Ai​厘米，宽
    
     
      
       
        
         B
        
        
         i
        
       
      
      
       B_i
      
     
    Bi​厘米；第
    
     
      
       
        i
       
      
      
       i
      
     
    i个盒子长
    
     
      
       
        
         C
        
        
         i
        
       
      
      
       C_i
      
     
    Ci​厘米，宽
    
     
      
       
        
         D
        
        
         i
        
       
      
      
       D_i
      
     
    Di​厘米。
 问是否能把巧克力分别装在盒子里，使其满足如下条件：
 
每个盒子里只能有一块巧克力。当我们将第
     
      
       
        
         i
        
       
       
        i
       
      
     i块巧克力放入第
     
      
       
        
         j
        
       
       
        j
       
      
     j个盒子里时，
     
      
       
        
         
          A
         
         
          i
         
        
        
         ≤
        
        
         
          C
         
         
          j
         
        
       
       
        A_ile C_j
       
      
     Ai​≤Cj​和
     
      
       
        
         
          B
         
         
          i
         
        
        
         ≤
        
        
         
          D
         
         
          j
         
        
       
       
        B_ile D_j
       
      
     Bi​≤Dj​必须都成立。 

    
     
      
       
        1
       
       
        ≤
       
       
        N
       
       
        ≤
       
       
        M
       
       
        ≤
       
       
        2
       
       
        ×
       
       
        1
       
       
        
         0
        
        
         5
        
       
      
      
       1le Nle Mle 2times10^5
      
     
    1≤N≤M≤2×105
 
    
     
      
       
        1
       
       
        ≤
       
       
        
         A
        
        
         i
        
       
       
        ,
       
       
        
         B
        
        
         i
        
       
       
        ,
       
       
        
         C
        
        
         i
        
       
       
        ,
       
       
        
         D
        
        
         i
        
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       1le A_i,B_i,C_i,D_ile 10^9
      
     
    1≤Ai​,Bi​,Ci​,Di​≤109
 
输入格式 

    
     
      
       
        N
       
       
         
       
       
        M
       
      
      
       N~M
      
     
    N M
 
    
     
      
       
        
         A
        
        
         1
        
       
       
         
       
       
        …
       
       
         
       
       
        
         A
        
        
         N
        
       
      
      
       A_1~dots~A_N
      
     
    A1​ … AN​
 
    
     
      
       
        
         B
        
        
         1
        
       
       
         
       
       
        …
       
       
         
       
       
        
         B
        
        
         N
        
       
      
      
       B_1~dots~B_N
      
     
    B1​ … BN​
 
    
     
      
       
        
         C
        
        
         1
        
       
       
         
       
       
        …
       
       
         
       
       
        
         C
        
        
         N
        
       
      
      
       C_1~dots~C_N
      
     
    C1​ … CN​
 
    
     
      
       
        
         D
        
        
         1
        
       
       
         
       
       
        …
       
       
         
       
       
        
         D
        
        
         N
        
       
      
      
       D_1~dots~D_N
      
     
    D1​ … DN​
 
输出格式 
如果有合法的方法，输出Yes；否则，输出No。
 
分析 
本题可以考虑如下贪心算法：
 
将所有的巧克力和盒子放入一个数组，按长度（
     
      
       
        
         
          A
         
         
          i
         
        
       
       
        A_i
       
      
     Ai​或
     
      
       
        
         
          C
         
         
          i
         
        
       
       
        C_i
       
      
     Ci​）的降序排序，长度相等的把盒子排在前面。准备好一个空序列
     
      
       
        
         S
        
        
         =
        
        
         (
        
        
         )
        
       
       
        S=()
       
      
     S=()，按如下规则遍历每个元素： 
  
如果当前遍历的是一个盒子
       
        
         
          
           (
          
          
           
            C
           
           
            i
           
          
          
           ,
          
          
           
            D
           
           
            i
           
          
          
           )
          
         
         
          (C_i,D_i)
         
        
       (Ci​,Di​)：
 将
       
        
         
          
           
            D
           
           
            i
           
          
         
         
          D_i
         
        
       Di​加入
       
        
         
          
           S
          
         
         
          S
         
        
       S。如果当前遍历的是一块巧克力
       
        
         
          
           (
          
          
           
            A
           
           
            i
           
          
          
           ,
          
          
           
            B
           
           
            i
           
          
          
           )
          
         
         
          (A_i,B_i)
         
        
       (Ai​,Bi​)：
 从
       
        
         
          
           S
          
         
         
          S
         
        
       S中删除不超过
       
        
         
          
           
            B
           
           
            i
           
          
         
         
          B_i
         
        
       Bi​的最小元素，如果没有元素可删除，输出No。 如果顺利地遍历了所有元素，输出Yes；否则，输出No。
 
本算法的时间复杂度是
    
     
      
       
        O
       
       
        (
       
       
        M
       
       
        N
       
       
        )
       
      
      
       mathcal O(MN)
      
     
    O(MN)，但经过multiset优化后可降为
    
     
      
       
        O
       
       
        (
       
       
        (
       
       
        M
       
       
        +
       
       
        N
       
       
        )
       
       
        log
       
       
        ⁡
       
       
        (
       
       
        M
       
       
        +
       
       
        N
       
       
        )
       
      
      
       mathcal O((M+N)log(M+N)
      
     
    O((M+N)log(M+N)，具体实现详见代码。
 
代码 
#include 
#include 
#include 
using namespace std;

struct Item {
	int w, h;
	bool type;
	inline bool operator <(const Item& i2) const {
		return w == i2.w? type > i2.type: w > i2.w;
		//                ^^^^^^^^^^^^^^
		// 注意sort必须有严格顺序，一开始我这里写成了type==1导致RE，详见：
		// https://atcoder.jp/contests/abc245/submissions/30526563
	}
} v[400005];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	// Chocolate
	for(int i=0; i s;
	for(int i=0; i