A.Buy Lottery Tickets
根据题意直接进行暴力dfs，因为一个return 错了四次 ；
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], ans[N];
bool st[N];
int m;
void dfs(int u)
{
if(u > 6)
{
for(int i = 1; i <= 6 ; i ++)
{
cout << ans[i] << " ";
}
cout << endl;
return ; //此处忘记写return直接WA四发
}
for(int i = 1 ; i <= m ; i ++)
{
if(!st[i] && ans[u - 1] < a[i])
{
ans[u] = a[i];
u ++;
st[i] = true;
dfs(u);
u --;
st[i] = false;
}
}
}
int main()
{
while(cin >> m)
{
memset(a , 0 , sizeof a);
memset(ans , 0 , sizeof ans);
memset(st , false , sizeof false);
if(m == 99)
{
cout << endl;
break;
}
if(m <= 6 || m >= 13)
{
cout << "ERROR" << endl;
cout << endl;
continue;
}
for(int i = 1; i <= m ; i ++) cin >> a[i];
dfs(1);
cout << endl;
}
}
B.Professor's Task
没啥含金量 直接代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main()
{
string s;
while(getline(cin,s))
{
memset(a , 0 , sizeof a);
for(int i = 0 ;i < s.size() ; i++)
{
int t = s[i] - 0;
if(t >= 97 && t <= 122)
a[s[i]-97] ++;
}
for(int i = 0; i < 26 ; i++)
{
cout<<char(i+97) <<':'<< a[i]<<endl;
}
cout << endl;
}
return 0;
}
C.Golden Coins
完全背包(类似)
对于题目所给的意思，也就是说拥有1-17这些平方的纸币，给出一个数（小于300）问用前面这些价值的纸币有多少种方法来凑出这个数；
转化一下问题，就是说：
有17种物品 ，每个物品的体积都是本身的平方 ，给出一个背包体积，问有多少种方法恰好将这个背包装满；
dp问题的难点就在于找状态转移方程的计算；
f[i][j] : 表示在前i个物品中选，且总体积为j的方案数;
状态转移方程计算：
1.如果不包含第 i 个物品 也就是题目所说的纸币； f[i][j] = f [i-1][j];
2.包含第i个物品 并且选k个这个物品 f[i][j] = f[i - 1][j - k * v[i]]; 转换的思想 选第i个也就是说 在前i-1选体积为j-v[i]的方案数；
写状态转移方程的时候一定需要保证不重不漏;
此处题解写不优化的完全背包:
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int v[N] , f[N][N];
int main()
{
for(int i = 0; i <= 17 ; i ++) //预处理体积
v[i] = i * i;
int m;
while(cin >> m)
{
if(m == 0) break;
f[0][0] = 1; //初始化;
for(int i = 1;i <= 17;i ++)
{
for(int j = 0;j <= m;j ++)
{
for(int k = 0;v[i] * k <= j;k ++)
{
if(k == 0) f[i][j] = f[i - 1][j]; //k等于0的时候就是不选第i这种情况
else f[i][j] += f[i - 1][j - k * v[i]];
}
}
}
cout << f[17][m] << endl;
}
return 0;
}
下面是优化的代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int v[N] , f[N][N];
int main()
{
for(int i = 0; i <= 17 ; i ++) //预处理体积
v[i] = i * i;
int m;
while(cin >> m)
{
if(m == 0) break;
f[0][0] = 1; //初始化;
for(int i = 1;i <= 17;i ++)
{
for(int j = 0;j <= m;j ++)
{
for(int k = 0;v[i] * k <= j;k ++)
{
if(k == 0) f[i][j] = f[i - 1][j]; //k等于0的时候就是不选第i这种情况
else f[i][j] += f[i - 1][j - k * v[i]];
}
}
}
cout << f[17][m] << endl;
}
return 0;
}
D.Happy 2004
数学知识，数论；
A 被分解质因数为：
一个数A = p1^k1 + p2^k2 + p3^k3 .....pn^kn ;一个数A可以为拆分为p1的k1次方 + p2的k2次方 +一直相加;
所以易得 A^B = p1^(k1*B) + p2^(k2*B) +....+pn^(kn*B);
约数个数： (k1+1)*(k2+1)*....*(kn+1);
A的约数之和： (p1^0+...p1^k1) * (p2^0+....+p2^k2) *...* (pn^0 +...+ pn^kn);
A^B的约数之和：(p1^(0*B) +...+ p1^(k1*B)) * (p2^(0*B) +....+ p2^(k2*B)) *...* (pn^(0*B) +...+ pn^(kn*B));
所以另sun(p,k) = (p^0+....+p^(k-1));这也是本题要用的重点公式,所以我们需要分析如何求这个sum(p,k);
相当于结论：
//这是k为偶数的条件下;
sum(p,k) = p^0+....+p^(k-1)
= p^0+...+p^(k/2 - 1)) + (p^(k/2) +...+p^(k - 1)); //发现后一项中都含有p^(k/2);
= p^0+...+p^(k/2 - 1)) + p^(k/2) * (p^0 + ...+ p^(k/2 - 1));
= (1 + p^(k/2)) * (p^0 + ...+ p^(k/2 - 1));
= (1 + p^(k/2)) * sum(p , k/2);
//k为奇数时；
sum(p,k) = p^0+....+p^(k-1)
= p^0 + p^1 +...+ p^(k-1) //拿出第二项；
= p^0 + p^1 * (p^0 + p^1 + ... + p^(k - 2))
= p^0 + p^1 * sum(p,k - 1);
= 1 + p * sum(p , k - 1);
sum(p,k) = p^0+....+p^(k-1)
= p^0 + p^1 +...+ p^(k-2) +p^(k-1);
= sum(p , k - 1) + p^(k-1);
#include <bits/stdc++.h>
using namespace std;
const int mod = 29;
int m;
int quick_pow(int a , int b) //模板快速幂 a的b次方;
{
int res = 1;
while(b)
{
if(b & 1) res = res * a % mod ;
a = a * a % mod;
b >>= 1;
}
return res;
}
int sum(int p , int k)
{
if(k == 1) return 1;//只有一项那么 p^0就是1；
//如果是偶数
if(k % 2 == 0)
return (1 + quick_pow(p , k/2)) * sum(p , k/2) % mod;
//如果是奇数
if(k % 2)
return (sum(p , k - 1) + quick_pow(p , k-1)) % mod; //对应上面奇数的第二个公式；
}
int main()
{
int b;
while(cin >> b && b != 0)
{
int a = 2004;
int ans = 1;
for(int i = 2 ; i <= a / i ; i ++) //对a进行因式分解；
{
if(a % i == 0)
{
int s = 0;
while(a % i == 0)
{
a /= i;
s ++; //这个s就是i的几次方；
}
ans = ans * sum(i , s * b + 1) % mod; //也就是求约数之和的公式; 注意要+1，不理解看上面公式
}
}
if(a > 1) ans = ans * sum(a , b + 1) % mod; //如果最后a>1说明存在一个质数；那么我们就再算一次;
if(a == 0) ans = 0;
cout << ans << endl;
}
}