感觉最近自己似乎有点摆，比赛基本都鸽了，一直在改题改题改题。
关键在于发现了好多历史遗留性问题（翻译：发现自己去年暑假啥也没学会），因此还得补。
状压DP
T1
感觉……不如背包。
赛时也意识到这完全是背包，然而没做过同类型的题（似乎整个机房qz1zOIer都没做过），因此赛时啥也想不出来。
由于我懒得打暴力认为与其打暴力不如改题，因此赛时啥也没写。
这一题的思路是枚举每一个或和（异或和），预处理出可以通过或运算组成它的数，然后背包求解。设 $dp{i,j}表示考虑前i个数，异或和为j的情况数，显然ans=dp{cnt,x}（cnt为可以通过或运算组成或和的数字总数，x$ 表示枚举出的或和）。
考虑到数据范围，记得开long long。
code：
#include
#define int long long
using namespace std;
const int N=60,M=(1<<14);
int n,a[N],b[N],cnt,dp[N][M],ans;
signed main()
{
freopen("orandxor.in","r",stdin);
freopen("orandxor.out","w",stdout);
scanf("%lld",&n);
for (int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for (int x=1;x<M;x++){
cnt=0;
for (int i=1;i<=n;i++){
if ((a[i]|x)==x){
b[++cnt]=a[i];
}
}
dp[0][0]=1;
for (int i=1;i=0;j--){
dp[i][j]=dp[i-1][j]+dp[i-1][j^b[i]];
}
}
ans+=dp[cnt][x];
}
printf("%lld",ans);
return 0;
}
T2
很疑惑这么裸的状压DP我是如何在考场上没有看出来的。个人认为扫了两眼就去改题是其一，对状压完全不熟是其二。
疑因丁真，鉴定为历史遗留问题，简称：我太菜。
写这个blog的时候还没改这题，先放下，原因后面会说。
单调队列
根据我对这个东西一点印象也没有并且我在洛谷的单调队列模板并没有提交过，我可能是之前暑假的时候忙于学习其它算法以至于把它忽略了。
于是补了一下，先从模板题开始。
单调队列是一种双端队列（既可以从队首出队又可以从队尾出队的队列），可以维护最值。由于每个元素只需进出队一次，它的时间复杂度为 O(n) 。
每入队一个元素，都从队尾弹出所有比它大/小的元素来维护队列的单调性。一个元素出队时则需要弹出它与在它之前的所有元素。
感觉学一下其实挺好理解的，我想去年的我大抵是个弱智罢。（虽然今年的我也是）
今天的题目还没改完，明天早上upd。