2020-2021:teams:namespace:面向对象与stl
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:面向对象与stl [2020/07/07 11:06] great_designer [set] |
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这种高级东西的，一般是非常困难的题目。 | 在算法比赛里，能够用到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.1594091182.txt.gz · 最后更改: 2020/07/07 11:06 由 great_designer
