A : Apple
题意:给出三个点,以及另一个点,求最后一个点是否在三个点的外接圆里面,如果在或者在边界上,输出“Rejected”,否则输出"Accepted"
思路:先求一个外接圆,得到圆心和半径,再判一下,注意精度问题,用JAVA
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 import java.math.BigDecimal; 2 import java.util.Scanner; 3 4 public class Main { 5 6 public static void main(String[] args) { 7 Scanner in = new Scanner(System.in); 8 int t = in.nextInt(); 9 for(int cas = 1; cas <= t; ++cas) 10 { 11 BigDecimal x1 = in.nextBigDecimal(); 12 BigDecimal y1 = in.nextBigDecimal(); 13 BigDecimal x2 = in.nextBigDecimal(); 14 BigDecimal y2 = in.nextBigDecimal(); 15 BigDecimal x3 = in.nextBigDecimal(); 16 BigDecimal y3 = in.nextBigDecimal(); 17 BigDecimal x = in.nextBigDecimal(); 18 BigDecimal y = in.nextBigDecimal(); 19 //x 20 BigDecimal temp1 = y2.subtract(y1); 21 BigDecimal temp2 = y3.multiply(y3).subtract(y1.multiply(y1)).add(x3.multiply(x3)).subtract(x1.multiply(x1)); 22 BigDecimal temp3 = y3.subtract(y1); 23 BigDecimal temp4 = y2.multiply(y2).subtract(y1.multiply(y1)).add(x2.multiply(x2)).subtract(x1.multiply(x1)); 24 temp1 = temp1.multiply(temp2); 25 temp3 = temp3.multiply(temp4); 26 BigDecimal x0 = temp1.subtract(temp3); 27 temp1 = x3.subtract(x1).multiply(y2.subtract(y1)).subtract(x2.subtract(x1).multiply(y3.subtract(y1))); 28 temp1 = temp1.multiply(BigDecimal.valueOf(2.0)); 29 x0 = x0.divide(temp1); 30 //y 31 temp1 = x2.subtract(x1); 32 temp2 = x3.multiply(x3).subtract(x1.multiply(x1)).add(y3.multiply(y3)).subtract(y1.multiply(y1)); 33 temp3 = x3.subtract(y1); 34 temp4 = x2.multiply(x2).subtract(y1.multiply(y1)).add(y2.multiply(y2)).subtract(y1.multiply(y1)); 35 temp1 = temp1.multiply(temp2); 36 temp3 = temp3.multiply(temp4); 37 BigDecimal y0 = temp1.subtract(temp3); 38 temp1 = y3.subtract(y1).multiply(y2.subtract(y1)).subtract(y2.subtract(y1).multiply(x3.subtract(x1))); 39 temp1 = temp1.multiply(BigDecimal.valueOf(2.0)); 40 y0 = y0.divide(temp1); 41 //r 42 temp1 = x1.subtract(x0); 43 temp2 = y1.subtract(y0); 44 temp1 = temp1.multiply(temp1); 45 temp2 = temp2.multiply(temp2); 46 BigDecimal r = temp1.add(temp2); 47 //dis 48 temp1 = x.subtract(x0); 49 temp2 = y.subtract(y0); 50 temp1 = temp1.multiply(temp1); 51 temp2 = temp2.multiply(temp2); 52 BigDecimal dis = temp1.add(temp2); 53 if(dis.compareTo(r) > 0) 54 { 55 System.out.println("Accepted"); 56 } 57 else 58 { 59 System.out.println("Rejected"); 60 } 61 } 62 } 63 } 64 //3 65 //-2 0 0 -2 2 0 2 -2 66 //-2 0 0 -2 2 0 0 2 67 //-2 0 0 -2 2 0 1 1
B:Bomberman
留坑。
C:The Dominator of Strings
题意:给出N个串,然后找出这N个串中是否有一个串包含其他所有串,如果有,输出那个串,如果没有,输出 No
思路:显然,如果答案存在,那么必定是长度最大的那个串。本来想着用KMP, 然后没想到用.find() 就可以过了。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 100010 6 7 string s[N], T; 8 9 int t, n; 10 11 int main() 12 { 13 cin.tie(0); 14 ios::sync_with_stdio(false); 15 cin >> t; 16 while (t--) 17 { 18 cin >> n; 19 int Max = 0, pos; 20 for (int i = 1; i <= n; ++i) 21 { 22 cin >> s[i]; 23 if (s[i].length() > Max) 24 { 25 Max = s[i].length(); 26 pos = i; 27 } 28 } 29 int cnt = 0; 30 for (int i = 1; i <= n; ++i) 31 { 32 if (i == pos) continue; 33 if (s[pos].find(s[i]) != s[pos].npos) 34 cnt++; 35 } 36 if (cnt == n - 1) 37 cout << s[pos] << endl; 38 else cout << "No "; 39 } 40 return 0; 41 }
KMP:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 // KMP 版本, 比.find() 还慢。。 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 #define N 100010 7 8 int t, n; 9 10 int Next[N]; 11 12 inline void pre(string x, int m) 13 { 14 int i, j; 15 j = Next[0] = -1; 16 i = 0; 17 while (i < m) 18 { 19 while (-1 != j && x[i] != x[j]) j = Next[j]; 20 if (x[++i] == x[++j]) Next[i] = Next[j]; 21 else Next[i] = j; 22 } 23 } 24 25 inline bool KMP(string x, int m, string y, int n) 26 { 27 int i, j; 28 pre(x, m); 29 i = j = 0; 30 while (i < n) 31 { 32 while (-1 != j && y[i] != x[j]) j = Next[j]; 33 i++, j++; 34 if (j >= m) 35 { 36 return true; 37 } 38 } 39 return false; 40 } 41 42 string s[N]; 43 44 int main() 45 { 46 cin.tie(0); 47 ios::sync_with_stdio(false); 48 cin >> t; 49 while (t--) 50 { 51 cin >> n; 52 int Max = 0, pos; 53 for (int i = 1; i <= n; ++i) 54 { 55 cin >> s[i]; 56 if (s[i].length() > Max) 57 { 58 Max = s[i].length(); 59 pos = i; 60 } 61 } 62 int cnt = 0, len = s[pos].length(); 63 for (int i = 1; i <= n; ++i) 64 { 65 if (i == pos) continue; 66 if (KMP(s[i], s[i].length(), s[pos], len)) 67 cnt++; 68 else 69 break; 70 } 71 if (cnt == n - 1) 72 cout << s[pos] << " "; 73 else 74 cout << "No "; 75 } 76 }
D:The Intersection
题意:给出两个函数,用一个有理分数去逼近两函数交点的横坐标,有理分数的分母小于1e5
思路:考虑二分
分数的二分可以用一个结论
a/b < (a + c) / (b + d) < c / d
然后考虑 k = k2 那么x3 = k 那么 先去逼近k (x - 1)3 < k <= x3 如果x3 == k 直接输出 x / 1
反之 令 l = (x - 1) / 2 r = (x) / 2 进行二分
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define ld long double 6 #define ll long long 7 8 int t; 9 10 inline ll GCD(ll a, ll b) 11 { 12 while (b ^= a ^= b ^= a %= b); 13 return a; 14 } 15 16 int main() 17 { 18 cin.tie(0); 19 cout.tie(0); 20 ios::sync_with_stdio(false); 21 cin >> t; 22 while (t--) 23 { 24 ll k; 25 cin >> k; 26 ld K = k * k; 27 ll x = 1; 28 while (x * x * x < K) x++; 29 if (x * x * x == K) 30 { 31 cout << x << "/1 "; 32 continue; 33 } 34 ll a = 1, b = x - 1, c = 1, d = x; 35 ll e, q, tar = K; 36 ld gap = x * x * x - tar; 37 while (true) 38 { 39 ll aa = a + c, bb = b + d; 40 if (aa > 1e5) break; 41 ld tmp = (ld)bb * bb * bb / aa / aa / aa; 42 if (fabsl(tmp - tar) < gap) 43 { 44 gap = fabsl(tmp - tar); 45 q = bb; 46 e = aa; 47 } 48 if (tmp > tar) 49 { 50 d = bb, c = aa; 51 } 52 else 53 { 54 b = bb, a = aa; 55 } 56 } 57 cout << q << "/" << e << " "; 58 } 59 return 0; 60 }
E:King's Visit
留坑。
F:Pythagoras
题意:找到所有满足$x^2 + y^2 = z^2$ 的$(x, y, z)$ $(x, y, z) < 1e9$ 满足 $x <y < z 并且 (x, y, z) 互质$ 计算 $sum {a_{y mod 2^k}}$
思路:毕达哥拉斯三元组
$x = a^2 - b^2$
$y = 2ab$
$z = a^2 + b^2$
z最大 , x, y 大小不定 当 a, b 互质时,(x, y, z) 互质 并且 a > b
暴力枚举a, b 然后取模 (1 << 17)
计算的时候,假设 k = 2 那么 $x equiv 1 pmod k$ 相当于 $x equiv 1 pmod {1 << 17}$ $x equiv 5 pmod {1 << 17}$ ...
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 200010 5 #define MOD 131072 6 #define ll long long 7 #define INF 1000000000 8 9 int t, k, n; 10 int arr[N]; 11 ll ans[N]; 12 vector <int> fac[25000]; 13 14 inline bool ok(int x, int y) 15 { 16 for (int i = 0, len = fac[y].size(); i < len; ++i) 17 if (x % fac[y][i] == 0) return false; 18 return true; 19 } 20 21 inline void Init() 22 { 23 for (int i = 2; i * i <= (INF >> 1); i += 2) 24 fac[i].emplace_back(2); 25 int limit = sqrt(INF >> 1); 26 for (int i = 3; i <= limit; i += 2) 27 { 28 if (fac[i].empty()) 29 for (int j = i; j * j <= (INF >> 1); j += i) 30 fac[j].emplace_back(i); 31 } 32 ll cnt = 0; 33 for (int b = 1; b * b <= (INF >> 1); ++b) 34 { 35 for (int a = b + 1; a * a + b * b <= INF; a += 2) 36 { 37 if (ok(a, b)) 38 ++ans[max(2 * a * b, a * a - b * b) % MOD]; 39 } 40 } 41 } 42 43 inline void Run() 44 { 45 Init(); 46 scanf("%d", &t); 47 while (t--) 48 { 49 scanf("%d", &k); n = 1 << k; 50 for (int i = 0; i < n; ++i) scanf("%d", arr + i); 51 ll sum = 0; 52 for (int i = 0; i < n; ++i) 53 for (int j = 0; j * n + i < MOD; ++j) 54 sum += (ll)arr[i] * ans[j * n + i]; 55 printf("%lld ", sum); 56 } 57 } 58 59 60 int main() 61 { 62 #ifdef LOCAL 63 freopen("Test.in", "r", stdin); 64 #endif 65 66 Run(); 67 68 return 0; 69 }
G:Zuma
题意:给出一个01串,若有三个相同的就可以消去,如果没有,可以发射若干个0或者若干个1使之消去,会有连锁反应,求最少的发射数
思路:我们可以先预处理一下,使得相同颜色的合并在一起。那么考虑 i, j 若第i个 与第j个 颜色相同
那么 dp[i][j] = dp[i + 1][j - 1] + max(3 - v[i] - v[j], 0) (v[] 表示这个合并后的区间内有多少个这种颜色)
还有一个区间dp通用转移方程 dp[i][j] = min(dp[i][j], dp[i][k], dp[k + 1][j])
还要考虑一个 如果 存在 i, j, k 若 v[i] + v[k] < 3 || v[k] + v[j] < 3
那么它们可能可以通过消去 区间[i + 1][k - 1] 和 [k + 1][j - 1] 来使得这三个产生连锁反应而有更优的答案
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 210 5 6 typedef pair <int, int> pii; 7 8 int t, cnt; 9 char s[N]; 10 pii arr[N]; 11 int dp[N][N]; 12 13 inline void Run() 14 { 15 scanf("%d", &t); 16 for (int kase = 1; kase <= t; ++kase) 17 { 18 printf("Case #%d: ", kase); 19 scanf("%s", s + 1); 20 cnt = 0; 21 for (int i = 1, len = strlen(s + 1); i <= len; ++i) 22 { 23 int id = s[i] - '0'; 24 if (i == 1 || id != arr[cnt].second) 25 arr[++cnt].first = 1, arr[cnt].second = id; 26 else 27 ++arr[cnt].first; 28 } 29 memset(dp, 0x3f, sizeof dp); 30 for (int i = 1; i <= cnt; ++i) dp[i][i] = (arr[i].first == 2 ? 1 : 2); 31 for (int i = 2; i <= cnt; ++i) 32 { 33 for (int j = 1; j + i - 1 <= cnt; ++j) 34 { 35 int l = j, r = j + i - 1; 36 if (arr[l].second == arr[r].second) 37 dp[l][r] = dp[l + 1][r - 1] + max(3 - arr[l].first - arr[r].first, 0); 38 for (int k = l; k < r; ++k) 39 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]); 40 if (arr[l].second == arr[r].second) 41 for (int k = l + 1; k < r; ++k) 42 { 43 if (arr[l].second == arr[k].second && (arr[l].first + arr[k].first < 3 || arr[k].first + arr[r].first < 3)) 44 dp[l][r] = min(dp[l][r], max(3 - arr[l].first - arr[k].first - arr[r].first, 0) + dp[l + 1][k - 1] + dp[k + 1][r - 1]); 45 } 46 } 47 } 48 printf("%d ", dp[1][cnt]); 49 } 50 } 51 52 53 int main() 54 { 55 #ifdef LOCAL 56 freopen("Test.in", "r", stdin); 57 #endif 58 59 Run(); 60 61 return 0; 62 }
H:Chinese Zodiac
按题意输出即可
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 map <string, int> mp; 6 7 inline void Init() 8 { 9 mp["rat"] = 1; 10 mp["ox"] = 2; 11 mp["tiger"] = 3; 12 mp["rabbit"] = 4; 13 mp["dragon"] = 5; 14 mp["snake"] = 6; 15 mp["horse"] = 7; 16 mp["sheep"] = 8; 17 mp["monkey"] = 9; 18 mp["rooster"] = 10; 19 mp["dog"] = 11; 20 mp["pig"] = 12; 21 } 22 23 int t; 24 25 int main() 26 { 27 cin.tie(0); 28 ios::sync_with_stdio(false); 29 Init(); cin >> t; 30 string a, b; 31 while (t--) 32 { 33 cin >> a >> b; 34 int ans = mp[b] - mp[a]; 35 if (ans < 1) ans += 12; 36 cout << ans << endl; 37 } 38 }
I:Smallest Minimum Cut
题意:给出一张图,然后给出两个点S, T, 要求选取一个含有最小边的一个边集,使得其流量为最大流
思路一: 可以将所有边权都乘以一个较大的数 + 1,那么本来边比较多的最大流,这样处理之后就不再是最大流,答案就是最大流%较大的数,因为这样处理之后,不会存在边数相同并且最大流相同的情况,可以分开考虑
因为最大流肯定是由若干个满流的容量组成,那么最后的最大流答案肯定是n * m + x (m 为一个较大的数,x 为边数)
如果存在更少边使得组成最大流,那么最大流肯定是 n2 * m + x2 (易知x2 < x 那么显然n2 > n) 那么这个流肯定比上面那个大,那么这个才是答案,矛盾
如果存在更多边使得组成最大流,那么最大流肯定是n3 * m + x3 (显然 x3 > x 那么 n3 < n) 因为 m足够大,那么这个最大流肯定要小于上面那个最大流,这个不会是答案
思路二:跑一边网络流后,如果有一条路是满流的话,那么这条路可能为所求答案的其中一条路,将这条路的流量改为1,再将其他路的流量改成1e9,再跑一次网络流就可以得出所求答案。
思路一:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1e3 + 10; 5 const int INF = 0x3f3f3f3f; 6 7 int n, m; 8 9 struct Edge{ 10 int from; 11 int to; 12 int cap; 13 int flow; 14 inline Edge(){} 15 inline Edge(int from,int to,int cap,int flow):from(from), to(to), cap(cap), flow(flow){} 16 }; 17 18 vector<Edge>edge; 19 vector<int>G[maxn]; 20 int vis[maxn]; 21 int d[maxn]; 22 int cur[maxn]; 23 int S,T; 24 25 inline void init() 26 { 27 edge.clear(); 28 for(int i = 1; i <= n; ++i) 29 G[i].clear(); 30 } 31 32 inline void addedge(int from,int to,int cap) 33 { 34 edge.push_back(Edge(from,to,cap,0)); 35 edge.push_back(Edge(to,from,0,0)); 36 int len = edge.size(); 37 G[from].push_back(len - 2); 38 G[to].push_back(len - 1); 39 } 40 41 inline bool bfs() 42 { 43 memset(d,0,sizeof d); 44 memset(vis,0,sizeof vis); 45 queue<int>q; 46 q.push(S); 47 d[S] = 1; 48 vis[S] = 1; 49 while(!q.empty()) 50 { 51 int x = q.front(); 52 q.pop(); 53 for(int i = 0; i < G[x].size(); ++i) 54 { 55 Edge &e = edge[G[x][i]]; 56 for(int i = 0; i < G[x].size(); ++i) 57 { 58 Edge &e = edge[G[x][i]]; 59 if(!vis[e.to] && e.cap > e.flow) 60 { 61 vis[e.to] = 1; 62 d[e.to] = d[x] + 1; 63 q.push(e.to); 64 } 65 } 66 } 67 } 68 return vis[T]; 69 } 70 71 inline int dfs(int x,int a) 72 { 73 if(x == T || a == 0) return a; 74 int flow = 0; 75 int f; 76 for(int &i = cur[x]; i < G[x].size(); ++i) 77 { 78 Edge &e = edge[G[x][i]]; 79 if(d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap- e.flow))) > 0) 80 { 81 e.flow += f; 82 edge[G[x][i] ^ 1].flow -= f; 83 flow += f; 84 a -= f; 85 if(a == 0) break; 86 } 87 } 88 return flow; 89 } 90 91 inline int dicnic() 92 { 93 int ans = 0; 94 while(bfs()) 95 { 96 memset(cur,0,sizeof cur); 97 ans += dfs(S,INF); 98 } 99 return ans; 100 } 101 102 int main() 103 { 104 int t; 105 scanf("%d",&t); 106 while(t--) 107 { 108 init(); 109 scanf("%d %d",&n, &m); 110 scanf("%d %d",&S, &T); 111 for(int i = 1;i <= m; ++i) 112 { 113 int x, y, z; 114 scanf("%d %d %d",&x, &y,&z); 115 addedge(x,y,z * 999 + 1); 116 } 117 int ans = dicnic(); 118 printf("%d ",ans % 999); 119 } 120 return 0; 121 }
思路二:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1e3 + 10; 5 const int INF = 0x3f3f3f3f; 6 7 int n, m; 8 9 struct Edge { 10 int from; 11 int to; 12 int cap; 13 int flow; 14 inline Edge() {} 15 inline Edge(int from, int to, int cap, int flow) :from(from), to(to), cap(cap), flow(flow) {} 16 }; 17 18 vector<Edge>edge; 19 vector<int>G[maxn]; 20 int vis[maxn]; 21 int d[maxn]; 22 int cur[maxn]; 23 int S, T; 24 25 inline void init() 26 { 27 edge.clear(); 28 for (int i = 1; i <= n; ++i) 29 G[i].clear(); 30 } 31 32 inline void addedge(int from, int to, int cap) 33 { 34 edge.push_back(Edge(from, to, cap, 0)); 35 edge.push_back(Edge(to, from, 0, 0)); 36 int len = edge.size(); 37 G[from].push_back(len - 2); 38 G[to].push_back(len - 1); 39 } 40 41 inline bool bfs() 42 { 43 memset(d, 0, sizeof d); 44 memset(vis, 0, sizeof vis); 45 queue<int>q; 46 q.push(S); 47 d[S] = 1; 48 vis[S] = 1; 49 while (!q.empty()) 50 { 51 int x = q.front(); 52 q.pop(); 53 for (int i = 0; i < G[x].size(); ++i) 54 { 55 Edge &e = edge[G[x][i]]; 56 for (int i = 0; i < G[x].size(); ++i) 57 { 58 Edge &e = edge[G[x][i]]; 59 if (!vis[e.to] && e.cap > e.flow) 60 { 61 vis[e.to] = 1; 62 d[e.to] = d[x] + 1; 63 q.push(e.to); 64 } 65 } 66 } 67 } 68 return vis[T]; 69 } 70 71 inline int dfs(int x, int a) 72 { 73 if (x == T || a == 0) return a; 74 int flow = 0; 75 int f; 76 for (int &i = cur[x]; i < G[x].size(); ++i) 77 { 78 Edge &e = edge[G[x][i]]; 79 if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) 80 { 81 e.flow += f; 82 edge[G[x][i] ^ 1].flow -= f; 83 flow += f; 84 a -= f; 85 if (a == 0) break; 86 } 87 } 88 return flow; 89 } 90 91 inline int dicnic() 92 { 93 int ans = 0; 94 while (bfs()) 95 { 96 memset(cur, 0, sizeof cur); 97 ans += dfs(S, INF); 98 } 99 return ans; 100 } 101 102 int main() 103 { 104 int t; 105 scanf("%d", &t); 106 while (t--) 107 { 108 init(); 109 scanf("%d %d", &n, &m); 110 scanf("%d %d", &S, &T); 111 for (int i = 1; i <= m; ++i) 112 { 113 int x, y, z; 114 scanf("%d %d %d", &x, &y, &z); 115 addedge(x, y, z); 116 } 117 int ans = dicnic(); 118 for (int i = 1; i <= n; ++i) 119 { 120 for (int j = 0; j < G[i].size(); ++j) 121 { 122 int it = G[i][j]; 123 if (edge[it].cap == 0) continue; 124 if (edge[it].flow == edge[it].cap) 125 { 126 edge[it].cap = 1; 127 edge[it].flow = 0; 128 } 129 else 130 { 131 edge[it].cap = INF; 132 edge[it].flow = 0; 133 } 134 } 135 } 136 ans = dicnic(); 137 printf("%d ", ans); 138 } 139 return 0; 140 }
J:Brute Force Sorting
题意:给出N个数,如果arr[i] > arr[i + 1] 那么,这连个数都要删去,删若干轮后,直到不能删,输出最终的序列
思路:可以想到,如果在第一轮中,两个数被删去了,那么在下一轮可能被删去的数就有这两个数左边邻接的一个数,右边邻接的一个数,压入队列,继续判断。
因为每个数最多入队一次,最坏的时间复杂度O(n),
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define INF 0x3f3f3f3f 6 #define N 100100 7 8 int t, n; 9 int arr[N]; 10 int L[N], R[N], vis[N]; 11 12 queue <int> q; 13 14 int main() 15 { 16 cin.tie(0); 17 ios::sync_with_stdio(false); 18 cin >> t; 19 while (t--) 20 { 21 cin >> n; 22 for (int i = 1; i <= n; ++i) 23 { 24 cin >> arr[i]; 25 L[i] = i - 1, R[i] = i + 1; 26 vis[i] = 0; 27 } 28 arr[0] = 0; arr[n + 1] = INF; 29 while (!q.empty()) q.pop(); 30 for (int i = 1; i <= n; ++i) 31 { 32 if (arr[i] < arr[i - 1] || arr[i] > arr[i + 1]) 33 q.emplace(i), vis[i] = 1; 34 } 35 while (!q.empty()) 36 { 37 int u = q.front(); q.pop(); 38 int l = L[u], r = R[u]; 39 R[l] = r, L[r] = l; 40 if (l && r != n + 1 && !vis[r] && arr[l] > arr[r]) 41 { 42 q.emplace(l); vis[l] = 1; 43 q.emplace(r); vis[r] = 1; 44 } 45 } 46 int cnt = 0; 47 for (int i = 1; i <= n; ++i) if (!vis[i]) cnt++; 48 cout << cnt << endl; 49 for (int i = 1; i <= n; ++i) if (!vis[i]) 50 cout << arr[i] << " "; 51 cout << " "; 52 } 53 }
K:A Cubic number and A cunbic Number
题意:给出一个素数p,判断它是不是能不能由两个不同的立方数相减得到
思路:假设p = a3 - b3 那么根据立方差公式 p = (a - b)(a2 + b2 + ab) 显然 (a - b) < (a2 + b2 + ab) 又p为素数 所以必然有一个为1,显然 (a - b) = 1
那么 p = (a2 + b2 + ab) 将a - b = 1 代入 有 p = 3a2 + 3a + 1;
预处理一下即可
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define ll long long 6 7 unordered_map <ll, bool> mp; 8 9 const ll D = (ll)1e12; 10 11 inline void Init() 12 { 13 mp.clear(); 14 for (ll i = 1; true; ++i) 15 { 16 ll value = 3 * i * i + 3 * i + 1; 17 if (value > D) break; 18 mp[value] = true; 19 } 20 } 21 22 int t; 23 ll p; 24 25 int main() 26 { 27 Init(); 28 scanf("%d", &t); 29 while (t--) 30 { 31 scanf("%lld", &p); 32 puts(mp[p] ? "YES" : "NO"); 33 } 34 return 0; 35 }
赛后总结:
- 如果TLE了,要检查一下是否是数组开小
- 如果开了队列或栈,MLE了,检查一下是否是死循环,一直在入栈,入队
- 如果计算几何或者有浮点数精度问题的,要考虑JAVA BigDecimal
- 输出的时候一定要检查格式,末尾有没有空格
- 输出YES NO 的答案时,一定要检查大小写是否正确
- 有时候要考虑队列暴力,栈暴力,不要一提到暴力,想到的就是很暴的暴力
- 如果数论题给出数特别特殊,比如说素数,一定要考虑其性质,即它不能表示为两个数的乘积之和,1除外
- 如果出现自己认为思路正确却依然wrong answer的时候,可以考虑重新写以及思路错误两个方面,而不是一味在原来代码上更改。
- 如果模数是2的幂次,那么卡常数取模可以用&(2 ^ k - 1)
- 二分的题目不一定每次都是取中间值,可以考虑其他值