T1质因数分解

思路：

---

因为n是由两个质数组成

一个大的一个小的

找到小的输出n/小的

---

时间复杂度$O(\sqrt n)$

代码如下

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

T2寻宝

思路：

---

直接模拟即可

不过，要将x%一个这层楼的楼梯数

---

时间复杂度$O(nm)$

代码如下

#include<bits/stdc++.h>
using namespace std;
int lt[10010],ylt[10010][110],su[10010][110];
int main()
{
    freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
    int n,m,h,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>ylt[i][j]>>su[i][j];
            lt[i]+=ylt[i][j];
        }
    }
    cin>>h;
    for(int i=1;i<=n;i++)
    {
        int x=(su[i][h]-1)%lt[i]+1;
        sum+=su[i][h]%20123;
        while(x)
        {
            if(ylt[i][h]==1) x--;
            if(x!=0) h=(h+1)%m;
        }
    }
    cout<<sum%20123;
}

T3摆花

思路：

---

多重背包版（货币）

初始化：f[i][0]=1 无论选几种货,体积为0只有都不选

状态转移方程：$f[i][j]=f[i-1][j]+f[i-1][j-1]+...+f[i-1][j-a[i]]$

因为每盆花体积为1,而上限为a[i],第i盆选x个的方案数是f[i-1][j-x]

---

时间复杂度$O(nm max(a[i]))$

代码如下

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

T4文化之旅

暂无