IBM Ponder this 2017 May

ibm越来越水了→_→

这题写了个退火就跑过去了

大概两三分钟的样子吧

状态的价值函数瞎jb定义一下就好

我写的是$\sum_{c=\text{'A'}}^{\text{'Z'}} (t(c)-c-\text{'A'})^2$，$t$表示两个字符$c$之间的字符个数

主要是转移

一个状态我们每次交换两个字符，得到一个新的状态

然而这个转移太垃圾了，26个字母跑10min也跑不出

转移我写的是一个状态取出一个字符，把它放到正确的位置

效果不错。。几分钟跑出来吧

附代码

#include <bits/stdc++.h>
using namespace std;
string s;
int n;

int score() {
  int i, u[26] = {}, t, ans = 0;
  for (i = 0; i < s.length(); i++)
    if (s[i] >= 'A' && s[i] <= 'Z') {
      int p = s[i] - 'A';
      if (u[p]) {
	t = i - u[p];
	t = abs(t - (p + 1));
	ans += t * t;
      } else u[p] = i + 1;
    }
  return ans;
}

string s0;
void change() {
  int i, j, L = s.length();
  s0 = s;
  do {i = rand() % L;} while (s[i] == '-');
  char c = s[i]; s.erase(i, 1);
  for (j = 0; j < L; j++) if (s[j] == c) break;
  int gap = c - 'A' + 1, _l = j - gap, _r = j + gap, b = rand() & 1;
  if (_l < 0) b = 1; if (_r >= L) b = 0;
  if (b == 0) b = _l; else b = _r;
  s.insert(b, 1, c);
}

void change_back() {
  s = s0;
}

int main(){
  srand(time(0));
  scanf("%d", &n);
  for (int i = 0; i < n; i++) s += char('A' + i), s += char('A' + i);
  s += '-';
  random_shuffle(s.begin(), s.end());
  int p, b, q;
  p = b = score();
  double e = 1;
  while (1) {
    change();
    q = score();
    if (q == 0) {
      freopen("outf.txt", "w", stderr); cerr << s << endl;
      return 0;
    }
    if (q < p || rand() < RAND_MAX * e) {
      p = q; e *= 0.999999; //e *= 0.999999; e = max(e, 0.01);
      if (q < b) {b = q; cout << s << ",b=" << b << ",e=" << setprecision(20) << e << endl;}
    } else change_back();
  }
}

看了一下solution。。

KPGOJNWCXVGCKYZJD-PONDERTHISEUWQVXHLIBMYBZRFATASLQFUM真心漂亮。。