小红书开发笔试题解
总体还是比较易，70分钟ak..（代价是鸽了今天的acm预选赛）
4个题，都是现场ac代码一点没改，不怎么好看。
第一题，给出用户的关注，互相关注的人在一个圈子里，并且有传递性。问总计有几个圈子。
裸并查集，或者忽视单向边跑一遍图有几个连通块，都是线性（并查集是接近线性）的复杂度。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int u[1005];
void init(int size)
{
for (int i = 0; i < size; i++) u[i] = -1;
}
int find(int x)
{
if (u[x] < 0) return x;
u[x] = find(u[x]);
return u[x];
}
void mix(int x, int y)
{
if ((x = find(x)) == (y = find(y))) return;
if (u[x] < u[y])
u[x] += u[y], u[y] = x;
else
u[y] += u[x], u[x] = y;
}
int main()
{
int i, j;
int n;
while (~scanf("%d", &n))
{
init(n);
int temp;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
scanf("%d", &temp);
if (temp == 1)
mix(i, j);
}
int ans = 0;
for (i = 0; i < n; i++)
if (u[i] < 0)
ans++;
printf("%d\n", ans);
}
return 0;
} 第二题，字符串的处理，删除所有括号内的内容（可能嵌套但一定成对），然后有<的删除它和它的前一个字符（如果有的话） 按照题意模拟就行..
#include <bits/stdc++.h>
using namespace std;
#define LL long long
char s[10005];
char ss[10005];
int main()
{
int i, j;
while (~scanf("%s", s))
{
int count = 0;
j = 0;
for (i = 0; s[i]; i++)
{
if (s[i] == '(')
count++;
if (count == 0)
ss[j++] = s[i];
if (s[i] == ')')
count--;
}
j = 0;
for (i = 0; ss[i]; i++)
{
if (ss[i] == '<')
{
j--;
j = max(0, j);
continue;
}
ss[j++] = ss[i];
}
ss[j] = 0;
puts(ss);
}
return 0;
} 第三题，给一个数组，从中取出一些数，保证取出的数位置不连续，和最大，且和最大的里取到的数的数目最少。问和多少，取几个数。数据范围1000 肯定往动态规划上想..（都是正数的话或许贪心也可？）
dp[i][j]表示最后一个取i，总计取了j个时的总和，有dp[i][k + 1] = max(dp[i][k + 1], dp[j][k] + a[i])，j取0到i-2，k取0-i。
这是O(n^3)的复杂度，不一定能过，但是有几个剪枝:都是正数的话，为了总和最大不可能连续空3个或以上，j只有3种取值（忘记题目是不是说都是正数了..）,不连续取k一定小于等于i/2+1。
其实O(n^3)就能过...
开始想着用la数组记录父节点，能少一维，没啥必要..就申请了初始化了但没用
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int dp[1005][1005], la[1005];
int a[1005];
int main()
{
int i, j, k;
int n;
while (~scanf("%d", &n))
{
memset(dp, 0, sizeof(dp));
memset(la, -1, sizeof(la));
for (i = 0; i < n; i++)
scanf("%d", a + i);
dp[0][1] = a[0];
dp[1][1] = a[1];
for (i = 2; i < n; i++)
for (j = 0; j < i - 1; j++)
for (k = 0; k <= i / 2 + 1; k++)
{
dp[i][k + 1] = max(dp[i][k + 1], dp[j][k] + a[i]);
}
int ma = 0, co = 1005;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (dp[i][j] > ma || (dp[i][j] == ma && j < co))
ma = dp[i][j], co = j;
}
printf("%d %d\n", ma, co);
}
return 0;
} 开始以为是nlogn的最长上升子序列，快写完才发现和顺序没有关系..（然而就算是最长上升子序列也不对）
不限复杂度就dp一下，n^2时间，但是1e6肯定8行。
考虑降维，对坐标的xy排序，这样每个点x值一定大于等于它前面所有的点x，就可以无视x值只看y值了。
然后按照dp的思想，dp[i]=max(dp[j])+1，j<i且j.y≤i.y。
所以维护一个数组a,a[i]表示当前最后一个点纵坐标为i的序列的最大长度。
需要logn的查询区间最大值和更新，套个线段树就行。
注意数组a大小不是n，是纵坐标最大值。（还好纵坐标给的小，不然害得套个哈希）
一个大坑，给的数据范围是大于0，然而有等于0的数据，导致运行错误..所以代码里对所有y值加一。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct poi { int x, y; }a[1000005];
struct { int l, r, n; }t[1000005 << 2];
void build(int l, int r, int i)
{
t[i].l = l, t[i].r = r, t[i].n = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(l, mid, i << 1), build(mid + 1, r, i << 1 | 1);
}
void update(int i, int x, int k)
{
t[k].n = max(t[k].n, x);
if (t[k].l == t[k].r)
return;
int mid = (t[k].l + t[k].r) >> 1;
if (i <= mid)
update(i, x, k << 1);
else
update(i, x, k << 1 | 1);
}
int sea(int l, int r, int k)
{
if (t[k].l == l && t[k].r == r)
return t[k].n;
int mid = (t[k].r + t[k].l) >> 1;
if (r <= mid)
return sea(l, r, k << 1);
if (l > mid)
return sea(l, r, k << 1 | 1);
return max(sea(l, mid, k << 1), sea(mid + 1, r, k << 1 | 1));
}
int cmp(poi a, poi b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int main()
{
int i, j, k;
int n;
while (~scanf("%d", &n))
{
int ma = 0;
for (i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].x, &a[i].y);
a[i].y++;
ma = max(ma, a[i].y);
}
sort(a + 1, a + n + 1, cmp);
build(1, ma, 1);
for (i = 1; i <= n; i++)
{
int temp = sea(1, a[i].y, 1);
update(a[i].y, temp + 1, 1);
}
printf("%d\n", sea(1, ma, 1));
}
return 0;
} 
投递网易有道等公司10个岗位 >
