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);
}
;
}