T1 质因数分解
做题情况：AC
思路
本题本质上来说还是质因数分解，我们可能会想到：
直接爆搜！但是会超时。
本题的确不可避免的出现搜索
可是不是爆搜，而是优化的搜索。
众所周知：如果x可以被y整除，那么x也可以被x/y整除 那么我们就可以枚举y，找到最小的满足题目条件的数，答案就是x/y。
找这个数时间范围
再判断这两个是不是质数就可以了（不会超，放心！得用的判断质数）
如果还想降低时间复杂度，可以加一个线性筛来打表质数
代码
#include<bits/stdc++.h>
using namespace std;
bool f(int n) {
if (n<2){
return 0;
}
for (int i=2;i<=n/i;i++){
if(n%i==0){
return 0;
}
}
return 1;
}
int main(){
int n;
cin>>n;
for(int i=2;i<=n/i;i++){
if(n%i==0){
if(f(i)&&f(n/i)){
cout<<n/i;
return 0;
}
}
}
return 0;
}
T2 寻宝
做题情况：TLE(0)
思路
本题可以用循环写，也可以用递归做。
由于题目模式过于简单所以是一个很简单的题目
就是用暴力！
代码
#include<bits/stdc++.h>
using namespace std;
struct P{
bool vis;
int x;
};
P a[10005][105];
int as[10005];
int n,m;
int f(int asd,int x,int i){
if(i>n){
return 0;
}
int nx=x%as[i],tu=0,y=0;
if(nx==0){
nx=x;
}
for(int j=asd;;j++){
if(j>=m){
j=m%j;
}
if(a[i][j].vis){
tu++;
}
if(tu>=nx){
y=j;
break;
}
}
return f(y,a[i+1][y].x,i+1)%20123+x;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j].vis>>a[i][j].x;
if(a[i][j].vis){
as[i]++;
}
}
}
int us;
cin>>us;
cout<<f(us,a[1][us].x,1)%20123;
return 0;
}
这是递归代码
反思
错误原因
我这一次超时的原因是出现了死循环
我这里忘记了为0的情况，从而出现了死循环
应对措施
如果那么就赋值为x
T3 摆花
思路
我们想一下，求方案数的形式有几个？
- 排列组合（多在初赛中出现）
- DP（方案数式）
枚举思路
本题先试试排列组合
我们经过草稿发现，排列组合除了用枚举法做，就没有其他办法了。
而枚举法又会超时
所以我们只能用DP！
正解思路
很显然，这是经典的多重背包问题
由于数据范围十分的小，所以可以不用任何优化。
状态表示：
状态属性：方案数
状态转移方程： 是~的随机数（所有数） 且不会大于j
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,mo=1e6+7;
int dp[110],as[110];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>as[i];
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int p=1;p<=j&&p<=as[i];p++){
dp[j]=(dp[j]+dp[j-p])%mo;
}
}
}
cout<<dp[m];
return 0;
}
T4 文化之路
思路
本题测试数据十分的水，所以有两种答题方案
非正解
本题数据由于很水，所以可以用倒着DFS过关，而正的只能得20分
正解
在原本的倒搜基础之上，加上一个启发式剪枝。
我们先写一个floyd，求出多元汇最短路用di数组存
我们知道假设走到这里的步数为，当前的位置为，那么结果肯定不会小于因为这是最短路，肯定不会有比最短路还短的路线
用一个栈（不能用str中的）表示已学了哪些文化，这样当新文化叉进来时就要遍历一遍栈
一个文化与自己排斥，就同化了他不想一种文化学习多次
代码
#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t,c[110],g[110][110],d[110][110],ans;
bool cd[105][105];
int p[110],top;
void dfs(int u,int dist){
if(dist+d[s][u]>=ans) return;
if(u==s){
ans=dist;
return;
}
for(int i=1;i<=n;i++){
if(g[i][u]<0x3f3f3f3f){
bool flag=1;
for(int j=0;j<top;j++){
if(cd[p[j]][c[i]]!=0){
flag=0;
break;
}
}
if(flag){
p[top++]=c[i];
dfs(i,dist+d[i][u]);
top--;
}
}
}
}
int main(){
cin>>n>>k>>m>>s>>t;
for(int i=1;i<=n;i++){
cin>>c[i];
}
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
cin>>cd[i][j];
}
}
for(int i=1;i<=k;i++){
cd[i][i]=1;
}
memset(g,0x3f3f3f3f,sizeof g);
for(int i=1;i<=n;i++){
g[i][i]=0;
}
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[a][b],c);
}
memcpy(d,g,sizeof d);
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
p[top++]=c[t];
ans=0x3f3f3f3f;
dfs(t,0);
if(ans!=0x3f3f3f3f){
cout<<ans;
}else{
cout<<-1;
}
return 0;
}
