cugb2-13 & zjnu2-15总结

两场均为区域赛难度,过的题都不多(tcl),所以写一起了

cugb 2-13

A - Trick or Treat

在二维平面上给出n个整数点(n<1e5),在x轴上找到一个点p,使得点p到这n个点的最大距离最小。

  • 思路:看到“最大值最小”这几个字就要考虑是否能用二分解决,简单思考后发现这道题并不满足单调性。但是通过观察可以发现,点p从x轴最左边(最小的xi)到最右边(最大的xi)的过程中,答案一定是先递减后递增,而我们要找的答案就是极小值点,可以用三分解决。
    • 简单提一下三分:在l到r上取三分点mid1,mid2,若f(mid1)<f(mid2),则极值点要么在两点之间,要么在mid1左边,一定不再mid2右边,所以使r=mid2;同理,若f(mid1)>f(mid2),则l=mid1。
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

int n;
double x[N],y[N];
double dis(int i,double mid){
return (x[i]-mid)*(x[i]-mid)+y[i]*y[i];
}
double get(double mid){
double ans=-1;
rep(i,1,n){
ans = max(ans,dis(i,mid));
}
return ans;
}
int main(){
while(~scanf("%d",&n) && n){

rep(i,1,n) {
scanf("%lf%lf",&x[i],&y[i]);
}
double l=-2000001.0, r=20000001.0;
while(l+eps<r){
double mid1=l+(r-l)/3, mid2=l+2*(r-l)/3;
double as1=get(mid1), as2=get(mid2);
if(as1<as2) r=mid2;
else l=mid1;
}
printf("%.9f %.9f\n",l,sqrt(get(l)));
}

return 0;
}


B - Working at the Restaurant

当读到 “DROP m” 从侍者手中接过盘子 m 个盘子放在 2 号堆。当读到 “TAKE m” ,就要从 1 号堆拿出 m 个盘子给洗碗机。题意要求拿出的盘子的顺序和进来的顺序一致。这就要用到 “MOVE 1->2 t” 操作,从 1 号堆转移 t 个盘子到 2 号堆。 注意每次取盘子都是从最顶端开始拿。每两个例子间空一行。

  • 模拟。每次 1 号堆为空都要把 2 号堆的所有盘子移到 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

int main()
{
int n;
while(1){
cin>>n;
int s1=0,s2=0;
if(!n) break;
string s;
for(int i=1,x;i<=n;i++){
cin>>s;
if(s[0]=='D'){
cin>>x;
printf("DROP 2 %d\n",x);
s2+=x;
}else{
cin>>x;
if(s1>=x) printf("TAKE 1 %d\n",x),s1-=x;
else{
if(s1){
printf("TAKE 1 %d\n",s1);x-=s1;s1=0;
}
printf("MOVE 2->1 %d\n",s2);s1=s2;s2=0;
printf("TAKE 1 %d\n",x);
s1-=x;
}
}
}
cout<<endl;
}
}

D - Darts

A 和 BBB 两个人比赛射飞镖,规则如下:

两个人轮流射飞镖,初始分数都为N,假设射中区域 x,如果 x≤N,分数减去 x;否则分数保持不变。第一个把分数清零的玩家获胜。

A 每次随便射飞镖,所以他射到每个区域的概率都相等。

B 有策略地射飞镖,他能够保证落到三块连续的区域内,且三块之间的概率相等。

假设初始值都为 N,问 A 先手获胜的概率和 B 先手获胜的概率。

1≤N≤501

