藍雪的Online Judge日誌

2013年10月16日星期三

STEP5 0047 : Ch特別篇-1.妹妹

[IMPLEMENT]
怎麼到處都是Unsigned Long Long >"<

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#define N 1000000
#define ULLI unsigned long long int
ULLI d[N+1];
ULLI sum[N+1];
int main()
{
    memset(d,0,sizeof(d));
    sum[0]=0;
    for(ULLI lx=1;lx<=N;lx++)
        for(ULLI ly=1;ly*lx<=N;ly++)
            d[lx*ly]+=lx;
    for(int lx=1;lx<=N;lx++)
        sum[lx]=sum[lx-1]+d[lx];
    int T;scanf("%d",&T);
    for(int lT=1;lT<=T;lT++)
    {
        int a,b;scanf("%d %d",&a,&b);
        printf("%I64u\n",sum[b]-sum[a-1]);
    }
    return 0;
}

STEP5 0006 Ch1-3.陷阱

[DP?]
應該算DP 反正就是每次搬過去後其實不需要重算的概念

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#define ULLI  long long int
ULLI max(ULLI a,ULLI b){if(a>b)return a;return b;}
ULLI min(ULLI a,ULLI b){if(a<b)return a;return b;}
ULLI a[1000000];
int main()
{
    int T;scanf("%d",&T);
    for(int lT=1;lT<=T;lT++)
    {
        int n;scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(int lx=0;lx<n;lx++)
            scanf("%I64u",&a[lx]);
        ULLI spend=0;ULLI sum=0;
        for(int lx=0;lx<n;lx++)
        {
            sum+=a[lx];
            if(sum<=0)
            {
                spend+=-sum+1;
                sum=1;
            }
        }
        ULLI mm=spend;
        for(int lx=n-1;lx>0;lx--)
        {
            if(a[lx]<=0)
                spend+=-a[lx];
            else
                spend=max(0,spend-a[lx]);
            mm=min(spend+n-lx,mm);
        }
        printf("%I64u\n",mm);
    }
    return 0;
}

2013年10月15日星期二

TIOJ 1043 F.名偵探蚵男

[DP]
久違的TIOJ

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#define ULLI unsigned long long int
using namespace std;
vector<int> stock;
ULLI dp[10001][100];
ULLI getdp(int a,int b)
{
    if((a<0)||(b<0))
        return 0;
    if(a==0)
        return 1;
    if(b==0)
        return (a%stock[0]==0);
    return dp[a][b];
}
int main()
{
    int n,p;
    while(scanf("%d %d",&n,&p)!=EOF)
    {
        stock.clear();
        memset(dp,0,sizeof(dp));
        if(!n&&!p)
            break;
        int inp;
        for(int lx=1;lx<=n;lx++)
        {
            scanf("%d",&inp);
            if(inp<=p)
                stock.push_back(inp);
        }
        for(int lx=0;lx<stock.size();lx++)
            for(int lp=0;lp<=p;lp++)
                dp[lp][lx]=getdp(lp,lx-1)+getdp(lp-stock[lx],lx);
        printf("%I64u\n",dp[p][stock.size()-1]);
    }
    return 0;
}

[閒] Brainf*ck 直譯器

第一次試寫Brainf*ck直譯器
大致上最需要注意的就是while迴圈需要用一個stack去記位置就OK了。(雖然說先做預處理也是可以啦....)

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<vector>
 6 #define N 10000
 7 
 8 using namespace std;
 9 int main()
10 {
11     char cmd[N];
12     scanf("%s",cmd);
13     int sl=strlen(cmd);
14 
15     int cmdptr=0;
16 
17     char mry[N];    memset(mry,0,sizeof(mry));
18     int mryptr=0;
19 
20     vector <int>outerwhile;
21     while(cmdptr<sl)
22     {
23         printf("[%c]",cmd[cmdptr]);
24         switch (cmd[cmdptr])
25         {
26             case '+':
27                 mry[mryptr]++;
28                 cmdptr++;
29                 break;
30             case '-':
31                 mry[mryptr]--;
32                 cmdptr++;
33                 break;
34             case '>':
35                 mryptr++;
36                 mryptr%=N;
37                 cmdptr++;
38                 break;
39             case '<':
40                 mryptr=(mryptr+N-1)%N;
41                 cmdptr++;
42                 break;
43             case '.':
44                 putchar(mry[mryptr]);
45                 cmdptr++;
46                 break;
47             case ',':
48                 mry[mryptr]=getchar();
49                 cmdptr++;
50                 break;
51             case '[':
52                 if(mry[mryptr])
53                 {
54                     outerwhile.push_back(cmdptr);
55                     cmdptr++;
56                 }
57                 else
58                 {
59                     int c=0;
60                     while(c>=0)//c||(cmd[cmdptr]!=']'))
61                     {
62                         cmdptr++;
63                         if(cmd[cmdptr]=='[')
64                             c++;
65                         else if(cmd[cmdptr]==']')
66                             c--;
67                     }
68                     cmdptr++;
69                 }
70                 break;
71             case ']':
72                 cmdptr=outerwhile.at(outerwhile.size()-1);
73                 outerwhile.pop_back();
74                 break;
75         }
76     }
77     return 0;
78 }

