A -- 计算几何你瞎暴力
Time Limit：5s Memory Limit：256MByte
Submissions：1597Solved：301
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 “玲珑杯”ACM比赛 Round #18 思路： 你会发现x，y，z都只是不超过10， 那么他的r最多也就30...然后就很水了，记下cnt[x][y][z]，记录这个点有几个，然后枚举两个点的坐标（10*10*10*10*10*10），计算他们的哈曼顿距离，算出这个距离有多少种，最后前缀和记录下就好了，注意枚举的点要分一样还是不一样， 不一样的你会发现会枚举两边，前缀的时候/2就好了 代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int cnt[15][15][15], book[15][15][15];
ll dp[50];
int main()
{
int t, n, q, x, y, z;
cin >> t;
while(t--)
{
memset(dp, 0, sizeof(dp));
memset(cnt, 0, sizeof(cnt));
scanf("%d%d", &n,&q);
for(int i = 1; i <= n; i++)
scanf("%d%d%d", &x, &y, &z), cnt[x][y][z]++;
for(int i = 0; i <= 10; i++)
for(int j = 0; j <= 10; j++)
for(int k = 0; k <= 10; k++)
for(int x = 0; x <= 10; x++)
for(int y = 0; y <= 10; y++)
for(int z = 0; z <= 10; z++)
{
int dis = abs(i-x) + abs(j-y) + abs(k-z);
if(i == x && j == y && k == z)
{
dp[dis] = dp[dis] + (ll)(cnt[i][j][k]-1)*(cnt[i][j][k])/2;
}
else dp[dis] = dp[dis] + (ll)(cnt[i][j][k]*cnt[x][y][z]);
}
for(int i = 1; i <= 30; i++)
dp[i] = dp[i]/2 + dp[i-1];
while(q--)
{
scanf("%d", &x);
if(x >= 30) x = 30;
printf("%lld\n", dp[x]);
}
}
return 0;
}
C -- 图论你先敲完模板
Time Limit：5s Memory Limit：256MByte
Submissions：660Solved：160
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 “玲珑杯”ACM比赛 Round #18
思路： 简单dp， dp【i】代表第i个休息点用到最少的能量， 转移很简单， dp[i] = min(dp[i], dp[i-j] + cnt[x[i]-x[i-j]]+a); 但是这样n2复杂度会t， 但是你会发现 他能量消耗是2的指数级的，2l+a2l+a.然后我们发现这个
2x2x很快就会比aa高到不知道哪里去,所以当这个距离超过一定值的时候肯定是分开
跑比较划算了,所以我们只需要枚举当前点前面的几十个点再转移一下就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxn = 1e5 + 5;
int t, n, a;
ll x[maxn], dp[maxn], cnt[50];
int main()
{
for(int i = 0; i <= 30; i++) //预处理
cnt[i] = (1<<i);
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &a);
for(int i = 0; i < maxn; i++)
dp[i] = INF;
for(int i = 1; i <= n; i++)
scanf("%d", &x[i]);
dp[1] = 0;
for(int i = 2; i <= n; i++)
{
for(int j = 1; j < i; j++)
{
if(x[i]-x[i-j] <= 30) //三十个点就大于a的最大值了
dp[i] = min(dp[i], dp[i-j] + cnt[x[i]-x[i-j]]+a);
else break;
}
}
printf("%lld\n", dp[n]);
}
return 0;
}
2l+a 2l+a
B -- 数论你还会快速幂
Time Limit：5s Memory Limit：256MByte
Submissions：405Solved：85
DESCRIPTION
今天HHHH在学数论,他看到一个很优美的式子:
∑ni=1ik mod p∑i=1nik mod p
一向热衷于抱队友大腿的HHHH便问队友ZZZZ怎么做
ZZZZ:"n,kn,k多大?"
HHHH:"105,105105,105"
ZZZZ:"快速幂嘛"
HHHH:"109,105109,105"
ZZZZ:"拉格朗日插值嘛"
HHHH:"1018,10181018,1018"
队友:"让我想想.."
INPUT 第一行是一个整数 T(1≤T≤1000)T(1≤T≤1000),表示有 TT组数据对于每组数据输入一行3个整数 n,k,p(1≤n≤1018,0≤k≤1018,1≤p≤1018,0≤n−p≤100)n,k,p(1≤n≤1018,0≤k≤1018,1≤p≤1018,0≤n−p≤100)且模数 pp 是质数, OUTPUT 对于每组数据输出题目中的表达式的值 SAMPLE INPUT 2 5 2 3 7 2 3 SAMPLE OUTPUT 1 2 HINT 对于第一组样例我们有 12+22+32+42+52=1(mod3)12+22+32+42+52=1(mod3)对于第二组样例我们有 12+22+32+42+52+62+72=2(mod3)12+22+32+42+52+62+72=2(mod3) SOLUTION “玲珑杯”ACM比赛 Round #18
官方题解：
看到nn比pp大了不到100个,我们可以思考一下假如我们只算到pp或者p−1p−1会是怎么样的
即考虑函数∑p−1i=1ik mod p∑i=1p−1ik mod p
我们先打个表能发现当kk是p−1p−1的倍数的时候这个值是p−1p−1,别的时候都是00
然而这是否正确的呢? 我们可以简单的推导一下:
假设gg是pp的原根,那么根据原根的性质,gg的1次方到p−1p−1次方在模pp的时候
对应了11到p−1p−1的某个全排列,即原式等价于
gk+g2k+g3k+...+g(p−1)kgk+g2k+g3k+...+g(p−1)k
然后我们用等比数列求和一下则得到
(gk−gpk)/(1−gk)=(gk−gpk)×inv(1−gk)(gk−gpk)/(1−gk)=(gk−gpk)×inv(1−gk)
再根据费马小定理我们便得到了gp=ggp=g,那么这个式子就变成了0
不过这是建立在这是等比数列的情况下的,所以我们对几种不是等比数列的情况需要特判:
(1) p为2的时候原根是1
(2) k为p-1的时候由费马小定理可以得到所有项均为1
所以我们现在只需要算剩下的100个左右的数就可以了,快速幂搞一下就行.
不过要小心这个范围乘法会爆long long 所以需要快速乘/O(1)快速乘
①首先我们知道，i^k%p和（i+p）^k%p的价值是一样的。
那么肯定以长度p为循环节，是有循环内容的。
②当k不是p-1的倍数的时候，我们发现，每一段长度为p的内容加和%p都是0.
②当k是p-1的倍数的时候，我们发现，每一段长度为p的内容加和都是p-1.
贯彻“遇事不决，就打表”
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL p, k;
LL quick_mul(LL x,LL y,LL MOD)
{
x = x%MOD,y = y%MOD;
return ((x*y-(LL)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;
}
LL quick_Mod(LL x, LL n)
{
LL ans = 1;
while(n)
{
if(n&1)
{
ans = quick_mul(ans, x, p);
}
x = quick_mul(x, x, p);
n >>= 1;
}
return ans;
}
int main()
{
LL n;
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lld%lld%lld", &n, &k, &p);
if(k==0)
{
printf("%lld\n",n%p);
continue;
}
LL ans = 0;
if(k%(p-1) == 0)
{
ans = (ans + quick_mul(p-1, n/p, p))%p;
}
n %= p;
for(LL i = 1; i <= n; i++)
{
ans = (ans + quick_Mod(i, k))%p;
}
printf("%lld\n", ans);
}
return 0;
}
2l+a 2l+a
![CF1394C 计算几何[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)