简答题 偏难
#22127

T4、擂台游戏(arena)

T4、擂台游戏(arena)

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include&lt;bits/stdc++.h&gt; #define INF 0x3f3f3f3f #define ll long long #define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d)) #define FOR(i,a,b) for(int i(a);i&lt;=(int)(b);++i) #define DOR(i,a,b) for(int i(a);i&gt;=(int)(b);--i) using namespace std; constexpr int N((1&lt;&lt;17)+10); namespace IOstream { #define getc() getchar() #define putc(ch) putchar(ch) #define isdigit(ch) ('0'&lt;=(ch)&amp;&amp;(ch)&lt;='9') template&lt;class T&gt;void rd(T &amp;x) { static char ch(0); for(x=0,ch=getc(); !isdigit(ch); ch=getc()); for(; isdigit(ch); x=(x&lt;&lt;1)+(x&lt;&lt;3)+(ch^'0'),ch=getc()); } template&lt;class T&gt;void wr(T x,const char End='\n') { static int top(0); static int st[50]; do st[++top]=x%10,x/=10; while(x); while(top)putc(st[top]^'0'),--top; putc(End); } } using namespace IOstream; bool d[N]; char s[N]; int n,m,k,Q; int a_[N],a[N],c[N],wt[N&lt;&lt;1],wn[N&lt;&lt;1]; ll sum[N]; #define v (u&lt;&lt;1) void dfs0(int u,int h) { if(!h)return wn[u]=a[wt[u]=u-(1&lt;&lt;k)+1],void(); dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]&lt;h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]&lt;h))]; } void dfs1(int u,int hmx,int h,int L,int R) { if(L&gt;R)return; if(!h) { int x(u-(1&lt;&lt;k)+1); if(L&lt;min(R,x))sum[L]+=x,sum[min(R,x)]-=x; if(a[x]&gt;=hmx&amp;&amp;max(L,x)&lt;R)sum[max(L,x)]+=x,sum[R]-=x; return; } dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]&gt;=h?min(wt[v|d[u]],R):R); } #undef v signed main() { rd(n),rd(m); while((1&lt;&lt;k)&lt;n)++k; FOR(i,1,n)rd(a_[i]); FOR(i,1,m)rd(c[i]); DOR(i,k-1,0) { scanf("%s",s); DOR(j,(1&lt;&lt;i)-1,0)d[j|1&lt;&lt;i]=s[j]^48; } rd(Q); while(Q--) { static int X[4]; rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]); FOR(i,1,n)a[i]=a_[i]^X[i&amp;3]; dfs0(1,k),RCL(sum+1,0,ll,n); FOR(i,0,k)dfs1(1&lt;&lt;(k-i),0,i,!i?1:(1&lt;&lt;(i-1))+1,(1&lt;&lt;i)+1); FOR(i,1,n)sum[i]+=sum[i-1]; ll ans(0); FOR(i,1,m)ans^=i*sum[c[i]]; wr(ans); } return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt; #define INF 0x3f3f3f3f #define ll long long #define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d)) #define FOR(i,a,b) for(int i(a);i&lt;=(int)(b);++i) #define DOR(i,a,b) for(int i(a);i&gt;=(int)(b);--i) using namespace std; constexpr int N((1&lt;&lt;17)+10); namespace IOstream { #define getc() getchar() #define putc(ch) putchar(ch) #define isdigit(ch) ('0'&lt;=(ch)&amp;&amp;(ch)&lt;='9') template&lt;class T&gt;void rd(T &amp;x) { static char ch(0); for(x=0,ch=getc(); !isdigit(ch); ch=getc()); for(; isdigit(ch); x=(x&lt;&lt;1)+(x&lt;&lt;3)+(ch^'0'),ch=getc()); } template&lt;class T&gt;void wr(T x,const char End='\n') { static int top(0); static int st[50]; do st[++top]=x%10,x/=10; while(x); while(top)putc(st[top]^'0'),--top; putc(End); } } using namespace IOstream; bool d[N]; char s[N]; int n,m,k,Q; int a_[N],a[N],c[N],wt[N&lt;&lt;1],wn[N&lt;&lt;1]; ll sum[N]; #define v (u&lt;&lt;1) void dfs0(int u,int h) { if(!h)return wn[u]=a[wt[u]=u-(1&lt;&lt;k)+1],void(); dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]&lt;h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]&lt;h))]; } void dfs1(int u,int hmx,int h,int L,int R) { if(L&gt;R)return; if(!h) { int x(u-(1&lt;&lt;k)+1); if(L&lt;min(R,x))sum[L]+=x,sum[min(R,x)]-=x; if(a[x]&gt;=hmx&amp;&amp;max(L,x)&lt;R)sum[max(L,x)]+=x,sum[R]-=x; return; } dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]&gt;=h?min(wt[v|d[u]],R):R); } #undef v signed main() { rd(n),rd(m); while((1&lt;&lt;k)&lt;n)++k; FOR(i,1,n)rd(a_[i]); FOR(i,1,m)rd(c[i]); DOR(i,k-1,0) { scanf("%s",s); DOR(j,(1&lt;&lt;i)-1,0)d[j|1&lt;&lt;i]=s[j]^48; } rd(Q); while(Q--) { static int X[4]; rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]); FOR(i,1,n)a[i]=a_[i]^X[i&amp;3]; dfs0(1,k),RCL(sum+1,0,ll,n); FOR(i,0,k)dfs1(1&lt;&lt;(k-i),0,i,!i?1:(1&lt;&lt;(i-1))+1,(1&lt;&lt;i)+1); FOR(i,1,n)sum[i]+=sum[i-1]; ll ans(0); FOR(i,1,m)ans^=i*sum[c[i]]; wr(ans); } return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码3 #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #define ls x&lt;&lt;1 #define rs x&lt;&lt;1|1 #define lson x&lt;&lt;1,l,mid #define rson x&lt;&lt;1|1,mid+1,r #define ll long long using namespace std; const int N = (1 &lt;&lt; 17) + 5; int mx[20][N &lt;&lt; 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1; bool vis[N]; ll ans[N], sum; struct node { ll sum; int x; bool tp, d; } t[N &lt;&lt; 2]; inline void build(int x, int l, int r) { if (l == r) { t[x].x = l; return ; } int mid = l + r &gt;&gt; 1, k = lg[r - l + 1], d = t[x].d; build(lson); build(rson); int win = a[t[x &lt;&lt; 1 | d].x] &gt;= k; t[x].x = t[x &lt;&lt; 1 | (d ^ !win)].x; if (!d &amp;&amp; win)t[x].tp = 1, ok[r]++, ok[mid]--; else t[x].tp = 0; } inline void build2(int x, int l, int r, int *mx) { t[x].sum = (l + r) * (r - l + 1ll) / 2; if (l == r)return ; int mid = l + r &gt;&gt; 1, k = lg[r - l + 1], d = t[x].d; if (~mx[x])mx[ls] = mx[rs] = mx[x]; else mx[x &lt;&lt; 1 | d] = k; build2(lson, mx); build2(rson, mx); } inline void up(int x) { sum += !vis[x] * x; vis[x] = 1; } inline int rd() { char c; int f = 1; while (!isdigit(c = getchar()))if (c == '-')f = -1; int x = c - '0'; while (isdigit(c = getchar()))x = x * 10 + (c ^ 48); return x * f; } inline char gc() { char c; while ((c = getchar()) &lt;= ' '); return c; } int main() { // freopen("arena.in","r",stdin); // freopen("arena.out","w",stdout); n = rd(); m = rd(); for (int i = 1; i &lt;= n; i++)aa[i] = rd(); for (int i = 1; i &lt;= m; i++)c[i] = rd(); while (nn &lt; n)nn &lt;&lt;= 1; for (int i = 2; i &lt;= nn; i++)lg[i] = lg[i &gt;&gt; 1] + 1; for (int i = nn / 2; i; i &gt;&gt;= 1) for (int j = i; j &lt; i * 2; j++) t[j].d = gc() - '0'; memset(mx, -1, sizeof mx); for (int s = 0; (1 &lt;&lt; s) &lt;= nn; s++) build2(1 &lt;&lt; s, 1, nn&gt;&gt;s, mx[s]); for (int T = rd(); T--;) { int yh[4] = {rd(), rd(), rd(), rd()}; for (int i = 1; i &lt;= n; i++)a[i] = aa[i] ^ yh[i &amp; 3]; memset(ok, 0, sizeof ok); build(1, 1, nn); for (int i = nn, rt = 1, s = 0; i; i--) { if ((1 &lt;&lt; lg[i]) == i) { if (i != nn)rt &lt;&lt;= 1, s++; for (int j = 1; j &lt;= i; j++)vis[j] = 0; sum = 0; up(t[rt].x); } ans[i] = sum; if (ok[i] += ok[i + 1])continue; up(i); int x = i + nn - 1; while (x != rt) { int d = x &amp; 1; x &gt;&gt;= 1; if (!d) if (t[x].tp)sum += t[rs].sum; else break; else if (a[t[ls].x] &gt;= mx[s][ls])up(t[ls].x); } } ll num = 0; for (int i = 1; i &lt;= m; i++)num ^= i * ans[c[i]]; printf("%lld\n", num); } return 0; }</pre>
这道题暂未补解析。