TIOJ 1213 樹論 之 最遠距點對

[DFS]

將所有的邊存在一個陣列

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define MAX 100000
#define max(a,b) ((a)>(b)) ? (a) : (b)
struct adj
{
    int a;int b;
    int w;
} adjs[2*MAX+1];
int corp[MAX+1];
int diam=0;
int compare(const void *a, const void *b)
{
    struct adj c = *(struct adj *)a;
    struct adj d = *(struct adj *)b;
    if(c.a < d.a) {return -1;}
    else if (c.a == d.a)
    {
        if(c.b>d.b)
            return 1;
        else
            return 0;
    }
    else
        return 1;
}
int bs(int down,int up,int f)
{
    if(down==up)
    {
        if(adjs[down].a==f)
            return down;
        return -1;
    }
    if(down==up-1)
    {
        if(adjs[down].a==f)
            return down;
        else if(adjs[up].a==f)
            return up;
        else
            return -1;
    }
    int mid=(up+down)/2;
    if(adjs[mid].a>=f)
        return bs(down,mid,f);
    else
        return bs(mid,up,f);
}
bool check(int a,int b)
{
    if(corp[a]==-1)
        return false;
    for(int lx=corp[a];adjs[lx].a==a;lx++)
        if(adjs[lx].b==b)
            return true;
    return false;
}
int dfs(int px,int x)
{

    int h1,h2;
    h1=h2=0;
    for(int lx=0;adjs[corp[x]+lx].a==x;lx++)
    {
        int nx=adjs[corp[x]+lx].b;
        if(nx==px) continue;
        int h=dfs(x,nx)+adjs[corp[x]+lx].w;
        if(h>h1){h2=h1;h1=h;}
        else if(h>h2)h2=h;
    }
    diam=max(diam,h1+h2);
    return h1;
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        int a,b,w,adjcnt;
        adjcnt=0;
        diam=0;
        for(int ln=1;ln<n;ln++)
        {
            scanf("%d %d %d",&a,&b,&w);
            adjs[adjcnt++].a=a;
            adjs[adjcnt-1].b=b;
            adjs[adjcnt-1].w=w;
            adjs[adjcnt++].a=b;
            adjs[adjcnt-1].b=a;
            adjs[adjcnt-1].w=w;
        }
        qsort((void *)adjs, adjcnt, sizeof(adj), compare);
        
        memset(corp,-1,sizeof(corp));
        for(int lx=0;lx<adjcnt;lx++)
            if(corp[adjs[lx].a]<0)
                corp[adjs[lx].a]=lx;
        dfs(adjs[0].a,adjs[0].a);
        printf("%d\n",diam);
    }

    return 0;
}

TIOJ 1751 Ch1. Section 1. 愛的啟程

[沒啥]
卡了一下，原來可能有負整數= =

#include<stdio.h>
#include<stdlib.h>
#define FIBMAX 45
int fibdp[FIBMAX+1];
int main()
{
 int inp;int T;
 fibdp[0]=1;
 fibdp[1]=2;
 fibdp[FIBMAX]=2147483647;
 for(int lx=2;lx<FIBMAX;lx++)
  fibdp[lx]=fibdp[lx-1]+fibdp[lx-2];
 //for(int lx=0;lx<FIBMAX;lx++)
 // printf("%d\n",fibdp[lx]);
 scanf("%d",&T);
 for(int lT=1;lT<=T;lT++)
 {
  scanf("%d",&inp);
  int cnt=0;
  if(inp<=0)
  {
   printf("iyada~\n");
   continue;
  }
  while(inp>0)
  {
   for(int i=0;i<FIBMAX;i++)
   {
    if((fibdp[i]<=inp)&&((i==FIBMAX-1)||(fibdp[i+1]>inp)))
    {
     cnt++;
     inp-=fibdp[i];
    }
   }
  }

  printf("%d\n",cnt);
 }
 return 0;
}

TIOJ 1703 f(x)g(x)

