D:题意：给定一个国际象棋棋盘，每个点都有权值，求在哪放置象，能使得象能攻击到的位置和最大。
Solution：由于数据范围很小，我们考虑最简单的暴力实现。对于每一个点，我们向四个攻击方向去走直到到达边界，定义方向数组即可。
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
| int dx[5]={1,1,-1,-1};
int dy[5]={-1,1,1,-1};
void solve(){
cin>>n>>m;
vector<vector<int>>v(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>v[i][j];
}
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int res=v[i][j];
for(int k=0;k<4;k++){
int tx=i,ty=j;
while(tx+dx[k]>=0&&tx+dx[k]<n&&ty+dy[k]>=0&&ty+dy[k]<m){
tx+=dx[k];
ty+=dy[k];
res+=v[tx][ty];
}
}
ans=max(ans,res);
}
}
cout<<ans<<endl;
}
|
给出jls的dp写法。复杂度较小，学习一下
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
| void solve() {
int n, m;
std::cin >> n >> m;
std::vector a(n, std::vector<int>(m)), f(a), g(a);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
std::cin >> a[i][j];
f[i][j] = g[i][j] = a[i][j];
if (i > 0 && j > 0) {
f[i][j] += f[i - 1][j - 1];
}
if (i > 0 && j + 1 < m) {
g[i][j] += g[i - 1][j + 1];
}
}
}
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < m; j++) {
if (j > 0) {
f[i - 1][j - 1] = f[i][j];
}
if (j + 1 < m) {
g[i - 1][j + 1] = g[i][j];
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans = std::max(ans, f[i][j] + g[i][j] - a[i][j]);
}
}
std::cout << ans << "\n";
}
|
F:题意：给定一个数组，我们希望寻求最大值域区间，使得区间内的每个数都出现k次。
Solution：显然我们答案与原序列的顺序无关，我们先把大于k次的数用map拿出来。此时的新vector已经有序，我们需要找到最大连续区间就是答案。
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
| void solve(){
cin>>n>>m;
map<int,int>mp;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]++;
}
vector<int>v;
for(auto [x,y]:mp)if(y>=m)v.push_back(x);
if(v.size()==0){
cout<<-1<<endl;
return ;
}
int l=v[0],r=v[0];int ans=0;
int ansl=l,ansr=r;
for(int i=1;i<v.size();i++){
if(v[i]!=v[i-1]+1){
if(ans<r-l+1){
ans=r-l+1;
ansr=r,ansl=l;
}
l=r=v[i];
}
else r++;
}
if(ans<r-l+1){ans=r-l+1;ansr=r,ansl=l;}
cout<<ansl<<" "<<ansr<<endl;
}
|
G:题意：给定一颗黑白树，我们希望找到子树中的黑白节点相等的子树数量。
Solution：考虑直接dfs这棵树，维护两个数组代表子树的黑点与百点数量，最后只需要逐一对比统计答案
debug:字符串下标0base导致全部信息偏移
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
| int bai[N],hei[N];
string s;
vector<int>e[N];
void dfs(int u){
if(s[u]=='W')bai[u]++;
else hei[u]++;
for(auto v:e[u]){
dfs(v);
bai[u]+=bai[v];
hei[u]+=hei[v];
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
bai[i]=hei[i]=0;
e[i].clear();
}
for(int i=2;i<=n;i++){
int x;cin>>x;
e[x].push_back(i);
}
cin>>s;
s=" "+s;
dfs(1);
int ans=0;
for(int i=1;i<=n;i++)if(hei[i]==bai[i])ans++;
cout<<ans<<endl;
}
|
H题意：给定一个数组，有两座桥，第一座桥上第i个点到第a[i]的点联想，其中第i个点在0-1之间，而a[i]的含义是a[i]-a[i]+1.我们希望钦定每个点的合适的位置，使得n条直线之间交点尽可能多，经过不断手模发现，答案就是当前的左端点的右边，所有右端点比当前右端点大的点都会贡献，好像就是正序对的数量。显然树状数组维护即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
Fenwick<int>c(n+2);
for(int i=1;i<=n;i++)c.add(a[i],1);
int ans=0;
for(int i=1;i<=n;i++){
c.add(a[i],-1);
ans+=c.sum(a[i]);
}
cout<<ans<<endl;
}
|
