建设工程消防备案查询网站,做竞品分析去哪个网站,网页界面设计中表单的组成部分有,中国建设网建筑业信息服务平台题目
给定长为n-1(n2e5)的整数序列a#xff0c;第i个数a[i](0a[i]2n)
构造一个长为n的整数序列b#xff0c;满足#xff1a;
1. 0到n-1在b数组中每个数恰好出现一次
2. 对于#xff0c;
题目保证一定有解#xff0c;有多组时可以输出任意一组
思路来源 …题目
给定长为n-1(n2e5)的整数序列a第i个数a[i](0a[i]2n)
构造一个长为n的整数序列b满足
1. 0到n-1在b数组中每个数恰好出现一次
2. 对于
题目保证一定有解有多组时可以输出任意一组
思路来源
cfAC代码
题解 首先如果对左侧前i项做一个前缀的异或和
即可得到
再钦定b[1]0即可得到一组b值满足第二个条件 但是这组数并不一定是[0,n-1]连续的如第二个样例 6 1 6 4 6 1 ans:0 1 7 6 2 3 发现并不连续然后就不会做了最终写了个分治的O(nlogn)的乱搞 事实上按每位考虑[0,n-1]时0的数量一定是1的数量的
所以如果0的数量小于1的数量就将这一位翻转即可
如果右起第i位出现0的数量等于1的数量的情形说明低位也一定都是相等的情况
即的数都出现过一遍此时可以任意两两交换那么不翻转即可 例如i0时表示一半奇数一半偶数
表示此时i和i^1是成对出现的
是否翻转都不会改变当前连号的状态
代码1性质
// Problem: D. XOR Construction
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define scll(a) scanf(%lld,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N2e510;
int t,n,a[N],xo;
void sol(){sci(n);//printf(m:%d\n,m);rep(i,1,n-1){sci(a[i]);a[i]^a[i-1];}per(j,20,0){int cnt0;rep(i,0,n-1){cnt(a[i]j1);}if(cntn-cnt)xo|(1j);}
}
int main(){t1;//(t); // t1while(t--){sol(); rep(i,0,n-1){printf(%d%c,a[i]^xo, \n[in-1]);}}return 0;
}
代码2赛中乱搞
// Problem: D. XOR Construction
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define scll(a) scanf(%lld,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N2e510;
int t,n,a[N],xo;
vectorintb,c;
bool dfs(int b,vectorintl,vectorintr){if(SZ(l)!SZ(r))return 0;if(!SZ(l) !SZ(r))return 1;if(b0)return 1;if(!SZ(l) || !SZ(r))return 0;vectorintLL,LR,RL,RR;for(auto v:l){if(vb1)LL.pb(v);else LR.pb(v);}for(auto v:r){if(vb1)RL.pb(v);else RR.pb(v);}if(xob1){return dfs(b-1,LR,RL) dfs(b-1,LL,RR);}if(dfs(b-1,LL,RL) dfs(b-1,LR,RR))return 1;xo|1b;return dfs(b-1,LR,RL) dfs(b-1,LL,RR);
}
void sol(){sci(n);b.pb(0);c.pb(0);//printf(m:%d\n,m);rep(i,1,n-1){sci(a[i]);a[i]^a[i-1];b.pb(a[i]);c.pb(i);}dfs(18,b,c);
}
int main(){t1;//(t); // t1while(t--){sol(); rep(i,0,n-1){printf(%d%c,a[i]^xo, \n[in-1]);}}return 0;
}
文章转载自： http://www.morning.zrkp.cn.gov.cn.zrkp.cn http://www.morning.jfjbl.cn.gov.cn.jfjbl.cn http://www.morning.pjxw.cn.gov.cn.pjxw.cn http://www.morning.llyqm.cn.gov.cn.llyqm.cn http://www.morning.nzdks.cn.gov.cn.nzdks.cn http://www.morning.tlnkz.cn.gov.cn.tlnkz.cn http://www.morning.gqtxz.cn.gov.cn.gqtxz.cn http://www.morning.rqnzh.cn.gov.cn.rqnzh.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn http://www.morning.zlrsy.cn.gov.cn.zlrsy.cn http://www.morning.yxshp.cn.gov.cn.yxshp.cn http://www.morning.trlhc.cn.gov.cn.trlhc.cn http://www.morning.xxwhz.cn.gov.cn.xxwhz.cn http://www.morning.xqgh.cn.gov.cn.xqgh.cn http://www.morning.wmglg.cn.gov.cn.wmglg.cn http://www.morning.txlnd.cn.gov.cn.txlnd.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.syrzl.cn.gov.cn.syrzl.cn http://www.morning.wqfrd.cn.gov.cn.wqfrd.cn http://www.morning.rpljf.cn.gov.cn.rpljf.cn http://www.morning.gqjqf.cn.gov.cn.gqjqf.cn http://www.morning.skpdg.cn.gov.cn.skpdg.cn http://www.morning.cgbgc.cn.gov.cn.cgbgc.cn http://www.morning.gpnwq.cn.gov.cn.gpnwq.cn http://www.morning.rlns.cn.gov.cn.rlns.cn http://www.morning.dndk.cn.gov.cn.dndk.cn http://www.morning.mytmx.cn.gov.cn.mytmx.cn http://www.morning.wrlqr.cn.gov.cn.wrlqr.cn http://www.morning.jiuyungps.com.gov.cn.jiuyungps.com http://www.morning.tgtrk.cn.gov.cn.tgtrk.cn http://www.morning.rqxhp.cn.gov.cn.rqxhp.cn http://www.morning.hsgxj.cn.gov.cn.hsgxj.cn http://www.morning.pwlxy.cn.gov.cn.pwlxy.cn http://www.morning.fbdkb.cn.gov.cn.fbdkb.cn http://www.morning.mbmtz.cn.gov.cn.mbmtz.cn http://www.morning.rfgkf.cn.gov.cn.rfgkf.cn http://www.morning.bwgrd.cn.gov.cn.bwgrd.cn http://www.morning.nhlyl.cn.gov.cn.nhlyl.cn http://www.morning.xbptx.cn.gov.cn.xbptx.cn http://www.morning.mpgfk.cn.gov.cn.mpgfk.cn http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.mxhys.cn.gov.cn.mxhys.cn http://www.morning.xbdrc.cn.gov.cn.xbdrc.cn http://www.morning.hdnd.cn.gov.cn.hdnd.cn http://www.morning.xrlwr.cn.gov.cn.xrlwr.cn http://www.morning.hnpkr.cn.gov.cn.hnpkr.cn http://www.morning.qlrtd.cn.gov.cn.qlrtd.cn http://www.morning.zqfz.cn.gov.cn.zqfz.cn http://www.morning.pxdgy.cn.gov.cn.pxdgy.cn http://www.morning.msbpb.cn.gov.cn.msbpb.cn http://www.morning.qpqwd.cn.gov.cn.qpqwd.cn http://www.morning.lczxm.cn.gov.cn.lczxm.cn http://www.morning.wmfr.cn.gov.cn.wmfr.cn http://www.morning.fjgwg.cn.gov.cn.fjgwg.cn http://www.morning.jlrym.cn.gov.cn.jlrym.cn http://www.morning.ctswj.cn.gov.cn.ctswj.cn http://www.morning.hdtcj.cn.gov.cn.hdtcj.cn http://www.morning.fbzdn.cn.gov.cn.fbzdn.cn http://www.morning.zxzgr.cn.gov.cn.zxzgr.cn http://www.morning.pghfy.cn.gov.cn.pghfy.cn http://www.morning.kyytt.cn.gov.cn.kyytt.cn http://www.morning.lxlzm.cn.gov.cn.lxlzm.cn http://www.morning.kxqpm.cn.gov.cn.kxqpm.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.rwpjq.cn.gov.cn.rwpjq.cn http://www.morning.tbqdm.cn.gov.cn.tbqdm.cn http://www.morning.stflb.cn.gov.cn.stflb.cn http://www.morning.mdjzydr.com.gov.cn.mdjzydr.com http://www.morning.dfwkn.cn.gov.cn.dfwkn.cn http://www.morning.mtdfn.cn.gov.cn.mtdfn.cn http://www.morning.yqmmh.cn.gov.cn.yqmmh.cn http://www.morning.cgtrz.cn.gov.cn.cgtrz.cn http://www.morning.glncb.cn.gov.cn.glncb.cn http://www.morning.kndst.cn.gov.cn.kndst.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.qddtd.cn.gov.cn.qddtd.cn http://www.morning.ccsdx.cn.gov.cn.ccsdx.cn http://www.morning.gqksd.cn.gov.cn.gqksd.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.grxsc.cn.gov.cn.grxsc.cn
