比赛地址:https://ac.nowcoder.com/acm/contest/5158
出题人题解:https://ac.nowcoder.com/discuss/411752
A-最短路
数学几何题,不会,卒。
B-组队
题意:$n$个数里选若干个数,任意两个数的差值小于等于$k$。
基本思路:滑动窗口--由暴力优化而来。
- 很容易想到的一种方法是先从小到大排序,然后枚举右端点$i$,由0往右找最小的$j$满足$a[i]-a[j] \leq k$,这样做的时间复杂度是$O(n^2)$的。
- 考虑一下当$i$已经找到满足要求的$j$时,$i+1$还需要从0开始找吗?显然是不需要的,因为$a[i]-a[j-1]>k$,则$a[i+1]-a[j-1]>k$,所以$i+1$只需要从$j$开始即可。滑动窗口每次右端点滑动一位,左端点要滑动若干位来满足条件限制(此题的限制是差值不能超过$k$)。每个点最多被访问两次,时间复杂度$O(n)$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;
int T;
int n, k;
int a[MAXN];
int l, r, ans;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
ans = l = r = 0;
while(r < n) {
ans = max(ans, r - l + 1);
r++;//右端点移动
while(a[r] - a[l] > k) l++;//左端点移动
}
printf("%d\n", ans);
}
return 0;
}
C-十面埋伏
注意题目中的一个限制:保证地图的边界处不会有士兵。这样我们把士兵看成障碍物,以地图的边界作为起点搜索一遍就可以找出外围的空间,并且在搜索的过程中碰到士兵则需要放置陷阱。如下图所示我们不关心士兵的连通块形成什么样的图案(是否有圈),我们只关心连通块的外围(上色的部分),把外围最靠近士兵的部分防止炸弹即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 500 + 117;
const int MAXM = 2e6 + 117;
int n, m;
char s[MAXN][MAXN];
bool vis[MAXN][MAXN];
void dfs(int i, int j) {
if(i < 1 && i > n) return;
if(j < 1 && j > m) return;
if(vis[i][j]) return;
if(s[i][j] != '.') return;
vis[i][j] = true;
if(s[i - 1][j] == '#') s[i][j] = '*';
if(s[i + 1][j] == '#') s[i][j] = '*';
if(s[i][j - 1] == '#') s[i][j] = '*';
if(s[i][j + 1] == '#') s[i][j] = '*';
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
dfs(1, 1);
for(int i = 1; i <= n; i++) puts(s[i] + 1);
return 0;
}
D-牛妹吃豆子
注意修改和查询不是交替进行而是分开的,且矩阵的规模不会超过2000。
- 先把问题简化成一维的,考虑一维的怎么做。 对于区间更新,我们维护其差分序列将问题转化成点修改,如下图所示:
- 修改操作完后,我们对差分序列求一遍前缀和即可得到原序列。现在问题剩下区间求和,很显然得到原序列的前缀和序列$sum$,区间$[l,r]$的和为$sum[r]-sum[l-1]$。
- 如果你能想明白一维的情况,那么二维也能轻松的推出相应的关系。推不出的话可以参照出题人分享的https://www.cnblogs.com/hulean/p/10824752.html。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 117;
const int MAXM = 2e6 + 117;
int n, m, k, q;
LL a[2017][2017];
int main() {
scanf("%d%d%d%d", &n, &m, &k, &q);
int x1, y1, x2, y2;
//维护差分
while(k--) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
a[x1][y1]++;
a[x1][y2 + 1]--;
a[x2 + 1][y1]--;
a[x2 + 1][y2 + 1]++;
}
//得到原来的值
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
}
}
//得到前缀和
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
}
}
//区间查询
while(q--) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%lld\n", a[x2][y2] + a[x1 - 1][y1 - 1] - a[x2][y1 - 1] - a[x1 - 1][y2]);
}
return 0;
}
E-旅旅旅游
图论结论:以1为起点的最短路和以$n$为起点的最短路分别为$dist1$和$dist2$,对于边$[u,v]$若$dist1[u]+[u,v]+dist2[v]=dist1[n]$或$dist1[v]+[u,v]+dist2[u]=dist1[n]$,则该边一定在1到$n$的某条最短路中。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;
int n, m;
int fa[MAXN];
struct qnode {
int v;
LL c;
qnode(int _v = 0, LL _c = 0): v(_v), c(_c) {}
bool operator <(const qnode &r)const {
return c > r.c;
}
};
struct Edge {
int u, v;
LL w;
int ne;
} edge[MAXM];
int head[MAXN], tot;
void init() {
tot = 0;
memset(head, -1, sizeof(head));
for(int i = 0; i <= n; i++) fa[i] = i;
}
void addedge(int u, int v, LL w) {
edge[tot].u = u;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].ne = head[u];
head[u] = tot++;
}
bool vis[MAXN];
LL dist1[MAXN], dist2[MAXN];
void dijkstra(int start, LL dist[]) {
memset(vis, false, sizeof(vis));
for(int i = 1; i <= n; i++) dist[i] = (LL)INF * INF;
priority_queue<qnode> que;
while(!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while(!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if(vis[u]) continue;
vis[u] = true;
for(int i = head[u]; i != -1; i = edge[i].ne) {
int v = edge[i].v;
LL cost = edge[i].w;
if(!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
int get_fa(int i) {
if(fa[i] == i) return i;
return fa[i] = get_fa(fa[i]);
}
int main() {
scanf("%d%d", &n, &m);
init();
while(m--) {
int u, v;
LL w;
scanf("%d%d%lld", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
dijkstra(1, dist1);
dijkstra(n, dist2);
for(int i = 0; i < tot; i += 2) {
int u = edge[i].u;
int v = edge[i].v;
LL w = edge[i].w;
if(dist1[u] + w + dist2[v] == dist1[n]) continue;
if(dist1[v] + w + dist2[u] == dist1[n]) continue;
fa[get_fa(u)] = get_fa(v);
}
int flag = get_fa(1);
for(int i = 2; i <= n; i++) {
if(get_fa(i) != flag) {
flag = -1;
break;
}
}
if(flag == -1) puts("NO");
else puts("YES");
return 0;
}
F-斗兽棋
单判牛妹赢的情况即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;
string s, t, ss[7];
int main() {
ss[0] = "elephant";
ss[1] = "tiger";
ss[2] = "cat";
ss[3] = "mouse";
ss[4] = "elephant";
cin >> s >> t;
for(int i = 0; i < 4; i++) {
if(t == ss[i]) {
if(s == ss[i + 1]) puts("tiangou txdy");
else puts("tiangou yiwusuoyou");
}
}
return 0;
}
G-做题
总的时间是固定的,贪心的选择所需时间少的题目。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;
int n;
LL m;
int a[MAXN];
int main() {
scanf("%d%lld", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
LL sum = 0;
int cnt = 0;
for(int i = 0; i < n; i++) {
if(sum + a[i] > m) break;
sum += a[i];
cnt++;
}
printf("%d\n", cnt);
return 0;
}
H-人人都是好朋友
- 手下的编号范围到了$10^9$,但是关系的数量级只有$10^6$,所以需要(离散化==排序+去重)。
- 注意题目只说朋友的朋友是朋友,但没有说敌人的敌人不是敌人,切记不要自己加条件。
- 并查集,给每个集合设置一个标记$fa[]$,合并集合的时候合并标记。例如集合$A=\{a,b,c\}$,集合$B=\{e,d,f\}$,现在$e$和$c$是朋友则需要合并两个集合,只需要把$B$指向$A$即可。一般情况下为了方便编码我们初始化每个值得标记为其本身,即$fa[i]=i$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2210000 + 117;
const int MAXM = 2e6 + 117;
int T;
int n, m, a[MAXN];
int fa[MAXN];
struct node {
int a, b, c;
} p[MAXN];
void init() {
for(int i = 0; i <= n * 2; i++) fa[i] = i;
sort(a, a + n * 2);
m = unique(a, a + n * 2) - a;
}
int get_hash(int x) {
return lower_bound(a, a + m, x) - a;
}
bool cmp(node x, node y) {
return x.c > y.c;
}
int get_fa(int i) {
if(fa[i] == i) return i;
return fa[i] = get_fa(fa[i]);
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
a[i * 2] = p[i].a;
a[i * 2 + 1] = p[i].b;
}
sort(p, p + n, cmp);
init();
bool pr = true;
for(int i = 0; i < n; i++) {
int u = get_fa(get_hash(p[i].a));
int v = get_fa(get_hash(p[i].b));
if(p[i].c == 1) fa[u] = v;
else if(u == v) {
pr = false;
break;
}
}
if(pr) puts("YES");
else puts("NO");
}
return 0;
}
I-求和
- 神奇的东西--dfs序,如下图所示对树dfs一遍,在dfs的过程中进入某个结点和返回时都进行赋值,则结点$i$的子树为$[l,r]$。
- 有了dfs序后就可以$O(1)$的得到子树区间,问题转变成一维上的区间修改区间求和,使用线段树即可解决。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e6 + 117;
int n, m, k;
int u, v, w, num;
LL tree[MAXN * 8];
int val[MAXN], ll[MAXN], rr[MAXN];
bool vis[MAXN];
struct Edge {
int u, v;
int ne;
} edge[MAXM];
int head[MAXN], tot;
void init() {
num = 1;
tot = 0;
memset(head, -1, sizeof(head));
memset(vis, false, sizeof(vis));
memset(tree, 0, sizeof(tree));
}
void addedge(int u, int v) {
edge[tot].u = u;
edge[tot].v = v;
edge[tot].ne = head[u];
head[u] = tot++;
}
void dfs(int id) {
vis[id] = true;
ll[id] = num++;
for(int i = head[id]; i != -1; i = edge[i].ne) {
if(!vis[edge[i].v]) dfs(edge[i].v);
}
rr[id] = num++;
}
void update(int i, int l, int r, int pos, int x) {
if(l == r) {
tree[i] += x;
return;
}
int mid = (l + r) / 2;
if(pos <= mid) update(i * 2, l, mid, pos, x);
else update(i * 2 + 1, mid + 1, r, pos, x);
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
LL query(int i, int l, int r, int left, int right) {
if(left <= l && r <= right) return tree[i];
int mid = (l + r) / 2;
LL ret = 0;
if(left <= mid) ret += query(i * 2, l, mid, left, right);
if(mid < right) ret += query(i * 2 + 1, mid + 1, r, left, right);
return ret;
}
int main() {
init();
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(k);
for(int i = 1; i <= n; i++) update(1, 1, n * 2, ll[i], val[i]);
while(m--) {
int op, pos, x;
scanf("%d%d", &op, &pos);
if(op == 1) {
scanf("%d", &x);
update(1, 1, n * 2, ll[pos], x);
} else printf("%lld\n", query(1, 1, n * 2, ll[pos], rr[pos]));
}
return 0;
}
J-建设道路
$$ \sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i-a_j)^2\\= \sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i^2-2*a_i*a_j+a_j^2)\\= \sum_{i = 1}^{n} ((n-1)*a_i^2-a_i*((\sum_{j = 1}^{n}a_j)-a_i)) $$
Markdown的渣渣实在不知道怎么打第三个式子……
第二个式子到第三个式子是把$2*a_i*a_j$拆成两个$a_i*a_j$分给$i$和$j$各一个即可。把总和预处理出来之后第三个式子可以$O(n)$的求值。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e6 + 117;
int n;
LL a[MAXN], sum, ans, num;
int main() {
sum = ans = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
sum = (sum + a[i]) % mod;
}
for(int i = 0; i < n; i++) {
ans = (ans + (n - 1) * a[i] % mod * a[i] % mod) % mod;
num = a[i] * ((sum - a[i]) % mod + mod) % mod;
ans = ((ans - num) % mod + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/147/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。