?

?

題面及數據及std（有本人的也有原來的） ：2017.6.11 校內模擬賽

?

?

?

T1

　　　

　　　　自己在紙上模擬一下后就會發現

　　　　可以用棧來搞一搞事情

　　　　受了上次zsq 講的雙棧排序的啟發。。

?

　　　　具體就是將原盤子大小copy一下排個序

　　　　用兩個指針維護兩個數組（原數據 和 排序后的數據）， 即分為1數據和2數組

　　　　將小于1指針指向的數據的2數組中的數據全部壓入棧中

　　　　后進行消除， 將棧棧頂元素與當前1數組中的1指針指向的元素進行比較

　　　　相同則消除

　　　　后重復過程

　　　　直至指針超過N

　　　　后判斷一下是否兩個指針都超過了N。。。

　　

?

　　　　

#include <algorithm> #include <cstring> #include <cstdio> #include <stack>#define Max 100090void read (int &now) {now = 0;register char word = getchar ();while (word < '0' || word > '9')word = getchar ();while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();} }int N, M;int dish[Max]; int data[Max];class Stack_Type {private :int Stack[Max];int Top_Cur;public :inline void Clear (){ Top_Cur = 0; }inline void Pop (){Top_Cur --;}bool Empty () { return Top_Cur == 0;}inline int Top (){return Stack[Top_Cur];}inline void Push (int x){Stack[++ Top_Cur] = x;} };Stack_Type Stack;int main (int argc, char *argv[]) {freopen ("disk.in", "r", stdin);freopen ("disk.out", "w", stdout);int T;for (; scanf ("%d", &N) != EOF; ){memset (dish, 0, sizeof dish);memset (data, 0, sizeof data);bool flag = false;Stack.Clear ();for (int i = 1; i <= N; i ++){read (dish[i]);data[i] = dish[i]; } std :: sort (data + 1, data + 1 + N);register int pos_1 = 1, pos_2 = 1;for (; (pos_1 <= N || pos_2 <= N) && (Stack.Empty () || dish[pos_1] >= Stack.Top ()); ){ for (; pos_2 <= N && dish[pos_1] >= data[pos_2]; )Stack.Push (data[pos_2 ++]); for (; !Stack.Empty () && pos_1 <= N && Stack.Top() == dish[pos_1]; Stack.Pop (), pos_1 ++); }if (pos_1 > N && pos_2 > N)printf ("Y\n");else printf ("J\n");} return 0; }

?

T2

　　　　這個題估計隨便亂搞搞就能A吧。。

　　　　看機房里眾dalao 以各種奇怪的姿勢AC此題。。

　　　　　

　　　　思路：枚舉每個點，算出對角線邊緣的兩個分別進行二分， 分別找出兩個符合條件的邊界點， 乘一乘就好了。。

?

　　　　寫了四個二分我也是醉了。。。寫完后才想起來有 lower_bound 這個東西。。。

　　

?

?

#include <algorithm> #include <cstdio>#define Max 10010void read (int &now) {now = 0;register char word = getchar ();bool temp = false;while (word < '0' || word > '9'){if (word == '-')temp = true;word = getchar ();}while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();}if (temp)now = -now; }struct Data_ {int x, y;Data_ (int __x, int __y) : x (__x), y (__y) {};Data_ () {};bool operator < (const Data_ &now) const{if (this->x == now.x)return this->y < now.y;return this->x < now.x;} };inline int abs (int x) {return x < 0 ? -x : x; }long long Answer; int N;bool Judge (Data_ now_1, Data_ now_2) {if (now_2.y <= now_1.y)return true;if (abs (now_1.x + now_1.y + now_2.x - now_2.y) % 2 == 1)return true;if (abs (now_2.x - now_1.x + now_1.y + now_2.y) % 2 == 1)return true;return false; }Data_ point[Max];bool ErFen_Judge (int now, int x, int y) {Data_ res (x, y);return point[now] < res; }bool ErFen_Re_Judge (int now, int x, int y) {if (point[now].x == x)return point[now].y > y;return point[now].x > x; }int main (int argc, char *argv[]) {freopen ("car.in", "r", stdin);freopen ("car.out", "w", stdout);read (N);for (int i = 1; i <= N; i ++){read (point[i].x);read (point[i].y);}std :: sort (point + 1, point + 1 + N);int l, r, Mid;for (int i = 1; i <= N; i ++)for (int j = i + 1; j <= N; j ++){if (point[i].x == point[j].x && point[i].y == point[j].y)continue ;if (Judge (point[i], point[j]))continue;register int now_x = (point[i].x + point[i].y + point[j].x - point[j].y) >> 1;register int now_y = (point[j].x - point[i].x + point[i].y + point[j].y) >> 1; l = 0;r = N + 1;while (l + 1 < r){Mid = l + r >> 1;if (ErFen_Judge (Mid, now_x, now_y))l = Mid;elser = Mid;}int Result_1 = l;l = 0;r = N + 1;while (l + 1 < r){Mid = l + r >> 1;if (ErFen_Re_Judge (Mid, now_x, now_y))r = Mid;elsel = Mid;}Result_1 = l - Result_1;now_x = (point[i].x - point[i].y + point[j].x + point[j].y) >> 1;now_y = (point[i].x + point[i].y - point[j].x + point[j].y) >> 1;l = 0;r = N + 1;while (l + 1 < r){Mid = l + r >> 1;if (ErFen_Judge (Mid, now_x, now_y))l = Mid;elser = Mid;}int Result_2 = l;l = 0;r = N + 1;while (l + 1 < r){Mid = l + r >> 1;if (ErFen_Re_Judge (Mid, now_x, now_y))r = Mid;elsel = Mid;}Result_2 = l - Result_2;Answer += (long long) Result_1 * Result_2;}printf ("%lld", Answer);return 0; }

