2020-2021:teams:namespace:面向对象与stl
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:面向对象与stl [2020/07/06 21:11] great_designer [deque] |
2020-2021:teams:namespace:面向对象与stl [2020/07/07 11:17] (当前版本) great_designer [deque] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| <del>Warning:找不到对象</del> | <del>Warning:找不到对象</del> | ||
| - | <del>STL容器的真正含义：啊！是大佬（ShiTaLao——方言）！我死了（WSL）</del> | + | <del>STL容器的真正含义：啊！是大佬（方言ShiTaLao）！我死了</del> |
| + | |||
| + | <del>同理，数据库语言SQL的真实含义：啊！是巨佬（方言ShiQuLao）！我死了</del> | ||
| =====vector===== | =====vector===== | ||
| 行 276: | 行 278: | ||
| 看吧，vector的insert功能就是这么方便。一般如果我们需要对一个数组（或者链表）里面执行插入操作，请使用vector来减少代码量。 | 看吧，vector的insert功能就是这么方便。一般如果我们需要对一个数组（或者链表）里面执行插入操作，请使用vector来减少代码量。 | ||
| + | |||
| + | <del>什么？你想写链表？用STL里的list？一个算法比赛用什么链表啊我的天哪（于是list就合理的不写了）</del> | ||
| + | |||
| =====deque===== | =====deque===== | ||
| 行 283: | 行 288: | ||
| 栈和队列都好写，因为它们都是单向增长或移动的。但是双端队列就不太好写了。这时候，我们需要合理运用deque的武器呢。 | 栈和队列都好写，因为它们都是单向增长或移动的。但是双端队列就不太好写了。这时候，我们需要合理运用deque的武器呢。 | ||
| - | （如果您非要开大空间从中间计数，或者取模，我也拦不住对吧。） | + | OJ编号314：毛毛虫。 |
| + | <hidden> | ||
| + | <code C++> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<queue> | ||
| + | #include<algorithm> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | deque<pair<int,int> > q; | ||
| + | bool flag; | ||
| + | int m, n; | ||
| + | int a, b; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | while(~scanf("%d%d", &m, &n)) | ||
| + | { | ||
| + | flag = true; | ||
| + | while (!q.empty())q.pop_back(); | ||
| + | for (int i = 0; i < m; ++i) | ||
| + | { | ||
| + | scanf("%d%d", &a, &b); | ||
| + | q.push_back(make_pair(a, b)); | ||
| + | } | ||
| + | while (n--) | ||
| + | { | ||
| + | scanf("%d%d", &a, &b); | ||
| + | q.pop_front(); | ||
| + | q.push_back(make_pair(a, b)); | ||
| + | } | ||
| + | if (q.front().first == q.back().first && q.front().second == q.back().second) | ||
| + | { | ||
| + | flag = false; | ||
| + | } | ||
| + | while (!q.empty()) | ||
| + | { | ||
| + | printf("%d %d\n", q.back().first, q.back().second); | ||
| + | q.pop_back(); | ||
| + | } | ||
| + | if (!flag) | ||
| + | { | ||
| + | puts("oh no"); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | OJ编号315：滚动的窗口。 | ||
| + | |||
| + | <hidden> | ||
| + | <code C++> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<queue> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | deque<int> dmin; | ||
| + | deque<int> dmax; | ||
| + | |||
| + | int a[100010]; | ||
| + | int top; | ||
| + | |||
| + | inline void write(int x) | ||
| + | { | ||
| + | if(x < 0)putchar('-'),x=-x; | ||
| + | if (x > 9)write(x / 10); | ||
| + | putchar(x % 10 + 48); | ||
| + | } | ||
| + | |||
| + | inline int read() | ||
| + | { | ||
| + | int k = 0, f = 1; | ||
| + | char c = getchar(); | ||
| + | while (c < '0' || c>'9') | ||
| + | { | ||
| + | if (c == '-')f = -1; | ||
| + | c = getchar(); | ||
| + | } | ||
| + | while (c >= '0' && c <= '9') | ||
| + | { | ||
| + | k = (k << 1) + (k << 3) + c - 48; | ||
| + | c = getchar(); | ||
| + | } | ||
| + | return k * f; | ||
| + | } | ||
| + | |||
| + | int n, k; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | while(~scanf("%d%d", &n, &k)) | ||
| + | { | ||
| + | int i; | ||
| + | for(i = 1; i <= n; ++i)a[i] = read(); | ||
| + | while (!dmin.empty())dmin.pop_back(); | ||
| + | for (i = 1; i <= k; ++i) | ||
| + | { | ||
| + | if (dmin.empty())dmin.push_back(i); | ||
| + | else | ||
| + | { | ||
| + | while (!dmin.empty() && a[dmin.back()] > a[i]) dmin.pop_back(); | ||
| + | dmin.push_back(i); | ||
| + | } | ||
| + | } | ||
| + | write(a[dmin.front()]); putchar(' '); | ||
| + | for (i = k + 1; i <= n; ++i) | ||
| + | { | ||
| + | while (!dmin.empty() && dmin.front() <= i - k)dmin.pop_front(); | ||
| + | if (dmin.empty())dmin.push_back(i); | ||
| + | else | ||
| + | { | ||
| + | while (!dmin.empty() && a[dmin.back()] > a[i]) dmin.pop_back(); | ||
| + | dmin.push_back(i); | ||
| + | } | ||
| + | write(a[dmin.front()]); putchar(' '); | ||
| + | } | ||
| + | putchar('\n'); | ||
| + | while (!dmax.empty())dmax.pop_back(); | ||
| + | for (i = 1; i <= k; ++i) | ||
| + | { | ||
| + | if (dmax.empty())dmax.push_back(i); | ||
| + | else | ||
| + | { | ||
| + | while (!dmax.empty() && a[dmax.back()] < a[i]) dmax.pop_back(); | ||
| + | dmax.push_back(i); | ||
| + | } | ||
| + | } | ||
| + | write(a[dmax.front()]); putchar(' '); | ||
| + | for (i = k + 1; i <= n; ++i) | ||
| + | { | ||
| + | while (!dmax.empty() && dmax.front() <= i - k)dmax.pop_front(); | ||
| + | if (dmax.empty())dmax.push_back(i); | ||
| + | else | ||
| + | { | ||
| + | while (!dmax.empty() && a[dmax.back()] < a[i]) dmax.pop_back(); | ||
| + | dmax.push_back(i); | ||
| + | } | ||
| + | write(a[dmax.front()]); putchar(' '); | ||
| + | } | ||
| + | putchar('\n'); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </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===== | ||
| 行 302: | 行 902: | ||
| 在这里就不写了。参见[[广度优先搜索_bfs_与标数最短路_dijkstra]]。 | 在这里就不写了。参见[[广度优先搜索_bfs_与标数最短路_dijkstra]]。 | ||
| - | 这个文中也提到，如何将默认大顶堆转换为小顶堆呢？**取相反数**存储与读取就完了。这是个很经典的技巧，相比之下在定义中修改优先级略为难记。 | + | 这个文中也提到，如何将默认大顶堆**转换为小顶堆**呢？**取相反数**存储与读取就完了。这是个很经典的技巧，相比之下在定义中修改优先级略为难记。 |
| 不过一定要记得读取的时候也要取相反——存的时候是反着存的，很容易忘。 | 不过一定要记得读取的时候也要取相反——存的时候是反着存的，很容易忘。 | ||
2020-2021/teams/namespace/面向对象与stl.1594041089.txt.gz · 最后更改: 2020/07/06 21:11 由 great_designer
