2019HPU-ICPC-Training-1部分题解

发挥还行,被$J$题吊着打。学弟们果然还是很强的。

A.Connecting Vertices

B.Local Exterma

题目大意:找一个数组中有几个数满足:$a_{i-1}\leq a_i \geq a_{i+1}$或$a_{i-1} \geq a_i \leq a_{i+1}$ $(2\leq i \leq n-1)$.

签到题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
int a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int res=0;
for(int i=2;i<n;i++){
if(a[i]<a[i-1] && a[i]<a[i+1]) res++;
if(a[i]>a[i-1] && a[i]>a[i+1]) res++;
}
printf("%d\n",res);
return 0;
}

C.Xor-MST

D.Buggy Robot

题目大意:一个机器人从点(0,0)出发,从$n$个向上下左右的操作中最多能挑出几个操作使得机器人移动完之后能够到达原点。

向左步数=向右步数,向上步数=向下步数,分别取最小值相加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
char s[maxn];
int a[10];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s);
for(int i=0;i<n;i++){
if(s[i]=='L') a[1]++;
if(s[i]=='R') a[2]++;
if(s[i]=='U') a[3]++;
if(s[i]=='D') a[4]++;
}
printf("%d\n",2*min(a[1],a[2])+2*min(a[3],a[4]));
return 0;
}

E.K-Dominant Character

给你一个长度为$n$字符串,求最小的长度$m$,使得字符串中所有长度为$m$的子字符串中均包含某一种字符。

二分模拟计算即可。

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<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
char s[maxn];
int a[100],n;
int vis[100];
map<char,int>mp;
bool check(int x){
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
for(int i=0;i<x;i++){
a[s[i]-'a']++;
}
for(int i=0;i<26;i++) if(!a[i]) vis[i]=1;
for(int i=x;i<n;i++){
a[s[i]-'a']++;
a[s[i-x]-'a']--;
for(int j=0;j<26;j++) if(!a[j]) vis[j]=1;
}
for(int i=0;i<26;i++){
if(mp[i]){
if(!vis[i]) return true;
}
}
return false;
}
int main()
{
scanf("%s",s);
n=strlen(s);
int l=1,r=n;
for(int i=0;i<n;i++){
mp[s[i]-'a']++;
}
while(l<=r){
int m=(l+r)/2;
if(check(m)) r=m-1;
else l=m+1;
}
printf("%d\n",r+1);
return 0;
}

F.Maximum Subsequence

题目大意:给你一个大小为$n$的数组和一个数m,求从数组中挑出任意多个数(可以为零,不可以重复),计算出
$$
(\sum_{i=1}^{k}a_{b_i})\space mod \space m
$$
的最大值,其中$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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
ll a[maxn];
ll q[maxn],p[maxn];
int main()
{
ll n,m;
scanf("%lld %lld",&n,&m);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
a[i]%=m;
}
ll x=n/2;
ll N=1<<x;
for(int i=0;i<N;i++){
ll sum=0;
for(int j=0;j<x;j++){
if((i>>j)&1) sum=(sum+a[j])%m;
}
p[i]=sum;
}
N=1<<(n-x);
for(int i=0;i<N;i++){
ll sum=0;
for(int j=0;j<n-x;j++){
if((i>>j)&1) sum=(sum+a[j+x])%m;
}
q[i]=sum;
}
sort(q,q+N);
ll res=0;
for(int i=0;i<1<<x;i++){
ll pos=lower_bound(q,q+N,m-1-p[i])-q;
res=max(res,(p[i]+q[pos])%m);
if(pos) res=max(res,(p[i]+q[pos-1])%m);
}
printf("%lld\n",res);
return 0;
}

G.Alomost Identity Permutations

题目大意:问$n$个数的全排列中,有多少排列满足$\sum p_i=i$的值大于等于$n-k$。

$k\leq$4,枚举即可。

对于$k=1$ , $res=1$;
对于$k=2$ , $res=C_{n}^{2}$
对于$k=3$ , $res=C_{n}^{3}*2$
对于$k=4$ , $res=C_{n}^{4}*9$
上面每一行的意义在于:从$n$个数中挑出$k$个数,每种选法又分别多少种方案使得$\sum_{i=1}^{k} p_i=1$ 的值为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;

int main()
{
ll n,k;
scanf("%lld %lld",&n,&k);
ll cur=n;
ll res=1;
ll fac=1;
for(ll i=2;i<=k;i++){
fac=fac*i;
cur=cur*(n-i+1)/i;
if(i==2) res+=cur;
if(i==3) res+=cur*2;
if(i==4) res+=cur*9;
}
printf("%lld\n",res);
return 0;
}

H.Alyona and Spreadsheet

题目大意:从$n*m$的矩阵中挑出从第$l$行到第$r$行,问在这$(r-l+1)*m$的矩阵中是否存在某一列,使得这一列的元素按序号从小到大非递减。

前缀和即可。计算每一行某个元素前面的所有的元素能够非递增的最小的起点,由于$n,m$的值未定,所以必须用一维数组来保存。

