[1549A]. Gregor and Cryptography
-
Idea: for a prime number, just find two numbers a , b a,b a. B. make P m o d a = P m o d b P\bmod a=P\bmod b Pmoda=Pmodb, which can make 0 = ( P − x ) m o d a = ( P − x ) m o d b 0=(P-x)\bmod a=(P-x)\bmod b 0=(P − x)moda=(P − x)modb, you can also think of making 0 = ( P − x ) = a × b 0=(P-x)=a\times b 0=(P−x)=a×b.
#include<bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, a, b) for(int i = a; i >= b; i--) #define ll long long #define db double #define pi acos(-1.0) const int INF = 0x7fffffff; const int N = 1e6 + 5; const db eps = 1e-10; using namespace std; int cas, n; int main(){ cin >> cas; while(cas--){ cin >> n; if(n == 5) cout << 2 << " " << 4 << endl; else cout << 2 << " " << (n - 1) / 2 << endl; } }
[1549B]. Gregor and the Pawn Game
-
Idea: first, go directly to the front of the enemy line. For a soldier of our side, only in " 101 " "101" "101" and at both ends 1 1 1. We should strive for the competition between the opposite sides 1 1 1 is forced to give up. Therefore, we can design a strategy (to reduce the waste of eating enemy soldiers): for each of our soldiers, try to eat the enemy on the opposite left first, and mark the enemy when he is eaten.
#include<bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, a, b) for(int i = a; i >= b; i--) #define ll long long #define db double #define pi acos(-1.0) const int INF = 0x7fffffff; const int N = 2e5 + 5; const db eps = 1e-10; using namespace std; int cas, n, a[N], b[N], ans; string sa, sb; inline void ff(int x){ a[x] = 2; ans++; } int main(){ cin >> cas; while(cas--){ cin >> n >> sa >> sb; ans = 0; memset(a, 0, sizeof a); rep(i, 0, n - 1){ if(sa[i] == '1') a[i] = 1; } rep(i, 0, n - 1){ if(sb[i] == '1'){ if(i > 0 && a[i - 1] == 1) ff(i - 1); else if(a[i] == 0) ff(i); else if(i < n - 1 && a[i + 1] == 1) ff(i + 1); continue; } } cout << ans << endl; } }
[1549C]. Web of Lies
-
Idea: a basic problem of graph theory. As long as you see it, only the penetration is 0 0 The point of 0 is the point that the simulation can stay after being killed. I use the adjacency table to save the map, and I use one s e t set set storage degree is 0 0 0, in order to query, do not repeat.
#include<bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, a, b) for(int i = a; i >= b; i--) #define ll long long #define db double #define pi acos(-1.0) const int INF = 0x7fffffff; const int N = 8e5 + 5; const db eps = 1e-10; using namespace std; int n, m, q, chu[N], ru[N], nxt[N], h[N], val[N], idx = 0, x, y, op; set<int> Set; //Save points with 0 degrees void add(int a, int b){ //Mapping chu[a]++, ru[b]++; val[idx] = b, nxt[idx] = h[a], h[a] = idx++; } void remove(int a, int b){ chu[a]--, ru[b]--; nxt[a] = nxt[nxt[a]]; } int main(){ cin >> n >> m; rep(i, 1, m){ cin >> x >> y; add(max(x, y), min(x, y)); } rep(i, 1, n) if(!ru[i]) Set.insert(i); cin >> q; rep(i, 1, q){ cin >> op; if(op == 1){ cin >> x >> y; add(max(x, y), min(x, y)); if(Set.count(min(x, y))) Set.erase(min(x, y)); } else if(op == 2){ cin >> x >> y; remove(max(x, y), min(x, y)); if(!ru[min(x, y)]) Set.insert(min(x, y)); } else{ cout << Set.size() << endl; } } }
[1549D]. Integers Have Friends
-
Idea: to find a a a the longest continuous interval makes it congruent ⟺ \iff "Looking for d i di The longest continuous interval of di makes it g c d ≠ 1 gcd\ne1 gcd=1. So we can consider using it first s t st Save st table g c d gcd gcd makes it possible to O ( 1 ) O(1) O(1) time query arbitrary interval g c d gcd gcd. For any interval, cycle the left end point, find the right end point in two points, determine the maximum value under each left end point, and finally find the maximum.
#include<bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, a, b) for(int i = a; i >= b; i--) #define ll long long #define db double #define pi acos(-1.0) const int INF = 0x7fffffff; const int N = 2e5 + 5; const db eps = 1e-10; using namespace std; int cas, n, ans; ll a[N], di[N], st[N][25]; ll gcd(ll a, ll b){ if(b == 0) return a; return gcd(b, a % b); } int main(){ cin >> cas; while(cas--){ cin >> n; ans = 0; rep(i, 1, n) scanf("%lld", &a[i]); rep(i, 1, n - 1) di[i] = abs(a[i + 1] - a[i]); rep(j, 0, 20) rep(i, 1, n - (1 << j)){ if(j == 0) st[i][j] = di[i]; else st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } rep(i, 1, n - 1){ int l = i, r = n; while(l < r){ int mid = (l + r) / 2, k = log2(mid - i + 1); if(gcd(st[i][k], st[mid - (1 << k) + 1][k]) != 1) l = mid + 1; else r = mid; } ans = max(ans, l - i); } cout << ans + 1 << endl; } }
[1549E]. The Three Little Pigs
Do it when it gets stronger
[1549F1]. Gregor and the Odd Cows (Easy)
-
Idea: I thought of Pike's theorem during the exam, but the opposite side can't be classified, and the complexity can only be O ( n 3 ) O(n^3) O(n3) has been timeout, no way. After reading the answer, I know to start with the point and classify the point. First, pick's theorem: 2 S = 2 a + b − 2 2S=2a+b-2 2S=2a+b − 2 (where a a a is the number of lattice points inside the polygon, b b b is the number of lattice points on the edge of the polygon, S S S is the area), this road( E a s y V e r s i o n Easy\;Version EasyVersion) limits that all coordinates are even, so the area S S S is even, required a a a is odd, then there is 4 ∣ b 4|b 4∣b. b b b is the sum of lattice points on three edges composed of three points. For one edge A B AB AB， A B AB Lattice number on AB edge p = gcd ( a b s ( x a − x b ) , a b s ( y a − y b ) ) p=\gcd(abs(x_a-x_b),abs(y_a-y_b)) p=gcd(abs(xa−xb),abs(ya−yb)). because x , y x, y x. Y is even, so 2 ∣ p 2|p 2∣p.
Again found p ≡ 0 m o d 4 ⟺ a b s ( x a − x b ) ≡ a b s ( y a − y b ) ≡ 0 m o d 4 ⟺ x a ≡ x b ( m o d 4 ) And y a ≡ y b m o d 4 p\equiv 0 \bmod 4 \iff abs(x_a-x_b)\equiv abs(y_a-y_b)\equiv 0\bmod 4\iff x_a\equiv x_b\pmod{4} and y_a\equiv y_b\bmod 4 p ≡ 0mod4 "abs(xa − xb) ≡ abs(ya − yb) ≡ 0mod4" xa ≡ xb (mod4) and ya ≡ yb mod4, so each point can be divided into four categories ( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 0 ) , ( 2 , 2 ) (0,0),(0,2),(2,0),(2,2) (0,0), (0,2), (2,0), (2,2) stands for ( x % 4 , y % 4 ) (x\%4,y\%4) (x%4,y%4).
The edge formed by any two points inside each class p ≡ 0 m o d 4 p\equiv0\bmod 4 p ≡ 0mod4, the edge formed by any two points of any two different classes p ≡ 2 m o d 4 p\equiv2\bmod 4 p≡2mod4.
Therefore, there are two methods: (1) two points can be selected from one category, and then one point can be selected from the other three categories( 0 + 2 + 2 ≡ 0 m o d 4 0+2+2\equiv0\bmod 4 0 + 2 + 2 ≡ 0mod4), (2) select three points from the same category( 0 + 0 + 0 ≡ 0 m o d 4 0+0+0\equiv0\bmod 4 0+0+0≡0mod4)
#include<bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, a, b) for(int i = a; i >= b; i--) #define ll long long #define db double #define pi acos(-1.0) const int INF = 0x7fffffff; const int N = 6e3 + 5; const db eps = 1e-10; using namespace std; int n, part[10]; ll sum, ans; ll C(int n, int x){ if(x == 2) return (n <= 1 ? 0 : (ll)n * (n - 1) / 2); else return (n <= 2 ? 0 : (ll)n * (n - 1) * (n - 2) / 6); } int main(){ //Pike's theorem: 2S = 2a + b - 2 cin >> n; memset(part, 0, sizeof part); rep(i, 1, n){ ll x, y; cin >> x >> y; if(!(x % 4) && !(y % 4)) part[0]++; else if(!(x % 4) && (y % 4)) part[1]++; else if((x % 4) && !(y % 4)) part[2]++; else if((x % 4) && (y % 4)) part[3]++; } rep(i, 0, 3) sum += part[i]; rep(i, 0, 3){ ans += (ll)(C(part[i], 2) * (sum - part[i])); ans += C(part[i], 3); } cout << ans << endl; }
[1549F2]. Gregor and the Odd Cows (Hard)
Do it when it gets stronger