AtCoder Beginner Contest 355

2024-06-11 02:28
文章标签 atcoder beginner contest 355

本文主要是介绍AtCoder Beginner Contest 355,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

C - Bingo 2

题意

有一个 n × n n\times n n×n 的网格,初始全白,有 t t t 次操作,每次操作涂黑一个指定的格子。
问执行第几个操作后,有一行或一列或对角线的格子全部被涂黑。

思路

如果暴力判断,那么总时间复杂度是 O ( n 2 t ) O(n^2t) O(n2t) 的,而 n ≤ 2000 , t ≤ 200000 n \le 2000,t \le 200000 n2000,t200000 ,会超时。

我们可以记录每行、每列、主次对角线中被涂黑的格子数量 r i , c i , d 0 , d 1 r_i,c_i,d_0,d_1 ri,ci,d0,d1,每次操作后检查该格子对应的行列对角线的黑格子数是否 = n =n =n 即可。

代码

#include <iostream>
#include <vector>
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, t;cin >> n >> t;vector<int> r(n, 0), c(n, 0), d(2, 0);for(int i = 0, num; i < t; i++){cin >> num; num--;int x = num / n, y = num % n;r[x]++; c[y]++;if(x == y) d[0]++;if(x + y == n - 1) d[1]++;if(r[x] == n || c[y] == n || d[0] == n || d[1] == n){cout << i + 1 << endl;return 0;}}cout << -1 << endl;return 0;
}

D - Intersecting Intervals

题意

给定 n n n 个区间 [ l i , r i ] [l_i,r_i] [li,ri],问两两相交的区间对数,交点重叠也算入。

思路

暴力枚举的时间复杂度是 O ( n 2 ) O(n^2) O(n2),不能满足要求。
发现直接求相交的对数不好想,但正难则反,我们可以求出不相交的区间对数 c n t cnt cnt,易知 n ( n − 1 ) 2 − c n t \dfrac{n(n-1)}{2} - cnt 2n(n1)cnt 就是答案。

发现不相交的两个区间 i , j i, j i,j一定满足 r j ≤ l i r_j \le l_i rjli(这里假定区间 j j j 在区间 i i i 左边)。

我们可以用双指针,将 l i l_i li r i r_i ri 分别升序排序。
记对于每个 i i i,满足 r j ≤ l i r_j \le l_i rjli j j j 的个数为 c i c_i ci
由于 r r r 升序,满足 r j ≤ l i r_j \le l_i rjli j j j 递增,因此可以得到以下算法:

按照 i = 1 , 2 , ⋯ , n i=1,2,\cdots,n i=1,2,,n 的顺序执行以下操作:

  1. c = 1 c = 1 c=1
  2. 如果 r c ≤ l i r_c \le l_i rcli,那么 c = c + 1 c=c+1 c=c+1,直到不满足前述条件。
  3. c i = c − 1 c_i=c-1 ci=c1

但稍加分析可以发现,上述算法的时间复杂度仍为 O ( n 2 ) O(n^2) O(n2),我们需要进一步优化。

发现 c i c_i ci 一定不降,所以计算 c i + 1 c_{i+1} ci+1 时,可以直接从 c i c_i ci 开始,这样时间复杂度就可以优化至 $O(n) $。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long longsigned main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;cin >> n;vector<int> l(n), r(n);for(int i = 0; i < n; i++) cin >> l[i] >> r[i];sort(l.begin(), l.end());sort(r.begin(), r.end());int ans = n * (n - 1) / 2, j = 0;for(int i = 0; i < n; i++){while(r[j] < l[i]) j++;ans -= j;}cout << ans << endl;return 0;
}

E - Guess the Sum

题意

交互题。
有一个长度为 2 n 2^n 2n 的序列 a a a,但是你不知道它。你需要用最少的询问次数求出 ( ∑ i = l r a i ) m o d 100 (\sum_{i=l}^r a_i) \mod 100 (i=lrai)mod100 的值。(下标从 0 0 0 开始)。
每次询问给出 i , j i,j i,j,回答 l = 2 i j , r = 2 i ( j + 1 ) − 1 , ( ∑ i = l r a i ) m o d 100 l=2^ij, \ r=2_i(j+1)-1, \ (\sum_{i=l}^r a_i) \mod 100 l=2ij, r=2i(j+1)1, (i=lrai)mod100 的值。

思路

审完题可以想到 ABC349D ,将区间变成左闭右开区间。
但是那题不能将两个区间相减,而本题可以,比如询问 [ 1 , 7 ] [1,7] [1,7],如果按照那题的思路,需要询问区间 [ 1 , 1 ] + [ 2 , 3 ] + [ 4 , 7 ] [1,1]+[2,3]+[4,7] [1,1]+[2,3]+[4,7] 即询问 ( 0 , 1 ) , ( 1 , 1 ) , ( 2 , 1 ) (0,1),(1,1),(2,1) (0,1),(1,1),(2,1),共三个询问。
但是可以用 [ 0 , 7 ] − [ 0 , 0 ] [0,7]-[0,0] [0,7][0,0],即询问 ( 3 , 0 ) , ( 0 , 0 ) (3,0),(0,0) (3,0),(0,0)

