Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-04-04

PKU 1841 -- Meadow

| 04:18 | PKU 1841 -- Meadow - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1841 -- Meadow - Wrong Answer -- japlj PKU 1841 -- Meadow - Wrong Answer -- japlj のブックマークコメント

最小全域森やるだけ。TLEとMLEがきつい。


#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

float D[2000][2000], u[2000], d[2000];
float prim(int n, int k)
{
  for(int i=0; i<n; ++i) d[i]=D[0][i];
  for(int i=1; i<n; ++i) {
    int v=-1;
    for(int j=0; j<n; ++j)
      if(d[j]!=0 && (v==-1 || d[j]<d[v])) v=j;
    u[i-1]=d[v]; d[v]=0;
    for(int j=0; j<n; ++j)
      if(D[v][j]<d[j]) d[j]=D[v][j];
  }
  sort(u, u+n-1);
  return u[n-k-1];
}

int f, b, m, e, x[2000], y[2000];
int main()
{
  scanf("%d%d", &f, &b);
  for(int i=0; i<f; ++i) scanf("%d%d", &x[i], &y[i]);
  for(int i=0; i<f; ++i)
    for(int j=i+1; j<f; ++j)
      D[i][j]=D[j][i]=sqrt((float)(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
  printf("%.2f\n", prim(f, b));
  return 0;
}

PKU 1838 -- Banana

| 03:41 | PKU 1838 -- Banana - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1838 -- Banana - Wrong Answer -- japlj PKU 1838 -- Banana - Wrong Answer -- japlj のブックマークコメント

Flood-Fillするだけ。


#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int U[16666];
void init(int n) { for(int i=0; i<n; ++i) U[i]=i; }
int find(int x) { if(U[x]!=x) U[x]=find(U[x]); return U[x]; }

int main()
{
  int N, K;
  scanf("%d%d", &N, &K);
  vector<pair<pair<int, int>, int> > P(N);
  for(int i=0; i<N; P[i].second=i++)
    scanf("%d%d", &P[i].first.first, &P[i].first.second);
  init(N);
  for(int i=0; i<2; ++i) {
    sort(P.begin(), P.end());
    for(int j=0; j<N-1; ++j)
      if(P[j].first.first==P[j+1].first.first&&P[j+1].first.second-P[j].first.second==1)
	U[find(P[j].second)] = find(P[j+1].second);
    for(int j=0; j<N; ++j)
      swap(P[j].first.first, P[j].first.second);
  }
  vector<int> R(N, 0);
  for(int i=0; i<N; ++i)
    R[find(i)]++;
  sort(R.begin(), R.end());
  int sol = 0;
  for(int i=0; i<K; ++i)
    sol += R[R.size()-i-1];
  printf("%d\n", sol);
  return 0;
}

PKU 1837 -- Balance

| 03:16 | PKU 1837 -- Balance - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1837 -- Balance - Wrong Answer -- japlj PKU 1837 -- Balance - Wrong Answer -- japlj のブックマークコメント

DPやるだけ。


#include<cstdio>

int dp[21][15050], p[21];
int main()
{
  int c, g;
  scanf("%d%d", &c, &g);
  for(int i=0; i<c; ++i) scanf("%d", &p[i]);
  dp[0][7500] = 1;
  for(int i=1; i<=g; ++i) {
    int w;
    scanf("%d", &w);
    for(int j=0; j<c; ++j)
      for(int k=0; k<=15000; ++k)
	if(dp[i-1][k]>0) dp[i][k+w*p[j]] += dp[i-1][k];
  }
  printf("%d\n", dp[g][7500]);
  return 0;
}

PKU 1200 -- Crazy Search

| 03:00 | PKU 1200 -- Crazy Search - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1200 -- Crazy Search - Wrong Answer -- japlj PKU 1200 -- Crazy Search - Wrong Answer -- japlj のブックマークコメント

rolling hashやるだけ。


#include<cstdio>

using namespace std;

char S[1<<24], P[256], V[1<<24] = {0};
int main()
{
  int l, n, nc;
  scanf("%d%d%s", &n, &nc, S);
  for(int i=0; i<256; ++i) P[i]=-1;
  for(l=nc=0; S[l]; ++l)
    if(P[S[l]]==-1) P[S[l]]=nc++;
  if(n>l) { puts("0"); return 0; }
  int hash = 0, exp = 1, sol = 0;
  for(int i=0; i<n; ++i, exp*=nc)
    hash = hash*nc+P[S[i]];
  V[hash]=1;
  sol=1;
  for(int i=n; i<l; ++i) {
    hash = nc*hash-exp*P[S[i-n]]+P[S[i]];
    sol+=!V[hash];
    V[hash]=1;
  }
  printf("%d\n", sol);
  return 0;
}
 |