?

?

?

T3

　　

　　　　主席樹 + 權值線段樹 板子題。。

?

?

#include <algorithm> #include <cstdio>#define Max 40000void read (int &now) {now = 0;register char word = getchar ();while (word > '9' || word < '0')word = getchar ();while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();} }void read_long_long (long long &now) {now = 0;register char word = getchar ();while (word > '9' || word < '0')word = getchar ();while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();} }struct Tree_Data {int key;int l, r;int Mid;};Tree_Data tree[Max * 20];Tree_Data node[Max];int N, M;class Tree_Type {private :int Count_;int People_Count;void __Build_ (Tree_Data &now, int l, int r){if (l == r)return ;now.Mid = l + r >> 1;now.l = ++ Count_;__Build_ (tree[now.l], l, now.Mid);now.r = ++ Count_;__Build_ (tree[now.r], now.Mid + 1, r);}void __Updata_ (Tree_Data &Pre, Tree_Data &now, int l, int r,int pos){if (l == r){now.key ++;return ;}now.Mid = Pre.Mid;if (pos <= now.Mid){now.r = Pre.r;now.l = ++ Count_;__Updata_ (tree[Pre.l], tree[now.l], l, now.Mid, pos);}else{now.l = Pre.l;now.r = ++ Count_;__Updata_ (tree[Pre.r], tree[now.r], now.Mid + 1, r, pos);}now.key = tree[now.l].key + tree[now.r].key;}int __Query_ (Tree_Data &Pre, Tree_Data &now, int l, int r, int k){if (l == r)return l;int res = tree[now.l].key - tree[Pre.l].key;if (k <= res)return __Query_ (tree[Pre.l], tree[now.l], l, now.Mid, k);elsereturn __Query_ (tree[Pre.r], tree[now.r], now.Mid + 1, r, k - res);}public :Tree_Type (){Count_ = 0;People_Count = 0;}inline void Build (int l, int r){__Build_ (node[0], l, r);return ;}inline void Updata (int now, int pos){__Updata_ (node[now - 1], node[now], 1, N, pos);return ;}inline int Query (int k){return __Query_ (node[0], node[k], 1, N, ++ People_Count);} };Tree_Type President_Tree;long long __rank[Max]; long long number[Max];int main (int argc, char *argv[]) {freopen ("rollcall.in", "r", stdin);freopen ("rollcall.out", "w", stdout);read (N);read (M);for (int i = 1; i <= N; __rank[i] = number[i], i ++)read_long_long (number[i]);std :: sort (__rank + 1, __rank + 1 + N);int Size = std :: unique (__rank + 1, __rank + 1 + N) - __rank - 1;President_Tree.Build (1, N);for (int i = 1; i <= N; i ++){number[i] = std :: lower_bound (__rank + 1, __rank + 1 + Size, number[i]) - __rank;President_Tree.Updata (i, number[i]); }for (int x; M --; ){read (x);printf ("%I64d\n", __rank[President_Tree.Query (x)]);}return 0; }

?

轉載于:https://www.cnblogs.com/ZlycerQan/p/6985382.html

總結

以上是生活随笔為你收集整理的2017.6.11 校内模拟赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。