程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj 3519: [Zjoi2014] 消棋子題解

bzoj 3519: [Zjoi2014] 消棋子題解

編輯：C++入門知識

【序言】在大家懷疑的眼光下，我做了一個中午和半個下午、調了一個晚上的題目總算A了！

【原題】

消棋子是一個有趣的游戲。游戲在一個r * c的棋盤上進行。棋盤的每個格

子，要麼是空，要麼是一種顏色的棋子。同一種顏色的棋子恰好有兩個。每一輪，
玩家可以選擇一個空格子(x, y)，並選擇上下左右四個方向中的兩個方向，如果
在這兩個方向上均存在有棋子的格子，而且沿著這兩個方向上第一個遇到的棋子
顏色相同，那麼，我們將這兩個棋子拿走，並稱之為合法的操作。否則稱這個操
作不合法，游戲不會處理這個操作。游戲的目的是消除盡量多的棋子。
給出這樣一個游戲和一個人的玩法。你需要：
z 指出此人能消去多少棋子。
z 給出一種能消去最多棋子的方案。
【輸入格式】
在輸入文件eliminate.in中，第一行給出了整數r, c。第二行給出了整數n，
表示不同顏色數。接下來n行，第i行含4個整數a[i], b[i], c[i], d[i]，表示顏色
為i的兩個格子分別是(a[i], b[i]), (c[i], d[i])。然後是一個整數m，表示此人的操
作數。接下來m行，每行有2個整數和2個字母，代表了他選擇的格子，以及
兩個方向。我們用“UDLR”分別表示上下左右。
【輸出格式】
在輸出文件eliminate.out中，第一行輸出此人能消去多少棋子。第二行含一
個整數k(0 ≤k ≤10
6
)，表示你給出的方案的操作數。接下來k行，每行2個整數和
2個字母，代表你選擇的格子以及兩個方向。
【樣例輸入】
4 4
4
1 1 1 4
1 2 3 4
1 3 3 2
4 1 2 3
6
2 3 U R
2 1 D R
2 2 L R
2 4 L D
3 1 L R
3 3 L U

【樣例】

【分析】開始感覺思路還是挺簡單的，但是代碼寫起來真的是越寫越長。。。

我的基本思路是用set維護相鄰的情況，有點像前幾天做的那道Garden。對於每一個橫行和每一個豎列分別開一個set，表示這一橫行和豎列上的坐標。每次的操作都是基於lower_bound的。

首先考慮讀入的那個人。顯然這個很簡單（代碼23行），直接模擬即可。比如我們要消掉這樣一對棋子。

設左上角(x1,y1)，右下角(x2,y2)。我們可以把x1所在的set裡的y1刪掉，把y1所在的set裡的x1刪掉，對於x2,y2也如此。每次判斷一對點中間路線上是否還有棋子並刪除點。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+wum3s7XEu7nKx9fu08UmIzIwNTQwO6Os1vfSqrXEwum3s9autKbU2tPat9bA4MzWwtuhozwvcD4KPHA+z8iw0daxvdPE3Mm+tcS3xcjrttPB0NbQo6zIu7rzw7+0zsTDs/bG5NbQ0ru21LXjoaPPyMm+tfTV4rbUteOjrMi7uvPF0LbP0rvPwtXittS147i9vfzKx7fx09DExLbUtePS8s6qyb6z/cHL1eK21LXjtvjSsr/J0tTJvrP9wcujrM2syrHI67bToaPXotLi0rvPwrXE0rvQqc+4vdqhozwvcD4KPHA+otnEs9K7teO/ycTcu+HI67bTusO8uLTOo6zS8rTL0qrTw2ZsYWe8x8K80rvPwqGjPC9wPgo8cD6i2rK70qrN/LzHzNjF0HgxPXgyus15MT15MrXEx+m/9qGjPC9wPgo8cD6i28/UyLvDtr7ZtcTKxyh4MSx5MSm6zSh4Mix5MinLxNbcuf3IpbXEtdrSu7j2teOho7WrysfXotLi1rvKx7K7ubu1xKOsu7nT0Ch4MSx5Mim6zSh4Mix5MSmhozwvcD4KPHA+otzV4tK7tePX7r/Twcujodei0uKjrGxvd2VyX2JvdW5ky9Gyu7W9tcTIt7vht7W72GVuZCgpo6y1q8rH1NplcmFzZaGiZmluZLXItcTKsbryo6zI57n7w7vT0MzYxdDKubT4vfjIpbXEaXRlcmF0b3K78sr9JiMyMDU0MDuyu7bUo6y74bGstfS1xKGjuNXQtM3quvPO0r7N0rvWsVJFoaM8L3A+CjxwPsi7uvPO0r7Nv6rKvML+s6S1xLX3s8zQ8tauwsPBy6Gj0tG+rdPQtePN/Mi0xMTA77eiyfrBy7TtzvOjrLWryse3tNX9s8zQ8tS9vNPUvbOko6jL5Mi70NDK/bK7yse63Lbgo6mho8Wqtb2688C0o6y007bUMbj2teO1vTO49rXj1Nm1vTW49rXjo6zWrrrztrzKx7Tzyv2+3cHLoaM8L3A+CjxwPtPayse+zb+qyry21MXEoaPOqsHLt72x46OsztLWu8XE1+7TxSYjMjA1NDA7tcTH6b/2oaM8L3A+CjxwPqG+1OzK/b7ds8zQ8qG/PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#include #include #include using namespace std; bool f[40005][40005];int x1,y1,x2,y2; int main() { freopen("eliminate.in","w",stdout); srand((int)time(0)); int r=10,c=10; printf("%d %d\n",r,c); int n=5; printf("%d\n",n); for (int i=1;i<=n;i++) { while (1) { x1=rand()%r+1;y1=rand()%c+1;x2=rand()%r+1;y2=rand()%c+1; if (!f[x1][y1]&&!f[x2][y2]&&(x1!=x2||y1!=y2)) break; } printf("%d %d %d %d\n",x1,y1,x2,y2); f[x1][y1]=f[x2][y2]=1; } }

