2019HDU多校第九场

86 阅读 0 评论 57 点赞

我是靠谱客的博主兴奋手链，最近开发中收集的这篇文章主要介绍2019HDU多校第九场，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

（记惊险刺激的一场！

1002 Rikka with Cake

传送：http://acm.hdu.edu.cn/showproblem.php?pid=6681

题意：有一个大小为$n*m$的方形，给定$k$条射线，每条射线以源点和方向的形式给出。问这个方形区域被分割成几个部分。

数据范围：$1<=n,m<=10^9,1<=k<=10^5$。

日记：（开场背后崔老师1A，然后好多人都过了。我：？？？？？为什么大家都会。

过了3h，学妹：这个题是划分成几个区域balabala。？？？？？我读了三个小时假题？？？

分析：随手画几个，可以发现这些射线每多一个交点，那么可以和一个“顶点”构成一个新的区域。那么问题就变成这些射线间有多少个交点。

根据题意是不存在任意两个射线重叠。那么交点一定是由横线和竖线相交得到。

我们考虑去维护横线，然后用竖线查询。

对于横线我们可以用这样三个数来表示：$x1,x2$：代表横线的范围；$hh$代表横线的高度。

同理竖线也用三个数来表示：$h1,h2$：代表竖线的范围；$xx$代表竖线的位置。

然后问题就变成了：对于一个在$xx$位置的竖线，在范围$[h1,h2]$内有多少个横线在$xx$范围覆盖过。

对于两维的数据，很容易想到用二维线段树维护？（但写起来好像太麻烦了qaq。我们考虑主席树怎么维护。

主席树就是若干棵线段树记录前缀得到的。

那么可以考虑对于高度为$h$的树插入范围为$[x1,x2]$的一条线段。然后查询$[h1,h2]$范围的树，有多少个$xx$被覆盖。

然后就是需要离散化处理一些细节问题。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define m(a,b) memset(a,b,sizeof a)
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=2e5+10;
 8 int reflx[N],refly[N];
 9 struct node{int xx,h1,h2;}Y[N];
10 struct node2{int hh,x1,x2;}X[N];
11 int cmp(node2 x,node2 y){return x.hh<y.hh;}
12 struct tree{int l,r;ll val;}t[N*100];
13 int root[N],sz;
14 void update(int &x,int y,int cl,int cr,int l,int r){
15     t[x=(++sz)]=t[y];
16     if(cl<=l&&r<=cr){
17         t[x].val=t[y].val+1;
18         return;
19     }
20     int mid=(l+r)>>1;
21     if(cl<=mid) update(t[x].l,t[y].l,cl,cr,l,mid);
22     if(cr>mid) update(t[x].r,t[y].r,cl,cr,mid+1,r);
23 }
24 ll tmp;
25 void query(int x,int y,int dex,int l,int r){
26     tmp+=t[y].val-t[x].val;
27     if(l==r) return;
28     int mid=(l+r)>>1;
29     if(dex<=mid) return query(t[x].l,t[y].l,dex,l,mid);
30     else return query(t[x].r,t[y].r,dex,mid+1,r);
31 }
32 int main()
33 {
34     int T;scanf("%d",&T);
35     while(T--)
36     {
37         sz=0;
38         int n,m,k,num1=0,num2=0,tot1=0,tot2=0;scanf("%d%d%d",&n,&m,&k);
39         reflx[++tot1]=n;reflx[++tot1]=1; refly[++tot2]=m;
40         for(int i=1;i<=k;++i)
41         {
42             int x,y;char s[3];scanf("%d%d%s",&x,&y,&s);
43             reflx[++tot1]=x;
44             if(s[0]=='U') Y[++num1]=(node){x,y,m};
45             if(s[0]=='D') Y[++num1]=(node){x,1,y};
46             if(s[0]=='L') X[++num2]=(node2){y,1,x},refly[++tot2]=y;
47             if(s[0]=='R') X[++num2]=(node2){y,x,n},refly[++tot2]=y;
48         }
49         sort(reflx+1,reflx+tot1+1);sort(refly+1,refly+tot2+1);
50         tot1=unique(reflx+1,reflx+tot1+1)-(reflx+1),tot2=unique(refly+1,refly+tot2+1)-(refly+1);
51         sort(X+1,X+num2+1,cmp);
52         for(int i=1;i<=num2;++i)
53         {
54             int l=lower_bound(reflx+1,reflx+tot1+1,X[i].x1)-reflx,r=lower_bound(reflx+1,reflx+tot1+1,X[i].x2)-reflx;
55             int h=lower_bound(refly+1,refly+tot2+1,X[i].hh)-refly;
56             update(root[h],root[h-1],l,r,1,tot1);
57         }
58         ll ans=1;
59         for(int i=1;i<=num1;++i)
60         {
61             int l,r;
62             if (Y[i].h1==1){
63                 l=1,r=lower_bound(refly+1,refly+tot2+1,Y[i].h2)-refly;
64                 if(refly[r]>Y[i].h2) --r;
65             }
66             if (Y[i].h2==m) l=lower_bound(refly+1,refly+tot2+1,Y[i].h1)-refly,r=tot2-1;
67             int xx=lower_bound(reflx+1,reflx+tot1+1,Y[i].xx)-reflx;
68             query(root[l-1],root[r],xx,1,tot1);
69             ans+=tmp,tmp=0;
70         }
71         printf("%lldn",ans);
72     }
73 }

