$T1$

思路：

质因数分解模版题，自己看讲义去，略。

代码：

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

$T2$

思路：

直接模拟即可，但还是要注意，题目中的 $x$ 太大了，所以需要对本层有楼梯的房间个数取余。

代码：

#include <bits/stdc++.h>
#define int long long
#define bl first
#define x second
using namespace std;
const int N=1e4+50;
int a[N][150],f[N];
bool vis[N][150];
signed 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;j++){
    		cin >> vis[i][j];
    		cin >> a[i][j];
    		f[i]+=vis[i][j];
		}
	}
	int st,ans=0;
	cin >> st;
	for(int i=1;i<=n;i++){
		int pz=a[i][st]%f[i]!=0?a[i][st]%f[i]:a[i][st];
		ans+=a[i][st];
		ans%=20123;
		int cnt=0;
		int j=st;
		while(true){
			if(vis[i][j]) pz--;
			if(!pz) break;
			j++;
			if(j==m) j=0;
		}
		st=j;
	}
	cout << ans%20123;
}

$T3$

思路：

《货币》变型题，DP方法如下：

初始化：f[0]=1

状态计算：i:1->n j:m->0 k:1->min(j,a[i]) f[j]=f[j]+f[j-k]

结果：f[m]

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=150,mod=1e6+7;
int f[N];
int n,m;
int main(){
	f[0]=1;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
    	int ai;
    	cin >> ai;
    	for(int j=m;j>=0;j--){
    		for(int k=1;k<=j&&k<=ai;k++){
    			f[j]=(f[j]+f[j-k])%mod;
			}
		}
	}
    cout << f[m]%mod << endl;
}

$T4$

思路：

本题在输入完成之后直接Floyd即可，无需深搜，只是需要注意以下三点：

$1$. 由于不能学习相同的文化，所以输入完后要将 $a_{ii}$ 直接设为 $1$。

$2$. 由于文化之间存在排斥，所以如果 a[j][i]=1，那么在输入完后，将 $i$ 和 $j$ 之间的距离设为极大值。

$3$. 最后如果结果大于等于极大值，表示没有合法路径，输出 $-1$ 。

有了以上这三点，我们就可以省去DFS了！

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=150;
int cg[N][N],c[N],mp[N][N];
deque<int> q;
int n,K,m,S,T;
signed 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 >> cg[i][j];
		}
	}
	for(int i=1;i<=K;i++) cg[i][i]=1;
	memset(mp,0x3f,sizeof mp);
	for(int i=1;i<=n;i++) mp[i][i]=0;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		mp[a][b]=mp[b][a]=min(mp[a][b],c);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cg[c[j]][c[i]]) mp[i][j]=0x3f3f3f3f;
		}
	}
	for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
               if(mp[i][j]>mp[i][k]+mp[k][j])
                    mp[i][j]=mp[i][k]+mp[k][j];
    if(mp[S][T]>=0x3f3f3f3f) cout << "-1";
    else cout << mp[S][T];
}