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=)