CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » namespace » 面向对象与stl
2020-2021:teams:namespace:面向对象与stl

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:面向对象与stl [2020/07/07 11:04]
great_designer [vector] 		2020-2021:teams:namespace:面向对象与stl [2020/07/07 11:17] (当前版本)
great_designer [deque]
行 287: 行 287:
  
 栈和队列都好写，因为它们都是单向增长或移动的。但是双端队列就不太好写了。这时候，我们需要合理运用deque的武器呢。 栈和队列都好写，因为它们都是单向增长或移动的。但是双端队列就不太好写了。这时候，我们需要合理运用deque的武器呢。
- 
-（如果您非要开大空间从中间计数，或者取模，我也拦不住对吧。） 
  
 OJ编号314：毛毛虫。 OJ编号314：毛毛虫。
行 441: 行 439:
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
 +
 +<​del>​当然，如果您非要开大空间从中间计数，或者取模，我也拦不住</​del>​
 =====set===== =====set=====
  
 +在算法比赛里，能够用到set这种高级东西的，一般是非常困难的题目。
 +
 +下面举几个例子：
 +
 +OJ编号89：LCSDataEnhanced。
 +
 +<​hidden>​
 +<code C++>
 +
 +#​include<​stdio.h>​
 +#​include<​string.h>​
 +#​include<​math.h>​
 +
 +#​include<​string>​
 +#​include<​set>​
 +
 +using namespace std;
 +
 +char A[110],​B[110];​
 +char tmp[110];
 +int n,m;
 +int dp[110][110];​
 +int lasta[110][27];​
 +int lastb[110][27];​
 +int targetLen;
 +set<​string>​ ans;
 +
 +void init()
 +{
 + memset(dp,​0,​sizeof(dp));​
 + memset(lasta,​0,​sizeof(lasta));​
 + memset(lastb,​0,​sizeof(lastb));​
 + memset(tmp,​0,​sizeof(tmp));​
 + ans.clear();​
 +}
 +
 +void buildDP()
 +{
 + int i;
 + for(i=1;​i<​=n;​++i)
 + {
 + int j;
 + for(j=1;​j<​=m;​++j)
 + {
 + if(A[i]==B[j])
 + {
 + dp[i][j]=dp[i][j]>​(dp[i-1][j-1]+1)?​dp[i][j]:​(dp[i-1][j-1]+1);​
 + }
 + else
 + {
 + dp[i][j]=dp[i-1][j]>​dp[i][j-1]?​dp[i-1][j]:​dp[i][j-1];​
 + }
 + }
 + }
 + targetLen=dp[n][m];​
 +}
 +
 +void buildLast()
 +{
 + int i;
 + for(i=1;​i<​=n;​++i)
 + {
 + int j;
 + for(j=0;​j<​26;​++j)
 + {
 + if(A[i]=='​A'​+j)
 + {
 + lasta[i][j]=i;​
 + }
 + else
 + {
 + lasta[i][j]=lasta[i-1][j];​
 + }
 + }
 + }
 + for(i=1;​i<​=m;​++i)
 + {
 + int j;
 + for(j=0;​j<​26;​++j)
 + {
 + if(B[i]=='​A'​+j)
 + {
 + lastb[i][j]=i;​
 + }
 + else
 + {
 + lastb[i][j]=lastb[i-1][j];​
 + }
 + }
 + }
 +}
 +
 +void dfs(int i,int j,int len)
 +{
 + if(len<​=0)
 + {
 + ans.insert(string(tmp+1));​
 + return;
 + }
 + if(i>​0&&​j>​0)
 + {
 + int k;
 + for(k=0;​k<​26;​++k)
 + {
 + int t1=lasta[i][k];​
 + int t2=lastb[j][k];​
 + if(dp[t1][t2]==len)
 + {
 + tmp[len]='​A'​+k;​
 + dfs(t1-1,​t2-1,​len-1);​
 + }
 + }
 + }
 +}
 +
 +void printAns()
 +{
 + set<​string>::​iterator it;
 + for(it=ans.begin();​it!=ans.end();​++it)
 + {
 + puts((*it).c_str());​
 + }
 +}
 +
 +int main()
 +{
 + while(~scanf("​%s%s",​A+1,​B+1))
 + {
 + init();
 + n=strlen(A+1);​
 + m=strlen(B+1);​
 + buildDP();​
 + buildLast();​
 + tmp[targetLen+1]='​\0';​
 + dfs(n,​m,​targetLen);​
 + printAns();​
 + }
 +}
 +
 +</​code>​
 +</​hidden>​
 +
 +OJ编号279：Z君的日常之集合处理。
 +
 +<​hidden>​
 +<code C++>
 +
 +#​include<​stdio.h>​
 +#​include<​algorithm>​
 +#​include<​set>​
 +#​include<​vector>​
 +
 +using namespace std;
 +
 +char tmp[3];
 +char op;
 +int t,n,m;
 +int tmpint;
 +
 +int main()
 +{
 + while(~scanf("​%d",​ &t))
 + {
 + while(t--)
 + {
 + scanf("​%s%d%d",​tmp,&​n,&​m);​
 + op=tmp[0];​
 + vector<​int>​ a,b;
 + int i;
 + for(i=0;​i<​n;​++i)
 + {
 + scanf("​%d",&​tmpint);​
 + a.push_back(tmpint);​
 + }
 + for(i=0;​i<​m;​++i)
 + {
 + scanf("​%d",&​tmpint);​
 + b.push_back(tmpint);​
 + }
 + sort(a.begin(),​a.end());​
 + sort(b.begin(),​b.end());​
 + if(op=='​+'​)
 + {
 + vector<​int>​ c;
 + set_union(a.begin(),​a.end(),​b.begin(),​b.end(),​back_inserter(c),​less<​int>​());​
 + std::​vector<​int>::​iterator m;
 + for(m=c.begin();​m!=c.end();​m++)
 + {
 + printf("​%d ",*m);
 + }
 + printf("​\n"​);​
 + }
 + else
 + {
 + vector<​int>​ c;
 + set_difference(a.begin(),​a.end(),​b.begin(),​b.end(),​back_inserter(c),​less<​int>​());​
 + if(!c.empty())
 + {
 + std::​vector<​int>::​iterator m;
 + for(m=c.begin();​m!=c.end();​m++) ​
 + {
 + printf("​%d ",*m);
 + } ​
 + printf("​\n"​);​
 + }
 + else
 + {
 + printf("​empty\n"​);​
 + }
 + }
 + }
 + }
 +}
 +
 +</​code>​
 +</​hidden>​
 +
 +OJ编号516：ModricWang的星灵棋。
 +
 +<​hidden>​
 +<code C++>
 +
 +#​include<​stdio.h>​
 +#​include<​string.h>​
 +
 +#​include<​set>​
 +
 +using namespace std; 
 +
 +set<​unsigned int> vis[5];
 +
 +bool win[171];
 +
 +struct State
 +{
 + unsigned char row[4],​col[4];​
 + unsigned char left,right;
 + unsigned char rc[2][2];
 + short step,turn;
 +};
 +
 +bool putChess(struct State *s,const int r,const int c,unsigned char p)
 +{
 + unsigned char pl2r=p<<​2*r,​pl2c=p<<​2*c,​al2r=~(3<<​2*r),​al2c=~(3<<​2*c);​
 + s->​row[r]&​=al2c,​s->​row[r]|=pl2c;​
 + if(win[s->​row[r]])
 + {
 + return 1;
 + }
 + s->​col[c]&​=al2r,​s->​col[c]|=pl2r;​
 + if(win[s->​col[c]])
 + {
 + return 1;
 + } 
 + if(r==c)
 + {
 + s->​left&​=al2c,​s->​left|=pl2c;​
 + if(win[s->​left])
 + {
 + return 1;
 + }
 + }
 + if(r+c==3)
 + {
 + s->​right&​=al2r,​s->​right|=pl2r;​
 + if(win[s->​right])
 + {
 + return 1;
 + }
 + }
 + return 0;
 +}
 +
 +struct State q[666666];
 +
 +int head;
 +int tail;
 +
 +bool getChess(int r,int c)
 +{
 + if(r<​0||c<​0||r>​3||c>​3)
 + {
 + return 0;
 + }
 + else
 + {
 + return ((unsigned char)(q[head].row[r]>>​2*c)&​3)==q[head].turn;​
 + }
 +}
 +
 +void before(int first,int second,int kind)
 +{
 + q[tail]=q[head];​
 + q[tail].rc[first][second]+=kind;​
 + ++q[tail].step; ​
 +}
 +
 +void after()
 +{
 + if(!vis[q[head].turn+1].count(*(unsigned int*)q[tail].row)) ​
 + { 
 + vis[q[head].turn+1].insert(*(unsigned int*)q[tail].row); ​
 + q[tail].turn=3-q[head].turn; ​
 + tail++;
 + } 
 +}
 +
 +int main()
 +{
 + struct State src;
 + memset(&​src,​0,​sizeof src);
 + win[170]=win[85]=1;​
 + int firstzero=1;​
 + int r;
 + for(r=0;​r<​4;​++r)
 + {
 + char str[123];
 + scanf("​%s",​str);​
 + int c;
 + for(c=0;​c<​4;​++c)
 + {
 + switch(str[c])
 + {
 + case '​B':​
 + if(putChess(&​src,​r,​c,​1))
 + {
 + puts("​0"​); ​
 + return 0;
 + } ​
 + break;
 + case '​W':​
 + if(putChess(&​src,​r,​c,​2))
 + {
 + puts("​0"​);​
 + return 0;
 + } ​
 + break;
 + case '​O':​
 + if(firstzero)
 + { ​
 + src.rc[1][0]=r,​src.rc[0][0]=c,​firstzero=0;​
 + }
 + else
 + { ​
 + src.rc[1][1]=r,​src.rc[0][1]=c;​
 + }
 + break;
 + }
 + }
 + }
 + head=0,​tail=2;​
 + q[0]=q[1]=src;​
 + q[1].turn=2;​
 + vis[2].insert(*(unsigned int*)src.row);​
 + vis[3].insert(*(unsigned int*)src.row);​
 + for(;​head!=tail;​head++)
 + {
 + if(getChess(q[head].rc[1][1]-1,​q[head].rc[0][1])) ​
 + { 
 + before(1,​1,​-1);​
 + if(putChess(&​q[tail],​q[tail].rc[1][1],​q[head].rc[0][1],​0)||putChess(&​q[tail],​q[head].rc[1][1],​q[head].rc[0][1],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + } 
 + if(getChess(q[head].rc[1][1],​q[head].rc[0][1]-1)) ​
 + { 
 + before(0,​1,​-1);​
 + if(putChess(&​q[tail],​q[head].rc[1][1],​q[tail].rc[0][1],​0)||putChess(&​q[tail],​q[head].rc[1][1],​q[head].rc[0][1],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + } 
 + if(getChess(q[head].rc[1][1]+1,​q[head].rc[0][1]))
 + { 
 + before(1,​1,​1);​
 + if(putChess(&​q[tail],​q[tail].rc[1][1],​q[head].rc[0][1],​0)||putChess(&​q[tail],​q[head].rc[1][1],​q[head].rc[0][1],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + } 
 + if(getChess(q[head].rc[1][1],​q[head].rc[0][1]+1)) ​
 + { 
 + before(0,​1,​1);​
 + if(putChess(&​q[tail],​q[head].rc[1][1],​q[tail].rc[0][1],​0)||putChess(&​q[tail],​q[head].rc[1][1],​q[head].rc[0][1],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + }
 + if(getChess(q[head].rc[1][0]-1,​q[head].rc[0][0])) ​
 + { 
 + before(1,​0,​-1);​
 + if(putChess(&​q[tail],​q[tail].rc[1][0],​q[head].rc[0][0],​0)||putChess(&​q[tail],​q[head].rc[1][0],​q[head].rc[0][0],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + } 
 + if(getChess(q[head].rc[1][0],​q[head].rc[0][0]-1)) ​
 + { 
 + before(0,​0,​-1);​
 + if(putChess(&​q[tail],​q[head].rc[1][0],​q[tail].rc[0][0],​0)||putChess(&​q[tail],​q[head].rc[1][0],​q[head].rc[0][0],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + } 
 + if(getChess(q[head].rc[1][0]+1,​q[head].rc[0][0])) ​
 + { 
 + before(1,​0,​1);​
 + if(putChess(&​q[tail],​q[tail].rc[1][0],​q[head].rc[0][0],​0)||putChess(&​q[tail],​q[head].rc[1][0],​q[head].rc[0][0],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + } 
 + if(getChess(q[head].rc[1][0],​q[head].rc[0][0]+1)) ​
 + { 
 + before(0,​0,​1);​
 + if(putChess(&​q[tail],​q[head].rc[1][0],​q[tail].rc[0][0],​0)||putChess(&​q[tail],​q[head].rc[1][0],​q[head].rc[0][0],​q[head].turn))
 + {
 + printf("​%d",​q[tail].step);​
 + return 0;
 + }
 + after();
 + }
 + }
 +}
 +
 +</​code>​
 +</​hidden>​
 +
 +<​del>​这些题都太难了，唉</​del>​
  
 =====map===== =====map=====
2020-2021/teams/namespace/面向对象与stl.1594091049.txt.gz · 最后更改: 2020/07/07 11:04 由 great_designer

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3