CSPJ$1201$. CSP-J $2012$ T$1$ 质因数分解

枚举

第一眼看到题目时我以为还要判质数，但后面发现两个质数相乘等于$n$的情况只有一种，所以$2$~$n$枚举就行了。

首先想到了双层循环，时间复杂度是$Θ（n^2）$，会超时；后面想到，其实两个质数相乘就是$i$与$n/i$相乘，就好了。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=2;i<=n/2;i++){
		if(n%i==0){
			cout<<max(n/i,i);
			return 0;
		}
	}
	return 0;
}

CSPJ$1202$. CSP-J $2012$ T$2$ 寻宝

模拟

首先我想到了可以用两个变量来分别表示现在在哪与要走第几个，但是时间复杂度是$Θ（n^{10}）$，肯定会超时；但是我们发现，因为它是环形，所以可以模一下，就不会超时了。

最后再模以$20123$即为答案。

#include<bits/stdc++.h>
using namespace std;
int a[10010][110],b[10010][110],st[10010];
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m-1;j++){
			cin>>a[i][j]>>b[i][j];
			if(a[i][j]) st[i]++;
		}
	}
	int k,ans=0;
	cin>>k;
	for(int i=1;i<=n;i++){
		ans+=b[i][k];
		ans%=20123; 
		int s=b[i][k]%st[i];
		if(!s) s=st[i];
		while(1){
			if(a[i][k]) s--;
			if(!s) break;
			k++;
			if(k==m) k=0;
		}
	}
	cout<<ans;
	return 0;
}

CSPJ$1203$. T$3$ 摆花

dp（背包问题）。

遇到这种问题真的是一点思路都没有，所以一定要好好积累dp的题目。

我们可以将这个问题转化一下：

• 将花盆数量看成背包容积。
• 将花看作物品，体积是$1$，容量是$a_i$。
• 求将背包装满的方案数。

那么就成背包问题了。

我们定义一个$dp_{i，j}$ ，表示当前只有前$i$个物品，且只摆放$j$盆花的情况下，总共有多少种摆法。$dp_{0，0}=1$, 表示当没有物品的时候，总共有一种情况，就是没有物品。

假设当前要摆放的花的数量是$j$，那么我们就去求出$i-1$号花盆数量为$j-1，j-2，…j-a_i$的时候的和，那么状态计算就是：

$$dp_{i，j}=dp_{i-1，j}+dp_{i-1，j-1}+dp_{i-1，j-2}+···+dp_{i-1，j-a_i}$$

了。

#include<bits/stdc++.h>
using namespace std;
int dp[110];
int main(){
	int n,m;
	cin>>n>>m;
	dp[0]=1;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		for(int j=m;j>=0;j--) for(int k=1;k<=j&&k<=a;k++) dp[j]=(dp[j]+dp[j-k])%(1000000+7);
	}
	cout<<dp[m];
	return 0;
}

CSPJ$1204$. CSP-J $2012$ T$4$ 文化之旅

搜索加剪枝。

首先会想到最短路，但是因为有不能到达排斥这种文化的其他国家的这种规定，所以每次需要判断有没有排斥的情况。

然后再想有没有可能终点排斥某个国家的文化呢？答案是有的，所以我们要从终点开始，那其实就是最短路里面套一个搜索了。

那怎么存储有哪些文化呢？用一个栈就可以了，这样当新文化叉进来时就要遍历一遍栈。

同时，还有一个条件：他不想一种文化学习多次。当新文化遍历栈时发现有一样的，也不行。

但是这样的话会超时，所以还有一个条件，若现在路径>目前最短路径，直接返回。（这就是剪枝）

#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t,c[110],l[110][110],d[110][110],ans,a[110][110],z[110],top;
void dfs(int b,int dist){
	if(dist+d[s][b]>=ans) return;
	if(b==s){
		ans=dist;
		return; 
	}
	for(int i=1;i<=n;i++){
		if(l[i][b]<0x3f3f3f3f){
			bool flag=1;
			for(int j=0;j<top;j++){
				if(a[z[j]][c[i]]!=0){
					flag=0;
					break;
				}
			}
			if(flag){
				z[top++]=c[i];
				dfs(i,dist+d[i][b]);
				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>>a[i][j];
	for(int i=1;i<=k;i++) a[i][i]=1;
	memset(l,0x3f,sizeof l);
	for(int i=1;i<=n;i++) l[i][i]=0;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		l[a][b]=min(l[a][b],c);
		l[b][a]=min(l[a][b],c);
	}
	memcpy(d,l,sizeof d);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
	z[top++]=c[t];
	ans=0x3f3f3f3f;
	dfs(t,0);
	if(ans==0x3f3f3f3f) cout<<-1; 
	else cout<<ans;
	return 0;
}