2013年10月13日星期日

STEP5 0106 2項式展開

反正N<64 那就XDD

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
long long int vec[65][65];
void Print(int v)
{
 if(v==1)
  printf("1+x\n");
 else if(v==0)
  printf("1\n");
 else
 {
  printf("1+%dx",v);
  for(int lx=2;lx<v;lx++)
   printf("+%I64dx^%d",vec[v][lx],lx);
  printf("+x^%d\n",v);
 }
}
int main()
{
 memset(vec,0,sizeof(vec));
 vec[0][0]=1;
 vec[1][0]=1;
 vec[1][1]=1;
 for(int lx=2;lx<=62;lx++)
 {
  vec[lx][0]=1;
  for(int ld=1;ld<=lx;ld++)
   vec[lx][ld]=vec[lx-1][ld]+vec[lx-1][ld-1];
 }
 int inp;
 while(scanf("%d",&inp)!=EOF)
  Print(inp);
 return 0;
}

STEP5 0011 Ch1-8.白之夢

[機率]
好像是機率問題@@?

#include<algorithm>
#include "special_0011.h"
#define max(a,b) (a>b) ? (a):(b)
int main()
{
 int T=Start_The_Loli_Dream();
 int lT;
 for(lT=1;lT<=T;lT++)
 {
  int N=Count_How_Many_Loli();
  int n=N/3+1;
  int mm=0;
  for(int lx=1;lx<=n;lx++)
  {
   int a=Get_Loli_Moeness();
   mm=max(mm,a);
  }
  bool IsChoose;
  for(int lx=n+1;lx<=N;lx++)
  {
   if(Get_Loli_Moeness()>mm)
   {
    You_Choose_This_Loli();
    break;
   }
  }
  if(IsChoose==false)
   You_Choose_This_Loli();
 }
 return 0;
}

STEP5 0005 Ch1-2.梗賤橋

[質數篩子]
只要用質數的篩子觀念處理即可。
複雜度是 nlg(lgn)
重點在於欲處理後的判斷"至否為質數"的三個條件

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<vector>
#define N 1000000
bool seive[N+1];
int nptr[N+1];
int RES[N+1];
std::vector<int>prime;
int main()
{
 memset(seive,true,sizeof(seive));
 seive[1]=false;
 for(int lx=2;lx<=N;lx++)
 {
  if(seive[lx])
  {
   prime.push_back(lx);
   for(int ly=2;ly*lx<=N;ly++)
    seive[lx*ly]=false;
  }
 }
 for(int ly=1;ly<=N;ly++)
  nptr[ly]=ly;
 for(int lx=0;lx<prime.size();lx++)
 {
  int tmp;
  if((N/prime[lx])<=1)
   break;
  for(int ly=(N/prime[lx]);ly>=2;ly--)
  {
   tmp=nptr[prime[lx]*ly];
   nptr[prime[lx]*ly]=nptr[prime[lx]*(ly-1)];
   nptr[prime[lx]*(ly-1)]=tmp;
  }
 }
 for(int lx=1;lx<=N;lx++)
  RES[nptr[lx]]=lx;
 free(nptr);
 //for(int lx=1;lx<=N;lx++)
 // assert((RES[lx]>0)&&((RES[lx]>=lx)||seive[RES[lx]]));
 int nn,M;
 int T,lT;scanf("%d",&T);
 for(lT=1;lT<=T;lT++)
 {
  scanf("%d %d",&nn,&M);
  if((RES[M]>nn)||seive[RES[M]]||(RES[M]<M))
   printf("Geng Jian malheureux roi mauvaise!!\n");
  else
   printf("%d\n",RES[M]);
 }
 return 0;
}

2013年10月16日 星期三

2013年10月15日 星期二

2013年10月13日 星期日

2013年10月16日星期三

2013年10月15日星期二

2013年10月13日星期日