AtCoder Beginner Contest 366 补题
A - Election 2
判断当前是否有值大于 $n/2$ 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 1e5+7, mod = 1e9+7;
void solve(){
int n,t,a;
cin>>n>>t>>a;
if(n==1&&t==0&&a==0){
cout<<"No\n";
}
else if(t>n/2||a>n/2){
cout<<"Yes\n";
}
else cout<<"No\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
B - Vertical Writing
翻转字符串，同时对翻转后的每行从末尾开始清 * 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 1e5+7, mod = 1e9+7;
void solve(){
int n,mx=0;
cin>>n;
string s[N];
for(int i=1;i<=n;i++){
cin>>s[i];
mx=max(mx,(int)s[i].length());
}
string ans[mx+1];
for(int i=0;i<mx;i++){
for(int j=n;j>0;j--){
if(i>=s[j].length())
ans[i]+="*";
else
ans[i]+=s[j][i];
}
}
for(int i=0;i<mx;i++){
bool flag=0;
for(int j=n-1;j>=0;j--){
if(ans[i][j]=='*'&&!flag){
ans[i][j]=' ';
}
if(ans[i][j]>='a'&&ans[i][j]<='z'){
flag=1;
}
}
cout<<ans[i]<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
C - Balls and Bag Query
开一个 map 记录某一个值当前出现了几次，第一次出现就 cnt++, 出现次数变为 0 就 cnt– 最后输出 cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 1e5+7, mod = 1e9+7;
void solve(){
int q;
cin>>q;
unordered_map<int,int>vis;
int cnt=0;
while(q--){
int op,x;
cin>>op;
if(op==1){
cin>>x;
if(!vis[x])cnt++;
vis[x]++;
}
else if(op==2){
cin>>x;
vis[x]--;
if(!vis[x])cnt--;
}
else cout<<cnt<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
D - Cuboid Sum Query
三维前缀和板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 1e2+10, mod = 1e9+7;
#define int long long
void solve(){
int n, a[N][N][N], q, lx, rx, ly, ry, lz, rz;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++) cin >> a[i][j][k];
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) a[i][j][k] += a[i - 1][j][k];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) a[i][j][k] += a[i][j][k - 1];
cin >> q;
while(q--){
cin >> lx >> rx >> ly >> ry >> lz >> rz;
ll sum = a[rx][ry][rz]
- (lx > 1 ? a[lx-1][ry][rz] : 0)
- (ly > 1 ? a[rx][ly-1][rz] : 0)
- (lz > 1 ? a[rx][ry][lz-1] : 0)
+ (lx > 1 && ly > 1 ? a[lx-1][ly-1][rz] : 0)
+ (lx > 1 && lz > 1 ? a[lx-1][ry][lz-1] : 0)
+ (ly > 1 && lz > 1 ? a[rx][ly-1][lz-1] : 0)
- (lx > 1 && ly > 1 && lz > 1 ? a[lx-1][ly-1][lz-1] : 0);
cout << sum << endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
|
E - Manhattan Multifocal Ellipse
可以枚举 $x$ 从 $-2e6$ 到 $2e6$，去掉原式中的绝对值得到，$\sum_{x_i < x} (x - x_i) + \sum_{x_i \geq x} (x_i - x)$，通过此公式可以得到每个 $x$ 的 $\sum_{i=1}^{n} |x - x_i|$，同理求得 $\sum_{i=1}^{n} |y - y_i|$，分别存入两个数组，将两个数组升序排序，此时只需要用双指针对每个 $x$ 找到其对应的最大的 $y$ 对应的位置，累加即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 1e5+7, mod = 1e9+7;
auto fc(vector<int> &a){
sort(a.begin(), a.end());
vector<ll> dis;
int r = 2e6+7;
int id = 0;
ll pre = 0, suf = accumulate(a.begin(), a.end(), 0LL);
for(int i = -r; i <= r; i++){
ll sum = 0;
while(id < a.size() && a[id] < i){
pre += a[id];
suf -= a[id];
++id;
}
sum = 1LL * id * i - pre + suf - 1LL * (a.size() - id) * i;
dis.push_back(sum);
}
sort(dis.begin(), dis.end());
return dis;
}
void solve(){
int n, d;
cin >> n >> d;
vector<int> x(n), y(n);
for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
auto dx = fc(x);
auto dy = fc(y);
ll ans = 0;
int id = dx.size();
for(auto i : dx){
while(id > 0 && dy[id-1] + i > d)
--id;
ans += id;
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
|
F - Maximum Composition
函数之间，选择的偏序（顺序）问题。这个偏序怎么定义呢？函数 $f_i, f_j$，如果 $f_i(f_j(x)) > f_j(f_i(x))$，则有 $a_i(a_jx + b_j) + b_i \geq a_j(a_ix + b_i) + b_j$，我们把 $i, j$ 分离在一左一右，得到 $\frac{a_i - 1}{b_i} \geq \frac{a_j - 1}{b_j}$。
如果 $\frac{a_i - 1}{b_i} \geq \frac{a_j - 1}{b_j}$，则 $f_i(f_j(x)) > f_j(f_i(x))$，那么排序顺序已经清晰
要使 $ans$ 最大，不光要找到偏序顺序，还要找到用哪 k 个函数，那就转化为了 01背包 问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 2e5+7, mod = 1e9+7;
struct Node {
int a, b;
bool operator < (const Node &t) const {
return (a - 1) * t.b < (t.a - 1) * b;
}
};
void solve() {
int n, k;
cin >> n >> k;
vector<Node> l(n + 1);
for (int i = 1; i <= n; i++) cin >> l[i].a >> l[i].b;
sort(l.begin()+1,l.end());
vector<ll> dp(k + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = k; j >= 1; j--) {
dp[j] = max(dp[j - 1] * l[i].a + l[i].b, dp[j]);
}
}
cout << dp[k] << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|