Codeforces Round #271 (Div. 2)_html/css_WEB-ITnose

Question A: Because the amount of data is too small, just violent replacement is enough. . . .

#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;}

Question B: The data is only 100000, so you can directly use a map to record the interval identification of each point.

#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;}

Question C: Directly violently enumerate the possibility of rotation, because each point can rotate up to 3 times, and finally judge whether it is a square.

#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;  }  

Question D: Use dp[i][0] to indicate that the i-th position is not W, and dp[i][1] to indicate that the i-th position is W. In this way, the transfer equation is easy to come out. See the code for details. Remember the initialization when dp[0]

#include <iostream>#include <algorithm>#include <string>#include <map>#include <vector>#include <string.h>using namespace std;typedef long long ll;ll dp[100010][2];ll sum[100010];int cnt[100010];int col[100010];int n,a,b,t,k;const int mod = 1e9+7;char c;string s = "qwertyuiopasdfghjkl;zxcvbnm,./";int main(){    while(cin>>t>>k)    {        memset(dp,0,sizeof(dp));        dp[0][0]=1;        dp[0][1]=0;        for(int i=1;i<=100000;i++)        {            dp[i][0] = (dp[i][0]+dp[i-1][0]+dp[i-1][1])%mod;            if(i-k>=0)            {                dp[i][1] = (dp[i][1]+dp[i-k][0]+dp[i-k][1])%mod;            }        }        sum[0] = 0;        for(int i=1;i<=100000;i++)            sum[i] = (sum[i-1]+dp[i][0]+dp[i][1])%mod;        while(t--)        {            int a,b;            cin>>a>>b;            ll ans = sum[b]-sum[a-1];            if(ans<0)                ans+=mod;            cout<<ans<<endl;        }    }    return 0;}