# 洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 #include #include #include #include #include #include using namespace std; struct point {     double x, y;     long long id;     point() :x(0), y(0) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; double area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } double dist(point x, point y) {     return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)); } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     double res = 0;     for (int i = 0; i < result.size(); i++) {         res += dist(result[i % result.size()], result[(i + 1) % result.size()]);     }     cout.setf(ios::fixed);     cout << setprecision(2) << res; }

# CG2017 PA1-1 Convex Hull (凸包)

### Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

### Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

pk = (xk, yk), k = 1, 2, …, n

### Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

### Sample Input (输入样例)

123456789101110
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8



### Sample Output (输出样例)

17   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)



### Limitation (限制)

• 3 ≤ n ≤ 10^5
• Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
• All points on extreme edges are regarded as extreme points and hence should be included in your solution.
• Time Limit: 2 sec
• Space Limit: 512 MB
• 3 ≤ n ≤ 10^5
• 所有点的坐标均为范围(-10^5, 10^5)内的整数，且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
• 极边上的所有点均被视作极点，故在输出时亦不得遗漏
• 时间限制：2 sec
• 空间限制：512 MB

### Hint (提示)

Use the CH algorithms presented in the lectures.

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 #include #include #include #include using namespace std; struct point {     long long x, y, id;     point() :x(0), y(0) {}     point(long long x, long long y) :x(x), y(y) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; long long area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     long long res = 1;     for (int i = 0; i < result.size(); i++) {         //cout << result[i].id << endl;//debug         res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);     }     res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);     cout << res; }

# BJD CTF Programming notakto_1

C++有漏洞，够用就行：

 12345678910111213141516171819202122232425262728293031323334353637383940414243 #include #include using namespace std; int process[10] = { 4 }; bool visited[10]; inline int cal(int x, int y) {     return x * 3 + y; } bool& vis(int x, int y) {     return visited[cal(x, y)]; } bool check(int x, int y) {     bool flag = false;     flag |= vis(0, y) & vis(1, y) & vis(2, y);     flag |= vis(x, 0) & vis(x, 1) & vis(x, 2);     if (x == y)flag |= vis(0, 0) & vis(1, 1) & vis(2, 2);     if (x + y == 2)flag |= vis(0, 2) & vis(1, 1) & vis(2, 0);     return flag; } void print(int n) {     for (int i = 0; i <= n; i++) {         cout << process[i];     }     cout << endl; } void dfs(int step) {     bool flag = true;     for (int i = 0; i < 9; i++) {         if (visited[i])continue;         visited[i] = true;         process[step] = i;         if (check(i / 3, i % 3) == 0) {             dfs(step + 1);             flag = false;         }         visited[i] = false;     }     if (flag&&step%2==1)print(step); } int main() {     visited[4] = true;     dfs(1); }

python连带着往外发socket麻烦得很：

 12345678910111213141516171819202122232425262728293031323334353637383940414243 from pwn import * sock = remote("222.186.56.247",8122) wordList = [] currentWord = "" def findNewWord():     global currentWord,wordList     for elem in wordList:         if elem[0:len(currentWord)]==currentWord:             return elem     raise Exception("Error:Word Not found!") def loadDic():     global wordList     with open("situation.txt","r") as f:         wordList = f.readlines()     def getIntfromSock(sock):     sock.recvuntil("My move: ")     x = sock.recv(1)     if x==b' ': x = sock.recv(1)     return int(x) def payGame(i):     global currentWord,wordList,sock     print("the ith:",i)     currentWord=""     while len(currentWord) < 5:         backupWord = findNewWord()         print("Send:",backupWord[len(currentWord)])         sock.sendline(str(backupWord[len(currentWord)]))         currentWord += backupWord[len(currentWord)]         if len(currentWord)==5:             print("break")             break         currentWord += str(getIntfromSock(sock))         print("currentWord",currentWord)     sock.recvuntil("win!") loadDic() for i in range(150):     payGame(i) sock.interactive()

# lower_bound/upper_bound简易实现