[數學]
反正就是計算n!的3的次方數，帶Lengndre 公式

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
 int n;
 int cnt;
 while(scanf("%d",&n)==1)
 {
  cnt=0;
  int a3=1;
  while((n>=a3))
  {
   a3*=3;
   cnt+=(n/a3);
  }
  printf("%d\n",cnt);
 }
 return 0;
}

TIOJ 1036 How Many Primes?

[篩子+空間壓到N/2]

搞這題搞好久= = 最後毅然決然去壓空間，竟然AC了.....

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#define MAX 10000000
using namespace std;
bool sieve[MAX/2+1];
int prime[664579];
int pcnt=0;
int bry(int a,int b,int r)
{
    if((r-1)*r==0)
        return 0;
    if(a==b)
        return a+1;
    if((a+1)==b)
    {
        if(prime[b]>r)
            return a+1;
        else
            return b+1;
    }

    int mid=(a+b)/2;
    if(prime[mid]>r)
        return bry(a,mid,r);
    else if(prime[mid]<r)
        return bry(mid,b,r);
    else
        return mid+1;
}
int g(int lx)
{
 if(lx==1)
  return 2;
 else
  return 2*lx-1;
}
int invg(int x){return (x+1)/2;}
int main()
{
    memset(sieve,true,sizeof(sieve));
    for (int lx=2; g(lx)*g(lx)<MAX; lx++)
  if (sieve[lx])
   for (int ly=3; g(lx)*ly<MAX; ly+=2)
                sieve[invg(g(lx)*ly)] = false;
    for(int lx=1;lx<MAX/2+1;lx++)
  if(sieve[lx])
   prime[pcnt++]=g(lx);
    free(sieve);
    int inp,in;scanf("%d",&inp);
    int min,max;

    for(int lx=1;lx<=inp;lx++)
    {
     scanf("%d",&in);
        min=floorf((double)(in)/(double)log2(in)/(double)3);
        max=ceilf((double)(in)/(double)log2(in)*(double)6);
        if(in>=100)
   max=ceilf((double)(in)/((double)log(in)-4));
  else
  {
   min=1;
   max=26;
  }
        if(min<=1) min=1;
        if((max>664578)||(max<0)) max=664578;
        printf("%d\n",bry(min,max,in));
    }
    return 0;
}

TIOJ 1358 丟失的數

[無]
進擊的流水題.....

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
 long long int n;
 long long int cnt=0;
 while(scanf("%I64d",&n)!=EOF)
 {
  cnt=0;
  n--;
  while(n>=1)
  {
   cnt+=n;
   n/=2;
  }
  printf("%I64d\n",cnt);
 }
 return 0;
}

TIOJ 1432 骨牌遊戲

[二分搜]
:3

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int inp[1003];
int max;
int n,k;
int check(int r)
{
 if(r<max)
  return false;
 int kcnt=0;int cnt=0;
 for(int lx=1;lx<=n;lx++)
 {
  cnt+=inp[lx];
  if(cnt>r)
  {
   cnt=inp[lx];
   kcnt++;
  }
  else if((cnt==r)&&(lx<n))
  {
   cnt=0;
   kcnt++;
  }
 }
 return (kcnt<=k);
}
int main()
{
 int sum=0;
 while(scanf("%d %d",&n,&k)==2)
 {
  sum=0;
  if((k+n)==0)
   break;
  max=0;
  for(int lx=1;lx<=n;lx++)
  {
   scanf("%d",&inp[lx]);
   max=fMax(max,inp[lx]);
   sum+=inp[lx];
  }

  int down=max;
  int up=sum;
  int res=0;
  int prc=0;
  while(1)
  {
   if(down==up)
   {
    res=down;
    break;
   }
   if(down==(up-1))
   {
    if(check(down))
     res=down;
    else
     res=up;
    break;
   }
   prc=(up+down)/2;
   if(check(prc))
    up=prc;
   else
    down=prc;
  }
  printf("%d\n",res);
 }
 return 0;
}

TIOJ 1086 放錯的信封

