wecing's OI dream

属于我喜欢的题，基本上就是在推导数学公式（因为在下的MO实在是个杯具……）。

O(1)。非常短。提交的时候看到SPOJ rank 1的Oleg君了。id 68949。
——————————————————————————

#include <stdio.h>
#include <math.h>

int main(void)
{
    double k, h1, ans, p = 10000000;
    int n;
    scanf("%d %lf", &n, &h1);
    ans = (n - 1) * (n - 2);
    k = ceil(sqrt(h1));
    if(k <= n - 1)
        p = h1 / k + k;
    k = floor(sqrt(h1));
    if(k <= n - 1 && p > h1 / k + k)
        p = h1 / k + k;
    if(p == 10000000)
        p = h1 / (n - 1) + n - 1;
    p = -p + 1;
    ans += p * (n - 1) + h1;
    printf("%.2lf", ans);
    return 0;
}

一开始觉得数据可能会灰常恶心，于是想到要用suffix tree/array。

杯具的是实在没研究明白这个东西……最后用的是strncmp()。

需要注意的是，strncmp()返回的值不止-1，0，1三个。

————————————————————————————

#include <stdio.h>
#include <string.h>
#define  SLEN  10000

int main(void)
{
     int i, n, len, ans;
     char s[SLEN * 2 + 1];
     scanf("%d", &n);
     while(n--)
     {
          scanf("%s", s);
          len = strlen(s);
          ans = 0;
          for(i = 0; i < len; i++)
               s[i + len] = s[i];
          s[len * 2] = '\0';
          for(i = 1; i < len; i++)
               if(strncmp(s + i, s + ans, len) < 0)
                    ans = i;
          printf("%d\n", ans + 1);
     }
     return 0;
}

 

并查集加不知名火星算法。

我为啥要把它贴上来呢？因为它很有可能是我人生中最丑的一段代码……（火星人表示看懂不能……）

————————我是分割线君————————

#include <stdio.h>
#include <string.h>

int in[26], out[26], ih[26], app[26];
int scnt, ecnt;
char s[1001];

int main(void)
{
     int n, t, p, i, ht, sig, cc, ht2;
     char ca, cb, ct;
     scanf("%d", &n);
     while(n--)
     {
          sig = 0;
          cc = 0;
          for(i = 0; i < 26; i++)
               ih[i] = i;
          memset(app, 0, sizeof(app));
          memset(in, 0, sizeof(in));
          memset(out, 0, sizeof(out));
          scnt = ecnt = 0;
          scanf("%d", &t);
          while(t--)
          {
               scanf("%s", s);
               ca = s[0] - 'a';
               cb = s[strlen(s) - 1] - 'a';
               ht = cb;
               while(ih[ht] != ht)
                    ht = ih[ht];
               ht2 = ca;
               while(ih[ht2] != ht2)
                    ht2 = ih[ht2];
               ih[ht] = ht2;
               app[ca] = 1;
               app[cb] = 1;
               in[ca]++;
               out[cb]++;
          }
          for(t = 0; t < 26; t++)
          {
               p = t;
               while(ih[p] != p)
                    p = ih[p];
               if(app[t] && ih[p] == t)
                    cc++;
          }
          if(cc > 1)
               sig = 1;
          else for(t = 0; t < 26; t++)
          {
               p = in[t] - out[t];
               if(p == 1)
                    scnt++;
               else if(p == -1)
                    ecnt++;
               if(p < 0)
                    p = -p;
               if(p >= 2 || scnt > 1 || ecnt > 1)
               {
                    sig = 1;
                    break;
               }
          }
          if(sig)
               printf("The door cannot be opened.\n");
          else
               printf("Ordering is possible.\n");
     }
     return 0;
}

 

spoj果然是为ACM准备的OJ，一个高精度都要弄个前缀冗余0让你就是没法一次AC。

鸡冻死了，过年的时候开始碰spoj，今天终于刷出了0.1 point（成绩点？）。

palin不是难题，可是要考虑的东西比较多。

过了样例之后提交，一次AC。

为了纪念ural的再次杯具，决定贴上AC程序。

——————————————————————————————

#include <stdio.h>
#include <string.h>
#define  CID(x)  (len-1-(x))
#define  SSIZE   1000005

int n, len;
char s[SSIZE];

void cal(int b)
{
     int i, t, k;
     if(b == len)
          return;
     if(s[b] == s[CID(b)])
          cal(b + 1);
     else if(s[CID(b)] > s[b])
          for(i = b; i < len; i++)
               s[i] = s[CID(i)];
     else
     {
          t = CID(len / 2);
          while(s[t] == '9')
               t--;
          s[t] += 1;
          for(i = t + 1; i <= len / 2; i++)
               s[i] = '0';
          for(i = len / 2; i < len; i++)
               s[i] = s[CID(i)];
     }
     return;
}

int main(void)
{
     int i, j, t, k, sig;
     scanf("%d", &n);
     fgetc(stdin);
     for(i = 0; i < n; i++)
     {
          scanf("%s", s);
          len = strlen(s);
          sig = 1;
          for(j = 0; j < len; j++)
               if(s[j] != '9')
               {
                    sig = 0;
                    break;
               }
          if(sig)
          {
               s[len] = s[0] = '1';
               for(j = 1; j < len; j++)
                    s[j] = '0';
               s[++len] = '\0';
          } else
          {
               t = len - 1;
               while(s[t] == '9')
                    t--;
               s[t] += 1;
               for(j = t + 1; j < len; j++)
                    s[j] = '0';
               cal(len / 2);
          }
          printf("%s\n", s);
     }
     return 0;
}

update：仔细想想其实不能说是一次AC，因为过年的时候做过这道题，当时提交N次都是TLE……

我是巨菜我NC，只会疯狂刷水题。

我在这里看到这样一句话：

“注意到加的反操作是减，所以加法的方程组消元就是把它减掉的。现在异或的反操作任然是异或，那么我们是不是也可以通过用异或来达到消元的目的呢？”

于是严重震精……

 

打死你我也想不出来这么WS的解法……

好一个强力的dfs……

讨厌用指针。因为实在是太慢。

讨厌动态分配内存。因为我不愿意为了节省时间而省略free()。

因为我是巨菜，所以我用数组套数组的方式模拟指针。

于是我写出来的treap和sbt都无比杯具，因为left-rotate和right-rotate完全不用指针是特别难写的。

后来有一天我终于发现，我干吗直接绕来绕去地传数据……

以前翻了几页《组合数学》，觉得暂时基本用不上，就放下了。

没想到这次遇到一个鸽笼原理的题……

之前想了一个空间和时间复杂度都是O(n)的算法（这都能想出来，我实在是太牛13了……），但不知道为什么，WA on point 17。

顺便膜拜下leokan，此牛居然在学古琴……orz……