德玛西亚万岁
题意：n*m的矩阵 1能站人，0不能站人，相邻的地方不能站人，问总方案数？
题解：知识点状态DP.
通过题意我们可以知道：
1，当位置(i,j)为0时，不能站人。
2，如果(i,j)站人，那么[i-1,j],[i+1,j],[i,j+1],[i,j-1]这四个地方不能站；
因为数据量不是很大所以我们可以想到用二进制来表示当前该位置上是否站人。
针对1，我们可以样做，因为那这个位置不能站人，所以他这个为对应的二进制位为0，这样之后判断就可以知道，这个位置可不可以站人了。
针对2，我们先看左右的，由于我们把能不能站人转化成了二进制，那么我们也可以用二进制来表示那些位置上站没站人，然后利用错位来判断是否有相邻的，例如
1010101//原本的二进制 101010//错位之后的二进制 0000000//比较之后比较之后如果是零就说明他没有相邻的。而如果有相邻的就是这种情况
11011000//原 01101100//错 01001000//结果我们可以知道前一对11和后一对11他们是相邻的 所以返回值不是0；
然后我们看上下：其实就是在枚举一遍上一层的二进制站位，原理跟左右一样，就是这一层是上一层继承过来的，所以若果没有相邻的也要加上上层的那个状态，
最后不要忘了，一个都不放 也是一种方案；
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=100000000;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[20][1<<16];
string str,s;
#define read read()
int main(){
while(~scanf("%lld%lld",&n,&m)){
p=(1<<m);//总的二进制方案数
//每次初始化
for(int i=1;i<=n;i++) dis[i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<p;j++)
dp[i][j]=0;
dp[0][0]=1;//什么都不放也算一种方案数
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++){
cin>>l;
dis[i]=dis[i]|(l<<j);//判断这一个位置有没有 用二进制表示
}
for(int i=1;i<=n;i++){
for(int j=0;j<p;j++){
//用二进制表示当前的状态
//没有这种状态
if((j&dis[i])!=j)continue;
//左右相邻了
if(j&(j>>1))continue;
for(int k=0;k<p;k++){
if(k&j) continue;//上下相邻了
else dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;//可以从上层转移过来
}
}
}
ans=0;
for(int i=0;i<p;i++){
ans=(ans+dp[n][i])%mod;
}
cout<<ans<<endl;
}
return 0;
}
扑克牌
题意：给你n种牌，并给你这n种牌的张数，再给你m张万能牌，让你求最多配出多少套牌(就是n中 种牌，一种一张)
题解：知识点：二分
从整体上来看，配出的多少套牌是单调的，想到二分。
重点说一下check判断函数吧，因为你二分出来结果是，一定要判断结果是否符合，如果你配x套，需要大于m张万能牌，那么这样肯定是不行的，再者一套牌中有两张万能牌也是不符合题意的，所以生成了这两个判断条件。
注意一下：他的右端不要设5e8，我当时就看到他给的范围是5e8我就设的5e8，这样想一下，如果n种牌都有5e8，再有5e8个万能牌，会怎样？当然结果就不在5e8范围内了。所以最右端应该是2*5e8。因为一套牌最多有一个万能牌，所以配出来的，最多加上n种牌数量最多的那个个数。也就是5e8+5e8喽。
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
bool check(ll x){
ll sum=0;
for(int i=1;i<=n;i++)
if(a[i]<x) sum+=x-a[i];
if(sum>min(x,m)) return 0;
else return 1;
}
#define read read()
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
l=0,r=1e9+10;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
cout<<ans<<endl;
return 0;
}