[流水題 :3]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long long int dp[20];
long long int f(int n)
{
 if(n<=3)
  return n-1;
 if(dp[n])
  return dp[n];
 return (n-1)*(f(n-1)+f(n-2));
}
int main()
{
 int inp;
 memset(dp,0,sizeof(dp));
 while(scanf("%d",&inp)==1)
 {
  if(inp==0) break;
  printf("%I64d\n",f(inp));
 }
 return 0;
}

TIOJ 1312 家族

[Disjoint Set]
這題有多筆測資這題有多筆測資這題有多筆測資這題有多筆測資這題有多筆測資
^
搞我半小時QAQ

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
 int father;
};
struct node lst[10001];
int cycle[10001];
int findfather(int a)
{
 if(lst[a].father==a)
  return a;
 lst[a].father=findfather(lst[a].father);
 return lst[a].father;
}
int setup(int a,int b)
{
 int fa=findfather(a);
 int fb=findfather(b);
 if(fa==fb)
  return 0;
 if(fb<fa)
  lst[fa].father=fb;
 else
  lst[fb].father=fa;
}

int main()
{
 int n,p;
 int x,y;
 int q;
 while(scanf("%d %d",&n,&p)==2)
 {
  for(int lx=1;lx<=n;lx++)
   lst[lx].father=lx;
  for(int lx=1;lx<=p;lx++)
  {
   scanf("%d %d",&x,&y);
   setup(x,y);
  }
  scanf("%d",&q);
  printf("%d\n",findfather(q));
 }

 return 0;
}

TIOJ 1063 最大矩形(Area)

[動態規劃]
O(N^3) ㄎㄎ 對動態規劃越來越熟了~XDD

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,m;
    bool sq1[201][201];
    int prc[201][201];
    int lx,ly;
    scanf("%d %d",&n,&m);
    for(lx=1;lx<=n;lx++)
        for(ly=1;ly<=m;ly++)
            scanf("%d",&sq1[lx][ly]);
    for(lx=0;lx<=n;lx++)
        prc[lx][0]=0;
    for(ly=0;ly<=m;ly++)
        prc[0][ly]=0;
    for(lx=1;lx<=n;lx++)
        for(ly=1;ly<=m;ly++)
            prc[lx][ly]=sq1[lx][ly]*(prc[lx][ly-1]+1);
    int max=0;
    for(ly=1;ly<=m;ly++)
    {
        for(lx=1;lx<=n;lx++)
        {
            if(sq1[lx][ly])
            {
                int lk=lx;
                while(prc[lk][ly]>=prc[lx][ly])
                    lk--;
                max=(max>(lx-lk)*(prc[lx][ly]))? max:(lx-lk)*(prc[lx][ly]);
            }
        }
    }
    printf("%d\n",max);
    return 0;
}

TIOJ 1029 A遊戲

[DP]
還滿有趣的ㄎㄎ

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int line[1001];
int sum[1001];
int dp[1001][1001];
int dfs(int,int);
int dfs(int s,int e)
{
 if(s==e) return line[s];
 if(dp[s][e]) return dp[s][e];
 if(((sum[e]-sum[s])-dfs(s+1,e)+line[s])>((sum[e-1]-sum[s-1])-dfs(s,e-1)+line[e]))
  dp[s][e]=((sum[e]-sum[s])-dfs(s+1,e)+line[s]);
 else
  dp[s][e]=(sum[e-1]-sum[s-1])-dfs(s,e-1)+line[e];
 return dp[s][e];
}
int main()
{
 int n;scanf("%d",&n);
 for(int ln=1;ln<=n;ln++)
  scanf("%d",&line[ln]);
 for(int ln=1;ln<=n;ln++)
  dp[ln][ln]=line[ln];
 sum[0]=0;
 for(int lx=1;lx<=n;lx++)
  sum[lx]=sum[lx-1]+line[lx];
 memset(dp,0,sizeof(dp));
 printf("%d %d\n",dfs(1,n),sum[n]-dfs(1,n));
 return 0;
}