lower_bound:

 123456789 int lower_bound(int v) { //arr[1..n],arr[0..n-1]     int l = 0, r = n-1,mid;     while (l < r) {         mid = (l + r) / 2;         if (arr[mid]

upper_bound:

 123456789 int upper_bound(int v) { //arr[1..n],arr[0..n-1]     int l = 0, r = n-1,mid;     while (l < r) {         mid = (l + r) / 2;         if (arr[mid]<=v)l=mid+1;         else r = mid;     }     return l; }

# 洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

https://www.luogu.org/blog/niiick/solution-p4777
https://www.luogu.org/problemnew/solution/P4777
https://blog.csdn.net/xiaobian_/article/details/87949337

https://www.cnblogs.com/yangsongyi/p/9867057.html
（快速乘规避溢出）
https://www.cnblogs.com/jt2001/p/6129914.html
https://blog.csdn.net/qq_39599067/article/details/81118467

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 #include #include #include #include using namespace std; typedef long long ll; int n; ll b[100005], a[100005]; //b是余数，a是模数 ll quickmultiply(ll a, ll b,ll mod) {     if (b == 0)return 0;     ll result = quickmultiply(a, b / 2, mod) % mod;     result = 2*result%mod;     if (b & 1)result = (result+a)%mod;     return result; } ll ngcd(ll a, ll b) {     return b == 0 ? a : ngcd(b, a % b); } ll exgcd(ll a, ll b, ll& x, ll& y) {     if (b == 0) {         x = 1; y = 0;         return a;     }     ll d = exgcd(b, a % b, y, x);     y -= a / b * x;     return d; } ll excrt() {     ll lcm = a[1], ans = b[1];     for (int i = 2; i <= n; i++) {         ll k1, k2, K, mod = lcm;         ll gcd = exgcd(lcm, a[i], k1, k2);         ll minus = ((b[i] - ans) % a[i] + a[i]) % a[i];         if ((minus % ngcd(lcm, a[i]) != 0))return -1;         K = (quickmultiply(k1,(minus / gcd),(a[i] / gcd)) + a[i] / gcd) % (a[i] / gcd);         lcm *= a[i] / gcd, ans = (K * mod + ans) % lcm;     }     return (ans % lcm + lcm) % lcm; } int main() {     cin >> n;     for (int i = 1; i <= n; i++) {         cin >> a[i] >> b[i];     }     cout<

# 洛谷 P3381 【模板】最小费用最大流

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374 #include #include #include #include using namespace std; const int eN = 100005; const int vN = 10005; const int INF = 0x7f7f7f7f; int n, m, s, t; int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边 int to[eN << 1], nxt[eN << 1], value[eN << 1], cost[eN << 1]; int head[vN], dis[vN], minV[vN]; int preID[eN << 1], preNode[eN << 1]; bool inqueue[vN]; inline void createEdge(int u, int v, int w, int c) {     to[++ePtr] = v;     value[ePtr] = w;     cost[ePtr] = c;     nxt[ePtr] = head[u];     head[u] = ePtr; } bool SPFA(int s, int t) {     queue q;     memset(dis, 0x7f, sizeof(dis));     memset(inqueue, false, sizeof(inqueue));     memset(preID, -1, sizeof(preID));     memset(preNode, -1, sizeof(preNode));     memset(minV, 0x7f, sizeof(minV));     dis[s] = 0;     inqueue[s] = true;     q.push(s);     while (!q.empty()) {         int x = q.front();         q.pop();         inqueue[x] = false;         for (int i = head[x]; ~i; i = nxt[i]) {             int dest = to[i];             if (dis[dest] > dis[x] + cost[i] && value[i]) {                 dis[dest] = dis[x] + cost[i];                 minV[dest] = min(minV[x], value[i]);                 preID[dest] = i;                 preNode[dest] = x;                 if (!inqueue[dest]) {                     inqueue[dest] = true;                     q.push(dest);                 }             }         }     }     return dis[t] != INF; } void MinCostMaxFlow(int s, int t, int& maxflow, int& mincost) {     while (SPFA(s, t)) {         for (int i = t; i != s; i = preNode[i]) {             value[preID[i]] -= minV[t];             value[preID[i] ^ 1] += minV[t];         }         maxflow += minV[t];         mincost += minV[t] * dis[t];     } } int main() {     memset(head, -1, sizeof(head));     scanf("%d%d%d%d", &n, &m, &s, &t);     for (int i = 1; i <= m; i++) {         int u, v, w, f;         scanf("%d%d%d%d", &u, &v, &w, &f);         createEdge(u, v, w, f);         createEdge(v, u, 0, -f);//第0号边被占用，这条语句为反向边留下空间     }     int maxflow = 0, mincost = 0;     MinCostMaxFlow(s, t, maxflow, mincost);     printf("%d %d\n", maxflow, mincost); }

# 洛谷 P3376 【模板】网络最大流

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 #include #include #include #include using namespace std; const int eN = 100005; const int vN = 10005; const int INF = 0x7f7f7f7f; int n, m, s, t; int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边 int to[eN<<1], nxt[eN<<1], value[eN<<1]; int head[vN], dis[vN]; inline void createEdge(int u, int v, int w) {     to[++ePtr] = v;     value[ePtr] = w;     nxt[ePtr] = head[u];     head[u] = ePtr; } bool bfs(int s, int t) {     queue q;     memset(dis, 0x7f, sizeof(dis));     dis[s] = 0;     q.push(s);     while (!q.empty()) {         int x = q.front();         q.pop();         for (int i = head[x]; ~i; i = nxt[i]) {             int dest = to[i];             if (dis[dest] == INF && value[i] != 0) {                 dis[dest] = dis[x] + 1;                 q.push(dest);             }         }     }     return dis[t] != INF; } int dfs(int x, int t, int maxflow) {     if (x == t)return maxflow;     int ans = 0;     for (int i = head[x]; ~i; i = nxt[i]) {         int dest = to[i];         if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue;         int f = dfs(dest, t, min(value[i], maxflow - ans));         value[i] -= f;         value[i ^ 1] += f;         ans += f;     }     return ans; } int dinic(int s, int t) {     int ans = 0;     while (bfs(s, t))ans += dfs(s, t, INF);     return ans; } int main() {     memset(head, -1, sizeof(head));     scanf("%d%d%d%d", &n, &m, &s, &t);     for (int i = 1; i <= m; i++) {         int u, v, w;         scanf("%d%d%d", &u, &v, &w);         createEdge(u, v, w);         createEdge(v, u, 0);//第0号边被占用，这条语句为下一个边留下空间     }     printf("%d", dinic(s, t)); }

# Codeforces 102346 problem K Keep Calm and Sell Balloons

$$\begin{bmatrix} F(n) \\ F(n-1) \\ F(n-2) \\ F(n-3) \end{bmatrix} = \begin{bmatrix} 6 & -8 & -8 & 16 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} * \begin{bmatrix} F(n-1) \\ F(n-2) \\ F(n-3) \\ F(n-4) \end{bmatrix}$$

$$\begin{bmatrix} F(n) \\ F(n-1) \\ F(n-2) \\ F(n-3) \end{bmatrix} = \begin{bmatrix} 6 & -8 & -8 & 16 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}^{n-4} * \begin{bmatrix} F(4) \\ F(3) \\ F(2) \\ F(1) \end{bmatrix}$$

