首页 > 代码库 > “玲珑杯”ACM比赛 Round #18 A 暴力水 C dp
“玲珑杯”ACM比赛 Round #18 A 暴力水 C dp
“玲珑杯”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 secondtypedef 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\n", ans1[N-1]); else printf("%lld\n", 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 secondtypedef 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\n", dp[k]); } return 0;}
“玲珑杯”ACM比赛 Round #18 A 暴力水 C dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。