1002

1005 Rikka with Game

传送：http://acm.hdu.edu.cn/showproblem.php?pid=6684

题意：有一个字符串$s$，先手和后手轮流操作：1）将一个字符变为其后一个；2）终止游戏。先手希望字符串字典序尽可能小，后手希望尽可能大。问最终结果的字符串为什么。

数据范围：$1<=|S|<=100$。

分析：能够不变的字符为$y$，再考虑其后面的$z$即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=110;
 5 char s[maxn];
 6 void rua()
 7 {
 8     scanf("%s",s);int st=strlen(s);
 9     int pos=-1;
10     for (int i=0;i<st;i++) if(s[i]=='y') pos=i;else break;
11     if(s[pos+1]=='z' && pos+1!=st) s[pos+1]='b';
12     printf("%sn",s);
13     return;
14 }
15 int main()
16 {
17     int t;scanf("%d",&t);
18     while (t--) rua();
19     return 0;
20 }

1005

1006 Rikka with Coin

传送：http://acm.hdu.edu.cn/showproblem.php?pid=6685

题意：有4种硬币：10，20，50，100。现在有$n$个物品，每个物品的价值为$w_i$，不找零。要求恰好所带的零钱购买任意一种物品都可以。问所携带的最少的硬币数为多少。

数据范围：$1<=n<=100,1<=w_i<=10^9$。

分析：贪心考虑。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll INF=1e18;
 5 const int maxn=110;
 6 int a[maxn];
 7 bool check(int i,int j,int k,int sum)
 8 {
 9     sum%=100;
10     int kk=sum/50;kk=min(kk,k);sum-=kk*50;
11     int jj=sum/20;jj=min(jj,j);sum-=jj*20;
12     int ii=sum/10;ii=min(ii,i);sum-=ii*10;
13     if(sum) return false;
14     return true;
15 }
16 void rua()
17 {
18     int n;scanf("%d",&n);
19     int mx=0,tag=1;
20     ll s1=10,ss=INF,s2=0;
21     for (int i=1;i<=n;i++) 
22     {
23         scanf("%d",&a[i]);mx=max(mx,a[i]);
24         if(a[i]%10!=0) s1=-1;
25         int res=a[i]%100;
26         if(a[i]==10 || res==30 || res==80) tag=0;
27         else
28         {
29             if(res==10) s2=max(s2,1ll*a[i]/100-1ll);
30             else s2=max(s2,1ll*a[i]/100);
31         }
32     }
33     if(s1==-1) {printf("-1n");return;}
34     int flag=0,f=0;
35     if(mx%100==0) f=1;
36     for(int i=0;i<=3;i++)for(int j=0;j<=3;j++)for(int k=0;k<=1;k++)
37     {
38         bool ff=true;
39         for (int id=1;id<=n;id++) if(!check(i,j,k,a[id])) {ff=false;break;}
40         if(ff) 
41         {
42             s1=min(s1,1ll*(i+j+k));
43             if(f && s1==4) ss=min(ss,1ll*mx/100+3ll);
44             else ss=min(ss,1ll*(i+j+k)+1ll*mx/100);
45             if(s1!=10) flag=1;
46         }
47     }
48     if(tag) ss=min(ss,s2+4);
49     if(!flag) {printf("-1n");return;}
50     printf("%lldn",ss);
51     return;
52 }
53 int main()
54 {
55     int t;scanf("%d",&t);
56     while (t--) rua();
57     return 0;
58 }