CodeForces 265 DIV2 题解

A. inc ARG

找到第一个0的位置, 将位置序号+1输出; 若找不到0, 则输出N即可.

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 0x4F4F4F4F
const int maxn = 1e5 + 10;

int n, m;

/////////////////

void solve() {

}

int main() {
  n = gint();
  char s[200];
  scanf("%s", s);
  int i;
  for (i = 0; i < n; i++)
    if (s[i] == '0') break;
  i++;
  if (i > n) i = n;
  cout << i << endl;
  solve();
  return 0;
}



/*



*/

B. Restore Cube

每一段连续的1的个数+1, 所有连续段加起来-1即可.

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 0x4F4F4F4F
const int maxn = 1e5 + 10;

int n, m;

/////////////////

void solve() {

}

int main() {
  n = gint();
  int cnt = 0;
  bool tag  = 0;
  for (int i = 0; i < n; i++) {
    int a = gint();
    if (a) {
      if (tag) cnt++;
      else {
        cnt += 2;
        tag = 1;
      }
    } else {
      tag = 0;
    }
  }
  cnt--;
  if (cnt < 0) cnt = 0;
  cout << cnt << endl;
  solve();
  return 0;
}



/*



*/

C. No to Palindromes!

这题的关键点是如何判断一个串是否含有回文子串. 首先需要用dfs穷举, 从已知序列开始按照字典序生成下一个序列. 每穷举出来一个序列, 就check是否符合题意. check的方法是从被修改位开始到最后一位都检查是否与前两位相等. 比如说当前位是b[pos], 则需要保证 b[pos] != b[pos-1] 且 b[pos] != b[pos-2].

dfs函数需要有两个参数, 一个是pos, 一个是ok. pos用来表示当前位是哪一位, ok用来表示递归到当前层之前的那些祖父层是否曾经修改过某一位. 如果修改过那么ok == true.

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 0
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 0x4F4F4F4F
const int maxn = 1e5 + 10;

int n, p;
char a[1001], b[1001];

/////////////////

bool dfs(int pos, bool ok) {
  if (pos == n) {
    dout << a << endl;
    return ok;
  }

  int start = ok ? 'a' : a[pos];  // 如果前面位修改过, 就从0开始; 否则从当前位开始.
  for (int i = start; i < p + 'a'; i++) {
    if (pos > 0 && b[pos-1] == i)
      continue;
    if (pos > 1 && b[pos-2] == i)
      continue;

    b[pos] = i;
    if (dfs(pos+1, ok | (i > start)))
      return true;
  }
  return false;
}

void solve() {
  if (dfs(0, 0)) {
    b[n] = '';
    printf("%sn", b);
  } else {
    printf("NOn");
  }
}

int main() {
  cin >> n >> p >> a;
  solve();
  return 0;
}



/*

4 3
abca

*/

D. Restore Cube

这题我看上去没什么思路, 但是畅神看了秒出正确思路. 对生成 (3!)^8 个可能的组合进行check, 如果符合条件则输出. 思路和上一题一样. 这题和上一题都隐藏得比较好, 有一种穷举会TLE的错觉. 实际上复杂度并不高.

check的方法也非常朴素, 有很多种方法, 其中一种方法是, 对于每一个点都应该有三个点和他距离为cube的边长. 而且这个点和那三个点组成的三条边应该两两垂直. 还有另一种判断的方法是, 对于每一个点, 其余七个点到他的距离的平方应该是三个L^2, 三个2*(L^2), 一个3*(L*2).

这样一来就可以做了.

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 1e18
const int maxn = 1e5 + 10;

int n, m;
int coodin[8][3];
long long d[8][8];
/////////////////

long long distan(int a, int b) {
  long long x = 0;
  for (int i = 0; i < 3; i++) {
    long long dx = (long long)coodin[a][i] - coodin[b][i];
    x += dx * dx;
  }
  return x;
}

bool judge() {
  long long l = 1LL << 60;
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < i; j++) if (i != j) {
      d[i][j] = d[j][i] = distan(i, j);
      l = min(l, d[i][j]);
    }
  }
  for (int i = 0; i < 8; i++) {
    int x,y,z;
    x = y = z = 0;
    for (int j = 0; j < 8; j++) if (i != j) {
      if (d[i][j] == l) x++;
      else if (d[i][j] == 2*l) y++;
      else if (d[i][j] == 3*l) z++;
    }
   // printf("x=%d y=%d z=%dn", x, y, z);
    if (x != 3 || y != 3 || z != 1)
      return false;
  }
  return true;
}

bool dfs(int deep) {
  if (deep == 8) {
    return judge();
  }
  do {
    if (dfs(deep + 1))
      return true;
  } while (next_permutation(coodin[deep], coodin[deep] + 3));
  return false;
}

void solve() {
  for (int i = 0; i < 8; i++)
    sort(coodin[i], coodin[i] + 3);
  if (dfs(0)) {
    printf("YESn");
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 3; j++) {
        if (!j) printf("%d", coodin[i][j]);
        else printf(" %d", coodin[i][j]);
      }
      printf("n");
    }
  } else {
    printf("NOn");
  }
}

int main() {
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 3; j++) {
      coodin[i][j] = gint();
    }
  }
  solve();
  return 0;
}



/*

887691 577079 -337
-193088 -342950 -683216
740176 -59645 -120545
592743 -30828 -283642
724594 652051 -193925
87788 -179853 -845476
665286 -133780 -846313
828383 -75309 -786168


*/