Codeforces Round #358 (Div. 2)

5/5

又是三题滚粗了，注定是打铁的命~~

 

题A Alyona and Numbers

题意：给你n和m，找[1, n]和[1,m]范围内的两个数相加，有多少个的和是5的倍数？

题解：枚举x在[1,n]的范围，然后得到范围[x + 1, x + m]的数，求有多少个是5的倍数即可。

 

/*zhen hao*/
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

int main() {
//  freopen("case.in", "r", stdin);
  int n, m;
  ll res = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int l = i + 1, r = i + m;
    res += (r / 5) - ((l - 1) / 5);
  }
  cout << res << endl;
  return 0;
}

 

题B Alyona and Mex

题意：给你n个数，让你可以对任意一个数变成小于它的数，然后问你最后这个序列的最小的没有的正整数是多少？

题解：水题，排个序，然后扫一下即可。

 

/*zhen hao*/
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5 + 100;
int v[maxn];

int main() {
//  freopen("case.in", "r", stdin);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    scanf("%d", v + i);
  }
  sort(v, v + n);
  int c = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] > c) c++;
  }
  cout << c + 1 << endl;
  return 0;
}

 

题C Alyona and the Tree

题意：给你n个带权点，然后组成一棵带权树，然后对于一个点u，如果存在子树中的点v使得dist（u，v） >  av，那么这个点为sad点，问你删除最少多少个点使得这棵树没有sad点？

题解：一开始想麻烦了，O（n ^ 2）肯定超时，开始的想法是对于这个点的子树中有多少个不是sad点，然后传上去继续判断，这样就中了出题人的圈套。应该分析的是这个v，而不是u，也就是说对于v的祖先是固定的，这么多祖先中有没有使得自己变sad点的，也就是存不存在u使得满足dist（u，v） >  av，av是固定的，也就是说我们去路径的最大值看一下满不满足，如果最大值都不满足的话，那么一定都可以，这个点就一定不是sad点，标记一下，最后再dfs一下统计个数即可。

 

/*zhen hao*/
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5 + 100;
int a[maxn], e, head[maxn], flag[maxn];

struct Edge {
  int v, w, nx;
} edges[maxn * 2];

void init() {
  e = 0;
  memset(head, -1, sizeof head);
}

void add_edge(int u, int v, int w) {
  edges[e] = (Edge){v, w, head[u]};
  head[u] = e++;
}

void dfs1(int u, int p, ll d) {
  for (int i = head[u]; ~i; i = edges[i].nx) {
    int v = edges[i].v;
    if (v == p) continue;
    if (d + edges[i].w > a[v] || edges[i].w > a[v]) flag[v] = 1;
    else dfs1(v, u, max((ll)edges[i].w, d + edges[i].w));
  }
}

int dfs2(int u, int p) {
  if (flag[u]) return 0;
  int ret = 1;
  for (int i = head[u]; ~i; i = edges[i].nx) {
    int v = edges[i].v;
    if (v == p) continue;
    ret += dfs2(v, u);
  }
  return ret;
}

int main() {
//  freopen("case.in", "r", stdin);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  init();
  for (int i = 2; i <= n; i++) {
    int u, w;
    scanf("%d%d", &u, &w);
    add_edge(i, u, w);
    add_edge(u, i, w);
  }
  dfs1(1, -1, 0);
  cout << n - dfs2(1, -1) << endl;
  return 0;
}

 

题D Alyona and Strings

题意：给你两个串，然后你可以分割s出k个子串，然后这k个子串在t串中出现，且顺序一样，问你这k个串最长是多少？

题解：这题是到水题，由于比赛没时间做，真是可惜了~~。正解是dp，dp（i，j，k）表示s的i，t的j，分割出了k各部分，然后最长是多少？有一个问题，就是想要接着上一个串继续组成k个部分要满足上一个串的最后两个刚好是i-1和j-1，所以这里要再加一维l，0表示最长，1表示以当且字符串结尾的最长，最后转移一下就好了。我觉得可行的还有一种解法就是pres和pret表示匹配的对应的s和t的最后两个位置，也是一样的效果，懒得写了！！

 

/*zhen hao*/
#include <bits/stdc++.h>
using namespace std;

const int L = 1100, K = 11;
int dp[L][L][K][2];
char s[L], t[L];

