C - Doubled
传送门
题目意思很简单:就是问1-N中有多少个像12341234,1212,3434这样的折叠的数又是解释跟没解释似的
N最大是10^12,其实我们直接暴力一半 1 0 6 10^6 106就行了。将每一个数构造出它的折叠数,看是不是在1-N以内就行了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll rebuild(ll x)
{
ll num=1,y=x;
while(y)
{
num*=10;//num其实就是看这个数有多少位
y/=10;
}
return x*num+x;
}
int main()
{
ll n,ans=0;
cin>>n;
for(ll i=1;i<=1000000;i++)
{
if(rebuild(i)<=n) ans++;
else break;
}
cout<<ans<<endl;
return 0;
}
D - Hanjo
传送门
其实这道题跟以前一道状压DP是一样的。
但不同的是这道题数据很小,似乎不用状压就可以。那咱就暴力DFS算了。
代码虽长,但极其通俗易懂
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a,b;
int ans=0;
bool vis[25][25];
void dfs(int x,int y)
{
if(x==n+1)
{
if(a==0&&b==0)
ans++;
return;
}
if(vis[x][y])//我已来过,就说明是上一次1*2的时候放的
{
if(y==m) dfs(x+1,1);
else dfs(x,y+1);
return;
}
if(b)//1*1
{
b--;
vis[x][y]=true;
if(y==m) dfs(x+1,1);
else dfs(x,y+1);
vis[x][y]=false;//还原现场
b++;
}
if(a)//1*2
{
a--;
vis[x][y]=true;
if(!vis[x+1][y])//如果能横着放
{
vis[x+1][y]=true;
if(y==m) dfs(x+1,1);
else dfs(x,y+1);
vis[x+1][y]=false;
}
if(!vis[x][y+1])//如果能竖着放
{
vis[x][y+1]=true;
if(y==m) dfs(x+1,1);
else dfs(x,y+1);
vis[x][y+1]=false;
}
a++;
vis[x][y]=false;
}
}
int main()
{
cin>>n>>m>>a>>b;
dfs(1,1);
cout<<ans;
return 0;
}