杭师训练赛4总结

手速场

杭师训练赛第四场

A - Mental Rotation

  • 题意:给出n*n的字符矩阵和旋转序列,L表示逆时针旋转,R表示顺时针旋转,求完成整个旋转序列后的矩阵。
  • 思路:
    • 统计逆时针旋转的次数num, 因为旋转4次相当于没有旋转,所以旋转(num%4+4)%4次即可。
    • 逆时针旋转90度:a[i][j] = b[j][n-i+1] ,i,j均从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

string op;
int n;
char s[N][N],a[N][N];
void charge(){
rep(i,1,n){
rep(j,1,n){
int k=n-i+1;
a[i][j] = s[j][k];
if(a[i][j]=='v') a[i][j]='>';
else if(a[i][j]=='>') a[i][j]='^';
else if(a[i][j]=='^') a[i][j]='<';
else if(a[i][j]=='<') a[i][j]='v';
}

}
memcpy(s,a,sizeof(s));
}
int main(){
cin>>n>>op;
rep(i,1,n)
scanf("%s",s[i]+1);
int num=0;
for(int i=0;i<op.size();i++){
if(op[i]=='L') num++;
else num--;
}
((num%=4) +=4) %= 4;
rep(i,1,num) charge();
rep(i,1,n)
printf("%s\n",s[i]+1);
return 0;
}

B - SpongeBob SquarePants

  • 题意:给定长宽判定是否为正方形
1
2
3
4
5
6
7
8
9
10
int main(){
int t,a,b;
rd(t);
while(t--){
rd(a),rd(b);
if(a==b) puts("YES");
else puts("NO");
}
return 0;
}

C - I Don’t Want To Pay For The Late Jar!

  • 题意:给定d组数据,每组一个n和s,后面n行输入fi和ti,若s>=ti,第i项权值为fi,否则第i项权值为fi-(ti-s),求最大权值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int d,n;
ll s,t,f;
int main(){
rd(d);
rep(_,1,d){
scanf("%d%lld",&n,&s);
ll ans = -inf;
rep(i,1,n){
scanf("%lld %lld",&f,&t);
if(t<=s) ans = max(ans,f);
else ans = max(ans,f-t+s);
}
printf("Case #%d: %lld\n",_,ans);
}

return 0;
}

E - Optimal Slots

  • 题意:有n个节目需要安排,每个节目占用一定单位的时间,各个节目的时间不能重合,你有T单位的时间可以使用,问最多可以安排多少时间,并且输出字典序最小的具体方案。
  • 思路: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
int m,n,a[200];
int f[200][200];
int main(){
while(~scanf("%d",&m)&&m){
clr(f,0);
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
repd(i,n,1){
rep(j,0,m){
f[i][j] = f[i+1][j];
if(j>=a[i])f[i][j] = max(f[i][j],f[i+1][j-a[i]]+a[i]);
}
}
int j=m;
rep(i,1,n){
if(j>=a[i] && i==n){
printf("%d ",a[n]);
break;
}
if(j<=0) break;
if(j-a[i]>=0 && f[i][j]==f[i+1][j-a[i]]+a[i]){
printf("%d ",a[i]);
j-=a[i];
}
}
printf("%d\n",f[1][m]);
}
return 0;
}

F - Military Class

  • 题意:有2n个士兵排成两行,每行都从1到n进行标记。现在要将这些士兵两两配对。给出k对关系(i,j),第一行的i和第二行的j不能配对,问有多少种方案可以完成n组配对。(n<2000,e<5,k<2000)
  • 思路
    • e<5是一个关键信息,一般这种情况极大的可能是状压dp。不会状压dp的话可以先看一下这道模板题
    • f[i][j]表示在处理到第2行第i个士兵时,第1行中与之距离<=e的士兵的匹配情况,采用状态压缩,1表示已匹配,0表示未匹配,j的范围为[0,2^(2*e+1)-1]
    • f[i][j] = ∑(f[i-1][ (j^(1<<k)) >>1]) + ∑(f[i][j] += f[i-1][( (j^(1<<k)) >>1) | (1<<2*e)]),其中j的第k位为1。
    • 初态:f[1][j]=1,其中j的二进制位只有1个1。
    • 终态:f[n][num],num为j的最高e+1位全1的状态。
    • 上式含义为对于第i个阶段的状态j,枚举j的第k位为1的情况A,A的答案由上一个阶段在相应位置没有1情况B转移得到,所以要先将j的第k为先置0。由于j只能包含当前状态的2*e+1个位置,所以上一个阶段的状态需要由j右移一位得到(可以将j描述状态的方式看作一个窗口,i到i-1相当于窗口左移,也就相当于窗口内的值右移),而最高位有0和1( |(1<<2*e) )两种情况,都要分别记入答案。
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
ll f[N][N];
int mp[N][N];
int main(){
int n,e,p;
scanf("%d%d%d",&n,&e,&p);
rep(i,1,p){
int x,y;
scanf("%d%d",&x,&y);
mp[x][y] = 1;
}
int sta = 1<<(2*e+1);
for(int j=max(e+1-n,0);j<=e;j++)
if(!mp[1+e-j][1]) f[1][1<<j]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<sta;j++){
for(int k=0;k<=2*e;k++){
if(i+e-k>n) continue;
if(i+e-k<=0) break;
if((j&(1<<k))){
if(mp[i+e-k][i]) continue;
(f[i][j] += f[i-1][(j^(1<<k))>>1])%=mod; //最高位为0
(f[i][j] += f[i-1][((j^(1<<k))>>1)|(1<<2*e)])%=mod; //最高位为1
}
}
}
}
ll ans=0, num = sta-1;
rep(i,0,e-1) num-=(1<<i);
printf("%lld\n",f[n][num]);
return 0;
}