int main() {
//  freopen("case.in", "r", stdin);
  int n, m, k;
  cin >> n >> m >> k >> s >> t;

  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      for (int l = 1; l <= k; l++) {
        if (s[i - 1] == t[j - 1]) {
          dp[i][j][l][1] = 1 + max(dp[i - 1][j - 1][l][1], dp[i - 1][j - 1][l - 1][0]);
        }
        dp[i][j][l][0] = max(dp[i][j][l][1], max(dp[i - 1][j][l][0], dp[i][j - 1][l][0]));
      }

  cout << dp[n][m][k][0] << endl;
  return 0;
}

 

题E Alyona and Triangles

题意：给你n个点和一个面积S，然后让你构造一个三角形，满足这个三角形包围了所有的点，并且面积不大于4S，输出满足的任意三个点即可。

题解：这道题是计算几何，一直没怎么做过计算几何的题目，暑假要好好补一补才行了。

这道题是凸包+旋转卡壳。

首先直接抛出这道题的做法：先从这n个点找出三个点使得所有组成的三角形中面积最大，然后构造一个三角形的所有边的中点为刚才求出的三角形的点，就像下图（其中ABC就是求出来的，A’B’C’就是扩大之后的）：

接下来证明一下为什么可以这么做：

（1）先证明这个A’B’C’三角形的面积是不会超过4S的。

假设这个ABC的面积是s，由题目得s <= S，然后由初中的几何性质可知BC//B’C’,AB//A’B’,AC//A’C’；然后我们可知ABA’C是一个平行四边形，所以角A等于角A’，根据面积公式S = a * b * sinC / 2.0所以面积变为原来面积的4倍，刚好是4s<=4S；

（2）接下来证明为什么这个大三角形包括了所有凸包上的点，假设有个点D跑出去了，很容易证这个ABD、ACD、BCD至少有一个三角形的面积是大于ABC的，这与ABC就是三个点构成三角形最大的矛盾了，所以一定可以包括这个凸包的所有点。

 

最后讲一下怎么找这个ABC？

这是个经典题目

这个题目的做法要用到类似用旋转卡壳找最远点对（凸包的直径）的做法。具体就是固定两个相邻点i和j，然后找最远的k，然后固定k移动j，然后k就随着j进行移动（O（n）），然后枚举所有的i点，所以复杂度就是O（n ^ 2）。

 

/*zhen hao*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 5e4 + 100;

struct Point {
  ll x, y;
  bool operator < (const Point& o) const {
    return x < o.x || (x == o.x && y < o.y);
  }
  Point operator - (const Point& o) const {
    return (Point){x - o.x, y - o.y};
  }
  bool operator == (const Point& o) const {
    return x == o.x && y == o.y;
  }
} p[maxn], ch[maxn];

ll cross(Point A, Point B) {
  return A.x * B.y - A.y * B.x;
}

int convex_hull(int n) {
  sort(p, p + n);
  n = unique(p, p + n) - p;
  int m = 0;
  for (int i = 0; i < n; i++) {
    while (m > 1 && cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) --m;
    ch[m++] = p[i];
  }
  int k = m;
  for (int i = n - 2; i >= 0; i--) {
    while (m > k && cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) --m;
    ch[m++] = p[i];
  }
  if (n > 1) --m;
  return m;
}

int resi, resj, resk;

void max_area(int n) {
  ll res = 0;
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    int k = (j + 1) % n;
    while (i != j && j != k) {
      while (k != i && cross(ch[j] - ch[i], ch[k + 1] - ch[i]) > cross(ch[j] - ch[i], ch[k] - ch[i]))
        k = (k + 1) % n;
      ll tmp = cross(ch[j] - ch[i], ch[k] - ch[i]);
      if (res - tmp < 0) {
        res = tmp;
        resi = i;
        resj = j;
        resk = k;
      }
      j = (j + 1) % n;
    }
  }
}

int main() {
//  freopen("case.in", "r", stdin);
  int n;
  ll s;
  cin >> n >> s;
  for (int i = 0; i < n; i++) {
    scanf("%I64d%I64d", &p[i].x, &p[i].y);
  }
  int m = convex_hull(n);
  max_area(m);
  cout << ch[resj].x + ch[resk].x - ch[resi].x << ' ' << ch[resj].y + ch[resk].y - ch[resi].y << endl;
  cout << ch[resi].x + ch[resk].x - ch[resj].x << ' ' << ch[resi].y + ch[resk].y - ch[resj].y << endl;
  cout << ch[resi].x + ch[resj].x - ch[resk].x << ' ' << ch[resi].y + ch[resj].y - ch[resk].y << endl;
}