$$\begin{bmatrix} F(n) \\ F(n-1) \\ … \\ F(n-k+2) \\ F(n-k+1) \end{bmatrix} = \begin{bmatrix} a_1 & a_2 & … & a_{n-k+1} & a_{n-k} \\ 1 & 0 & … & 0 & 0 \\ 0 & 1 & … & 0 & 0 \\ … & … & … & … & … \\ 0 & 0 & … & 1 & 0 \end{bmatrix} * \begin{bmatrix} F(n-1) \\ F(n-2) \\ … \\ F(n-k+1) \\ F(n-k) \end{bmatrix}$$

 1234567891011121314151617181920212223242526272829303132333435363738394041424344 #include using namespace std; const long long MOD = 1e9 + 7; const int maxtrixN=4; struct matrix {     long long arr[maxtrixN][maxtrixN];     matrix operator * (matrix m2) {         matrix result;         long long(&arr)[maxtrixN][maxtrixN] = result.arr;         const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;         const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;         for (int i = 0; i < maxtrixN; i++) {             for (int j = 0; j < maxtrixN; j++) {                 arr[i][j] = 0;                 for (int k = 0; k < maxtrixN; k++) {                     arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;                     arr[i][j] += MOD;                     arr[i][j] %= MOD;                 }             }         }         return result;     } }; const matrix c = { 6,-8,-8,16,1,0,0,0,0,1,0,0,0,0,1,0 }; matrix quickpow(long long n) {     if (n == 1)return c;     matrix half = quickpow(n / 2);     matrix result = half * half;     if (n & 1)result = result * c;     return result; } long long getValue(long long n) {     matrix result = quickpow(n);     long long(&arr)[4][4] = result.arr;     return (arr[0][0] * 1536 % MOD + arr[0][1] * 416 % MOD + arr[0][2] * 96 % MOD + arr[0][3] * 24 % MOD +MOD) % MOD; } int main() {     int n;     long long a1[] = { 0,2,24,96,416,1536 };     cin >> n;     if (n < 6)cout << a1[n];     else cout << getValue(n-5); }

# 洛谷 P3386 【模板】二分图匹配

 123456789101112131415161718192021222324252627282930313233343536373839404142434445 #include #include #include #include #include #include #include #include #include #include using namespace std; int n, m, e; vector edges[2005]; bool visited[2005]; int match[2005]; bool biFind(int node) {     if (visited[node])return false;     visited[node] = true;     for (int i = 0; i < edges[node].size(); i++) {         if (!match[edges[node][i]] || biFind(match[edges[node][i]])) {             match[node] = edges[node][i];             match[edges[node][i]] = node;             return true;         }     }     return false; } int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cin >> n >> m >> e;     for (int i = 1; i <= e; i++) {         int u, v;         cin >> u >> v;         if (u > n || v > m)continue;         edges[u].push_back(v + n);         edges[v + n].push_back(u);     }     int cnter = 0;     for (int i = 1; i <= n; i++) {         memset(visited, false, sizeof(visited));         if (biFind(i))cnter++;     }     cout << cnter; }