真的要好好感謝我的造數據程序。首先是發現了x1==x2特判的時候有點問題。之後就過了8個點，然後剩下的兩個最大的點就一直錯誤，而且答案相差僅一點點！！然後我只好再次無奈的對拍，大約20分鐘後拍出了n==5的錯誤。

一下是錯點圖片：

後來才發現，iterator的指針基本每個函數都有，還開了全局變量。這樣，Find裡的iterator因為執行了一個check過程而有微小的變化。數據真的是太厲害了！

【代碼】

#include
#include
#include
#include
#define N 100005
using namespace std;
mapprex[N],prey[N];
multisetP[N],Q[N],X[N],Y[N];
typedef multiset::iterator It;
It it1,it2,it;
int m,n,r,c,h,t,x,y,x1,x2,y1,y2,i,wri[N][2],id[N][4],flag[N];
char re[N][2];
void Person()
{
  scanf("%d",&m);int ans=0,c[2];char s1[2],s2[2];It it[2];
  while (m--)
  {
    scanf("%d%d%s%s",&x,&y,&s1,&s2);
    if (P[x].find(y)!=P[x].end()) continue;
    int o=0,tx,ty;It it[2];c[0]=-1;c[1]=-2;
    if (s1[0]=='U'||s2[0]=='U') {it[o]=Q[y].lower_bound(x);if (it[o]==Q[y].begin()) continue;c[o]=prey[y][*(--it[o])];o++;}
    if (s1[0]=='L'||s2[0]=='L') {it[o]=P[x].lower_bound(y);if (it[o]==P[x].begin()) continue;c[o]=prex[x][*(--it[o])];o++;}
    if (s1[0]=='D'||s2[0]=='D') {it[o]=Q[y].lower_bound(x);if (it[o]==Q[y].end()) continue;c[o]=prey[y][*it[o]];o++;}
    if (s1[0]=='R'||s2[0]=='R') {it[o]=P[x].lower_bound(y);if (it[o]==P[x].end()) continue;c[o]=prex[x][*it[o]];o++;}
    if (c[0]!=c[1]) continue;
    ans+=1;o=0;
    if (s1[0]=='U'||s2[0]=='U') {tx=*it[o];Q[y].erase(it[o]);P[tx].erase(P[tx].find(y));o++;}
    if (s1[0]=='L'||s2[0]=='L') {ty=*it[o];P[x].erase(it[o]);Q[ty].erase(Q[ty].find(x));o++;}
    if (s1[0]=='D'||s2[0]=='D') {tx=*it[o];Q[y].erase(it[o]);P[tx].erase(P[tx].find(y));o++;}
    if (s1[0]=='R'||s2[0]=='R') {ty=*it[o];P[x].erase(it[o]);Q[ty].erase(Q[ty].find(x));o++;}
  }
  printf("%d ",ans);
}
void y1_s_y2(int num)
{
  if (flag[num]) return;
  it1=X[x1].upper_bound(y1);it2=Y[y2].lower_bound(x1);
  if ((*it1>y2||it1==X[x1].end())&&*it2==x2)
    {re[++t][0]='L';re[t][1]='D';wri[t][0]=x1;wri[t][1]=y2;flag[num]=1;return;}
  it1=Y[y1].upper_bound(x1);it2=X[x2].lower_bound(y1);
  if ((*it1>x2||it1==Y[y1].end())&&*it2==y2)
    {re[++t][0]='R';re[t][1]='U';wri[t][0]=x2;wri[t][1]=y1;flag[num]=1;}
}
void y1_b_y2(int num) 
{
  if (flag[num]) return;
  it1=Y[y1].upper_bound(x1);it2=X[x2].upper_bound(y2);
  if ((*it1>x2||it1==Y[y1].end())&&(*it2>y1||it2==X[x2].end()))
    {re[++t][0]='L';re[t][1]='U';wri[t][0]=x2;wri[t][1]=y1;flag[num]=1;return;}
  it1=X[x1].lower_bound(y2);
  it2=Y[y2].lower_bound(x1);
  if (*it1==y1&&*it2==x2)
    {re[++t][0]='R';re[t][1]='D';wri[t][0]=x1;wri[t][1]=y2;flag[num]=1;}
}
void x1_e_x2(int num)
{
  if (flag[num]) return;  
  if (y1>y2) swap(y1,y2);It it=X[x1].upper_bound(y1);if ((*it)x2) swap(x1,x2),swap(y1,y2);int o=0;
  if (x1==x2) {x1_e_x2(num);return;}
  if (y1==y2) y1_e_y2(num);
  if (y1y2) y1_b_y2(num);
}
void DO(int x,int y)
{
    It dd=Y[y].lower_bound(x);int fd=dd==Y[y].end();
    It rr=X[x].lower_bound(y);int fr=rr==X[x].end();
    It uu=dd;int fu=(uu==Y[y].begin());if (!fu) uu--;
    It ll=rr;int fl=(ll==X[x].begin());if (!fl) ll--;
    int d=*dd,r=*rr,u=*uu,l=*ll;
    if (!fd) check(d,y);
    if (!fu) check(u,y);
    if (!fl) check(x,l);
    if (!fr) check(x,r);
}
void Find()
{
  int G1,G2;
  for (int i=1;i<=n;i++)
  {
     x1=id[i][0];
     y1=id[i][1];
     check(x1,y1);
  }
  while (h