“玲珑杯”ACM比赛 Round #18
题意：如果从一个坐标为 (x1,y1,z1)的教室走到(x2,y2,z2)的距离为 |x1−x2|+|y1−y2|+|z1−z2|。那么有多少对教室之间的距离是不超过R的呢？
tags：坐标范围很小，瞎暴力
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<bitset> #include<vector> #include<set> #include<list> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 205; int n, q, T, r; ll mp[15][15][15], ans[N], ans1[N]; bool vis[15][15][15]; int Dis(int x1, int y1, int z1, int x2, int y2, int z2) { return abs(x1-x2)+abs(y1-y2)+abs(z1-z2); } int main() { scanf("%d", &T); while(T--) { mes(mp, 0); mes(vis, false); mes(ans, 0); mes(ans1, 0); scanf("%d %d", &n, &q); int x, y, z; rep(i,1,n) { scanf("%d %d %d", &x, &y, &z); ++mp[x][y][z]; } rep(cx,0,10) rep(cy,0,10) rep(cz,0,10) { vis[cx][cy][cz]=1; if(mp[cx][cy][cz]) { rep(tx,0,10) rep(ty,0,10) rep(tz,0,10) if(mp[tx][ty][tz] && vis[tx][ty][tz]==0) { int d= abs(cx-tx)+abs(cy-ty)+abs(cz-tz); ans[d]+= (mp[cx][cy][cz]*mp[tx][ty][tz]); } ans[0]+= (mp[cx][cy][cz]*(mp[cx][cy][cz]-1)/2); } } rep(i,0,N-1) ans1[i]= ans1[i-1]+ans[i]; rep(i,1,q) { scanf("%d", &r); if(r>=N) printf("%lld ", ans1[N-1]); else printf("%lld ", ans1[r]); } } return 0; }
题意：现在这个操场上有n个可以休息的点,他们的坐标分别为x1,x2...xn(xi≤xi+1),HH刚开始在 x1，并且他只能在这些点休息,在中途不能停下来,否则会因为旁边的音浪太强而被晃到。如果HH连续跑一段长度为l的距离,那么他将会消耗2^l+a的能量(a为HH的可爱值)。现在给你这些点的坐标,请帮HH计算他跑到xn点所需要消耗的能量最少是多少。
tags：2^len这个数在这个题不会超过long long 范围，故到 xi点时，最多往前面跑 60米，可以直接暴力 dp。
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<bitset> #include<vector> #include<set> #include<list> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 100005; int T, n, a, k, x[N]; ll dp[N]; int main() { scanf("%d", &T); while(T--) { scanf("%d %d", &n, &a); rep(i,1,n) scanf("%d", &x[i]); k=unique(x+1, x+1+n)-(x+1); mes(dp, 63); dp[1]=0; rep(i,2,k) { int x1=x[i]; per(j,i,1) { int x2=x[j]; if(x1-x2>60) break; dp[i]=min(dp[i], dp[j]+(1LL<<(x1-x2))+a); } } printf("%lld ", dp[k]); } return 0; }