P5657 格雷码
找规律题
首先先记下这个格雷码的生成方法
有个很重要的结论有k位时
如果自左往右编号
那么第i号是（ i XOR i/2 ）以2进制表示
洛谷P3811
记忆化求逆元，递推
用于求一连串数字对于一个(mod p)的逆元
只能用这种方法，别的算法都比这些要求一串要慢。
那么我们如何递推嘞？
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 1e10+5
#define maxn 30000005
#define minn -105
#define ld long double;
#define uint unsigned int;
#define ull unsigned long long;
typedef long long ll;
#define re register
inline int read()
{
re int t=0;
re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')
{
t=(t<<3)+(t<<1)+v-48;
v=getchar();
}
return t;
}
int invn[maxn];
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
int n,p;
n=read();p=read();
invn[1]=1;
cout<<1<<endl;
for(int i=2;i<=n;i++)
{
invn[i]=(ll)(p-p/i)*invn[p%i]%p;
cout<<invn[i]<<'
';
}
return 0;
}
Xidian OJ 1038 DP
http://acm.xidian.edu.cn/problem.php?id=1038
原题题意：
我只提供少量输入数据
https://www.luogu.com.cn/paste/r1tqrhlt
虽热数据比较小，这题真的很坑爹，状态转移比较难找
思路：
注意第一组数据
4 3
0 1 1
0 1 1
1 1 0
1 1 0
显然状态的转移要基于前面行数满排的情况
但是，是跨几行嘞？
显然无法确定
3 5
0 0 0 1 1
0 1 1 1 1
0 1 1 0 0
所以状态不能通过简单的方法表示
故我们考虑采用状态压缩
dp数组表示某行使用某个决策
每一个决策，使用状态压缩：
用二进制位的有无来判断当前位置是否被选择，1表示此位置可选，0表示此位置不可选
但是这个位置会不会真的选上，我们不关注，我们用dp表示的只是可选性
那么n，m的范围比较小
我们可以暴力枚举0->1023这些可能的决策状态
首先，如果这个位置我们的决策认为它为1，即可选，但是该位置的玻璃损坏了，显然形成矛盾，直接continue
扫完一遍发现，ok，没问题，那么我们开始考虑这些点位如何进行贪心原则
我们要先将所有比他小的这些幂集的答案更新上去，因为他们可选择的位点更少，所以当前决策的dp值肯定大于等于他们，并且由于我们是0->1023去枚举，那么他就一定提前被更新掉了
其次，也是这道题目的核心，如何找比上述更优的值嘞？
其实无非我们现在就要保证这个决策cur值转成2进制后它是所有11是成对出现的
抓满足上述这句话的决策来更新
如110110,11110110,1100011这样
拿任意一对11而言，根据贪心原则
只要是上一行对应的两个位置可取1，那么我们就从上一行那两个位置决策为00的状态转移过来并+1（上一个决策你选00，就默认它锁定没有被选，但它本身是好的，这一行才被决策取走）
到这，有人可能会产生疑惑？
如111这样的三个连续的会被更新到最优值吗？显然因为（11）0，和0（11）在之前更新过了，所以只要1以奇数形式连续，它的最优状态一定在之前出现过并且在之前步骤中转移给了它
但是又有人问如1111，我前两个11，后两个11，都不能拼成2*2，但是我中间两个可以，这不会忽略掉最优解吗？显然不会，跟上面问题同理，0110状态在之前以及被更新过了，所以在前面的步骤已经将最优解给力当前值
至此，我们还有最后一个问题，在进行成对更新的过程中，我们算完了可更新的对数，那么前继状态该如何选择？
前继承状态一定是可选位数越多越好，即非违法状态下的最大值，
而这个最大值上，为1的bit，也表示了当前位置的可选性
一旦我们11这一对被选上了，说明前面这里刚好被挖掉成了00，
所以我们统计一个sum，累加每次11代表的值，最后取上一行最大值与sum的异或，就是前继状态了
ac：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 15
#define minn -105
#define ll long long int
#define ull unsigned long long int
#define uint unsigned int
inline int read()
{
int ans=0;
char last=' ',ch=getchar();
while(ch<'0'|ch>'9')last=ch,ch=getchar();
while(ch>='0'&&ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
int dp[maxn][1025];
int a[maxn][maxn];
int curmax[maxn];
int n,m;
vector<int>line;
void dfs(int row,int cur,int index,int sum)
{
dp[row][cur]=max(dp[row][cur],dp[row][cur-sum]);
if(index==line.size())return;
dfs(row,cur,index+1,sum+line[index]);
dfs(row,cur,index+1,sum);
}
void _DP(int row,int cur)
{
int num=0,sum=0;
for(int i=0;i<m;i++)
{
if(cur&(1<<i))
{
if(a[row-1][i]&&a[row-1][i+1])
{
num++;
sum+=3<<i;
}
i++;
}
}
dp[row][cur]=max(dp[row-1][curmax[row-1]^sum]+num,dp[row][cur]);
}
void _renew(int row,int cur)
{
bool ok=1,check=0;
for(int i=0;i<m;i++)
{
if(check&&!(cur&(1<<i)))ok=0;
if(cur&(1<<i))
{
line.push_back((1<<i));
check=!check;
}
}
if(check)ok=0;
dfs(row,cur,0,0);
line.clear();
if(ok)_DP(row,cur);
}
void solve()
{
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
memset(curmax,0,sizeof(curmax));
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int ans=0;
for(int i=2;i<=n;i++)
{
for(int cur=0;cur<1024;cur++)
{
bool ok=1;
for(int t=0;t<10;t++)
{
if(cur&(1<<t))
if(!a[i][t])ok=0;
}
if(!ok)continue;
curmax[i]=cur;
_renew(i,cur);
ans=max(ans,dp[i][cur]);
//cout<<i<<" "<<cur<<" "<<dp[i][cur]<<endl;
}
//cout<<endl<<endl;
}
cout<<ans<<endl;
}
int main()
{
int _t;
_t=read();
while(_t--)solve();
return 0;
}