质因数分解 （枚举&数学）

思路

考察数学。首先要知道唯一分解定理：

一个数能且只能分解为一组质数的乘积。

可知，若输入的数满足题目条件，它就只能分解为两个质数的乘积。所以在比他小且大于$1$的自然数中，只有那两个数能整除它，之间不可能再有任何合数或质数能整除它了，因为最小的能整除它的合数已经是它本身了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	int n;
	cin >>n;
	for(int i=2;i<=n;i++){
		if(n%i==0){
			cout <<n/i;
			break;
		}
	}
	return 0;
}

寻宝（模拟）

思路

模拟逆时针的走法，但是一个一个模拟是不切实际的，会$TLE$。于是我们要寻找优化方法。

再一看，一层楼有楼梯的门就那么几个，找来找去都是它们，这让我想到了周期问题，周期问题**取$\%$**是关键。假设一下，若$a[i]$为该层楼梯门个数，就会出现$0$的情况。

而如果你现在的门又没楼梯，为了让它的原始状态不变，要在$\%$之前$-1$，$\%$之后$+1$，这样还避免了该层门个数为$1$的情况。

所以我们的核心代码就是：

if(cnt==(a[i][step]-1)%f[i][m]+1){
	break;
}

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+10,M=2e3+10;
const int mod=20123;
int f[N][M],a[N][M]; 

int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	int n,m;
	cin >>n>>m;
	int law=0;
	for(int i=1;i<=n;i++){
		law=0;
		for(int j=0;j<m;j++){
			cin >>f[i][j]>>a[i][j];
			if(f[i][j]==1){
				law++;
			}
		}
		f[i][m]=law;
	}
	int step;
	cin >>step;
	int ans=0,cnt=0,j=0;
	for(int i=1;i<=n;i++){
		ans+=a[i][step]%mod;
		cnt=0;
		for(j=step;;j++){
			if(j==m){
				j=0;
			}
			if(f[i][j]==1){
				cnt++;
			}
			if(cnt==(a[i][step]-1)%f[i][m]+1){
				break;
			}
		}
		step=j;
	}
	cout <<ans%mod;
	return 0;
}

摆花（DP）

思路

状态表示：$f[i][j]$表示表示前$i$个数总和为$j$的方案数。

状态计算：$f[i][j]=(f[i][j]+f[i-1][j-k])\%1e6+7$

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=110;
const int mod=1e6+7;
int f[tt][tt],a[tt];

int main(){
	int n,m;
    cin >>n>>m;
    for(int i=1;i<=n;i++){
    	cin >>a[i];
	}
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=min(j,a[i]);k++){
            	f[i][j]=(f[i][j]+f[i-1][j-k])%mod;
			}
        }
    }
    cout <<f[n][m];
    return 0;
}  

文化之旅（暴搜+剪枝）

思路

首先，如果直接利用暴力来解答，数据范围肯定不允许，会$TLE$。

此题性能提升的关键在于如何去暴搜，需要考虑一种有效的剪枝策略，减少搜索的层级。

只需要用数组$f$记录每次遍历到的点时的距离，$f[u]=cnt$。

在$dfs$开始处，如果当前再次走到$u$点时的距离$cnt>=$之前保存过的$f[u]$，则没有必要在继续走了，可以提前$return$。

这样一来就大大减少的搜索的次数。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=110;
int n,m,k,s,t;
int dist[tt][tt];
int a[tt],f[tt];
bool vis[tt];
int ans=0x3f3f3f3f;

struct node{
	int u;
	int v;
	int d;
};

vector<node> g[tt];

void dfs(int u,int cnt){
	if(cnt>=f[u]) return;
	f[u]=cnt;
	if(u==t){
		ans=min(ans,cnt);
		return;
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		if(vis[a[v]]) continue;
		bool qs=0;//歧视
		for(int j=1;j<=k;j++){
			if(vis[j]&&dist[a[v]][j]){
				qs=1;
				break;
			}
		}
		if(qs==1) continue;
		vis[a[v]]=1;
		dfs(v,cnt+g[u][i].d);
		vis[a[v]]=0;
	}
}

int main(){
	memset(f,0x3f,sizeof(f));
	cin >>n>>k>>m>>s>>t;
	for(int i=1;i<=n;i++) cin >>a[i];
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			cin >>dist[i][j];
		}
	}
	for(int i=1;i<=m;i++){
		int u,v,d;
		cin >>u>>v>>d;
		g[u].push_back({u,v,d});
		g[v].push_back({v,u,d});
	}
	vis[a[s]]=1;
	dfs(s,0);
	if(ans==0x3f3f3f3f) cout <<-1;
	else cout <<ans;
	return 0;
}

谢谢