H:::::::::::::::::::::::::::::::::::序列求和(DFS，唯一分解定理)
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 tt，总是可以找到含有 tt 个约数的整数。小明对于含有 tt 个约数的最小数非常感兴趣，并把它定义为 S_tSt 。
例如S1=1,S2=2,S3=4,S4=6，⋅⋅⋅ 。
现在小明想知道，前 60 个 Si 的和是多少？即 S1+S2+⋅⋅⋅+S60 是多少？
运行限制
最大运行时间：1s
最大运行内存: 128M
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<long long> m; int su[100000]; bool check(long long x){ if(x==1){ return false; } if(x==2){ return true; } for(int i=2;i*i<=x;i++){ if(x%i==0){ return false; } } return true; } long long pow1(long long a,long long b){ long long ans=1; while(b){ if(b&1) ans=ans*a; b/=2; a*=a; } return ans; } long long ans; long long res1=1e18; long long dfs(long long x,vector<long long>g) { if(check(x)||x==1)return pow1(2,x-1); for(long long i=2;i*i<=x;i++) { if(x%i==0) { long long t=x/i; g.push_back(i); vector<long long>tmp=g; tmp.push_back(t); sort(tmp.begin(),tmp.end(),greater<long long>()); long long s=1; for(int j=0;j<tmp.size();j++) s*=pow1(su[j],tmp[j]-1); res1=min(res1,s); dfs(t,g); g.pop_back(); } } return res1; } int main(){ int cc=0; for(int i=2;i<=100000;i++){ if(check(i)){ su[cc]=i; cc++; } } ans=1+2+4+6; for(int i=5;i<=60;i++){ res1=1e18; m.clear(); long long ans1=dfs(i,m); ans+=ans1; } cout<<ans; return 0; }
I:::::::::::::::::::::::::::::::::::青蛙跳杯子（BFS）
题目描述
XX 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
XX 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
∗WWWBBB
其中，W 字母表示白色青蛙，B 表示黑色青蛙，*∗ 表示空杯子。
X 星的青蛙很有些癖好，它们只做 3 个动作之一：
跳到相邻的空杯子里。
隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。
隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要 1 步，就可跳成下图局面：
WWW∗BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入描述
输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。
输出描述
输出要求为一个整数，表示至少需要多少步的青蛙跳。
输入输出样例
示例
输入
*WWBB WWBB*
输出
2
运行限制
最大运行时间：1s
最大运行内存: 256M
#include <iostream> #include <queue> #include <string> #include <map> using namespace std; string a,b; struct node{ string a; int bu; int x; node(string aa,int buu,int xu){ a=aa; bu=buu; x=xu; } }; string jiaohuan(string a,int x,int y){ char m=a[x]; a[x]=a[y]; a[y]=m; return a; } map<string,bool> kk; queue<node> q; bool check(int x){ return x>=0 && x<a.size(); } int f[6]={1,-1,2,-2,3,-3}; int main(){ cin>>a>>b; int c=0; for(int i=0;i<a.size();i++){ if(a[i]=='*'){ c=i; } } kk[a]=1; q.push(node(a,0,c)); while(!q.empty()){ node t=q.front(); q.pop(); if(t.a==b){ cout<<t.bu; break; } for(int i=0;i<6;i++){ int tx=t.x+f[i]; string xx=jiaohuan(t.a,t.x,tx); if(check(tx) && !kk[xx]){ kk[xx]=1; q.push(node(xx,t.bu+1,tx)); } } } return 0; }
J:::::::::::::::::::::::::::::::::::剪格子（DFS）
题目描述
如下图所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 60。
本题的要求就是请你编程判定：对给定的 m×n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。
输入描述
输入描述
程序先读入两个整数 m,n 用空格分割 (m,n<10)，表示表格的宽度和高度。
接下来是 n 行，每行 m 个正整数，用空格分开。每个整数不大于 104。
输出描述
在所有解中，包含左上角的分割区可能包含的最小的格子数目。
输入输出样例
示例
输入
3 3 10 1 52 20 30 1 1 2 3
输出
3
运行限制
最大运行时间：5s
最大运行内存: 64M
#include <iostream> using namespace std; int a[15][15]; int n,m; int sum; int he; int ans=1e9; bool vis[15][15]; int aa[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; bool check(int x,int y){ return x>=0&&x<=n&&y>=0&&y<=m; } void dfs(int x,int y,int g){ if(g>=ans){ return; } if(he==sum/2){ ans=min(ans,g); } for(int i=0;i<4;i++){ int tx=x+aa[i][0]; int ty=y+aa[i][1]; if(check(tx,ty) && !vis[tx][ty]){ vis[tx][ty]=1; he+=a[tx][ty]; dfs(tx,ty,g+1); he-=a[tx][ty]; vis[tx][ty]=0; } } } int main(){ cin>>m>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int x=0; cin>>x; a[i][j]=x; sum+=x; } } if(sum%2==1){ cout<<0; return 0; } vis[1][1]=1; he=a[1][1]; dfs(1,1,1); cout<<ans; return 0; }