在查找$[l,r]$行时,只需要看第$r$行的m个元素是否存在某个元素,他所在的非递减序列的起点小于等于$l$即可,由于不能用$for$循环查询,所以需要前缀和。

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;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
ll a[maxn];
ll b[maxn];
ll res[maxn];
ll dp[maxn];
int main()
{
ll n,m,q,l,r;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n*m;i++){
scanf("%lld",&a[i]);
}
res[0]=1;
for(int j=1;j<=m;j++){
ll pos=1;
res[j]=1;
for(int i=2;i<=n;i++){
if(a[m*(i-1)+j]>=a[(i-2)*m+j]) res[(i-1)*m+j]=pos;//非递减
else{//递减的话就是一个新的起点
res[m*(i-1)+j]=i;
pos=i;
}
if(j>1) res[m*(i-1)+j]=min(res[m*(i-1)+j],res[m*(i-1)+j-1]);\\计算前缀最小值
}
}
scanf("%lld",&q);
while(q--){
scanf("%lld %lld",&l,&r);
if(res[r*m]<=l) printf("Yes\n");
else printf("No\n");
}
return 0;
}

I.Shell Game

题目大意:三个杯子,初始某个杯子中有一个小球,经过$n$次下列操作后,小球在第$x$号杯子(0,1,2号):

  1. 此次操作次数的序号为第奇数次,交换0号和1号杯子。
  2. 此次操作次数的序号为第偶数次,交换1号和2号杯子。

问初始小球在那个杯子。

模拟后发现,每6次操作一个循环,因此$n \space mod \space 6$后模拟计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
int a[maxn];
int res[maxn];
int dp[maxn];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
n%=6;
int a[10];
a[0]=0;a[1]=1;a[2]=2;
for(int i=1;i<=n;i++){
if(i&1) swap(a[0],a[1]);
else swap(a[1],a[2]);
}
printf("%d\n",a[m]);
return 0;
}

J.Hanoi Factory

题目大意:给你$n$个圆环,每个圆环有一个外径和内径,现在将这些圆环堆起来,满足上面的圆环外径$b_i \leq b_j 且b_i >a_j$ 其中$a_j,b_j$分别为下面一个圆环的内径和外径。问最高能将这些圆环堆多高。

一个简单的模拟题。。。(我居然写了一下午的区间更新查询线段树)

按照圆环外径从大到小排序,如果外径相同按照内径从大到小排序,然后按照顺序模拟即可,如果当前这个圆环放不到前面这个圆环,就继续往前面找,直到找到为止(这里可以用一个数组保存每个圆环找到的位置。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=2000000+10;
const int INF=0x3f3f3f3f;
struct node{
ll l,r,h;
bool friend operator<(node i,node j){
if(i.r==j.r) return i.l>j.l;
return i.r>j.r;
}
}a[maxn];
ll res[maxn];
ll pre[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld %lld",&a[i].l,&a[i].r,&a[i].h);
}
sort(a+1,a+n+1);
res[1]=a[1].h;
int cur=1;
for(int i=2;i<=n;i++){
while(!(a[cur].l<a[i].r && a[i].r<=a[cur].r) && cur) cur=pre[cur];
res[i]=res[cur]+a[i].h;
pre[i]=cur;
cur=i;
}
ll ans=0;
for(int i=1;i<=n;i++) ans=max(ans,res[i]);
printf("%lld\n",ans);
return 0;
}

K.Cloud of Hashtags

题目大意:有$n$个新闻标题,你要删除最少的字符,使得最后所有的标题按照输入顺序字典序升序排列。并输出删除后的新闻标题。

首先知道如果两个标题的字典序比较为降序,那么一定是要删除前面的那个标题,使得那个标题字典序变小。所以我们从后往前删除,能够保证每个标题删除的字符数量最少。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
string a[maxn];
int len[maxn];
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
len[i]=a[i].length();
}
for(int i=n-1;i>0;i--){
bool flag=0;
for(int j=1;j<=min(len[i],len[i+1]);j++){
if(a[i][j]<a[i+1][j]) break;
if(a[i][j]>a[i+1][j]){
a[i][j]='\0';
break;
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;a[i][j]!='\0';j++){
cout << a[i][j];
}
cout << endl;
}
return 0;
}

L.Game of Credit Cards

题目大意:$S$某,$M$某分别有一张序号长度为$n$的信用卡,他们定了一个规则:比赛分为$n$局,每局$S$某,$M$某从$n$个数字中分别不重复的取出一个数字,谁的数字小谁得一分,平局不算分。
问如果随机排列这些数字,$S$某可能的最高得分和M某可能的最低得分分别为多少。

模拟题,算最高分时只要从小到大让$S$某牌去压$M$某小于自己当前牌大小的牌即可。算最低分时,只要从大到小让$M$某去压$S$某大于等于自己当前牌大小的牌即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
char s[maxn],t[maxn];
int a[100],b[100];
int main()
{
int n;
scanf("%d",&n);
scanf("%s %s",s,t);
for(int i=0;i<n;i++){
a[s[i]-'0']++;
b[t[i]-'0']++;
}
int res1=0,res2=0;
int sum=0;
for(int i=0;i<10;i++){
sum+=a[i];
res1+=min(b[i],sum);
sum-=min(b[i],sum);
}
sum=0;
for(int i=9;i>=0;i--){
res2+=min(a[i],sum);
sum-=min(a[i],sum);
sum+=b[i];
}
printf("%d\n%d\n",n-res1,res2);
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------