Codeforces Round #189 (Div. 2)

第一题：基本题，判断mod 1000，mod 100.，mod 10是不是等于144、14、1，直到为0

代码如下：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

const int N=10001;

typedef long long LL;

int main()

{

    int i,j,t,T,n;

    int a[3]={144,14,1};

    while(cin>>n)

    {

        int flag=0;

        while(n)

        {

            if(n%1000==144)

                n/=1000;

            else if(n%100==14)

                n/=100;

            else if(n%10==1)

                n/=10;

            else{

            flag=1;

            break;

            }

        }

        if(flag==0)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return 0;

}

第二题：给你一些单向路径。

"1 x y"-----插入

"2 a b"----判断

让你判断能否从a到b。

用深搜，开始的时候vis标记每次做完回溯都修改标记，结果超时了，最后有人说回溯的时候不需要修改，

自己想了想，好像是这样的，因为是单向的，到达一个点了之后不管后面怎样都还是可以到这个点。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef long long LL;

const int N=105;

int parent[N];

int x[N],y[N];

int m,flag;

int a,b,c;

int vis[N];

void dfs(int t)

{

    vis[t]=1;

    if(flag==1)

        return ;

    if(t==c)

    {

        flag=1;

        return ;

    }

    for(int i=1;i<=m;i++)

    {

        if(vis[i]==1)

            continue;

        if(x[t]>x[i]&&x[t]<y[i]||y[t]>x[i]&&y[t]<y[i])

        {

            dfs(i);//这个地方不能要 vis[i]=0; 要了就TLE

        }

    }

}

int main()

{

    int i,j,t,T,n,xx;

    scanf("%d",&T);

    m=0;

    while(T--)

    {

        scanf("%d%d%d",&a,&b,&c);

        if(a==1)

        {

            m++;

            x[m]=b;

            y[m]=c;

        }

        if(a==2)

        {

            flag=0;

            memset(vis,0,sizeof(vis));

            dfs(b);

            if(flag==1)

                printf("YES\n");

            else

                printf("NO\n");

        }

    }

    return 0;

}

第三题：打表找规律。

从后往前走，

当遇见1的时候，last=(last*2+a4[j])%II; temp=last;

当遇见0的时候，last=(last*2)%II;

代码如下：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef long long LL;

const int N=105;

const LL II=1000000007;

char s[N];

LL a4[N];

int main()

{

    int i,j,t,T,n,xx;

    a4[0]=1;

    for(i=1;i<N;i++)

    {

        a4[i]=(a4[i-1]*4)%II;

        //printf("%lld\n",a4[i]);

    }

    scanf("%s",s);

    int len=strlen(s);

    int k=0;

    while(k<len&&s[k]=='0')

        k++;

    if(k==len)

    {

        printf("0\n");

        return 0;

    }

    LL last=0,temp=0;

    for(i=len-1,j=0;i>=k;i--,j++)

    {

        if(s[i]=='1')

        {

            last=(last*2+a4[j])%II;

            temp=last;

        }

        else

        {

            last=(last*2)%II;

        }

    }

    for(i=k-1;i>=0;i--)

        temp=(temp*2)%II;

    printf("%lld\n",temp);

    return 0;

}

第四题：

未完待续…………

第五题：

未完待续…………

秒客网

Codeforces Round #189 (Div. 2)

相关文章