比赛链接

A

思路:因为是严格大于,所以很容易想到最小的数一定不会被消除掉,取子序列长度为2,里面一个数是最小值,另一个是非最小值。即可最大化被删除的元素。那么答案就是总数减去最小值的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int _,n,m;
int a[maxn];
map<int ,int > MP;
int mx;
int main
{
for(cin>>_;_;_--)
{
mx=0;
MP.clear();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
MP[a[i]]++;
mx=max(mx,MP[a[i]]);
}
sort(a+1,a+n+1);
cout<<n-MP[a[1]]<<endl;
}
return 0;
}

B

思路:任意两个数的差的绝对值一定要大于等于所选序列最大值。因为是输出个数,所以排序后,照题意模拟维护当前最大值和最大差值的绝对值就行。

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
const ll mod=1e9+7;
int _,n,m;
ll a[maxn];
int place;
int main()
{
for(cin>>_;_;_--)
{
place=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
if(a[i]>0)
{
place=i-1;
break;
}
}
//维护最小差值和最大的元素
ll midelta=mod*2;
ll mx=-mod;
bool f=0;
for(int i=2;i<=n;i++)
{
mx=max(mx,a[i]);
midelta=min(midelta,abs(a[i]-a[i-1]));
if(midelta<mx)
{
cout<<i-1<<endl;
f=1;
break;
}
}
if(!f)
{
cout<<n<<endl;
}
}
return 0;
}

C

思路:首先猜一下肯定要取得是两边,那么每个元素就只有取最大值和最小值的区别了。
dp[i][j]表示对于以i为根的树。
dp[i][0]表示i号节点选择最小值,dp[i][1]表示i号节点选最大值。
对于非叶子节点i而言(son表示这个叶子节点的任意一个儿子):
dp[i][0] += max(dp[son][0]+abs(l[i]-l[son]) , dp[son][1]+abs(l[i]-r[son]));
dp[i][1] += max(dp[son][0]+abs(r[i]-l[son]) , dp[son][1]+abs(r[i]-r[son]));

最后把输出max(dp[root][0],dp[root][1])。

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
int _,n,m;
vector <int > tree[maxn];
ll ans,mx;
bool vis[maxn];
int viss;
ll a,b;
ll l[maxn],r[maxn];
ll vl[maxn];
ll vr[maxn];
ll dp[maxn][2];
void dfs(int rt ,int fa)
{
for(auto &son: tree[rt])
{
if(son==fa)
{
continue;
}
dfs(son,rt);
dp[rt][0]+=max(dp[son][0]+abs(l[son]-l[rt]),dp[son][1]+abs(r[son]-l[rt]));
dp[rt][1]+=max(dp[son][0]+abs(l[son]-r[rt]),dp[son][1]+abs(r[son]-r[rt]));
}
}
int main()
{
ios::sync_with_stdio(false);
for(cin>>_;_;_--)
{
cin>>n;
int u,v;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;++i)
{
cin>>l[i]>>r[i];
}
for(int i=1;i<n;++i)
{
cin>>u>>v;
tree[u].push_back(v);
tree[v].push_back(u);
}

dfs(1,0);
cout<<max(dp[1][0],dp[1][1])<<endl;
for(int i=1;i<=n;i++)
{
tree[i].clear();
}
}
return 0;
}

写在最后:
以后会对思路里面的代码部分进行加粗,自己发现更好看一点。
D题补了,但是懒得写了。