首页 > 代码库 > “玲珑杯”ACM比赛 Round #18
“玲珑杯”ACM比赛 Round #18
“玲珑杯”ACM比赛 Round #18
Start Time:2017-07-15 12:00:00 End Time:2017-07-15 15:46:00
A -- 计算几何你瞎暴力
Time Limit:5s Memory Limit:256MByte
Submissions:1764Solved:348
DESCRIPTION
今天HHHH考完了期末考试,他在教学楼里闲逛,他看着教学楼里一间间的教室,于是开始思考:
如果从一个坐标为 (x1,y1,z1)(x1,y1,z1)的教室走到(x2,y2,z2)(x2,y2,z2)的距离为 |x1?x2|+|y1?y2|+|z1?z2||x1?x2|+|y1?y2|+|z1?z2|
那么有多少对教室之间的距离是不超过RR的呢?
INPUT
第一行是一个整数T(1≤T≤10)T(1≤T≤10), 表示有TT组数据 接下来是TT组数据,对于每组数据: 第一行是两个整数n,q(1≤n≤5×104,1≤q≤103)n,q(1≤n≤5×104,1≤q≤103), 表示有nn间教室, qq次询问. 接下来是nn行, 每行3个整数xi,yi,zi(0≤xi,yi,zi≤10)xi,yi,zi(0≤xi,yi,zi≤10),表示这间教室的坐标. 最后是qq行,每行一个整数R(0≤R≤109)R(0≤R≤109),意思见描述.
OUTPUT
对于每个询问RR输出一行一个整数,表示有多少对教室满足题目所述的距离关系.
SAMPLE INPUT
1 3 3 0 0 0 1 1 1 1 1 1 1 2 3
SAMPLE OUTPUT
1 1 3
HINT
对于样例,1号教室和2号教室之间的距离为3, 1号和3号之间的距离为3, 2号和3号之间的距离为0
SOLUTION
这道题就是要暴力,不过一般的暴力是要出问题的,因为数组你要开的特别大。所以我想FFT去做,可是不存在的啊,怎么做的出来
xi,yi,zi(0≤xi,yi,zi≤10)xi,yi,zi(0≤xi,yi,zi≤10),这个是真的骚,所以就是10^6了,具体实现如下
#include <bits/stdc++.h> using namespace std; typedef long long LL; int M[11][11][11]; LL N[32]; int main(){ int t; cin>>t; while(t--){ memset(M,0,sizeof(M)); memset(N,0,sizeof(N)); int n,q; cin>>n>>q; for(int i=0;i<n;i++){ int x,y,z; cin>>x>>y>>z; M[x][y][z]++; } for(int i=0;i<11;i++) for(int j=0;j<11;j++) for(int k=0;k<11;k++) for(int l=0;l<11;l++) for(int m=0;m<11;m++) for(int n=0;n<11;n++){ if(i==j&&k==l&&m==n) N[0]+=M[i][k][m]*1LL*(M[i][k][m]-1); else N[abs(j-i)+abs(l-k)+abs(n-m)]+=M[i][k][m]*1LL*M[j][l][n]; } LL f=0; for(int i=0;i<31;i++){ N[i]+=f; f=N[i]; } while(q--){ int p; cin>>p; if(p>30) cout<<n*1LL*(n-1)/2<<endl; else cout<<N[p]/2<<endl; } } return 0; }
C -- 图论你先敲完模板
Time Limit:5s Memory Limit:256MByte
Submissions:786Solved:201
DESCRIPTION
今天HHHH在操场上跑步,HHHH作为一个爱运动的人,肯定会想方设法把跑步所消耗的能量减到最少.
现在这个操场上有nn个可以休息的点,他们的坐标分别为x1,x2...xn(xi≤xi+1)x1,x2...xn(xi≤xi+1),HHHH刚开始在 x1x1 ,并且他只能在这些点休息,在中途不能停下来,否则会因为旁边的音浪太强而被晃到.
如果HHHH连续跑一段长度为ll的距离,那么他将会消耗2l+a2l+a的能量(aa为HHHH的可爱值)
现在给你这些点的坐标,请帮HHHH计算他跑到xnxn点所需要消耗的能量最少是多少.
INPUT
第一行是一个整数T(1≤T≤10)T(1≤T≤10),表示有TT组数据 对于每组数据输入一行2个整数n,a (1≤n≤105,1≤a≤106)n,a (1≤n≤105,1≤a≤106) 表示总共有nn个休息点,HHHH的可爱值为aa. 接着一行nn个数x1,x2...,xn(0≤xi≤3×106,0≤xi+1?xi≤30)x1,x2...,xn(0≤xi≤3×106,0≤xi+1?xi≤30),表示点的位置.
OUTPUT
每组数据输出一行,一个整数,表示最小需要花费的体力
SAMPLE INPUT
2 3 2 3 5 7 3 10 3 5 7
SAMPLE OUTPUT
12 26
HINT
对于第一组样例,最少的体力消耗是先从3跑到5,消耗6点体力,再从5跑到7,消耗6点体力,共12点 对于第二组样例,最少的体力消耗是直接从3跑到7,消耗26点体力.
SOLUTION
图论个皮皮虾啊,分明就是dp,d[i]=min(d[j]+2xi?xj+a),而且t=2xi?xj增长相当快,而答案显然不超过1e5?2^30,
“玲珑杯”ACM比赛 Round #18
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。