STEP5 0093 數御坂妹妹

[DP]
還是不太熟%I64u

主要是遞推公式(狀態懶得畫了:P)：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<stdio.h> #include<stdlib.h> #include<string.h> #define ULLI unsigned long long int ULLI dp[51]; int main() { int n,m; //printf("%d",1<<3); scanf("%d %d",&n,&m);; memset(dp,0,sizeof(dp)); dp[0]=1; for(int lx=1;lx<=n;lx++) dp[lx]=dp[lx-1]<<1; for(int lx=n+1;lx<=m;lx++) for(int ly=lx-1;ly>=lx-n-1;ly--) dp[lx]+=dp[ly]; printf("%I64u\n",dp[m]); return 0; }

UVA 10036 Divisibility

[DP?]
頗好玩XD
因為只要檢驗是否被K整除，因此只需要檢查K的完全剩餘系。應該算在DP。
複雜度O(N*K)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
int Mod(int a,int p)
{
 a%=p;
 if(a<0)
  a+=p;
 return a;
}
int main()
{

 int T;scanf("%d",&T);
 int n,k;
 for(int lT=1;lT<=T;lT++)
 {
  int inp;
  std::vector<int> line;
  bool stamp[100];memset(stamp,false,sizeof(stamp));
  bool tmp[100];memset(tmp,false,sizeof(tmp));
  scanf("%d %d",&n,&k);
  for(int lx=1;lx<=n;lx++)
  {
   scanf("%d",&inp);
   if(inp%k!=0)
    line.push_back(Mod(inp,k));
  }
  //for(int lx=0;lx<line.size();lx++)
  // printf("%d ",line[lx]);
  //printf("\n");
  stamp[0]=1;
  for(int lx=0;lx<line.size();lx++)
  {
   for(int lr=0;lr<k;lr++)
   {
    if(stamp[lr])
    {
     tmp[Mod(lr+line[lx],k)]++;
     tmp[Mod(lr-line[lx],k)]++;
     //printf("lr=%d line[lx]=%d\n",lr,line[lx]);
    }
   }
   for(int lr=0;lr<k;lr++)
    stamp[lr]=tmp[lr];
   memset(tmp,0,sizeof(tmp));
  }
  if(stamp[0]>0)
   printf("Divisible\n");
  else
   printf("Not divisible\n");
 }
 return 0;
}

UVA 103 Stacking Boxes

[LIS+DFS]
用TOP_DOWN的方式就OK了
不過用拓樸排序壓扁應該也可以。
要找一個線性的檢查方式去確認BOX_A是否可放入BOX_B
若BOX_B內可置入一個BOX_A，則 BOX_B的vec最小值必然大於BOX_A的vec最小值(要不然矛盾)，因此，只需要把vec排序後再做比較即可。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<vector> #include<algorithm> using namespace std; class box { public: int vec[10]; int d; box() { memset(vec,0,sizeof(vec)); d=0; } void setup(int _d,int _v[10]) { d=_d; for(int lx=0;lx<d;lx++) vec[lx]=_v[lx]; sort(vec,vec+d); } bool operator>(box _a) { bool ok=true; for(int lx=0;lx<d;lx++) if(_a.vec[lx]>=vec[lx]) ok=false; return ok; } }; box bs[30]; bool to[30][30]; int n,d; void GetLIS(int index,vector<int>& re) { bool sum=false; re.clear(); re.push_back(index+1); for(int lx=0;lx<n;lx++) sum=(sum||to[index][lx]); if(sum==false) return; vector<int> prc(re); for(int lx=0;lx<n;lx++) { if((to[index][lx])) { GetLIS(lx,prc); if(prc.size()>=re.size()) { re=prc; re.push_back(index+1); } } } return; } int main() { while(scanf("%d %d",&n,&d)!=EOF) { for(int lx=0;lx<n;lx++) { int vec[10]; for(int ly=0;ly<d;ly++) scanf("%d",&vec[ly]); bs[lx].setup(d,vec); } memset(to,false,sizeof(to)); for(int lx=1;lx<n;lx++) //建表 { for(int ly=0;ly<lx;ly++) { if(bs[lx]>bs[ly]) { to[lx][ly]=true; to[ly][lx]=false; } else if(bs[ly]>bs[lx]) { to[ly][lx]=true; to[lx][ly]=false; } } } vector<int>mm,prc; mm.push_back(1); for(int lx=0;lx<n;lx++) { GetLIS(lx,prc); if(mm.size()<prc.size()) mm=prc; } printf("%d\n",mm.size()); for(int lx=0;lx<mm.size();lx++) printf("%d%c",mm[lx],((lx==(mm.size()-1)) ? '\n':' ')); } return 0; }

UVA 111 History Grading

[LIS基礎]
這題練習LIS。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define max(a,b) (a>b) ? (a):(b)
int LIS(int a[20],int dg)
{
 int lg[20];
 lg[0]=1;
 for(int lx=1;lx<dg;lx++)
 {
  lg[lx]=1;
  for(int ly=0;ly<lx;ly++)
   if(a[lx]>a[ly])
    lg[lx]=max(lg[lx],lg[ly]+1);
 }
 int m=1;
 for(int lx=1;lx<dg;lx++)
  m=max(m,lg[lx]);
 return m;
}
int main()
{
 int dg;scanf("%d",&dg);
 int a[20];
 int inp[20];
 for(int lx=0;lx<dg;lx++)
  scanf("%d",&a[lx]);
 while(scanf("%d",&inp[a[0]-1])!=EOF)
 {
  for(int lx=1;lx<dg;lx++)
   scanf("%d",&inp[a[lx]-1]);
  printf("%d\n",LIS(inp,dg));
 }
 return 0;
}

