前言
这一场也还是比较简单的…..对着题解都能够做出来
A. Cancel the Trains
签到题，给定一些x轴和y轴上的点(x_i,0)和(0,y_i)问有多少个点对满足x_i == y_i。由于x_i和y_i的都很小，所以开一个类似于桶排序的数组记录一下就好
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 <iostream>
#include <cstring>
using namespace std;
int t,n,m,x,ans;
bool arr[110];
int main(){
ios_base::sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n>>m;
while(n--){
cin>>x;
arr[x]=true;
}
while(m--){
cin>>x;
if(arr[x])++ans;
}
cout<<ans<<"\n";
memset(arr,0,sizeof arr);
ans=0;
}
return 0;
}
|
B. Suffix Operations
给定一个长度为n的数组arr。我们拥有对数组的两种操作，
- 将arr任意后缀上的所有元素+1
- 将arr任意后缀上的所有元素-1
现在我们拥有一次机会能改变数组中的任意一个元素为数组中的另外一个元素，求一个操作的最小次数使得数组中所有的元素都相同。
首先，假设我们不使用这一次机会，那么我们可以直接把需要的修改次数求出来, which is 数组上的所有相邻元素的abs之和，这个数记做ans。
现在考虑使用这一次机会会对我们的ans产生何种影响。考虑数组中的任意位置i ，在不使用机会的时候，我们对于i这一段的处理应该是，首先将 [i+1,n]的上所有元素调整成和arr[i]相同，接着将[i,n]的所有元素调整成和arr[i-1]相同。这样的做需要abs(arr[i+1]-arr[i])+abs(arr[i-1]-arr[i])次。在使用机会之后，我们可以将arr[i]换成arr[i+1]或者arr[i-1]，这样替换之后需要的机会次数就是abs(arr[i-1]-arr[i+1])，即我们此时不需要再对arr[i]做任何处理。因此这样对ans的影响就是abs(arr[i-1]-arr[i+1])-abs(arr[i+1]-arr[i])-abs(arr[i-1]-arr[i])
最后，对于数组的首尾元素需要特别的写法因为一个没有i-1，一个没有i+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
| #include <iostream>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int maxm=200010;
int t,arr[maxm],n,cnt,upd=0x3f3f3f3f;
signed main(){
ios_base::sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n>>arr[0];
for(int i=1;i<n;++i){
cin>>arr[i];
cnt+=abs(arr[i]-arr[i-1]);
}
for(int i=1;i<n-1;++i){
upd=min(upd,abs(arr[i-1]-arr[i+1])-abs(arr[i-1]-arr[i])-abs(arr[i]-arr[i+1]));
}
upd=min(upd,-abs(arr[0]-arr[1]));
upd=min(upd,-abs(arr[n-1]-arr[n-2]));
cout<<min(cnt,cnt+upd)<<"\n";
cnt=0,upd=0x3f3f3f3f;
}
return 0;
}
|
C. Triangles
给定一个n×n的方阵，方阵中的每一个元素都属于[0,9]。定义一个函数f(d)，其中d属于[0,9]，f(d)的值为一个方阵上的最大的三角形面积，其中，
1. 三角形每个点落在方阵的某个元素上
2. 三角形每个点落在的方阵元素都是d
3. 三角形至少要有一条边同方阵的边平行
对于每一个d∈[0,9]，求出在最多一次能够把方阵中的任意一个元素修改成d后的2*f(d)。
n的范围<=2000
显然要面积最大，那么在指定一个点之后，另外两个点应该隔得越远越好。因此我们首先用一个2层的for循环把d出现的最小行，最大行，最小列，最大列记录下来。然后枚举修改点d，对于每一个修改点，我们用它与相隔最远的两个点组成三角形，记录面积即可。
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2010;
int t,n,ans[10],x,minr[10],maxr[10],minc[10],maxc[10];
char arr[maxn][maxn];
void init();
int main(){
ios_base::sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;++i)
cin>>arr[i]+1;
init();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
x=arr[i][j]-'0';
minr[x]=min(minr[x],i),maxr[x]=max(maxr[x],i);
minc[x]=min(minc[x],j),maxc[x]=max(maxc[x],j);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
x=arr[i][j]-'0';
ans[x]=max(ans[x],max(i-1,n-i)*max(j-minc[x],maxc[x]-j));
ans[x]=max(ans[x],max(j-1,n-j)*max(i-minr[x],maxr[x]-i));
}
for(int i=0;i<10;++i)cout<<ans[i]<<' ';
cout<<"\n";
}
return 0;
}
void init(){
memset(maxr,0,sizeof maxr);
memset(maxc,0,sizeof maxc);
memset(minr,0x3f,sizeof minr);
memset(minc,0x3f,sizeof minc);
memset(ans,0,sizeof ans);
}
|
D. Checkpoints
背景是玩游戏，通过一个游戏的关卡的概率是恒定的1/2。游戏由许多连续的关卡组成，有些关卡设置了存档点，当在某一个关卡挑战失败后，会从最近的一次存档点开始重新挑战。例如该游戏有4个关卡，而存档点在1和3号关卡。在1号和2号关卡挑战失败会回到1号关卡重新开始挑战；而一旦到达3号之后，3号的存档点就被激活，之后就会从3号开始重新挑战。
给定一个数k，要求构造出一个关卡使得通过该游戏的期望次数是k。假如无法构造则输出-1
这道题是构造做法，采用的技巧是计算以存档点开始，之后跟随若干个无法存档的关卡的关卡段期望，其序列记做[1….0]；之后按照k组合预先构造的关卡段。
对于一个仅有存档关卡，即[1]，通过的期望是2次。
+ 假设通过[1]的期望是x，那么x=1 * 1/2 + (1 + x) * 1/2，即1/2的概率直接通过，1/2的概率花费1次之后没有通过之后还需要x次通过，解得x=2
对于一个长度为n的[1…..0]的关卡，假设其通过的期望为x。考虑如何计算通过[1……00]，即在其后再附加一个0，的期望次数x1。
- x1 = x + 1 * 1/2 + (1+x1)*1/2 = 2 * (1+x)。其含义是已经使用了x次到达了最后一次关卡的门口，有1/2的概率使用1步直接通过；另外1/2的概率再使用1步之后回到了起点，需要额外的x1步通过。
最后得出f(1)=1, f(n+1)=2(f(n)+1)
构造出关卡段之后，就将k按照贪心或者二进制不断分配给当前最长的可能的段即可
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll =long long;
const int maxm=2010;
ll n,t,k,arr[65]{2},ans[maxm],sz;
int main(){
ios_base::sync_with_stdio(0);
for(ll i=1;i<=60;++i){
arr[i]=(arr[i-1]+1)<<1ll;
}
cin>>t;
while(t--){
cin>>k;
if(k&1){
cout<<"-1\n";
continue;
}
for(int i=60;k&&i>=0;){
if(k>=arr[i]){
ans[sz]=1;
sz+=i+1;
k-=arr[i];
}else --i;
}
cout<<sz<<"\n";
for(int i=0;i<sz;++i)
cout<<ans[i]<<' ';
cout<<"\n";
memset(ans,0,sizeof ans);
sz=0;
}
return 0;
}
|
E. Dog Snacks
题目意思有点点冗长，但是理解起来难度不大这里就不再复述题目了；因为题目中要求的是一个最小k使得小狗能够完成任务；考虑某一个子树r，小狗总是从r的一个子树移动到另外一个子树，最后从r返回父节点。因此一个简单的想法就是让r最后一次的子树应该越短越好，因为最后一次从子树回来通过r回到r的父节点本身需要的路程就会长一点。有了这个基础想法后，我们考察r上的所有子树的“返回距离”，选择其中的最小的那一个再+1(通过r)返回给父节点作为r的父节点挑选其子树的根据。当然了，对于k的还有其他的约束，因为我们需要保证小狗最后一次不仅能够从r返回，也需要k能够保证小狗在r的子树之间穿梭，因此k应该至少是这些”返回距离”中的最大值+1，才能够保证从最深的子树中还有能力回到别的子树上。
此外，一个例外就是根节点。因为根节点不需要考虑其父节点；因此k至少应该大于根节点中的”返回距离”最大的子树(对应最后返回根节点完成任务)，以及“返回距离“第二大的+1(对应穿梭完之后有能力进入最深的子树)
用一个变量ans一直dfs维护k即可。
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
| #include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxm=200010;
int t,n,dfs(int cur,int p),ans;
vector<int> adj[maxm];
int main(){
ios_base::sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n;
for(int i=0,x,y;i<n-1;++i){
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1,0);
cout<<ans<<"\n";
ans=0;
for(int i=1;i<=n;++i)adj[i].clear();
}
return 0;
}
int dfs(int cur,int p){
vector<int> tmp;
for(int nxt:adj[cur])
if(nxt!=p){
tmp.push_back(dfs(nxt,cur));
}
if(tmp.size()>1){
sort(tmp.begin(),tmp.end());
ans=(cur==1?max({ans,tmp.back(),tmp[tmp.size()-2]+1}):max(ans,tmp.back()+1));
}
if(tmp.empty())return 1;
ans=max(ans,tmp[0]);
return tmp[0]+1;
}
|
F. Even Harder
平台跳跃类游戏里存在n个不同高度的平台，第i个平台有一个数arr[i]，代表可以跳跃到[i+1,i+arr[i]]中的任意一个平台。现在的要求是将一些平台的a_i置0，使得从第一个平台跳跃到第n个平台的方式数恰好只有一种，求最小操作次数。
因为目标要求跳跃到某一个平台的方法数只有一种，因此某一个被跳跃到的平台的前驱一定是唯一的；否则就至少会有两种目标方案。定义状态dp[i] [j]表示在某一个平台k上，下一步会跳跃到i平台，同时最高能够跳跃到j平台的最小需要调整平台的次数。答案即为dp[n] [n]。接下来考虑状态转移方程；考察从某个j平台经过一次跳跃能否到达i平台上。按照我们的定义，dp[j] [i-1]为目前处于j的前驱而且最多也只能跳跃到i-1平台。假设 j +arr[j]>=i，此时意味着从j平台跳跃到i平台是可行的；综上此处的dp[j] [i-1] 在j +arr[j] >=i的情况下可以转移到 dp[i] [j+arr[j]]。那么这个转移的cost是多少呢？我们需要把从[j+1,i-1]中的所有能够跳跃到i的平台给清空，因为需要保证前驱唯一性，将这个cost记做cnt。对于j之前的前驱唯一性是由dp本身的性质保证的，因此不用再做额外计算。
此外，按照我们的定义dp[i] [j]中的j始终是>=i的。在按照上述的转移方程计算完成之后，我们还需要对于所有的n>=j>=i+1,有dp[i] [j]=min(dp[i] [j], dp[i] [j-1])。理由是按照题目要求，我们一定能够在将来跳到n处，因此需要对所有没有处理过的状态取min。
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxm=3010;
int t,n,arr[maxm],dp[maxm][maxm];
int main(){
ios_base::sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;++i)cin>>arr[i];
for(int i=2,cnt=0;i<=n;++i,cnt=0){
memset(dp[i]+i,0x3f,sizeof(int)*(n-i+1));
for(int j=i-1;j>=1;--j)
if(j+arr[j]>=i)
dp[i][j+arr[j]]=min(dp[i][j+arr[j]],dp[j][i-1]+cnt++);
for(int j=i+1;j<=n;++j)
dp[i][j]=min(dp[i][j],dp[i][j-1]);
}
cout<<dp[n][n]<<"\n";
}
return 0;
}
|