5532 Almost Sorted Array
题目大意:给你一个序列,如果它拿掉其中一个数后,可以是该序列成为非递减或非递增序列,则输出YES。
有两种思路,第一种代码比较简单,是LIS,复杂度nlogn,第二种是On的复杂度。
LIS的代码如下。
#include <set> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; #define mem(x,y) memset(x, y, sizeof(x)) #define lson l,m,rt << 1 #define rson m+1,r,rt << 1 | 1 const int INF = 0x3f3f3f3f; ; int s[maxn], dp[maxn]; int T, n; bool judge() { mem(dp, INF); ; i < n; i++) { *upper_bound(dp, dp + n, s[i]) = s[i]; } int len = lower_bound(dp, dp + n, INF) - dp; mem(dp, INF); ; i < n; i++) { *upper_bound(dp, dp + n, -s[i]) = -s[i]; } int len2 = lower_bound(dp, dp + n, INF) - dp; len = max(len2, len); ); } int main() { scanf("%d",&T); while(T--) { scanf("%d", &n); ; i < n; i++) { scanf("%d", s+i); } printf("%s\n", judge() ? "YES" : "NO"); } ; }
5533 Dancing Stars on Me题意:给你n个点对,然后求一个正多边形(当然是凸的)。问存不存在。
题目给的坐标都是整数,看一看那个tanα = 1 / n (n = 1, 2, 3, 4,....)好像只有α = 45°的时候才有可能构成正多边形。
然后瞎搞搞。。
#include <cstdio> #include <algorithm> using namespace std; ; int T, n; ]; struct ss{int x, y;}s[maxn]; int get_dis(int x1, int y1, int x2, int y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } int main() { scanf("%d", &T); while(T--) { scanf("%d", &n); ; i < n; i++) { scanf("%d%d", &s[i].x, &s[i].y); } ) {printf("NO\n");continue;} , tot = ; ; i < n; i++) { ; j < n; j++) { temp[tot] = get_dis(s[i].x, s[i].y, s[j].x, s[j].y); tot++; } } sort(temp, temp + tot); ] == temp[]) ok = ; printf("%s\n", ok ? "YES" : "NO"); } ; }
5536 Chip Factory
题意:在数组a中找到三个数满足,ai+aj ^ ak 的值最大且i,j,k各不相同。
经典的异或用01字典树,推荐使用数组形式,快而且内存小。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; + ; * maxn; int n, T; LL a[maxn]; LL sz, ch[maxnode][], val[maxnode]; void init() { sz = ; memset(ch[], , ])); } //d=1表示插入,d=-1表示删除 void trie_update(LL x, int d) { ; ; i >= ; i--) { ; if(!ch[u][c]) { memset(ch[sz], , sizeof(ch[sz])); val[sz] = ; ch[u][c] = sz++; } u = ch[u][c]; val[u] += d; } } LL trie_query(LL v) { LL ans = ; ; ; i >= ; i--) { ; ] && val[ch[u][c ^ ]]) { ans |= ( << i); u = ch[u][c ^ ]; } else u = ch[u][c]; } return ans; } int main() { scanf("%d", &T); while(T--) { init(); scanf("%d", &n); ; i < n; i++) { scanf("%I64dd", a + i); trie_update(a[i], ); } LL ans = (a[] + a[]) ^ a[]; ; i < n; i++) { trie_update(a[i], -); ; j < n; j++) { trie_update(a[j], -); LL temp = trie_query((LL)a[i] + a[j]); ans = max(ans, temp); trie_update(a[j], ); } trie_update(a[i], ); } printf("%I64d\n", ans); } ; }
5538 House Building
题意:求这个东西的表面积。
#include <cstdio> #include <algorithm> using namespace std; int n, m, T; #define judge(x, y) 0 <= x && x < n && 0 <= y && y < m ][]; , , -, }; , -, , }; int main() { scanf("%d", &T); while(T--) { , bottom = , cnt = ; scanf("%d%d", &n, &m); ; i < n; i++) { ; j < m; j++) { scanf("%d", &ma[i][j]); tot += ma[i][j]; if(ma[i][j]) bottom++; ) cnt += (ma[i][j] - ) * ; } } * tot - bottom - cnt; ; ; i < n; i++) { ; j < m; j++) { ; k < ; k++) { int fx = i + dx[k]; int fy = j + dy[k]; if(judge(fx, fy)) { d += min(ma[fx][fy], ma[i][j]); } } } } ans -= d; printf("%d\n", ans); } ; }