題目鏈接

http://codeforces.com/contest/1205/problem/C

題解

菜雞永遠(yuǎn)做著變巨的夢(mèng)
然而依然連div1BC題都不會(huì)做
要是那天去打cf怕是又要1題滾粗了。。。。

首先第一步顯然是對(duì)于所有\(i+j\)為偶數(shù)的點(diǎn)(下稱“偶點(diǎn)”)求出\(a_{i,j}\)的值，對(duì)于所有\(i+j\)為奇數(shù)的點(diǎn)(下稱“奇點(diǎn)”)求出它們之間的相對(duì)關(guān)系。也就相當(dāng)于強(qiáng)行令\(a_{1,2}=x\)之后求出所有奇點(diǎn)是\(x\)還是\(x\ \text{xor}\ 1\).
然后我們就是要確定\(x\)的值。

后面題解給了兩種做法，在上面的基礎(chǔ)上分別只多詢問(wèn)\(1\)次：

做法一

比較暴力的做法。
暴力枚舉\(x=0\)和\(x=1\)的情況，因?yàn)橛薪馑赃@兩種情況肯定存在一組詢問(wèn)\((x_1,y_1,x_2,y_2)\)滿足此詢問(wèn)在兩種情況下答案不同。
于是我們可以暴力DP求出所有詢問(wèn)的答案，然后找到不同的位置詢問(wèn)一次來(lái)確定。
(果然是大力出奇跡啊)

做法二

這是我的最初想法，但是最終還是失敗了。
對(duì)于任何聯(lián)通的四個(gè)格\(c_1,c_2,c_3,c_4\) (注意只需聯(lián)通即可，不一定非要在一條直線上)，如果\(c_1\ \text{xor}\ c_4=c_2\ \text{xor}\ c_3\)，那么詢問(wèn)\(c_1\)和\(c_4\)兩點(diǎn)可以確定答案。因?yàn)槿绻?span id="ze8trgl8bvbq" class="math inline">\(c_1=c_4\)則\(c_2=c_3\)一定存在，否則一定不存在。
注意到題目里的限制\(a_{1,1}=1,a_{n,n}=0\), 可以證明一定存在連續(xù)的\(4\)個(gè)格使得這四個(gè)格上數(shù)異或和為\(0\). 證明: 假設(shè)不存在，那么考察一條\((1,1)\)到\((n,n)\)的NE Lattice Path, 其長(zhǎng)度模\(4\)一定余\(1\), 且上面的數(shù)\(4\)個(gè)一循環(huán)，故有最后一個(gè)和第一個(gè)相等，矛盾。
于是隨便找出一條\((1,1)\)到\((n,n)\)的異或和為\(0\)的四格連續(xù)路徑，詢問(wèn)一下，做完了。

由于我太智障，思路一直局限在一條直線上的四個(gè)格，于是歡樂(lè)滾大粗……

代碼

做法二

#include<cstdio> #include<cstdlib> #include<iostream> #include<vector> using namespace std;void read(int &x) {int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f; }const int N = 50; int a[N+3][N+3]; vector<int> pth; int n,ans;int query(int lx,int ly,int rx,int ry) {printf("? %d %d %d %d\n",lx,ly,rx,ry); fflush(stdout);int ret; scanf("%d",&ret); return ret; }int main() {scanf("%d",&n);a[1][1] = 1; a[n][n] = 0;for(int i=1; i<=n; i++){if(i&1){if(i!=1) {a[i][1] = a[i-2][1] ^ query(i-2,1,i,1)^1;}for(int j=3; j<=n; j+=2){if(i==n&&j==n) continue;a[i][j] = a[i][j-2] ^ query(i,j-2,i,j)^1;}}else{for(int j=2; j<=n; j+=2){a[i][j] = a[i-1][j-1] ^ query(i-1,j-1,i,j)^1;}}}a[1][2] = 0;for(int i=4; i<=n; i+=2) {a[1][i] = a[1][i-2] ^ query(1,i-2,1,i)^1;}for(int i=3; i<=n; i+=2) {a[2][i] = a[1][i-1] ^ query(1,i-1,2,i)^1;}a[2][1] = a[2][3] ^ query(2,1,2,3)^1;for(int i=3; i<=n; i++){if(i&1){for(int j=2; j<=n; j+=2) {a[i][j] = a[i-2][j] ^ query(i-2,j,i,j)^1;}}else{for(int j=1; j<=n; j+=2) {a[i][j] = a[i-2][j] ^ query(i-2,j,i,j)^1;}}} /* printf(":\n");for(int i=1; i<=n; i++){for(int j=1; j<=n; j++) printf("%d",a[i][j]);puts("");} */ for(int i=1; i<=n; i++) {pth.push_back(a[i][1]);}for(int i=2; i<=n; i++) {pth.push_back(a[n][i]);}int lx,rx,ly,ry;for(int i=3; i<=n+n-2; i++){if((pth[i]^pth[i-1]^pth[i-2]^pth[i-3])==0){lx = i-3<n ? i-3+1 : n;ly = i-3<n ? 1 : i-3-n+2;rx = i<n ? i+1 : n;ry = i<n ? 1 : i-n+2;break;}}if(query(lx,ly,rx,ry)){ans = a[rx][ry]^a[lx][ly];}else{ans = a[rx][ry]^1^a[lx][ly];}puts("!");for(int i=1; i<=n; i++){for(int j=1; j<=n; j++) printf("%d",((i+j)&1)?(a[i][j]^ans):a[i][j]);puts("");}fflush(stdout);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1205C Palindromic Paths (交互题、DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。