营销网站四大要素,绵阳网站搜索优化,广州网络推广专员,网页设计公司取名OR
题意#xff1a;
给你一个数组b和c(数值位于下标2到n) 问是否存在一个a序列#xff0c;biai−1oraibia_{i-1} or a_{i}biai−1orai , ciai−1aic_{i}a_{i-1}a_{i}ciai−1ai
题解#xff1a;
我是这样想的#xff0c;对于每一个bi和ci(i从2开始)#xff0…OR
题意
给你一个数组b和c(数值位于下标2到n) 问是否存在一个a序列biai−1oraibia_{i-1} or a_{i}biai−1orai , ciai−1aic_{i}a_{i-1}a_{i}ciai−1ai
题解
我是这样想的对于每一个bi和ci(i从2开始)都可以确定ai的取值情况然后我们再计算bi1和ci1时可以根据上一轮ai得到的情况来确定本轮ai1的情况。 如何通过bi和ci确定ai的取值呢 我们利用二进制来判断对于bi和ci的每一位分析从第0位到第31位依次分析 考虑第j位时,f表示当前是否有进位如果b0,c0,f0,那么ai,ai-1的第j位为0如果b1,c1,f1,那么ai,ai-1为1如果b1,c1,f1,那么ai和ai-1一个为0一个为1如果b1,c0,f1,那么ai和ai-1一个为0如果b1,c0,f0那么ai,ai-1为1且会产生进位f1如果b0,c1,f1,那么ai,ai-1为0进位在此处用掉进位消失f0不满足上列情况a无法取到值 F[i]表示第i个位置的情况 F[i]2表示第i个位置有两个值可以取如果ai取1则ai-1取0反之初始化为-1 F[i]1/0:分别表示当前位置取1或0 F[i]-1:说明当前位置无法取到值 F[i]会不断更新F[i]的作用相当于将Ai的取值情况与Ai-1相连(Ai-1的情况就是通过F[i]来表示)完事后并更新F[i],给后面Ai1接着使用 w表示当前第j位的取值情况 如果w-1则F[i]-1如果w0/1F[j]2,则F[j]w如果w2F[j]!2,则F[j]F[j] ^ 1(ai-1这一个位置取w(0或1)而ai与ai-1是两种取值ai的取值是w ^ 1)如果w0F[j]1则F[j]-1;如果w1F[j]0则F[j]-1; 然后更新答案 详细看代码
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime clock(); //计时开始freopen(in.txt,r,stdin);#endif
}
void Time_test(){#ifdef ONLINE_JUDGE#elseendTime clock(); //计时结束printf(\n运行时间为:%lfs\n,(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif
}
const int maxn2e59;
ll b[maxn],c[maxn],F[maxn];
int main()
{//rd_test();int n;cinn;ll sum1e11;for(int i2;in;i){cinb[i];}for(int i2;in;i){cinc[i];}for(int i0;i33;i)F[i]2; for(int i2;in;i){ll tot1;ll w0;int f0;for(int j0;j31;j){int x((b[i]j)1);int y((c[i]j)1);if(x0y0f0)w0;else if(x1y1){if(f1){w1;}else w2;}else if(x1y0){if(f1){w2;f1;}else{w1;f1;} }else if(x0y1f1){f0;w0;}else {w-1;}if(w-1)F[j]-1;else if(F[j]2w!2) F[j]w;else if(w2F[j]!2)F[j]F[j]^1;else if(F[j]1w0)F[j]-1;else if(F[j]0w1) F[j]-1;if(F[j]1)tot1ll*tot*1;else if(F[j]0)tot1ll*tot*1;else if(F[j]2)tot1ll*tot*2;else if(F[j]-1)tot1ll*tot*0;}if(f1)tot0;summin(sum,tot);}coutsum;//Time_test();
}
