AtCoder Beginner Contest 336

所有代码都在如下模板中运行

#include<bits/stdc++.h>
using namespace std;
namespace gza{
	#define int long long
	#define pb push_back
	#define MT int TTT=R;while(TTT--)
	#define pc putchar
	#define R read()
	#define fo(i,a,b) for(int i=a;i<=b;i++)
	#define rep(i,a,b) for(int i=a;i>=b;i--)
	#define m1(a,b) memset(a,b,sizeof a)
	namespace IO
	{
		inline int read()
		{
		    int x=0;
		    char ch=getchar();
		    bool f=0;
		    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
		    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		    if(f) x=-x;
		    return x;    
		}
		template<typename T> inline void write(T x)
		{
		    if(x<0) pc('-'),x=-x;
		    if(x>9) write(x/10);
		    pc(x%10+'0');
		}
	};
	using namespace IO;
	
	void main(){
		
	}
}
signed main(){
	gza::main();
}

A

简单模拟。

void main(){
    int n=R;
    pc('L');
    fo(i,1,n) pc('o');
    pc('n'),pc('g');
}

B

有现成的函数，谁不用啊。

write(__builtin_ctz(R));

C

可以发现每一位是偶数等价于每一位 \(\leq 4\)。

类似于五进制一一对应了。

void main(){
    int n=R-1;
    if(!n) puts("0");
    else
    {
        string s="";
        while(n) s.pb(n%5*2+'0'),n/=5;
        reverse(s.begin(),s.end());
        cout<<s;
    }
}

D

求出以一个点开头和结尾的半个金字塔序列的最大的 \(k\)。

就是说，求出 \(1,2,3,\cdots,k\) 这一段的最大长度，和 \(k,k-1,\cdots,1\) 这一段的最大长度。

先考虑第一个，因为第二个几乎同理。有一个朴素的 dp，有转移式：

\(f_i=\min(f_{i-1}+1,a_i)\)

转移式很巧妙，仔细想一想，可以直接继承 \(f_{i-1}\) 过来，但是 \(a_i\) 对于 \(k\) 做出了限制。

const int N=2e5+10;
int n=R,ans;
int a[N];
int f[N],g[N];
void main(){
    fo(i,1,n) a[i]=R;
    fo(i,1,n) f[i]=min(f[i-1]+1,a[i]);
    rep(i,n,1) g[i]=min(g[i+1]+1,a[i]);
    fo(i,1,n) ans=max(ans,min(f[i],g[i]));
    write(ans);
}

E

枚举数字和。

考虑一个数位 dp，记录 \(f_{x,s,sum,lim}\) 表示目前考虑到第 \(x\) 位，还剩下 \(s\) 的数字和可以用，当前数字和取模后为 \(sum\)，是否至今还贴着最高位。

转移是显然的，但是记得记忆化，记得考虑一些边界问题。

const int N=30,M=130;
int n,cnt;
int a[N];
int f[N][M][M];
int calc(int x,int sum,int st,int lim,int mod)
{
    if(x>cnt&&sum==0) return 0;
    if(x>cnt) return st==0&&sum==mod?1:0;
    if(!lim&&f[x][sum][st]!=-1) return f[x][sum][st];
    int res=0,top=lim?a[cnt-x+1]:9ll;
    for(int i=0;i<=top;i++) res+=calc(x+1,sum+i,(st*10+i)%mod,lim&&i==top,mod);
    return lim?res:f[x][sum][st]=res;
}
int solve(int x)
{
    while(x) a[++cnt]=x%10,x/=10;
    int ans=0;
    fo(i,1,9*cnt) m1(f,-1),ans+=calc(1,0,0,1,i);
    return ans;
}
void main(){
    n=R;
    write(solve(n));
}

F

考虑折半搜索，预处理出起始状态 10 步以内可以走到的状态，以及目标状态 10 步以内可以走到的状态。

使用 map 记录一下状态对应的步数，不难实现，但是我写了 30min。

int n,m;
vector<vector<int> > v,goal;
map<vector<vector<int> >,int> ma,mb;
vector<vector<int> > rotate(vector<vector<int> > vec,int dx,int dy)
{
    fo(i,0,(n-2)/2) fo(j,0,m-2) swap(vec[i+dx][j+dy],vec[n-2-i+dx][m-2-j+dy]);
    if(n%2==0)
    {
        int i=(n-2)/2;
        fo(j,0,(m-2)/2) swap(vec[i+dx][j+dy],vec[n-2-i+dx][m-2-j+dy]);
    }
    return vec;
}
void dfs(map<vector<vector<int> >,int>& M,vector<vector<int> > vec,int step)
{
    vector<vector<int> > backup=vec;
    if(!M.count(vec)) M[vec]=step;
    else M[vec]=min(M[vec],step);
    if(step==10) return;
    vec=rotate(vec,0,0);
    dfs(M,vec,step+1);
    vec=backup;

    vec=rotate(vec,0,1);
    dfs(M,vec,step+1);
    vec=backup;

    vec=rotate(vec,1,0);
    dfs(M,vec,step+1);
    vec=backup;

    vec=rotate(vec,1,1);
    dfs(M,vec,step+1);
    vec=backup;

}
void main(){
    n=R,m=R;
    fo(i,0,n-1)
    {
        v.pb(vector<int>());
        fo(j,0,m-1) v[i].pb(R);
    }
    fo(i,0,n-1)
    {
        goal.pb(vector<int>());
        fo(j,0,m-1) goal[i].pb(m*i+j+1);
    }
    dfs(ma,v,0),dfs(mb,goal,0);
    int ans=2e9;
    for(auto i:ma) if(mb.count(i.first)) ans=min(ans,i.second+mb[i.first]);
    write(ans>20?-1:ans);
}

代码可能有点混乱邪恶，看着玩玩就好。

G

是道黑，不知道将来会不会补。