于是相当于在一张 2 n 2^n 2n 个点的无向图上,对于所有 i , j i,j i,j,连接 2 i j 2^ij 2ij 2 i ( j + 1 ) 2^i(j+1) 2i(j+1),求 l l l r + 1 r+1 r+1 的最短路。

由于边权为 1 1 1,我们直接 bfs,记录下路径。
接下来遍历路径,考虑如何提问,实际上这很简单,每次查询时往左跳就减去查询的和,往右跳就加上,如果从后往前的话就反过来。

为了省空间,可以不建图,直接bfs时判断(其实没必要)。

代码

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, l, r;cin >> n >> l >> r;r++;int v = 1 << n;vector<int> pre(v + 1, -1);queue<int> q;q.push(l);pre[l] = l;while(q.size()) {int x = q.front();q.pop();for (int i = 1; i <= v; i *= 2) {for (auto y : {x - i, x + i}) {if (y < 0 || y > v) continue;if (pre[y] == -1) {pre[y] = x;q.push(y);}}if (x & i) break;}}int ans = 0;for (int i = r; i != l; i = pre[i]) {int a = pre[i], b = i, t = 1;if (a > b) {swap(a, b);t = -1;}int p = __lg(b - a), q = a / (b - a), res;cout << "? " << p << " " << q << endl;cin >> res;ans = (ans + t * res + 100) % 100;}cout << "! " << ans << endl;return 0;
}

F - MST Query

题意

给你一棵 n n n 个点的带边权的树,有 q q q 次询问,每次询问添加一条边,输出当前的最小生成树的边权和。
所有边权不大于 10 10 10

思路

首先否决掉跑 q q q 次 kruskal 的做法。

可以LCT做,但是这道题中边的权值非常小,那么我们从可以这里找突破口.

考虑维护每个边权选择的数量,算出生成树边权,删边的话,可以维护边权为 i i i 的边所形成的连通性, 这样加一条边权为 i i i 的边时,看有没有边权 > i >i >i 的使得那两点连通,从而决定删除哪条边。但会发现不好维护,因为会产生依赖关系。

为了不依赖其他情况,我们可以用并查集维护边权 $ \le i$ 的边所形成的连通性情况,这样我们就建立 10 10 10 个互不依赖的并查集。

接下来看如何求出最小生成树的边权,关键是求出每个边权的在MST中的个数。由于每加一条边,连通块的个数就会少一。
所以边权为 i i i 使用的个数就是 d i d_i di 的连通块个数减去 d i − 1 d_{i-1} di1 的连通块个数。

代码

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;struct DSU {vector<int> f;DSU() {}DSU(int n){init(n);}void init(int n){f.resize(n);iota(f.begin(), f.end(), 0);}int find(int x){while (x != f[x]) x = f[x] = f[f[x]];return x;}bool same(int x, int y){return find(x) == find(y);}bool merge(int x, int y){x = find(x);y = find(y);if (x == y) return false;f[y] = x;return true;}
};int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, q;cin >> n >> q;vector<DSU> dsu(10, DSU(n));vector<int> cnt(10, n);for(int i = 0, a, b, c; i < n - 1; i++){cin >> a >> b >> c;a--, b--;for(int j = c; j <= 10; j++) cnt[j - 1] -= dsu[j - 1].merge(a, b);}for(int i = 0, u, v, w; i < q; i++){cin >> u >> v >> w;u--, v--;for(int j = w; j <= 10; j++) cnt[j - 1] -= dsu[j - 1].merge(u, v);int ans = 0, last = n;for(int j = 1; j <= 10; j++){ans += j * (last - cnt[j - 1]);last = cnt[j - 1];}cout << ans << endl;}return 0;
}

这篇关于AtCoder Beginner Contest 355的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1049949

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

CF Bayan 2015 Contest Warm Up A.(模拟+预处理)

A. Bayan Bus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/problem/A The fi

AtCoder Beginner Contest 369 D - Bonus EXP 动态规划

原题链接: https://atcoder.jp/contests/abc369/tasks/abc369_d 思路:   这道题为什么要用动态规划呢,其实,对于第i个怪物,我们有打与不打两种处理方式,而对于打,我们是获得两倍的经验值,还是一倍的经验值,与我们打了奇数只怪物还是打了偶数只怪物有关了,因此我们定义dp[i][0] 为前i只怪物总共打了偶数次,dp[i][1] 为前i只怪物总

2015 Multi-University Training Contest 5 1009 MZL#39;s Border

MZL's Border  Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=5351   Mean:  给出一个类似斐波那契数列的字符串序列,要你求给出的f[n]字符串中截取前m位的字符串s中s[1...i] = s[s.size()-i+1....s.size()]的最大长度。 analyse:   过计算

【UVa】10600 ACM Contest and Blackout 次小生成树

类型:次小生成树 题目大意: 为了举办ACM竞赛,市长决定给所有的n(3 <= n <= 100)所学校提供可靠的电力供应。当且仅当一个学校直接连到电站,或者连到另一个有可靠供应的学校时,才有可靠供应。现在给出在不同学校之间的布线成本,找出最便宜的两种连线方案。一个方案的成本等于其中所有学校之间连线的成本的总和。 题目分析: 次小生成树。 先求出最小生成树,然后枚举所有不在

【POJ】3660 Cow Contest floyd(可以拓扑排序?)

Cow Contest Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6925 Accepted: 3792 Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating i