[Regionals 2012 :: Asia - Tokyo ]

2022-06-20 22:12:39

链接：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=566

A  uva live 6182 - Ginkgo
Numbers

题目意思：

规则：

1、<m, n>
· <x, y>
= <mx − ny, my + nx>

2、假设<m,n>是<p,q>的“除数”。则存在<x,y>，使得<m, n>
· <x, y>
= <p, q>.

3、假设<m, n>
· <x, y>
= <p, q>,
则 (m2 + n2)(x2 + y2)
= p2 + q2.

给定n,m，推断n,m是否恰好仅仅有<1,
0>, <0, 1>, <-1, 0>, <0,-1>, <m, n>,
<-n,m>,
<-m,-n>
and <n,-m>这8个“除数”。

解题思路：

简单数学。

实际上仅仅用依据第三条规则来就能够了，由于n*n+m*m<2000,仅仅用把n^2+m^2分解成两个约数的乘积，看这两个约数能否分别凑成两个数的平方和。

代码：

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

#define Maxn 22000

bool isc[Maxn];

bool isp[Maxn];

int pri[Maxn],cnt;

void init()

{

    memset(isc,false,sizeof(isc));

    for(int i=1;i*i<=20000;i++)

    {

        int a=i*i;

        isc[a]=true;

        for(int j=i;j*j+a<=20000;j++)

            isc[a+j*j]=true;

    }

    cnt=0;

    memset(isp,true,sizeof(isp));

    for(int i=2;i<=20000;i++)

    {

        if(isp[i])

        {

            pri[++cnt]=i;

            for(int j=i*2;j<=20000;j+=i)

                isp[j]=false;

        }

    }

}

int main()

{

    int t,n,m;

    scanf("%d",&t);

    init();

    while(t--)

    {

        scanf("%d%d",&n,&m);

        int sum=n*n+m*m;

        if(isp[sum])

        {

            printf("P\n");

            continue;

        }

        bool flag=true;

        for(int i=2;i*i<=sum;i++)

        {

            if(sum%i==0&&isc[i]&&isc[sum/i])

            {

                flag=false;

                break;

            }

        }

        if(flag)

            printf("P\n");

        else

            printf("C\n");

    }

    return 0;

}

option=com_onlinejudge&Itemid=8&category=566&page=show_problem&problem=4194">B uva live 6183 - Stylish

题目意思：

依据第一段代码圆括号、方括号、大括号的缩进法则。输出第二段代码缩进。

解题思路：

模拟

题目非常难看懂。但注意题目细节就能够看懂。但本题数据范围比較小。

先把全部情况都罗列出来，置为能够满足的，然后依据第一段的每一行的法则，排除不能满足的情况。

最后再对每一行，找出符合要求的RSC,假设有两种答案。则为非法。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

bool isc[22][22][22];

int n,m;

char sa[110];

int main()

{

    //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(scanf("%d%d",&n,&m)&&n+m)

   {

       memset(isc,true,sizeof(isc));

       int rr=0,ss=0,cc=0;

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

       {

           scanf("%s",sa);

           //printf("%s",sa);

           int p=0;

           while(sa[p]&&sa[p]=='.')

                p++;

           for(int j=1;j<=20;j++)

                for(int k=1;k<=20;k++)

                    for(int q=1;q<=20;q++)

                   {

                       if(j*rr+k*ss+q*cc!=p)

                       {

                           isc[j][k][q]=false;

                       }

                   }

          //printf("i:%d p:%d %c\n",i,p,sa[p]);

          while(sa[p])

          {

              if(sa[p]=='(')rr++;

              else if(sa[p]==')')rr--;

              else if(sa[p]=='[')ss++;

              else if(sa[p]==']')ss--;

              else if(sa[p]=='{')cc++;

              else if(sa[p]=='}')cc--;

              p++;

          }

       }

       scanf("%s",sa);

       printf("0");

       int p=0;

       rr=ss=cc=0;

       while(sa[p])

        {

          if(sa[p]=='(')rr++;

          else if(sa[p]==')')rr--;

          else if(sa[p]=='[')ss++;

          else if(sa[p]==']')ss--;

          else if(sa[p]=='{')cc++;

          else if(sa[p]=='}')cc--;

          p++;

        }

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

        {

            //printf("i:%d rr:%d ss:%d cc:%d %d\n",i,rr,ss,cc,isc[9][1][1]);

            //system("pause");

            int ans=-1;

            bool flag=true;

            for(int j=1;j<=20&&flag;j++)

                for(int k=1;k<=20&&flag;k++)

                    for(int q=1;q<=20&&flag;q++)

                   {

                       if(isc[j][k][q])

                       {

                           if(ans==-1)

                                ans=j*rr+k*ss+q*cc;

                           else if(j*rr+k*ss+q*cc!=ans)

                           {

                               flag=false;

                               break;

                           }

                       }

                   }

            if(!flag)

                printf(" -1");

            else

                printf(" %d",ans);

            scanf("%s",sa);

            p=0;

            while(sa[p])

              {

                  if(sa[p]=='(')rr++;

                  else if(sa[p]==')')rr--;

                  else if(sa[p]=='[')ss++;

                  else if(sa[p]==']')ss--;

                  else if(sa[p]=='{')cc++;

                  else if(sa[p]=='}')cc--;

                  p++;

              }

        }

        putchar('\n');

   }

    return 0;

}

option=com_onlinejudge&Itemid=8&category=566&page=show_problem&problem=4195">C uva live 6184 - One-Dimensional
Cellular Automaton