标靶为环形,权值为:20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5。(包含1~20所有的数字)

  • 设f1[i][j]和f2[i][j]分别为A分数为i,B分数为j,A先手A获胜的概率和B先手B获胜的概率。
  • 如果i和j都小于20,那么他们就处于”A有1/20的概率直接获胜,B有1/3的概率直接获胜”的状态,那么对于他们来说就只有射中和每射中两种结果,因为如果A射中一个比i小的数,A的下一步依旧有1/20的概率直接获胜,对于B来说也是一样,也就是如果没有射中想要的分数的话,他们依旧处于上诉状态,而答案也不会产生变化。即如果i和j都小于20,f1[i][j] = 0.136363636364, f2[i][j] = 0.909090909091(不要问这俩数字哪来的,看看样例)。
  • 对于f1[i][j],f1[i][j] = ∑ (1-f2[i-x][j]) / 20.0。其中如果x大于i的话,应当用f2[i][j]参与计算。A先手等价于:在B先手前先走一步。因为f2表示的是B获胜的概率,所以要用(1-f2)进行计算。
  • 同理对于f2[i][j],f2[i][j] = max(1-f1[i][j-x] + 1-f1[i][j-y] + 1-f1[i][j-z]),同样当x>j时要用f1[i][j]进行计算,y,z也是一样。
  • 注意i-x<0时,f1[i][j]可能会通过f2[i][j]转移;j-x<0时,f2[i][j]可能会通过f1[i][j]进行转移。i,j同时小于20时答案固定直接跳过即可;i>20 j<20 时,i-x<0="" 不可能发生,此时先更新f1[i][j];i<20="" j="">20 时,j-x<0 不可能发生,先更新f2[i][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
37
38
39
40
41
42
43
44
45
46

double f1[N][N],f2[N][N];
int s[30] = {0,20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5,20,1};
int n;
int gt(int x,int y){
return x>=y? x-y: x;
}
void solve1(int i,int j){
rep(x,1,20){
int p = gt(i,x);
f1[i][j] += (1.0-f2[p][j]);
}
f1[i][j]/=20.0;
}
void solve2(int i,int j){
rep(k,1,20){
int x=gt(j,s[k]), y=gt(j,s[k+1]), z=gt(j,s[k+2]);
f2[i][j] = max(f2[i][j], (3.0-f1[i][x]-f1[i][y]-f1[i][z]));
}
f2[i][j] /= 3.0;
}
int main(){
rep(i,1,20)
rep(j,1,20){
f1[i][j] = 0.136363636364;
f2[i][j] = 0.909090909091;
}
rep(i,1,501){
rep(j,1,501){
if(i<=20 && j<=20) continue;
else if(j<=20){
solve1(i,j);
solve2(i,j);
}
else {
solve2(i,j);
solve1(i,j);
}
}
}
while(~scanf("%d",&n) && n){
printf("%.10f %.10f\n",f1[n][n],f2[n][n]);
}
return 0;
}


F - Haunted Graveyard

在二维地图上,有障碍物,传送门。人物每次可以往上下左右四个方向走,花费为1,走到传送门会传送到另一个位置花费为t(可能为负),障碍物上不能走,求从(1,1)走到(n,m)的最短耗时,不能走到和存在负环时要输出指定字符。

  • 因为存在传送门且花费不为1,不能直接bfs,每个格子与相邻格子建边,传送门之间建边,spfa跑最短路即可。
  • 坑点:到达传送门必须传送;若负环唯一且包含终点,则此负环不算,应该输出应有的答案,解决方法:使终点出度为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
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
80
81
82
83

struct edge{
int to,w,next;
}e[M];
int head[M],cant[M],v[M],d[M],used[M],tot=0;
int n,m;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
void add(int x,int y,int z){
e[tot] = (edge){y,z,head[x]};
head[x] = tot++;
}
inline int get(int x,int y){
return (x-1)*m+y;
}
inline void init(){
clr(head,-1);clr(v,0);
clr(d,inf);
clr(cant,0);clr(used,0);
tot=0;
}
inline bool check(int x,int y){
if(x<1||x>n||y<1||y>m) return false;
if(cant[get(x,y)]==1) return false;
return true;
}
bool spfa(){
queue<int>q;
while(!q.empty()) q.pop();
q.push(1);
d[1]=0,v[1]++,used[1]=1;
while(!q.empty()){
int x=q.front();q.pop();used[x]=0;
if(x==n*m) continue;
for(int i=head[x];~i;i=e[i].next){
int y=e[i].to;
double w=e[i].w;
if(d[x]+w<d[y]){
d[y]=d[x]+w;
if(!used[y]){
v[y]++;
if(v[y]>=n*m) return true;
used[y]=1,q.push(y);
}

}
}
}
return false;
}
int main(){
while(~scanf("%d%d",&n,&m) && (n+m)){
init();
int x,y,x1,y1,tem,t;
scanf("%d",&tem);
rep(i,1,tem){
scanf("%d%d",&x,&y);
cant[get(x+1,y+1)]=1;
}
scanf("%d",&tem);
rep(i,1,tem){
scanf("%d%d%d%d%d",&x,&y,&x1,&y1,&t);
add(get(x+1,y+1),get(x1+1,y1+1),t);
cant[get(x+1,y+1)]=2;
}
rep(i,1,n){
rep(j,1,m){
if(i==n && j==m) continue;
if(cant[get(i,j)]) continue;
rep(k,0,3){
int ti=i+dir[k][0], tj=j+dir[k][1];
if(check(ti,tj))
add(get(i,j),get(ti,tj),1);
}

}
}
if(spfa()) puts("Never");
else if(d[n*m]==inf) puts("Impossible");
else printf("%d\n",d[n*m]);
}
return 0;
}


I - Happy Telephones

给出一个区间集合A,每次询问给出一个区间b,问A中和b有交叉的区间有多少个

  • 签到题数据小,n*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

int n,m;
int a[N],b[N];
bool check(int x,int y,int i){
if(a[i]>=y || b[i]<=x) return false;
return true;
}
int main(){
while(~scanf("%d%d",&n,&m) && (n+m)){
int tem;
rep(i,1,n){
scanf("%d%d%d%d",&tem,&tem,&a[i],&b[i]);
b[i] += a[i];
}
while(m--){
int x,y,ans=0;
rd(x),rd(y);
rep(i,1,n){
if(check(x,y+x,i)) ans++;
}
printf("%d\n",ans);
}
}

return 0;
}

J - Stammering Aliens

给出一个字符串s和一个数字m,求在s中出现至少m次的最长子串的长度以及这个子串最后一次出现的位置。

  • 前置知识:后缀数组,二分
  • height[i]表示排名为i的后缀与排名为i-1的后缀的最长前缀长度。
  • 二分最大长度,将排好序的后缀进行分区,保证每个分区中相邻两个后缀的最长前缀都至少为mid(只有一个后缀的分区就不管了),检查是否有后缀数量至少m的分区存在,有的话l=mid,否则r=mid-1。
  • 找到最大长度后以其为标准再分区扫一次,对于数量至少为m的分区,找到max(sa[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
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

const int N = 100005;
char ch[N], all[N];
int sa[N], rk[N], height[N], tax[N], tp[N], a[N], n, m, num;
char str[N];
//rk[i] 第i个后缀的排名; sa[i] 排名为i的后缀位置; height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
//tax[i] 计数排序辅助数组; tp[i] rank的辅助数组(计数排序中的第二关键字),与SA意义一样。
//a为原串
void RSort() {
for (int i = 0; i <= m; i ++) tax[i] = 0;
for (int i = 1; i <= n; i ++) tax[rk[tp[i]]] ++;
for (int i = 1; i <= m; i ++) tax[i] += tax[i-1];
for (int i = n; i >= 1; i --) sa[tax[rk[tp[i]]] --] = tp[i];
}

int cmp(int *f, int x, int y, int w) { return f[x] == f[y] && f[x + w] == f[y + w]; }

void Suffix() {
for (int i = 1; i <= n; i ++) rk[i] = a[i], tp[i] = i;
m = 127 ,RSort();
for (int w = 1, p = 1, i; p < n; w += w, m = p) {
for (p = 0, i = n - w + 1; i <= n; i ++) tp[++ p] = i;
for (i = 1; i <= n; i ++) if (sa[i] > w) tp[++ p] = sa[i] - w;
RSort(), swap(rk, tp), rk[sa[1]] = p = 1;
for (i = 2; i <= n; i ++) rk[sa[i]] = cmp(tp, sa[i], sa[i - 1], w) ? p : ++ p;
}
int j, k = 0;
for(int i = 1; i <= n; height[rk[i ++]] = k)
for( k = k ? k - 1 : k, j = sa[rk[i] - 1]; a[i + k] == a[j + k]; ++ k);
}

void Init() {
clr(sa,0);clr(rk,0);clr(height,0);
clr(tax,0);clr(tp,0);clr(a,0);
scanf("%s", str);
n = strlen(str);
for (int i = 0; i < n; i ++) a[i + 1] = str[i];
}
bool check(int len){
int sum = 1;
for(int i=2;i<=n;i++){
if(height[i]>=len) sum++;
else sum=1;
if(sum>=num) return true;
}
return false;
}
int main() {
while(~scanf("%d",&num) && num){
Init();
Suffix();
if(num==1){
printf("%d 0\n",n);
continue;
}
int l=0, r=50000, flag=0;
while(l<r){
int mid = l+r+1>>1;
if(check(mid)) l = mid, flag=1;
else r = mid-1;
}
int res = 1, sum=1, mx=sa[1];
for(int i=2;i<=n;i++){
if(height[i]>=l) sum++, mx=max(mx,sa[i]);
else sum=1, mx=sa[i];
if(sum>=num) res = max(res,mx);
}
if(flag)printf("%d %d\n", l, res-1);
else puts("none");
}
return 0;
}

zjnu 2-15

A - fart frontwards

有一个时长为t秒的录像带,有x3和/3两个按钮,每一秒录像带会检测,如果x3按钮按下,则速度乘3;如果/3按钮按下,则速度除以3;若没有按钮按下则速度不变;初始速度为1。在第t秒的时候要能回到速度1(可以为3,因为此时/3可以马上变成1,然后开始看),问从0到t最少需要多少时间。

  • 要想时间最小,速度必然先增后减,且最后一刻的速度尽可能为3,那么使前面的速度为1,3,最后一刻速度为3,然后从两边尽量往中间逼近,每次乘3,最后会得到一个速度先一直乘3后一直除3的序列。假设这段序列花的时间距离指定时间还差p秒,则将p按3进制从大到小进行拆分,依次塞入之前的序列中,因为序列中相邻数字倍数为3,所以一定可以塞进去。
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
ll n;
int main(){
scanf("%lld",&n);
if(n==0){
puts("0");
return 0;
}
ll x=1,ans=1,y=0,p=3;
while(x+y+2*p<=n){
x+=p,y+=p;
p*=3;
ans+=2;
}
ll t=n-x-y;
while(p && t>=3){
if(t>=p){
ans+=t/p;
t%=p;
}
else p/=3;
}
if(t>0) ans+=t;
printf("%lld\n",ans);
return 0;
}


B - estimating the Flood kirs

通过移动格子的高度将二维平面扩展到三维,每个格子与相邻格子的高度差最多为1。给定平面的长宽一些格子拉伸后的坐标,问是否有满足条件的扩展方案存在,如果有,则找到平均高度最低的方案,输出所有格子高度总和。

  • 要满足海拔最低一定是要在满足条件的情况下尽可能往下凹。用优先队列维护格子的高度,每次取出最高的格子往四周扩散,如果四周没有被题目锁定,则令他们高度-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

int hi[100][100],n,m,t;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
struct node{
int x,y,h;
bool operator < (const node &e)const {
return h<e.h;
}
};
bool bfs(){
int a,b,c;
rep(i,1,n) rep(j,1,m) hi[i][j]=inf;
priority_queue<node> q;
while(t--){
scanf("%d%d%d",&a,&b,&c);
hi[a][b] = c;
q.push((node){a,b,c});
}
while(!q.empty()){
node now = q.top();q.pop();
rep(i,0,3){
int tx=now.x+dir[i][0],ty=now.y+dir[i][1];
if(tx<1 || ty<1 || tx>n || ty>m ) continue;
if(hi[tx][ty]!=inf && abs(hi[tx][ty]-now.h)>1) return false;
if(hi[tx][ty]==inf){
hi[tx][ty] = now.h-1;
q.push((node){tx,ty,now.h-1});
}
}
}
return true;
}

int main(){
scanf("%d%d%d",&n,&m,&t);
if(!bfs()) puts("No");
else {
int ans=0;
rep(i,1,n)
rep(j,1,m)
ans+=hi[i][j];
printf("%d\n",ans);
}

return 0;
}
Donate comment here