10.17——10.24ACM笔记

1.产生数
给出一个整数 nn（n lt 10^{30}n<10
30
）和 kk 个变换规则（k le 15k≤15）。

规则：

一位数可变换成另一个一位数。
规则的右部不能为零。
例如：n=234n=234。有规则（k=2k=2）：

22－>55
33－>66
上面的整数 234234 经过变换后可能产生出的整数为（包括原数）:

234234
534534
264264
564564
共 44 种不同的产生数。

现在给出一个整数 nn 和 kk 个规则。求出经过任意次的变换（00次或多次），能产生出多少个不同整数。

仅要求输出个数。

#include
#include
#include
#include
using namespace std;
string qwq;
int s[33],num[33],k,nxt[33][16],qaq;
bool vis[10];
int ans[33];
void dfs(int x,int y)
{
vis[x]=1;
if(vis[y])return;
qaq++;
for(int i=1;i<=num[y];i++)
dfs(y,nxt[y][i]);



}
void mul()
{int jw=0;
for(int i=30;i;i--)
{
ans[i]=ans[i]*qaq+jw;
jw=ans[i]/10;
ans[i]%=10;

}

}
int main()
{

ans[30]=1;
cin>>qwq>>k;
int len=qwq.size();
for(int i=0;i>x>>y;
nxt[x][++num[x]]=y;


}
for( i=1;i<=len;i++)
{
qaq=1;
for(int j=1;j<=num[s[i]];j++)
dfs(s[i],nxt[s[i]][j]);
memset(vis,0,sizeof(vis));
mul();

}
int l=0;
for(;ans[l]==0;l++)
for( i=1;i<=30;i++)
{if(ans[i]!=0)
{	cout< 
dfs题，比较简单，dfs搜索，mul用来计算。
 2.《爱与愁的故事第三弹·shopping》娱乐章
 爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？
 
#include 
int i,j,k,m,n,l,o,p,x,y;
int sum(int x,int y)
{
	int t,i,j,s1,s2,s3,s4;
	if(x 
细节：发现这个return s4不写，函数仍然返回s4的
 值因为定义在函数内部（包括main()）的变量用栈来分
 配空间，所以有时是随机数。
 在函数外部的变量用static
 分配，值总是0。函数的返回值在栈底（返回给
 main()，c++用ESP做栈寄存器），这个s4恰好就是栈
 底，如果没有定义变量的话栈底就是随机数了
 所以不写return也可以
 3.
 有一个 n×m 的棋盘，在某个点 (x, y)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};
queue > q;
int f[500][500];
bool vis[500][500];
int main()
{
	int n,m,x,y;
	memset(f,-1,sizeof(f));memset(vis,false,sizeof(vis));
	cin>>n>>m>>x>>y;
	f[x][y]=0;vis[x][y]=true;q.push(make_pair(x,y));
	while(!q.empty())
	{
		int xx=q.front().first,yy=q.front().second;q.pop();
		for(int i=0;i<8;i++)
		{
			int u=xx+dx[i],v=yy+dy[i];
			if(u<1||u>n||v<1||v>m||vis[u][v])continue;
		    vis[u][v]=true;q.push(make_pair(u,v));f[u][v]=f[xx][yy]+1;
		}
	}
	for(int i=1;i<=n;i++)
	 {for(int j=1;j<=m;j++)printf("%-5d",f[i][j]);printf("n");}
	return 0;
}
 
用STL模板库 来广搜这道题