AtCoder Regular Contest 153 A-B题解

2023/1/15 C++ 算法竞赛 题解 AtCoder Regular Contest 153

小年快乐😊！

A. AABCDDEFE

题面

记个数，在纸上写一写就明白怎么搞了.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    n-=1;
    int a=n/100000+1;
    int a1=n%100000/1000;
    int b=n%1000/100;
    int c=n%100/10;
    int d=n%10;
    ll num=(10*a+a)*10000000+a1*100000+(10*b+b)*1000+100*c+c+10*d;
    cout<<num<<'\n';
    return 0;
}

B. Grid Rotations

题面

比赛时候只能想出O(Q*H*W)的算法😥，想用map优化来着，可惜还是没能做出思维的突破(单独考虑横纵坐标).

赛后补题
看了Editorial后发现这题真的很巧妙.

按着他的思路写了一份代码，AC了.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+1e4;
int H,W;
char a[N];
int x[N];
int _x[N];
int y[N];
int _y[N];
inline int num(int x,int y)
{
    return (x-1)*W+y;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>H>>W;
    for(int i=1;i<=H;i++)
    {
        x[i]=x[i+H]=i;
        _x[i]=_x[i+H]=H+1-i;
    }
    for(int j=1;j<=W;j++)
    {
        y[j]=y[j+W]=j;
        _y[j]=_y[j+W]=W+1-j;
    }
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
            cin>>a[num(i,j)];
    }
    int Q;
    cin>>Q;
    int x_=0,y_=0;
    int x__,y__;
    for(int i=1;i<=Q;i++)
    {
        cin>>x__>>y__;
        if(i%2==1)
            x_=(x_+x__)%H,y_=(y_+y__)%W;
        else
            x_=(x_+H-x__)%H,y_=(y_+W-y__)%W;
    }
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(Q%2==0)
                cout<<a[num(x[i+x_],y[j+y_])];
            else
                cout<<a[num(_x[H+i-x_],_y[W+j-y_])];
        }
        cout<<'\n';
    }
    return 0;
}
img_show