H - Are You Safe?

  • 题意:给出n个点,求凸包,再给p个点,问这些点是否在凸包内。
  • 思路
    • 求凸包
    • 判定点是否在凸包内:P-A得到向量x,P-B得到向量y,求x和y的叉积f。按照上述方法依次处理凸包上相邻两点,若第i次求出的叉积与第i-1次求出的叉积正负性不同,则说明点不在凸包内。
    • 两向量:a=(x1,y1), b=(x2,y2),他们的叉积为x1*y2 - y1*x2
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int dcmp(double x)  {
if(fabs(x)<eps)return 0;
else return x>0?1:-1;
}
int n;
struct Point{
double x,y;
inline Point(double x=0,double y=0):x(x),y(y){}
}p[N],ch[N],p1[N];

bool myCmp(Point A,Point B){
if(A.x!=B.x)return A.x<B.x;
else return A.y<B.y;
}
Point operator + (Point A,Point B){
return Point(A.x+B.x,A.y+B.y);
}
Point operator - (Point A,Point B){
return Point(A.x-B.x,A.y-B.y);
}
bool operator == (const Point& A,const Point& B){
return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;
}
inline double Cross(Point A,Point B) // 计算叉积
{
return A.x * B.y - A.y * B.x;
}
int ConvexHull(){
sort(p+1,p+n+1,myCmp);
int m=0;
for(int i=1;i<=n;i++){
while(m>1 && dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-1;i>=1;i--){
while(m>k && dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)m--;
ch[m++]=p[i];
}
return m;
}

double Dis(Point A,Point B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool check(Point A,int m){
Point a1 = A-ch[0], a2=A-ch[1];
double f = Cross(a1,a2);
for(int i=1;i<m-1;i++){
a1 = A-ch[i], a2 = A-ch[i+1];
double f1=Cross(a1,a2);
if(f1*f <= 0) return false;
f=f1;
}
return true;
}
int main(){
int t,q,m;
scanf("%d",&t);
rep(_,1,t){
scanf("%d%d",&n,&q);
rep(i,1,n)
scanf("%lf%lf",&p[i].x,&p[i].y);
rep(i,1,q)
scanf("%lf%lf",&p1[i].x,&p1[i].y);
m=ConvexHull();
printf("Case %d\n",_);
rep(i,0,m-1){
printf("%.0f %.0f\n",ch[i].x,ch[i].y);
}
rep(i,1,q){
printf("%.0f %.0f is ",p1[i].x,p1[i].y);
if(check(p1[i],m)) puts("unsafe!");
else puts("safe!");
}
puts("");
}
return 0;
}

I - To Crash Or Not To Crash

  • 题意:给一个字符矩阵,找到’=’右边第一个不是’.’的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char a[10][20];
int main(){
rep(i,1,3) scanf("%s",a[i]+1);
int x=0, y=0;
rep(i,1,3)
rep(j,1,10)
if(a[i][j] == '='){
x=i, y=j;
break;
}
rep(j,y+1,10){
if(a[x][j]!='.'){
printf("%c\n",a[x][j]);
return 0;
}
}
puts("You shall pass!!!");
return 0;
}

J - Kitchen Plates

  • 题意:给出5个字符的大小关系,将字符从小到大依次输出。
  • 思路:数据小,直接全排列,然后判断是否有满足条件的字符对即可;数据大的话建有向图求拓扑序。
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
int f[10][10];
int a[10];
bool cmp(int i,int j){
return f[i][j];
}
int main(){
string s;
rep(i,1,5){
a[i]=i;
cin>>s;
if(s[1]=='>') f[s[2]-'A'+1][s[0]-'A'+1]=1;
else f[s[0]-'A'+1][s[2]-'A'+1]=1;
}
do{
int flag=1;
rep(i,1,5)
rep(j,i+1,5)
if(f[a[j]][a[i]]) flag=0;
if(flag){
rep(i,1,5) printf("%c",a[i]-1+'A');
return 0;
}
}while(next_permutation(a+1,a+6));
puts("impossible");
return 0;
}

K - Help The Support Lady

  • 题意:机器人在同一时间接到了n个任务,第i个任务耗时x[i],只要在2*x[i]的时间内完成第i个任务,这个任务的发布者就会满意,请问最多可以使多少任务发布者满意。
  • 思路
    • 贪心,优先完成耗时小的任务,如果前面完成的任务总时间小于当前任务的时间,则当前任务可以满足要求,否则就把当前任务舍弃掉。
    • 因为当前任务对答案的贡献为1,如果前面的任务耗时已经比当前任务多,并且采取“为了当前任务(贡献+1)而舍弃前面的任务(贡献-x,x>=1)”的决策的话,对答案的贡献并不会增加,所以直接舍弃没有问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int t,n;
ll a[N],s[N];
int main(){
rd(t);
rep(_,1,t){
clr(s,0);
rd(n);
rep(i,1,n) rd(a[i]);
sort(a+1,a+1+n);

int ans=0;
rep(i,1,n){
s[i]=s[i-1]+a[i];
if(s[i-1]<=a[i]) ans++;
else s[i]=s[i-1];
}
printf("Case #%d: %d\n",_,ans);
}

return 0;
}

本场总结

  • 涉及知识点:矩阵转置,小模拟,背包问题输出具体方案,状压dp,凸包,叉积,拓扑排序,贪心。
  • ABCIJK签到,H凸包模板题,J状压dp。

个人总结

总体来说没什么大问题,签得飞起。

Donate comment here