各位大佬都只有两三百分，那我拿160几好像也不奇怪了哈
今天的内容主要用例题展示：
1 AGAGA XOOORRR{
-
题意：每相邻两个数之间异或，求最终是否能留下两个相等的值
-
思路：先扫描一遍数组，用一个初始值pre=0对所有数进行异或，如果最后恒为0说明一定可以，没有的话再判断能否分割成三段及以上的段使得段内的异或值为0，有则为YES
}
核心代码：
for(int i=1;i<=n;i++) total ^= xr[i];//不断异或取值
if(total==0){
cout<<"YES"<<endl;//如果一开始就能等于0直接输出YES
continue;
}
int cnt=0,tot=0;
for(int i=1;i<=n;i++){
tot^=xr[i];
if(tot==total){//分段查找可能答案
cnt++;
tot=0;
}
}
if(cnt>=3) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
2 Vampiric power,anyone?{
-
题意：每当选择数组内的一个下标时，数组尾部都会添加一个下标往后的后缀异或值，求最终添加的后缀最大值
-
思路：我们设一开始选择下标p，则新添加的值为total^pre[p](pre为前缀异或值),再往后添加的值则为total^(total^pre[p])。不难看出数值再次变为了pre[p]，因此我们不需要往后遍历整个数组求异或值，而是可以预处理出整个数组的异或值，再遍历0到256寻找答案，判断此时的数是否用过，更新最大值
}
核心代码：
for(int i=0;i<n;i++){
int x;
cin >> x;
pre^=x;
for(int i=0;i<256;i++)
if(seen[i]) ans=max(ans,pre^i);//找到了就更新异或最大值
seen[pre]=true;//记录已使用
}
3 Short program{
1.题意：一种新计算机语言CALPUS，专门负责接收数字并对其进行位与，位或和异或运算，现给出此种语言的一段代码，求一种等效代码使得其运行结果在0到1023范围内与原代码的运行结果一致，输出代码长度和代码内容
2.思路：看到1023我们就有救了（本人对数字不是很敏感），因为1023的二进制形式都是1，而0则就是0，因此我们可以借助这两个数来对原代码进行模拟，看输出的结果最终是什么，再对原数进行比较，这里要分情况讨论：{
1.res1==1&&res2==1:都是1时，取位或
2.res1==1||res2==1:有一个为1就取位与
3.res1==1&&res2==0:0为0时取异或
}
因为只涉及到三种运算，所以代码长度恒为3，最终输出三种运算的不同模拟结果即可
}
核心代码：
for(int i=0;i<10;i++){//数字位运算的恒等变换
int x0=(z>>i)&1,x1=(o>>i)&1;
if(x0||x1) am|=(1<<i);//有一个为1时取位与值
if(x0&&x1) om|=(1<<i);//两个都为1时取位或值
if(x0&&!x1) xm|=(1<<i);//一个为1一个为0时取异或值
}
4 Orray{
-
题意：给定一个a数组，求一种排列组合的顺序，使得数组b的字点序最大（当xi!=yi&&xi>yi时，x数组的字点序大于y数组）：b数组中的元素大小：b[i]=a[1]|a[2]|...|a[i];
-
初步构思：因为原数组是取或，所以原先已经被转换为1的位置不再可能变为0，所以我们需要让一开始的元素尽可能的大，因此我们令一个前缀cur，让它每次都对剩余的a[i]取或，而每个a[i]的最大值不超过1e9,因此我们只需要遍历查找30次就能囊括所有情况（本人TLE就T在这里），用过的顺带标记一下,如果初始化的最大下标id==-1||cur|a[i]==cur，直接break不找了
}
核心代码：
for(int i=0;i<31;i++){
int id=-1;
for(int i=0;i<n;i++)
if((!used[i])&&((id==-1)||(cur|xr[i])>(cur|xr[id]))) id=i;
if(id==-1||(cur|xr[id])==cur) break;
used[id]=true;
cur|=xr[id];
ans.push_back(xr[id]);
}
5 Good keys and bad keys{
-
题意：有一组宝箱，你可以选择花费k枚金币够买一把好钥匙从而直接打开它，也可以选择白嫖一把坏钥匙，但是代价则是让所有宝箱内剩余的金币数全部减半并向下取整，求你最终能获得的金币总数
-
思路：这题唯一的代价是坏钥匙，而题目允许存款出现负数，因此我们也可以再获得宝箱中的钱币以后再去补之前倒贴的钱，所以我们可以遍历已经用了几把坏钥匙j，考虑两种情况，这也是这道状压的核心所在：{
1 选坏钥匙：dp[j]=max(dp[j],dp[j]+(a[i]>>(j+1))：选坏钥匙时，下一个宝箱的钱数减半，因此j要+1
2 选好钥匙：dp[j]=max(dp[j],dp[j]+a[i]>>j-k)：选好钥匙时，宝箱内的钱虽然不减少，但是要花费k元来买钥匙，因此要减去k元的代价
}
核心代码：
dp[0]=0;
for(int i=0;i<n;i++){
vector<ll> ndp(32,M);
for(int j=0;j<=31;j++){
if(dp[j]==M) continue;
ndp[j]=max(ndp[j],dp[j]+(mon[i]>>j)-k);//用好钥匙时的贡献值
int nj=min(j+1,31);//防止越界
ndp[nj]=max(ndp[nj],dp[j]+(mon[i]>>nj));//用坏钥匙的贡献值
}
dp.swap(ndp);
}
6 Kefa and Dishes{
-
题意：给定一组菜，其中的每一项分别是第i道菜的满意度,Kefa现在受到一种规则约束，如果吃完第x道菜之后立即吃第y道菜，那么他就会额外增加k点满意度，求最终kefa能最多收获多少满意度
-
思路：暴力：枚举每一种选了第i道菜之后还能选第几道菜，时间复杂度为O(!n)，而n最多到18，显然超时。因此我们可以枚举选菜的状态，用dp[mask]第一维来表示选到了第几道菜，dp[last]第二维来表示最后一道选的菜，而best[mask][last]则表示选到的菜中的最后一道菜的满意度，而last则作为我们选往下一道菜的接口。每次dp的过程中，我们只会关心下一道菜选什么，以及会不会有额外满意度，因此中间的过程便不再重要，不过这题需要注意的东西还是很多的，不然也不会成为S组的难题，下面展示代码以及注释：
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<ll> a(n);
vector<vector<ll>> dp(1<<n,vector<ll>(n,-1));//初始化成二进制形式，方便之后的区间合并与查找
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) dp[1<<i][i]=a[i];//在mask中且最后一个元素为i时
vector<vector<ll>> best(n,vector<ll>(n));
for(int i=0;i<k;i++){
int x,y;
ll c;
cin>>x>>y>>c;
best[x-1][y-1]=c;//额外满意度的初始化
}
ll ans=0;
for(int mask=1;mask<(1<<n);mask++){//状态遍历
for(int last=0;last<n;last++){
if(dp[mask][last]<0) continue;//没出现过不找
if(__builtin_popcount(mask)==m){
ans=max(ans,dp[mask][last]);//满足条件时取最大值
}
for(int nxt=0;nxt<n;nxt++){
if(mask&(1<<nxt)) continue;//不能出现在同一集合中
int nmask=(mask|(1<<nxt));//合并状态
dp[nmask][nxt]=max(dp[nmask][nxt],dp[mask][last]+a[nxt]+best[last][nxt]);
}//新集合中的状态需要跟下一道菜的满意度进行结合，且要算上额外的满意度
}
}
cout<<ans;
}
评论
0