/*
1.如果一堆数的gcd ！= 1，就一定凑不出来
2.如果如果一堆数的gcd == 1,就一定能凑出来。
完全背包:
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 110,M = 10010;
int f[M];
int v[N];
int gcd(int a, int b) // 欧几里得算法
{
return b ? gcd(b, a % b) : a;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) cin>>v[i];
//判断是否无解
int t = 0;
for(int i=1;i<=n;i++)
{
t = gcd(t,v[i]);
}
if(t!=1)
{
puts("INF");
return 0;
}
else
{
//最大的凑不出来的数就是(a-1)(b-1) - 1
f[0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<M;j++)
{
f[j] = f[j] + f[j-v[i]]; //还是多重背包求方案数,和第一道题是一样的。
}
}
int res = 0;
for(int i=1;i<M;i++) //这里多循环几位也没关系，因为之后的一定都能够凑出来
{
if(f[i] == 0) res ++; //如果方案数为0，就是凑不出来
}
cout<<res<<endl;
}
return 0;
}
活动打卡代码
AcWing 1226. 包子凑数（蓝桥杯辅导课）
活动打卡代码
AcWing 3382. 整数拆分（每日一题）
MLE代码:
/*
第一遍写错了，主要是状态转移方程写错了，没有理解最后一步，去掉相同的之后能够提出更小的状态。
cin>>n;
首先预处理所有2的次幂:log(n)
完全背包：
f[i][j]:从前1~i中选，每个物品不限，价值就是体积，总体积恰好为j的所有选法.
属性:cnt
f[i][0] = 1;
f[i][j] = ;//不选i
f[i][j] = f[i-1][j]+f[i-1][j-V[i]]+f[i-1][j-V[i]*2],……
f[i][j-V[i]] =f[i-1][j-V[i]]+
so:
f[i][j] = f[i-1][j] + f[i][j-V[i]]
时间复杂度：
o(nlogn)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n;
const int N = 1e6+10,mod = 1e9;
vector<int> V;
int f[30][N];
int main()
{
scanf("%d", &n);
int m = n;
V.push_back(0);
for(int i=1;i<=n;i*=2)
{
V.push_back(i);
}
n = V.size()-1;
// for(auto t:V) cout<<t<<" ";
// cout<<endl<<n<<endl;
//f[0][0] = 1;
for(int i=1;i<=n;i++) f[i][0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j] = f[i-1][j];
if(j>=V[i]) f[i][j] = (f[i][j] + f[i][j-V[i]])%mod;
}
}
printf("%d\n",f[n][m]);
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n;
const int N = 1e6+10,mod = 1e9;
vector<int> V;
int f[N];
int main()
{
scanf("%d", &n);
int m = n;
V.push_back(0);
for(int i=1;i<=n;i*=2)
{
V.push_back(i);
}
n = V.size()-1;
// for(auto t:V) cout<<t<<" ";
// cout<<endl<<n<<endl;
//f[0][0] = 1;
f[0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=V[i];j<=m;j++)
{
f[j] = (f[j] + f[j-V[i]])%mod;
}
}
printf("%d\n",f[m]);
return 0;
}
活动打卡代码
AcWing 9. 分组背包问题（算法基础课）
/*
枚举每一个物品组选哪一个物品
f[i][j] = f[i-1][j];
f[i][j] = max(,f[i-1][j-v[i][k]] + w[i][k];)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N],v[N][N],w[N][N];
int s[N];
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
{
scanf("%d", &s[i]);
for(int k=1;k<=s[i];k++)
{
scanf("%d%d", &v[i][k],&w[i][k]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j] = f[i-1][j];
for(int k=1;k<=s[i];k++)
{
if(j>=v[i][k])
{
f[i][j] = max(f[i][j],f[i-1][j-v[i][k]] + w[i][k]);
}
}
}
}
printf("%d\n",f[n][m]);
return 0;
}
活动打卡代码
AcWing 3. 完全背包问题（算法基础课）
// f[i][j] = ; //不选第i个
// f[i][j] = max(f[i-1][j],f[i-1][j-v],f[i-1][j-2v],f[i-1][j-kv] ……) + w[i]
// f[i][j-v] = max(f[i-1][j-v],f[i-1][j-2*v],……) + w[i]
// f[i][j] = max(f[i-1][j],f[i][j-v]);
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
{
scanf("%d%d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 0; j <= m; j ++ )
{
f[i][j] = f[i-1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]] + w[i]);
}
}
printf("%d\n",f[n][m]);
return 0;
}
活动打卡代码
AcWing 2. 01背包问题（算法基础课）
/*
f[i][j]:
集合:从前i个物品中选，总体积不超过j的所有选法；
属性:max
集合划分：
不选第i个物品:
f[i][0] = 0;//初始化
f[i][j] = max(f[i][j] ,f[i-1][j]);//不选第i个物品
f[i][j] = max(f[i-1][j-v[i]] + w[i],f[i][j]);
答案:f[n][m]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j] = f[i-1][j];
if(j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
}
}
printf("%d\n",f[n][m]);
return 0;
}
活动打卡代码
AcWing 4005. 取石子游戏（每日一题）
思考:
这道题如果直接用sg函数来做，那么就会有n==1e9个状态，TLE，所以要想一想优化的方法:
笔记:
一上来收获了一道小学奥数题:
一共有n个石子，每次可以从中取1~m个石子，如果某一方不能取了，就输了，问先手必胜还是后手必胜。
结论：
如果m+1|n,就是就是先手必败；如果m+1不能|n,就是先手必胜。
证明:
如果m+1|n先手取x个，后手都取m+1-x个，到先手一定取不了；
如果果m+1不能|n，先手可以取n % (m+1)个，到后手就可以整出了，就输了。
原来所有状态都可以分为必胜态和必败态两类:
必胜态:存在一种走法，可以走到必败态
必败态: 只能走到必胜态
需要猜测什么状态是必胜态，什么状态是必败态。
证明太难了，暂时先打标:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;
const int N = 110;
int f[N];
int main()
{
scanf("%d%d", &n,&k);
f[0] = 0;
for(int i=1;i<=n;i++)
{
int s[] = {1,2,k};
for(int j=0;j<3;j++)
{
if(s[j]<=i && f[i-s[j]] == 0) f[i] = 1;
}
}
for(int i=0;i<=n;i++) printf("%d ",f[i]);
return 0;
}
通过改变k的值，看几个一循环:
3 4 0 1 1 1
4 3 0 1 1
5 3 0 1 1
6 7 0 1 1 0 1 1 1
7 3 0 1 1
8 3 0 1 1
9 10 0 1 1 0 1 1 0 1 1 1
规律:
k % 3 !=0:
0 1 1 循环
if(n % 3) 先手必胜
else 先手必败
k % 3 == 0:
n %= (k+1);//
if(n%3 || n == k) 先手必胜
else 先手必败
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;
const int N = 110;
int f[N];
int T;
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
if(k%3)
{
if(n%3) puts("Alice");
else puts("Bob");
}
else
{
n %= (k+1);
if(n%3 || n==k) puts("Alice");
else puts("Bob");
}
}
return 0;
}
活动打卡代码
AcWing 893. 集合-Nim游戏（算法基础课）
sg函数:
Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数(自然数)的运算，即:mex(S)= min{x},x属于自然数，且x不属于S
Sg函数定义:
Sg[终点] = 0;
Sg[x] = mex(Sg[y1],Sg[y2],……Sg[yn]),其中y1……y2是x能够到达的点。
规则:
如果Sg[x] == 0,就是必败，!=0就是必胜，因为Sg==0,就一定不能走到0，如果Sg!=0,就一定能够走到0。
定理：
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。
证明方式:
终点的Sg[xi] ^ 起来一定是0.
如果所有起点的Sg[xi]异或==x，那一定能够找到一个Sg[xi],使得Sg[xi]走到Sg[xi] ^ x(小于Sg[xi]) 这个节点,从而使
所有节点的异或值为0。
如果所有起点的Sg[xi]异或==0，那一定不能走到一个全零的局面，否则的话(反证法)，就能够得到两个相邻节点的Sg值相等的情况，矛盾，因为Sg[x]能走到了。
思考:
其实如果只有一个图，其实Sg只需要具有两个值即可，但是本题中的集合nim游戏，指的是集合中的所有元素都对应一个有向图，如果最终所有集合起点的Sg值异或起来依然是0，就说明是先手必败状态。
本题中，不是说最后必须拿完，即使不拿完，如果最后没有能拿的了，也算输。
最后如果所有起点的Sg异或起来是0，即使有两个起点的Sg相同，实际含义就是在一堆集合中选完之后，后手可以在另一个集合中选，使得先手面对异或都是0的局面。
状态数量是10000(就是每一个有向图最多有10000（每一堆石子的最大值就是1000，拿走1个，最多也就是从0~10000右10001个状态）个节点)，但是一共有100个有向图（有100堆石子）,所以时间复杂度就是o(10^6);
#include<iostream>
#include<cstring>
#include<unordered_set>
#include<algorithm>
using namespace std;
int n,m;
const int N =110,M=10010;
int t[N],f[M];//t表示所有可能取走的石子数量,f表示所有可能出现的sg的值（可能取到很小的数，小于t数组的最小值，所以取值在1~n之间）
int sg(int x)
{
if(f[x]!=-1) return f[x];//记忆化搜索，只要t集合一定，那么某一个元素的sg的值就是确定的，如果某一个元素的sg的值求过了，就直接返回即可。
unordered_set<int> C;//注意每一次递归C都被重新定义，每一次C都不一样。
//用集合（可以删掉重复元素）来存储所有能到的状态的sg的值，来计算本状态的sg的值。
for(int i=0;i<n;i++)//dfs,先可t[0]来，一条道走到头（t[i]全都>x)
{
int sum=t[i];
if(sum<=x) //这一步就是找到所有状态,其中状态数一定<=10000
{
C.insert(sg(x-sum));
}
}
for(int i=0;;i++)//当t[i]全都>x时，说明到末状态了，末状态由于C没有被辐值，所以末状态的值都是0
{
if(!C.count(i)) return f[x]=i; //表面上是for遍历，但是实际上if的时间效率比return 的时间效率小很多，所以可以近似看成是o(1)的时间复杂度。
}
}
int main()
{
memset(f,-1,sizeof f);//sg函数值最小也是0,不可能是-1，所以可以用-1表示f值没有被计算过。
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&t[i]);
}
int res=0;
scanf("%d",&m);
while(m--)
{
int x;
scanf("%d",&x);
res^=sg(x);//所有sg(x)的值做异或，相当于nim游戏。
}
if(res) puts("Yes");
else puts("No");
return 0;
}
活动打卡代码
AcWing 891. Nim游戏（算法基础课）
笔记:
公平组合游戏ICG
若一个游戏满足:
1.由两名玩家交替行动;
2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
3.不能行动的玩家判负;
则称该游戏为一个公平组合游戏。
NIM博奔属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是平组合戏。因为用准交5双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。
先手必胜状态:可以走到某一个必败状态
先手必败状态 : 走不到任 何一个必败状态
答案：
将所有石子异或起来，如果是0，先手必败；否则，先手必胜。
1.终点的异或值一定是0
2.如果所有数的异或值不是0，为x，假设x的二进制中最高位的一位1是第k位，一定能够从某一堆（第k位是1的那一堆,a[i]）中拿走一个数(a[i]-a[i] ^ x)，使得剩下的数的异或值变为0
3.如果异或都是0，下一个走到的状态异或一定不为0.
综上所述，先手必胜就是异或不为0，否则就是先手必败。
#include<iostream>
using namespace std;
int n;
int main()
{
int res=0;//0和任何一个数的异或值都为那个数。
cin>>n;
while(n--)
{
int x;
cin>>x;
res^=x;
}
if(res) puts("Yes");
else puts("No");
return 0;
}
活动打卡代码
AcWing 4496. 吃水果（每日一题）
/*
C[n-1][k] * (m * m-1 * m-1 * ……),()中一共有 k+1 项，也就是无论如何先*m,然后再*k个(m-1)。从n-1开始是因为要排除掉第一个小朋友,
从第2到第n个小朋友之间选择k个隔板，从隔板开始，水果种类开始变得与前面的小朋友不同。 * (m * m-1 * m-1 * ……)就是从最左边开始看，每一段有多少种选择。
本题采用o(n^2)的做法即可。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2010,mod = 998244353;
int n,m,k;
int f[N][N];
int qmi(int a,int k,int p)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL) res * a % p;
k >>= 1;
a = (LL)a*a % p;
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i=0;i<N;i++)
{
for(int j=0;j<=i;j++)
{
if(!j) f[i][j] = 1;
else f[i][j] = (f[i-1][j] + f[i-1][j-1]) % mod;
}
}
int res = (LL)f[n-1][k] * m % mod;
res = (LL)res * qmi(m-1,k,mod) % mod; //虽然说求组合数中使用的是加法,
//求最终答案时使用的是乘法,但是其实%mod可以先对加法求mod,在对*求mod,不影响最终答案
printf("%d\n",res);
return 0;
}
活动打卡代码
AcWing 886. 求组合数 II（算法基础课）
思考:
如果a,b的范围变为了10^5,那么就不能使用o(n^2)的算法进行扫描,需要使用快速幂来进行优化。
感谢大佬们详细的题解：
https://www.acwing.com/solution/content/16482/
https://www.acwing.com/solution/content/22076/
时间复杂度:
o(1e5 * log1e9)
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 100010,mod = 1e9 + 7;
typedef long long LL;
LL fact[N],infact[N];
int qmi(int a,int k,int p)
{
int res = 1;//!!! res == 1竟然写错了 !!!
while(k)
{
if(k & 1) res = (LL) res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
scanf("%d", &n);
fact[0] = 1,infact[0] = 1;
for(int i=1;i<N;i++)
{
fact[i] = fact[i-1] * i % mod;
}
for(int i=1;i<N;i++)
{
infact[i] = infact[i-1] * qmi(i,mod-2,mod) % mod;
}
while (n -- )
{
int a,b;
scanf("%d%d", &a, &b);
printf("%d\n",fact[a] * infact[b] % mod * infact[a-b] % mod);
}
return 0;
}