UVA 102 Ecological Bin Packing

[炸]
看背景介紹，原本以為是啥DP，原來只是硬炸XD

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

long long int b1,g1,c1;
long long int b2,g2,c2;
long long int b3,g3,c3;
long long int cost(const char ch[4])
{
    long long int re=0;
    re+=(ch[0]=='B')*(b2+b3)+(ch[0]=='G')*(g2+g3)+(ch[0]=='C')*(c2+c3);
    re+=(ch[1]=='B')*(b1+b3)+(ch[1]=='G')*(g1+g3)+(ch[1]=='C')*(c1+c3);
    re+=(ch[2]=='B')*(b2+b1)+(ch[2]=='G')*(g2+g1)+(ch[2]=='C')*(c2+c1);
    return re;
}
int main()
{
    while(scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)!=EOF)
    {
        long long int cc=cost("GCB");
        char p[4]="GCB";
        if(cc>=cost("GBC")){cc=cost("GBC");strcpy(p,"GBC");}
        if(cc>=cost("CGB")){cc=cost("CGB");strcpy(p,"CGB");}
        if(cc>=cost("CBG")){cc=cost("CBG");strcpy(p,"CBG");}
        if(cc>=cost("BGC")){cc=cost("BGC");strcpy(p,"BGC");}
        if(cc>=cost("BCG")){cc=cost("BCG");strcpy(p,"BCG");}
        printf("%s %d\n",p,cc);
    }
    return 0;
}

UVA 101 The Blocks Problem

[LIST]

這題PRESENTATION ERROR 搞半天>"<

主要就是Implement、Simulation。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define QUIT 0
#define MOVE 1
#define PILE 2
#define ONTO 3
#define OVER 4
struct node
{
 int prev;
 int next;
};
int n;
node nods[100];
int clearat(int i)
{
 int prc;
 while(nods[i].next!=-1)
 {
  prc=nods[i].next;
  nods[i].next=-1;
  nods[prc].prev=prc-n;
  nods[prc-n].next=prc;
  i=prc;
 }
}
int getend(int i)
{
 while(nods[i].next!=-1)
  i=nods[i].next;
 return i;
}
int setto(int under,int a)
{
 nods[nods[a].prev].next=-1;
 nods[under].next=a;
 nods[a].prev=under;
}
void showline(int i)
{
 printf("%d:",i-1);
 while(nods[i].next!=-1)
 {
  i=nods[i].next;
  printf(" %d",i-n-1);
 }
 printf("\n");
}
int cmd(char ch[5])
{
 //DEBUG
 //if(ch[0]=='z')
 // return 99;
 switch(ch[1])
 {
  case 'u':
   return QUIT;
  case 'o':
   return MOVE;
  case 'i':
   return PILE;
  case 'n':
   return ONTO;
  case 'v':
   return OVER;
 }
 return QUIT;
}
int main()
{
 while(scanf("%d",&n)!=EOF)
 {
  for(int lx =1;lx<=n;lx++)
  {
   nods[lx].prev=-1;
   nods[lx].next=lx+n;
   nods[n+lx].prev=lx;
   nods[n+lx].next=-1;
  }
  char cmd1[5],cmd2[5];
  int a,b;
  while(1)
  {
   scanf("%s",cmd1);
   if(cmd(cmd1)==QUIT) break;
   /*if(cmd(cmd1)==99)
   {
    for(int lx=1;lx<=n;lx++)
     printf("qnd[%d]=%d\n",lx-1,getend(lx+n)-n-1);
    continue;
   }*/
   scanf("%d %s %d",&a,cmd2,&b);
   a+=1;b+=1;
   if((a==b)||((getend(a+n)==getend(b+n)))) continue;

   if((cmd(cmd1)==MOVE)&&(cmd(cmd2)==ONTO))
   {
    clearat(a+n);clearat(b+n);
    setto(b+n,a+n);
   }
   if((cmd(cmd1)==MOVE)&&(cmd(cmd2)==OVER))
   {
    clearat(a+n);
    setto(getend(b+n),a+n);
   }
   if((cmd(cmd1)==PILE)&&(cmd(cmd2)==ONTO))
   {
    clearat(b+n);
    setto(b+n,a+n);
   }
   if((cmd(cmd1)==PILE)&&(cmd(cmd2)==OVER))
    setto(getend(b+n),a+n);
   /*printf("====================\n");
   for(int lx=1;lx<=n;lx++)
    showline(lx);*/
  }
  for(int lx=1;lx<=n;lx++)
   showline(lx);
 }
 return 0;
}

UVA 100 3n+1 Problem

[無]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define gMax(a,b) ((a)>(b)) ? (a):(b)
int cb(int a)
{
    if(a==1)
        return 1;
    if(a%2==0)
        return cb(a/2)+1;
    else
        return cb(3*a+1)+1;
}
int main()
{
    int max=1;
    int a,ta;int b,tb;
    while(scanf("%d %d",&a,&b)!=EOF)
    {
        if(b<a){ta=b;tb=a;}else{ta=a;tb=b;}
        for(int lx=ta;lx<=tb;lx++)
            max=gMax(max,cb(lx));
        printf("%d %d %d\n",a,b,max);
        max=0;
    }
    return 0;
}