题目意思：

给一个t=0时刻，0-n-1的原始数据，求依据S(i, t +
1) = (A × S(i −
1, t)
+ B × S(i, t)
+ C × S(i +
1, t))
mod M,求出S(i,t).

解题思路：

高速幂

构造n*n的矩阵。

直接转移即可。

代码：

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

#define ll long long

#define Maxn 55

ll M,n,a,b,c,t;

struct Mar

{

    int row,col;

    ll s[Maxn][Maxn];

    void init(int a,int b)

    {

        row=a,col=b;

        memset(s,0,sizeof(s));

    }

};

Mar operator *(const Mar &a,const Mar &b)

{

    Mar res;

    res.init(a.row,b.col);

    for(int k=1;k<=a.col;k++)

    {

        for(int i=1;i<=res.row;i++)

        {

            if(a.s[i][k]==0)

                continue;

            for(int j=1;j<=res.col;j++)

            {

                if(b.s[k][j]==0)

                    continue;

                res.s[i][j]=(a.s[i][k]*b.s[k][j]+res.s[i][j])%M;

            }

        }

    }

    return res;

}

int main()

{

    while(scanf("%lld%lld%lld%lld%lld%lld",&n,&M,&a,&b,&c,&t))

    {

        if(!n&&!M&&!a&&!b&&!c&&!t)

            break;

        Mar ba;

        ba.init(n+2,n+2);

        ba.s[1][1]=b,ba.s[1][2]=c;

        for(int i=2;i<=n-1;i++)

        {

            ba.s[i][i-1]=a,ba.s[i][i]=b;

            ba.s[i][i+1]=c;

        }

        ba.s[n][n-1]=a,ba.s[n][n]=b;

        Mar ans;

        ans.init(n+2,1);

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

            scanf("%lld",&ans.s[i][1]);

        while(t)

        {

            if(t&1)

                ans=ba*ans;

            ba=ba*ba;

            t>>=1;

        }

        bool fi=true;

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

        {

            if(!fi)

                printf(" ");

            else

                fi=false;

            printf("%lld",ans.s[i][1]);

        }

        putchar('\n');

    }

    return 0;

}

option=com_onlinejudge&Itemid=8&category=566&page=show_problem&problem=4198">F uva live 6187 - Never
Wait for Weights

题目意思：

规则：

。 a b v 表示a物品比b物品重量少v

？a b    询问a物品比b物品少多少重量，假设不知道，则输出UNKNOWN

解题思路：

并查集。维护每一个节点与当前根的数值大小关系

查找完成后，该节点与根的关系就算出来了

合并时先查找，然后把根连过去。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 1100000

int fa[Maxn],n,m;

LL va[Maxn];

int Find(int x)

{

    if(fa[x]==x)

        return x;

    int fx=Find(fa[x]);

    va[x]+=va[fa[x]];

    return fa[x]=fx;

}

void Unio(int x,int y,LL v)

{

    int fx=Find(x),fy=Find(y);

    if(fx==fy)

        return ;

    va[fx]=v+va[y]-va[x];

    fa[fx]=fy;

}

int main()

{

    //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(scanf("%d%d",&n,&m)&&n+m)

   {

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

            fa[i]=i;

       memset(va,0,sizeof(va));

       char sa[10];

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

       {

           int a,b;

           LL c;

           scanf("%s",sa);

           if(*sa=='!')

           {

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

               Unio(a,b,c);

           }

           else

           {

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

               int fa=Find(a),fb=Find(b);

               if(fa!=fb)

                    printf("UNKNOWN\n");

               else

                    printf("%lld\n",va[a]-va[b]);

           }

       }

   }

    return 0;

}

option=com_onlinejudge&Itemid=8&category=566&page=show_problem&problem=4201">I uva live 6190 - Beautiful
Spacing

题目意思：

把已知长度的n个单词，放到宽度为w的格子中，要求单词的顺序不能变，且每行的开头格子和结尾格子必须有单词，两个单词中间至少有一个空格，求单词之间空格数的最大值最小。

解题思路：

二分+思维

二分答案，推断答案是否合理。dp[i]表示第i个结尾是否可行，对每一个可行。推出后面的是否可行。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 51000

bool dp[Maxn];

int n,w;

LL sum[Maxn];

bool iscan(int m)

{

    if(sum[n]+n-1<=w)

        return true;

    memset(dp,0,sizeof(dp));

    dp[0]=1;

    int la=0;

    for(int i=0;i<=n-2;i++)

    {

        if(!dp[i])

            continue;

        for(int j=max(i+1,la+1);j<=n;j++)

        {

            if(sum[j]-sum[i]+j-i-1>w) //最小的不行

                break;

            if(sum[j]-sum[i]+(j-i-1)*m<w) //最大要超过才干可行

                continue;

            dp[j]=true;

            la=j;

            if(sum[n]-sum[j]+n-j-1<=w)

                return true;

        }

    }

    return false;

}

int main()

{

    //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(scanf("%d%d",&w,&n)&&w+n)

   {

       sum[0]=0;

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

       {

           LL temp;

           scanf("%lld",&temp);

           sum[i]=sum[i-1]+temp;

       }

       int l=1,r=w,m,ans;

       while(l<=r)

       {

           m=(l+r)>>1;

           if(iscan(m))

           {

               ans=m;

               r=m-1;

           }

           else

                l=m+1;

       }

       printf("%d\n",ans);

   }

    return 0;

}
上一篇：《Effective Modern C++》翻译--简单介绍


下一篇：FastJson反序列化漏洞