【P3662】[USACO17FEB]Why Did the Cow Cross the Road II S
求解连续的k个数的最大值，利用前缀和维护即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e6+10; 4 int sum[N]; 5 int main() 6 { 7 int n,b,k; 8 scanf("%d%d%d",&n,&k,&b); 9 for(int i=0,x;i<b;i++){ 10 scanf("%d",&x); 11 sum[x] = 1 ; 12 } 13 for(int i=1;i<=n;i++) sum[i] = sum[i-1] + sum[i] ; 14 int ans = n ; 15 for(int i=1;i+k-1<=n;i++){ 16 ans = min( sum[i+k-1] - sum[i-1] , ans); 17 } 18 printf("%d ",ans); 19 return 0 ; 20 }
【P1540 机器翻译】
利用数组来存是否出现过，因为容量优先，所以可以开一个数组模拟队列出队和入队过程即可。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 const int N = 1e5+10; 6 int vis[N],a[N],cnt,n,m; 7 int main() 8 { 9 int L = 0 , R = 0 , x ; 10 scanf("%d%d",&m,&n); 11 for(int i=0;i<n;i++){ 12 scanf("%d",&x); 13 if( vis[x] == 0){ 14 15 vis[ x ] = 1 ; 16 cnt ++ ; 17 a[++R] = x ; 18 if( R > m ){ 19 vis[a[++L]] = 0; 20 } 21 } 22 } 23 printf("%d ",cnt); 24 return 0; 25 }
【P1090 合并果子】
利用二叉堆或者用STL中的优先队列进行插入和取出操作。完成这一个贪心的过程。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+100; 4 typedef long long ll; 5 ll a[N]; 6 int main() 7 { 8 priority_queue< ll , vector<ll>, greater<ll> > Q; 9 //priority_queue< ll > Q; 10 int n; 11 cin >> n ; 12 for( int i = 1 ; i <= n ; i++ ){ 13 cin >> a[i]; 14 Q.push(a[i]); 15 } 16 if( n < 2 ){ 17 cout << a[1] << endl; 18 }else{ 19 ll ans = 0 ; 20 ll cur; 21 n--; 22 while( n-- ){ 23 cur = Q.top(); 24 //cout << " Cur 1 : " << cur <<endl; 25 Q.pop(); 26 cur = cur + Q.top(); 27 //cout << " Cur 2 : " << cur <<endl; 28 Q.pop(); 29 ans += cur ; 30 Q.push(cur); 31 } 32 cout<<ans<<endl; 33 } 34 return 0; 35 }
【P1996 约瑟夫问题】
利用队列或者链表模拟，或者用STL进行模拟即可。
我这里就使用最传统的模式。
1 #include<cstdio> 2 #include<queue> 3 #include<cstdlib> 4 using namespace std; 5 const int N = 1e5+10; 6 7 typedef struct Node{ 8 int val ; 9 Node * next; 10 }Node; 11 Node *head , *tail , *tmp, *p ; 12 13 int main() 14 { 15 int n,m; 16 head = new Node ; 17 head -> next = NULL ; 18 tail = head ; 19 scanf("%d%d",&n,&m); 20 for(int i=1;i<=n;i++){ 21 p = new Node ; 22 p -> val = i ; 23 p -> next = NULL ; 24 tail -> next = p ; 25 tail = p ; 26 } 27 28 p = head -> next ; 29 tail -> next = head -> next; 30 31 for(int i=1;i<=n;i++){ 32 33 for(int j=0;j<m-2;j++){ 34 p = p->next; 35 } 36 printf("%d ",p->next->val); 37 tmp = p -> next ; 38 p -> next = tmp -> next ; 39 p = p -> next ; 40 free(tmp); 41 } 42 return 0; 43 }
【P1160 队列安排】
题目描述
一个学校里老师要将班上NN个同学排成一列，同学被编号为1∼N，他采取如下的方法：
-
先将1号同学安排进队列，这时队列中只有他一个人；
-
2-N号同学依次入列，编号为i的同学入列方式为：老师指定编号为i的同学站在编号为1∼(i−1)中某位同学（即之前已经入列的同学）的左边或右边；
-
从队列中去掉M(M<N)个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
输入输出样例
输入 #1
4 1 0 2 1 1 0 2 3 3
输出 #1
2 4 1
说明/提示
样例解释：
将同学2插入至同学11左边，此时队列为：
2 1
将同学3插入至同学22右边，此时队列为：
2 3 1
将同学4插入至同学11左边，此时队列为：
2 3 4 1
将同学3从队列中移出，此时队列为：
2 4 1
同学3已经不在队列中，忽略最后一条指令
最终队列：
2 4 1
【题意】名字很像用队列来做，其实使用链表来做的。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 typedef struct Node{ 5 Node * L ; 6 Node * R ; 7 int val ; 8 Node () {} 9 }Node ; 10 11 Node *Ptr[N]; 12 int n,m,k,opt; 13 int vis[N]; 14 int main() 15 { 16 Node *Start = new Node() ; 17 Node *First = new Node() ; 18 Node *End = new Node() ; 19 Node *tmp = new Node() ; 20 21 22 23 Start->L = NULL ; 24 Start->R = First ; 25 First->L = Start; 26 First->R = End ; 27 First->val = 1 ; 28 End->L = First ; 29 End->R = NULL ; 30 31 32 Ptr[1] = First; 33 34 //printf("#### %d #### ",Ptr[1]->val ); 35 scanf("%d",&n); 36 37 for(int i=2;i<=n;i++){ 38 39 scanf("%d%d",&k,&opt); 40 Node *p = new Node(); 41 p->val = i ; 42 if( opt == 1 ){ 43 tmp = Ptr[k]-> R ; 44 45 p->R = tmp ; 46 p->L = Ptr[k]; 47 48 tmp->L = p; 49 Ptr[k]->R = p ; 50 51 Ptr[i] = p ; 52 }else{ 53 tmp = (Ptr[k]->L) ; 54 55 p->L = tmp ; 56 p->R = Ptr[k]; 57 58 tmp->R = p; 59 Ptr[k]->L = p ; 60 61 62 Ptr[i] = p ; 63 } 64 } 65 66 scanf("%d",&m); 67 for(int i=1;i<=m;i++){ 68 scanf("%d",&k); 69 vis[k] = 1 ; 70 } 71 int cnt = 120; 72 for( tmp = Start->R; tmp->R != NULL ; tmp = tmp->R ){ 73 if( !vis[tmp->val] ){ 74 printf("%d",tmp->val); 75 if( tmp->R == End ){ 76 printf(" "); 77 }else{ 78 printf(" "); 79 } 80 } 81 82 //cnt --; 83 } 84 return 0; 85 }
【P2776小组队列】
【题解】
求解下一个是哪一组的同学弹出，如果弹空就下一组。
需要用两个队列来存放，第一个队列是存放哪一个组排在前面，第二个队列是哪一组存放哪些同学。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+100; 4 5 template <class T> 6 void read( T & x ){ 7 x = 0 ; 8 int f = 1 ; 9 char c =getchar(); 10 while( !('0'<=c && c<='9') ){ 11 if( c=='-' ) f = -1 ; 12 c = getchar(); 13 } 14 while( ('0'<=c && c<='9') ){ 15 x = (x<<1) + (x<<3) + c-'0'; 16 c = getchar(); 17 } 18 x = x * f ; 19 } 20 queue<int> Q , que[305]; 21 char opt[N] ; 22 int group[N]; 23 int n,m,k,t; 24 25 int main(){ 26 read(n),read(m); 27 for(int i=0;i<n;i++) read( group[i] ); 28 29 read(k); 30 for(int i=1;i<=k;i++){ 31 scanf("%s",opt); 32 if( opt[1] == 'u' ){ 33 scanf("%d",&t); 34 if( que[group[t]].empty() ) Q.push(group[t]); 35 que[group[t]].push(t); 36 37 }else{ 38 int tmp = Q.front(); 39 printf("%d ",que[tmp].front()); 40 que[tmp].pop(); 41 if( que[tmp].empty() ) 42 Q.pop(); 43 } 44 } 45 return 0; 46 }
【P1087 FBI树】
非常感谢这位网友的图。
其实我一直没有看懂题意是什么。
F 长度为8
F F 长度为4
F B F I 长度为2
I B B B I B I I长度为1
| | | | | | | |
| | | | | | | |
1 0 0 0 1 0 1 1
【题意】
给出一个2^n的序列，然后最底的一层就是题目所给的。请问这棵树建出来之后就需要看看。每一个节点的情况。
利用后序遍历序列。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e6+10; 4 int tree[N],n; 5 6 void print( int K , int d ){ 7 if( K == 0 ){ 8 printf("B"); 9 }else if( K == 1<<d ){ 10 printf("I"); 11 }else{ 12 printf("F"); 13 } 14 } 15 16 int dfs(int id,int dep){ 17 int res = 0 ; 18 if( dep == n ){ 19 return tree[id]; 20 } 21 22 int L = dfs(id<<1 ,dep + 1); 23 print(L,(n-dep-1)); 24 int R = dfs(id<<1|1,dep + 1); 25 print(R,(n-dep-1)); 26 tree[id] = L + R ; 27 if( id == 1 ){ 28 print(tree[id],n); 29 } 30 return tree[id]; 31 } 32 int main() 33 { 34 scanf("%d",&n); 35 36 for(int i=1<<n ; i<1<<n+1 ; i++ ) 37 scanf("%1d",&tree[i]); 38 if( n == 0 ){ 39 printf("%c ",tree[1] ? 'I':'B'); 40 return 0; 41 } 42 dfs(1,0); 43 44 return 0; 45 }
【P1827 美国血统 American Heritage】
【题解】
经典问题之知道两个序列，如何求第三条。
我看了别人的代码后，一拍脑袋，发现是如此简单。
我们可以利用下标来存起末位置。
然后利用前缀和中缀的根节点的位置，确定左子树和右子树的规模。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 void dfs( string u , string v ){ 5 if( !u.length() ) return ; 6 int pos = u.find( v[0] ) ; 7 dfs( u.substr(0,pos) , v.substr(1,pos) ) ; 8 dfs( u.substr(pos+1) , v.substr(pos+1) ) ; 9 cout << v[0] ; 10 } 11 int main() 12 { 13 ios_base :: sync_with_stdio(false); 14 cin.tie(NULL) , cout.tie(NULL) ; 15 string s , t ; 16 cin >> s >> t ; 17 dfs( s , t ); 18 cout << endl; 19 return 0; 20 }
【P1030 求先序排列】
【题意】
知道中序遍历和后序遍历，求先序遍历
1 #include<bits/stdc++.h> 2 using namespace std; 3 void dfs( string u , string v ){ 4 if( !u.length() ) return ; 5 int pos = u.find( v[v.length()-1] ); 6 cout << v[v.length()-1] ; 7 dfs( u.substr(0,pos) , v.substr(0,pos) ); 8 dfs( u.substr(pos+1) , v.substr(pos,v.length()-pos-1) ); 9 } 10 int main() 11 { 12 ios_base :: sync_with_stdio(false ); 13 cin.tie(NULL) , cout.tie(NULL) ; 14 string u , v ; 15 cin >> u >> v ; 16 dfs( u , v ); 17 cout << endl; 18 return 0; 19 }