F. Asya And Kittens

确认过眼神,是div2的人

a Sea Battle

题意:

将两个紧邻的矩形围起来需要的方块数

周长+4

b Draw

题意：

给定出现的分数，求最多可能出现的平局数

计算\((x_i:y_i) to (x_{i+1},y_{i+1})\)可能出现的平局数，可包含一边，如左边，如果不一样，最后可特判右边是否为平局

code

#include 
    
     using namespace std;#define ll long long;#define inf 0x3f3f3f3f#define CL(a,b) memset(a,b,sizeof(a))#define sf(a) scanf("%d",&a)#define pr(a) printf("%d\n",a)#define db(a) printf("db %d\n",a)#define fr0(i,m) for(int i=0;i
    

c Birthday

题意:

排列n个数使得\(abs(a_{i+1}-a_i)\)的最大值最小化，包含\(a_{n-1}-a_0\)的情况

构造的做:排序,从小到大一次从两边向中间放，即数组边缘小，数组中心大

证明:

假设排序后的结果为\(a_0,a_1..a_i,a_{i+1}..a_{n-1}\) ,显然我们的做法不会大于\(max(a_{i+2}-a_i)\);

下面只需证明，任何一种做法都不会小于\(max(a_{i+2}-a_{i})\) 盗用codeforce图进行证明:

要使其小于\(a_{i+2}-a_{i}\) 则\(a_{i+2}\)和\(a_i\)之间必须有\(a_{i+1}\),同时\(a_{i+2}\)右边一定是更大的,\(a_i\)左边一定是更小的，那么最左端和最右端就矛盾了.

code

#include 
    
     using namespace std;#define ll long long;#define inf 0x3f3f3f3f#define CL(a,b) memset(a,b,sizeof(a))#define sf(a) scanf("%d",&a)#define pr(a) printf("%d\n",a)#define db(a) printf("db %d\n",a)#define fr0(i,m) for(int i=0;i
     
      >1;        int b=n-1-a;        ans[a]=hei[i];        if(i+1
     
    

D. Gourmet choice

题意

给出n个菜和m个菜之间的相互关系(>,<,=),问是否矛盾，不矛盾则给出最少需要的等级编号

并查集缩点+有向无环图的最长路径(注意建图方式)

code

#include 
    
     using namespace std;#define ll long long;#define inf 0x3f3f3f3f#define CL(a,b) memset(a,b,sizeof(a))#define sf(a) scanf("%d",&a)#define sfs(a) scanf("%s",a);#define pr(a) printf("%d\n",a)#define db(a) printf("db %d\n",a)#define fr0(i,m) for(int i=0;i