Fight For ACM

Kyrieh 发表于 2009-07-30 20:55:24

                     10.26  - 10.28                    南京赛区            

                      11.2   -  11.3                      日本赛区            
收藏: QQ书签 del.icio.us 订阅: Google 抓虾

计算几何

Tsuzuki 发表于 2008-08-03 10:04:15

      由于被某题搞昏了,就在网上发现了这么个东西。有一些基本的计算几何判断


             http://blog.csdn.net/lithe/archive/2005/01/22/263487.aspx
收藏: QQ书签 del.icio.us 订阅: Google 抓虾

PKU3105 Expectation

Tsuzuki 发表于 2008-07-10 17:22:55

    即将有新的组织。心情颇为复杂。希望新的member加油。。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
  int tot , n;
  double save , ans;
  long long M , MM , p0 , p1 , tmp , nn , temp;

  scanf("%d" , &tot);
  while (tot--)
    {
      scanf("%d" , &n);
      M = 1;
      tmp = n - 1;
      nn = n - 1;
      save = n;
      save *= n;
      ans = 0;
      for ( ; tmp ; tmp /= 2 , M *= 2)
 {
   MM = M * 2;
   temp = nn / MM + 1;
   if (tmp % 2)
     {
       p0 =  temp * M;
       p1 =  (temp - 1) * M + nn % M + 1;
     }
   else {
     p0 = (temp - 1) * M + nn % M + 1;
     p1 = (temp - 1) * M;
   }
   double tt = p0;
   tt *= p1 , tt *= MM;
   ans += tt / save;
 }

      printf("%.2lf\n" , ans);
    }
}

收藏: QQ书签 del.icio.us 订阅: Google 抓虾

PKU3535 A+B

Tsuzuki 发表于 2008-04-20 13:19:24

      其实我真的写不动代码啊~~~感觉点积差积都不记得了~~~怎么办啊。。。。。TAT

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxN = 100005;
const int N = 26;

char s[maxN];
int exist[maxN][30] , cnt[maxN] , a[4][maxN] , b[maxN];
int n , m;

void init()
{
  scanf("%d %d" , &m , &n);
  for (int i = 0 ; i < n ; ++i)
    {
      scanf("%s" , s);
      for (int j = 0 ; j < m ; ++j)
 exist[j][s[j] - 'a'] = 1;
    }

  memset(cnt , 0 , sizeof(cnt));
  for (int i = 0 ; i < m ; ++i)
    for (int j = 0 ; j < N ; ++j)
      if (!exist[i][j])
      exist[i][j] = cnt[i]++;
      else exist[i][j] = -1;

  for (int j = 0 ; j < 2 ; ++j)
    {
      scanf("%s" , s);
      for (int i = 0 ; i < m ; ++i)
 a[j][i] = exist[i][s[i] - 'a'];
    }
}

void work()
{
  int w = 0;

  for (int i = 0 ; i < m ; ++i)
    a[2][i] = a[0][i] + a[1][i];
  for (int i = m - 1 ; i >= 0 ; --i)
    {
      a[2][i] += w;
      w = a[2][i] / cnt[i];
      a[2][i] %= cnt[i];
    }
}

void show()
{
  for (int i = 0 ; i < m ; ++i)
    for (int j = 0 ; j < N ; ++j)
      if (exist[i][j] == a[2][i])
 printf("%c" , j + 'a');
  printf("\n");
}

int main()
{
  init();
  work();
  show();
}

 

收藏: QQ书签 del.icio.us 订阅: Google 抓虾

PKU3510 A Tale from the Dark Side of the Moon

Tsuzuki 发表于 2008-03-18 21:17:43

     我想说这题目好无聊.....-____-||||

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

char s[1000];
int L;
bool END;

void translate()
{
  L = strlen(s);
  for (int i = 0 ; i < L ; ++i)
    if (s[i] == ' ') printf(" ");
    else if (i + 2 < L && s[i] == 'E' && s[i + 1] == 'O' && s[i + 2] == 'F')
      {
 END = 1;
 if (i) printf("\n");
 return;
      }
    else if (s[i] >= 'a' && s[i] <= 'z')
      if (i < L - 1 && s[i] == 'd' && s[i + 1] == 'd')
 {
   printf("p");++i;
 }
      else if (i < L - 1 && s[i] == 'e' && s[i + 1] == 'i' && (!i || s[i - 1] != 'c'))
 {
   printf("ie");++i;
 }
      else if (i + 3 < L && s[i] == 'p' && s[i + 1] == 'i' && s[i + 2] == 'n' && s[i + 3] == 'k')
 {
   printf("floyd");i += 3;
 }
      else printf("%c" , s[i]);
  printf("\n");
}

int main()
{
  END = 0;
  while (!END && gets(s))
      translate();
}

收藏: QQ书签 del.icio.us 订阅: Google 抓虾

PKU3511 Fermat's Christmas Theorem

Tsuzuki 发表于 2008-03-18 20:34:11

      这题很无聊.....居然有负数的情况....没天理TAT

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1000000;

int f[N + 10] , h[N + 10];
bool prime[N + 10] , add[N + 10];

void Get()
{
  int T;

  memset(add , 0 , sizeof(add));
  memset(prime , 0 , sizeof(prime));
  for (int i = 2 ; i <= N ; ++i)
    if (!prime[i])
      {
 int j = i * 2;
 while (j <= N)
   prime[j] = 1, j += i;
      }
  add[2] = 1;
  for (int i = 1 ; i < 1000 ; ++i)
    for (int j = i + 1 ; j < 1000 ; j += 2)
      {
 T = i * i + j * j;
 if (T < N) add[T] = 1;
 else break;
      }
  f[0] = f[1] = h[0] = h[1] = 0;
  for (int i = 2 ; i <= N ; ++i)
    if (!prime[i])
      {
 f[i] = f [i - 1] + 1;
 if (add[i]) h[i] = h [i - 1] + 1;
 else h[i] = h[i - 1];
      }
    else f[i] = f[i - 1] , h[i] = h[i - 1];
}

int main()
{
  int n , m , N , M;

  Get();
  while (2 == scanf("%d %d" , &n , &m) && (n != -1 || m != -1))
    {
      N = max(n , 1) , M = max(m , 1);
      printf("%d %d %d %d\n" , n , m , f[M] - f[N - 1] , h[M] - h[N - 1]);
    }
}

 

收藏: QQ书签 del.icio.us 订阅: Google 抓虾