首页 > 代码库 > Mutual Training for Wannafly Union #7（待续）
Mutual Training for Wannafly Union #7（待续）
剩下的题等礼拜天补吧。最近要赶作业什么的还要补点dp
A - Ada and List（伸展树或者vector暴力- -）
思路：
vector玄学均摊复杂度...能直接暴力A了。窝居然写了人生第一个伸展树- -。蠢到家了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 vector<int>vec; 6 int n, m; 7 scanf("%d%d", &n, &m); 8 for(int i = 1; i <= n; i++) 9 { 10 int x; 11 scanf("%d", &x); 12 vec.push_back(x); 13 } 14 15 for(int i = 0; i < m; i++) 16 { 17 int cmd, k, x; 18 scanf("%d%d", &cmd, &k); 19 if(cmd == 1) 20 { 21 scanf("%d", &x); 22 vec.insert(vec.begin() + k - 1, x); 23 } 24 else if(cmd == 2) 25 { 26 vec.erase(vec.begin() + k - 1); 27 } 28 else if(cmd == 3) 29 { 30 printf("%d\n", vec[k - 1]); 31 } 32 } 33 return 0; 34 }
这个伸展树的板子还是挺厉害了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define Key_value ch[ch[root][1]][0] 5 const int MAXN = 500010; 6 const int INF = 0x3f3f3f3f; 7 int pre[MAXN],ch[MAXN][2],key[MAXN],size[MAXN]; 8 int root,tot1; 9 int sum[MAXN],rev[MAXN],same[MAXN]; 10 int lx[MAXN],rx[MAXN],mx[MAXN]; 11 int s[MAXN],tot2;//内存池和容量 12 int a[MAXN]; 13 int n,q; 14 15 void NewNode(int &r,int father,int k) 16 { 17 if(tot2) r = s[tot2--];//取的时候是tot2--,存的时候就是++tot2 18 else r = ++tot1; 19 pre[r] = father; 20 ch[r][0] = ch[r][1] = 0; 21 key[r] = k; 22 sum[r] = k; 23 rev[r] = same[r] = 0; 24 lx[r] = rx[r] = mx[r] = k; 25 size[r] = 1; 26 } 27 void Update_Rev(int r) 28 { 29 if(!r)return; 30 swap(ch[r][0],ch[r][1]); 31 swap(lx[r],rx[r]); 32 rev[r] ^= 1; 33 } 34 void Update_Same(int r,int v) 35 { 36 if(!r)return; 37 key[r] = v; 38 sum[r] = v*size[r]; 39 lx[r] = rx[r] = mx[r] = max(v,v*size[r]); 40 same[r] = 1; 41 } 42 void push_up(int r) 43 { 44 int lson = ch[r][0], rson = ch[r][1]; 45 size[r] = size[lson] + size[rson] + 1; 46 sum[r] = sum[lson] + sum[rson] + key[r]; 47 lx[r] = max(lx[lson],sum[lson] + key[r] + max(0,lx[rson])); 48 rx[r] = max(rx[rson],sum[rson] + key[r] + max(0,rx[lson])); 49 mx[r] = max(0,rx[lson]) + key[r] + max(0,lx[rson]); 50 mx[r] = max(mx[r],max(mx[lson],mx[rson])); 51 } 52 void push_down(int r) 53 { 54 if(same[r]) 55 { 56 Update_Same(ch[r][0],key[r]); 57 Update_Same(ch[r][1],key[r]); 58 same[r] = 0; 59 } 60 if(rev[r]) 61 { 62 Update_Rev(ch[r][0]); 63 Update_Rev(ch[r][1]); 64 rev[r] = 0; 65 } 66 } 67 void Build(int &x,int l,int r,int father) 68 { 69 if(l > r)return; 70 int mid = (l+r)/2; 71 NewNode(x,father,a[mid]); 72 Build(ch[x][0],l,mid-1,x); 73 Build(ch[x][1],mid+1,r,x); 74 push_up(x); 75 } 76 void Init() 77 { 78 root = tot1 = tot2 = 0; 79 ch[root][0] = ch[root][1] = size[root] = pre[root] = 0; 80 same[root] = rev[root] = sum[root] = key[root] = 0; 81 lx[root] = rx[root] = mx[root] = -INF; 82 NewNode(root,0,-1); 83 NewNode(ch[root][1],root,-1); 84 for(int i = 0;i < n;i++) 85 scanf("%d",&a[i]); 86 Build(Key_value,0,n-1,ch[root][1]); 87 push_up(ch[root][1]); 88 push_up(root); 89 } 90 //旋转,0为左旋，1为右旋 91 void Rotate(int x,int kind) 92 { 93 int y = pre[x]; 94 push_down(y); 95 push_down(x); 96 ch[y][!kind] = ch[x][kind]; 97 pre[ch[x][kind]] = y; 98 if(pre[y]) 99 ch[pre[y]][ch[pre[y]][1]==y] = x; 100 pre[x] = pre[y]; 101 ch[x][kind] = y; 102 pre[y] = x; 103 push_up(y); 104 } 105 //Splay调整，将r结点调整到goal下面 106 void Splay(int r,int goal) 107 { 108 push_down(r); 109 while(pre[r] != goal) 110 { 111 if(pre[pre[r]] == goal) 112 { 113 push_down(pre[r]); 114 push_down(r); 115 Rotate(r,ch[pre[r]][0] == r); 116 } 117 else 118 { 119 push_down(pre[pre[r]]); 120 push_down(pre[r]); 121 push_down(r); 122 int y = pre[r]; 123 int kind = ch[pre[y]][0]==y; 124 if(ch[y][kind] == r) 125 { 126 Rotate(r,!kind); 127 Rotate(r,kind); 128 } 129 else 130 { 131 Rotate(y,kind); 132 Rotate(r,kind); 133 } 134 } 135 } 136 push_up(r); 137 if(goal == 0) root = r; 138 } 139 int Get_kth(int r,int k) 140 { 141 push_down(r); 142 int t = size[ch[r][0]] + 1; 143 if(t == k)return r; 144 if(t > k)return Get_kth(ch[r][0],k); 145 else return Get_kth(ch[r][1],k-t); 146 } 147 148 //在第pos个数后面插入tot个数 149 void Insert(int pos,int tot) 150 { 151 for(int i = 0;i < tot;i++)scanf("%d",&a[i]); 152 Splay(Get_kth(root,pos+1),0); 153 Splay(Get_kth(root,pos+2),root); 154 Build(Key_value,0,tot-1,ch[root][1]); 155 push_up(ch[root][1]); 156 push_up(root); 157 } 158 159 //删除子树 160 void erase(int r) 161 { 162 if(!r)return; 163 s[++tot2] = r; 164 erase(ch[r][0]); 165 erase(ch[r][1]); 166 } 167 //从第pos个数开始连续删除tot个数 168 void Delete(int pos,int tot) 169 { 170 Splay(Get_kth(root,pos),0); 171 Splay(Get_kth(root,pos+tot+1),root); 172 erase(Key_value); 173 pre[Key_value] = 0; 174 Key_value = http://www.mamicode.com/0; 175 push_up(ch[root][1]); 176 push_up(root); 177 } 178 179 180 //得到第pos个数开始的tot个数的和 181 int Get_Sum(int pos,int tot) 182 { 183 Splay(Get_kth(root,pos),0); 184 Splay(Get_kth(root,pos+tot+1),root); 185 return sum[Key_value]; 186 } 187 188 189 void InOrder(int r) 190 { 191 if(!r)return; 192 push_down(r); 193 InOrder(ch[r][0]); 194 printf("%d ",key[r]); 195 InOrder(ch[r][1]); 196 } 197 198 int main() 199 { 200 scanf("%d%d", &n, &q); 201 Init(); 202 203 while(q--) 204 { 205 int cmd; 206 scanf("%d", &cmd); 207 if(cmd == 1) 208 {//1 k x means that you will add number x to position k 209 int k; 210 scanf("%d", &k); 211 Insert(k - 1, 1); 212 } 213 else if(cmd == 2) 214 {//2 k means that you will erase number from position k 215 int k; 216 scanf("%d", &k); 217 Delete(k, 1); 218 } 219 else if(cmd == 3) 220 {//3 k means that you will print number from position k 221 int k; 222 scanf("%d", &k); 223 printf("%d\n",Get_Sum(k,1)); 224 } 225 226 } 227 return 0; 228 }
B - Ada and Queue（双端队列）
思路：
打个标记，记录一下现在是正着还是反着就好了。然后就是一个双端队列。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 deque<int>que; 6 deque<int>::iterator it; 7 deque<int>::reverse_iterator rit; 8 9 int n; 10 scanf("%d", &n); 11 int tig = 0; 12 while(n--) 13 { 14 char cmd[100]; 15 scanf("%s", cmd); 16 17 if(cmd[0] == ‘b‘) 18 {//back - Print number from back and then erase it 19 if(que.size() == 0) 20 { 21 puts("No job for Ada?"); 22 } 23 else if(tig == 0) 24 { 25 rit = que.rbegin(); 26 cout << *rit << "\n"; 27 que.pop_back(); 28 } 29 else 30 { 31 it = que.begin(); 32 cout << *it << "\n"; 33 que.pop_front(); 34 } 35 } 36 else if(cmd[0] == ‘f‘) 37 {//front - Print number from front and then erase it 38 if(que.size() == 0) 39 { 40 puts("No job for Ada?"); 41 } 42 else if(tig == 1) 43 { 44 rit = que.rbegin(); 45 cout << *rit << "\n"; 46 que.pop_back(); 47 } 48 else if(tig == 0) 49 { 50 it = que.begin(); 51 cout << *it << "\n"; 52 que.pop_front(); 53 } 54 } 55 else if(cmd[0] == ‘r‘) 56 {//reverse - Reverses all elements in queue 57 tig ^= 1; 58 } 59 else if(cmd[0] == ‘p‘) 60 {//push_back N - Add element N to back 61 int x; 62 scanf("%d", &x); 63 if(tig == 0) 64 { 65 que.push_back(x); 66 } 67 else 68 { 69 que.push_front(x); 70 } 71 } 72 else if(cmd[0] == ‘t‘) 73 {//toFront N - Put element N to front 74 int x; 75 scanf("%d", &x); 76 if(tig == 1) 77 { 78 que.push_back(x); 79 } 80 else 81 { 82 que.push_front(x); 83 } 84 } 85 } 86 return 0; 87 }
C - Ada and Field
D - Ada and Cycle（bitset优化bfs）
E - Face Detection（水题暴力枚举）
思路：
暴力枚举一下2*2的小矩形的左上角就好了，wa点！！！n*m的图，两层for循环写成n*n了！！！
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n, m; 5 char ma[55][55]; 6 #define isInside(x, y) 1 <= x && x <= n && 1 <= y && y <= m 7 8 bool judge(int x, int y) 9 { 10 if(isInside(x, y) && isInside(x + 1, y) && isInside(x, y + 1) && isInside(x + 1, y + 1)) 11 { 12 map<char, int>s; 13 s[ma[x][y]] = 1; 14 s[ma[x + 1][y]] = 1; 15 s[ma[x][y + 1]] = 1; 16 s[ma[x + 1][y + 1]] = 1; 17 if(s[‘f‘] + s[‘a‘] + s[‘c‘] + s[‘e‘] == 4) return true; 18 } 19 return false; 20 } 21 int main() 22 { 23 scanf("%d%d", &n, &m); 24 for(int i = 1; i <= n; i++) 25 scanf("%s", ma[i] + 1); 26 27 int ans = 0; 28 for(int i = 1; i <= n; i++) 29 { 30 for(int j = 1; j <= m; j++) 31 { 32 if(judge(i, j)) ans++; 33 } 34 } 35 printf("%d\n", ans); 36 return 0; 37 }
F - Gears
Mutual Training for Wannafly Union #7（待续）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。