藍雪的Online Judge日誌

2013年12月7日星期六

Codeforce B. Berland Bingo

[IMPLEMENT]

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
int main()
{
    bool tb[100][100];
    int n;scanf("%d",&n);
    memset(tb,false,sizeof(tb));
    for(int lx=0;lx<n;lx++)
    {
        int k,I;scanf("%d",&k);
        while(k--)
        {
            scanf("%d",&I);
            tb[lx][I-1]=true;
        }
    }
    for(int lx=0;lx<n;lx++)
    {
        bool OK=true;
        for(int ly=0;(ly<n)&&OK;ly++)
        {
            if(ly==lx) continue;
            bool child=true;
            for(int lz=0;(lz<100)&&child;lz++)
                if(tb[ly][lz])
                    child=tb[lx][lz];
            if(child)
                OK=false;
        }
        if(OK)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

2013年12月4日星期三

Codeforce 235A A. LCM Challenge

[MATH]
恩，就那幾種

#include<stdio.h>
#include<algorithm>
int main()
{
    int n;scanf("%d",&n);
    if(n<=2)
        printf("%d\n",n);
    else if(n&1)
        printf("%d\n",n*(n-1)*(n-2));
    else
    {
        if(n%3==0)
            printf("%d\n",(n-1)*(n-2)*(n-3));
        else
            printf("%d\n",n*(n-1)*(n-3));
    }
    return 0;
}

2013年12月3日星期二

TIOJ 1092 A.跳格子遊戲

[TOPOSORT]

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100011
#define V 10010
using namespace std;
struct Edge{int a,b;};
bool operator<(Edge e1,Edge e2)
{
    if(e1.a<e2.a)
        return true;
    else if(e1.a==e2.a)
        return (e1.b<e2.b);
    else
        return false;
}
int n,ecnt;
Edge G[N];
int andS[V];
int andE[V];
//TOPO SORT
int Stamp[V];
vector<int> Stk;
bool Visited[V];
void Toposort()
{
    int Time=0;
    Stk.clear();Stk.push_back(1);
    memset(Visited,false,sizeof(Visited));
    while(Stk.size())
    {
        int get=Stk[Stk.size()-1];
        if(Visited[get])
        {
            Time++;
            Stamp[Time]=get;
            Stk.pop_back();
            continue;
        }
        Visited[get]=true;
        if(get<n)
        {
            for(int lx=andS[get];(lx<=andE[get]);lx++)
                if((Visited[G[lx].b]==false))
                    Stk.push_back(G[lx].b);
        }
    }
    return;
}
bool Status[V];
char NAME[2][10]={"Mimi","Moumou"};
int main()
{
    while(scanf("%d %d",&n,&ecnt)&&(n+ecnt))
    {
        memset(andS,-1,sizeof(andS));
        memset(andE,-1,sizeof(andE));
        memset(Status,false,sizeof(Status));
        int i1,i2;
        for(int lx=0;lx<ecnt;lx++)
        {
            scanf("%d %d",&i1,&i2);
            G[lx].a=i1;G[lx].b=i2;
        }
        char ss[40];
        scanf("%s",ss);
        sort(G,G+ecnt);
        for(int lx=0;lx<ecnt;lx++)
        {
            if(andS[G[lx].a]==-1) andS[G[lx].a]=lx;
            andE[G[lx].a]=lx;
        }
        Toposort();
        Status[n]=true;
        for(int lx=2;lx<=n;lx++)
        {
            bool S=false;
            for(int ly=andS[Stamp[lx]];(ly<=andE[Stamp[lx]]);ly++)
                S=(S||Status[G[ly].b]);
            Status[Stamp[lx]]=1-S;
        }
        if(strlen(ss)==4)
            printf("%s\n",NAME[1-Status[1]]);
        else
            printf("%s\n",NAME[Status[1]]);
    }
    return 0;
}

2013年12月2日星期一

UVA 200 Rare Order

[TOPO SORT]

#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
int Tb[26][26];
bool Exist[26];
int Time[26];
int tt=0;
void dfs(int a)
{
    if(Time[a]) return;
    //printf("DFS:%d\n",a);
    for(int lx=0;lx<26;lx++)
        if((Exist[lx])&&(Tb[a][lx]==-1))
            dfs(lx);
    tt++;
    Time[a]=tt;
    for(int lx=0;lx<26;lx++)
        if((Exist[lx])&&(Tb[lx][a]==1))
            dfs(lx);
}
int main()
{
    memset(Tb,0,sizeof(Tb));
    memset(Exist,false,sizeof(Exist));
    memset(Time,0,sizeof(Time));
    char ss[40];scanf("%s",ss);
    char aa[40];
    for(int lx=0;ss[lx]!='\0';lx++)
        Exist[ss[lx]-'A']=true;
    while(scanf("%s",aa)!=EOF)
    {
        if((aa[0]=='#')&&(aa[1]=='\0')) break;

        for(int lx=0;(ss[lx]!='\0')&&(aa[lx]!='\0');lx++)
        {
            if(aa[lx]!=ss[lx])
            {
                Tb[aa[lx]-'A'][ss[lx]-'A']=1;
                Tb[ss[lx]-'A'][aa[lx]-'A']=-1;
                break;
            }
        }
        strcpy(ss,aa);
        for(int lx=0;ss[lx]!='\0';lx++)
            Exist[ss[lx]-'A']=true;
    }
    int cnt=0;
    for(int lx=0;lx<26;lx++)
        if(Exist[lx]){cnt++;dfs(lx);}
    char str[27];
    for(int lx=0;lx<26;lx++)
    {
        if(Exist[lx])
        {
            //printf("%c:%d\n",lx+'A',Time[lx]);
            str[cnt-Time[lx]]=lx+'A';
        }
    }
    str[cnt]='\0';
    printf("%s\n",str);
    return 0;
}

HOJ 003 童話故事

[二分搜]

#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long int
#define MM 1000000
#define MAX(a,b) (((a)>(b)) ? (a):(b))
LL N;
LL VAL[MM];
LL DIS[MM];
bool Check(LL a)
{
    //printf("Check(%I64d)\n",a);
    LL Center=0;
    bool OK=true;
    for(int lx=0;lx<N;lx++)
        if(VAL[lx]>=a)
            Center+=MAX(VAL[lx]-a-DIS[lx],0);

    for(int lx=0;(lx<N)&&OK;lx++)
    {
        if(VAL[lx]<a)
            Center-=a-VAL[lx]+DIS[lx];
        OK=(Center>=0);
    }
    return OK;
}
int main()
{
    scanf("%I64d",&N);
    LL min=-1,max=0,mid;
    for(LL lx=0;lx<N;lx++)
    {
        scanf("%I64d %I64d",&DIS[lx],&VAL[lx]);
        if((min==-1)||(min>VAL[lx])) min=VAL[lx];
        max+=VAL[lx];
    }
    max/=N;
    while(min<max)
    {
        //printf("min=%I64d max=%I64d\n",min,max);
        if(min==max-1)
        {
            if(Check(max))
                min=max;
            break;
        }
        mid=(min+max)>>1;
        if(Check(mid))
            min=mid;
        else
            max=mid-1;
    }
    printf("%I64d\n",min);
    return 0;
}

TIOJ 1288 D.三角旅行

[DP]

#include<stdio.h>
#include<string.h>
#define max(a,b) (((a)>(b)) ? (a):(b))
int main()
{
    int TB[102][102];
    int OT[102][102];
    int N;
    memset(TB,0,sizeof(TB));
    memset(OT,0,sizeof(OT));
    scanf("%d",&N);
    for(int lx=1;lx<=N;lx++)
        for(int ly=1;ly<=lx;ly++)
            scanf("%d",&TB[lx][ly]);
    OT[1][1]=TB[1][1];
    for(int lx=2;lx<=N;lx++)
        for(int ly=1;ly<=lx;ly++)
            OT[lx][ly]=max(OT[lx-1][ly-1],OT[lx-1][ly])+TB[lx][ly];
    int m=0;
    for(int lx=1;lx<=N;lx++)
        m=max(m,OT[N][lx]);
    printf("%d\n",m);
    return 0;
}

UVA 10162 Last Digit

[數學]
考慮

應該會具有周期。

#include<stdio.h>
#include<string.h>
int main()
{
    int a[101]; a[0]=0;
    for(int lx=1;lx<=100;lx++)
    {
        int sum=0,r=1;
        for(int y=1;y<=lx;y++)
            r=(r*lx)%10;
        a[lx]=(a[lx-1]+r)%10;
    }
    char I[103];
    while(scanf("%s",I)!=EOF)
    {
        int sl=strlen(I);
        if(I[0] == '0' && I[1] == '\0') break;
        int n;
        if(sl==1) n=I[0]-'0';
        if(sl>=2) n=(I[sl-2]-'0')*10+I[sl-1]-'0';
        printf("%d\n", (a[n%100]));
    }
    return 0;
}

2013年12月7日 星期六

2013年12月4日 星期三

2013年12月3日 星期二

2013年12月2日 星期一

2013年12月7日星期六

2013年12月4日星期三

2013年12月3日星期二

2013年12月2日星期一