Codeforces ラウンド #271 (ディビジョン 2)_html/css_WEB-ITnose

質問A: データ量が少なすぎるので、暴力的な置き換えだけで十分です。 。 。 。

#include <iostream>#include <algorithm>#include <string>#include <map>#include <vector>#include <string.h>using namespace std;typedef long long ll;int arr[100010];int cnt[100010];int col[100010];int n,a,b;char c;string s = "qwertyuiopasdfghjkl;zxcvbnm,./";int main(){    while(cin>>c)    {        string input;        cin>>input;        if(c=='L')        {            string output="";            for(int i=0;i<input.length();i++)            {                for(int j=0;j<s.length();j++)                {                    if(input[i]==s[j])                    {                        output+=s[j+1];                        break;                    }                }            }            cout<<output<<endl;        }        else        {            string output="";            for(int i=0;i<input.length();i++)            {                for(int j=0;j<s.length();j++)                {                    if(input[i]==s[j])                    {                        output+=s[j-1];                        break;                    }                }            }            cout<<output<<endl;        }    }    return 0;}

質問 B: データは 100000 しかないので、マップを直接使用して各ポイントの間隔識別を記録できます。

#include <iostream>#include <algorithm>#include <string>#include <map>#include <vector>#include <string.h>using namespace std;typedef long long ll;int arr[100010];int cnt[100010];int col[100010];int n,a,b;char c;string s = "qwertyuiopasdfghjkl;zxcvbnm,./";int main(){    while(cin>>n)    {        int all = 0;        map<int,int> m;        for(int i=1;i<=n;i++)        {            cin>>arr[i];            for(int j=all+1;j<=all+arr[i];j++)                m[j]=i;            all+=arr[i];                    }        int k;        cin>>k;        for(int i=0;i<k;i++)        {            int q;            cin>>q;            cout<<m[q]<<endl;        }    }    return 0;}

質問C: 各点は最大 3 回回転できるため、回転の可能性を直接暴力的に列挙し、最終的に正方形であるかどうかを判断します。

#include <iostream>  #include <cstdio>  #include <algorithm>  #include <cstring>  const int inf=9999999;  using namespace std;  struct node  {      int x;      int y;  }p[5][5],home[5];  long long d[8];  long long dis(node a,node b)//距离的平方  {      return (long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y);  }  void solve()  {      int ans=inf;      for(int i=0;i<4;i++)      {          for(int j=0;j<4;j++)          {              for(int k=0;k<4;k++)              {                  for(int l=0;l<4;l++)                  {                      d[0]=dis(p[i][0],p[j][1]);//四边距离的平方                      d[1]=dis(p[j][1],p[k][2]);                      d[2]=dis(p[k][2],p[l][3]);                      d[3]=dis(p[l][3],p[i][0]);                      d[4]=dis(p[i][0],p[k][2]);//对角线的平方                      d[5]=dis(p[j][1],p[l][3]);                        sort(d,d+6);                      if(d[0]==0)                      continue;                      else if(d[0]==d[1]&&d[1]==d[2]&&d[2]==d[3]&&2*d[3]==d[4]&&d[4]==d[5])//判断是否为正方形                      {                          ans=min(ans,i+j+k+l);                      }                  }              }          }      }      if(ans!=inf)      printf("%d\n",ans);      else      printf("-1\n");  }  int main()  {      int t;      scanf("%d",&t);      while(t--)      {          for(int i=0;i<4;i++)          {              scanf("%d%d",&p[0][i].x,&p[0][i].y);              scanf("%d%d",&home[i].x,&home[i].y);              int x=p[0][i].x-home[i].x;              int y=p[0][i].y-home[i].y;                p[1][i].x=home[i].x-y;//逆时针旋转90度              p[1][i].y=home[i].y+x;                p[2][i].x=home[i].x-x;              p[2][i].y=home[i].y-y;                p[3][i].x=home[i].x+y;              p[3][i].y=home[i].y-x;          }          solve();      }      return 0;  }  

質問 D: i 番目の位置が W ではないことを示すには dp[i][0] を使用し、i 番目の位置が W であることを示すには dp[i][1] を使用します。ちなみに、伝達方程式は簡単に理解できます。詳細についてはコードを参照してください。dp[0] での初期化を覚えておいてください。