0704暑假集訓前的歡樂大雜燴總結

在TM迎接暑假超級無敵20天happy樂的前夕來了一場巨多人的超級爽的歡樂賽

然而老劉的資料翻車了（是以我們在這裡就暫且不去論第5題）

T1 --質因數分解

【正解】：我都不想說什麼，爆0是最騷的。這麼睿智的一道題我居然GG了，平時的闆子要去多多複習啊。（話說我自己還寫過相應的部落格啪啪）

重點：

被分解的數在long long範圍内

這題後來訂正的時候，枚舉質因子時我是

for(int j=2;j*j<=p;j++)
 .....

但是這樣會爆j的int範圍導緻失去部分分數。

是以我們得注意定義一個int級的變量時，如果有乘法要麼将變量還是改成ll，或者在乘法前加上（1LL）* 或者前面加上（long long）

【注意不是加在後面，不然前面已經炸了再加上就沒什麼意義了，我的T6最後一個點就是因為加在後面然後GG了】

T2—蛇形方陣2

【正解】每一圈k的起點必定是（k,k）,然後再按順時針逆時針去模拟就可以了，比較水。

T3—大采購

【正解】多重背包闆子，注意二進制拆分操作。

(好吧,現在已經是單調隊列了,誰還用二進制拆分？)

T4—吉波雞脖那切數列

【問題描述】

有⼀個很著名的數列叫做斐波那契數列，它的定義式是

Fn = Fn−1 + Fn−2

其中，遞推的初始值為：F0 = 1, F1 = 1

在吉波那契數列這個問題中，我們相似地定義了⼀個吉波那契數列 Gn：

Gn = Gn−1 + Gn−2

對任何情況⽽⾔，G0 = 1, ⽽ G1 是⼀個随機的正整數 t。

現在告訴你 Gi 的值和兩個正整數 i, j，請你求出 Gj。鑒于 Gj 可能很⼤，

請你輸出 Gj mod 19960515。

【輸入格式】

輸⼊⽂件名為 gibonacci.in

有多組測試資料。第⼀⾏是⼀個正整數 T，表示測試資料的組數。

接下來 T ⾏，每⾏為⼀組測試資料，每組測試資料包含 3 個正整數 i, Gi

, j。

【輸出格式】

輸出⽂件名為 gibonacci.out

對于每組資料，輸出 Gj mod 19960515。

假如沒有合适的 t，請輸出 −1。

【樣例輸入】

1 1 2

3 5 4

【樣例輸出】

【資料規模與約定】

對于 30% 的資料，每個 Gibonacci 數列的 G1 = t ≤ 50

對于 50% 的資料，有 T ≤ 30

對于 100% 的資料，有 T ≤ 10000, 1 ≤ i, j ≤ 100000, 0 ≤ Gi < 19960515

不妨設G1=x

則序列可變為：1,x,x+1,2x+1,3x+2,5x+3,8x+5…

發現x的系數滿足斐波那契數列，常數項也滿足斐波那切數列，那麼已知Gi便可以知道它的x系數和常數項，看看x能否得出是正整數即可。

然後以此得出Gj的x系數和常數項然後就OK

别忘了取模%%%

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int q=19960515;
int f[100010],t;
int main()
{
	freopen("gibonacci.in","r",stdin);
	freopen("gibonacci.out","w",stdout);
   scanf("%d",&t);
   f[0]=0;
   f[1]=f[2]=1;
   for(int i=3;i<=100000;i++)
     f[i]=(f[i-1]+f[i-2])%q;
   while(t--)
   {
   	int x,y,c,w;
   	ll num;
	scanf("%d%lld%d",&x,&num,&y);
    c=f[x-1];
	w=f[x];
	if((num-c)%w||num-c<0) printf("-1\n");
	else 
	{
		int g=((num-c)/w)%q;
		printf("%lld\n",(((1LL)*f[y]*g)%q+f[y-1])%q);
	} 
   }
   return 0;
}

T5—魔塔

由于這道題老劉翻車了，利用記憶化搜尋dfs會有漏洞，而正解是什麼IDA*加堆優化，于是我暫且先不去談%%%（其實是我不會）

老劉别打我

0704暑假集訓前的歡樂大雜燴總結

T6—對戰

【題面】

對戰

(inhouse.cpp/c/pas)

【問題描述】

在⼀條街道上有 n 個⼈，他們都喜歡打乒乓球。任意兩個⼈的家的位置都

不相同，按順序标為 1, 2, · · · , n。每個⼈都有⼀定的⽔平，用兩兩不等的整數表

示。

當兩個⼈想打球的時候，會找另⼀個⼈作為裁判，并到裁判家裡進⾏⼀場

較量。出于某種原因，他們希望裁判的⽔平介于兩⼈之間；同時，他們希望兩個

⼈到裁判家的總路程不超過兩個⼈的家的距離。

對于兩場較量，如果打球的兩個⼈不完全相同或者裁判不同，我們就認為

這兩場較量不同。求不同的較量的總數。

【輸入格式】

輸⼊⽂件名為 inhouse.in

輸⼊包含多組資料

輸⼊的第⼀⾏是⼀個整數 T，表示資料組數；

每組資料占⼀⾏，包含 n + 1 個整數：n, a1, a2, · · · , an。其中 a1, a2, · · · , an

表示家位于相應位置的⼈的⽔平。

【輸出格式】

輸出⽂件名為 inhouse.out

對每組資料，用⼀⾏輸出⼀個整數，表示不同的較量的總數。

【樣例輸入】

3 1 2 3

【樣例輸出】

【資料規模與約定】

對于 40% 的資料，有 n ≤ 1000；

對于所有資料，有 T ≤ 20, 3 ≤ n ≤ 100000，每個⼈的⽔平都是不超過200000 的正整數。

【正解】一開始看到題想到使用雙指針指向兩個互相對決的人，然後累加他們之間合法的裁判，發現這樣就十分暴力，時間複雜度高。

正難則反的思想：枚舉2~n-1個人去做裁判，看看能給多少組人去當裁判即可。

明顯隻需知道裁判i左邊比他高的L1[i],右邊比他低的R1[i]，左邊比他矮的L2[i]，右邊比他高的R2[i]

答案就是SUM(L1[i]*R2[i]+L2[I]*R1[i]) 2<=i<=n-1

那麼現在的問題就是如何快速得到這個L1,R1,L2,R2；

用樹狀數組維護這種關系，類似逆序對的求法，隻需要減一減就OK了。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,maxx=-1;
ll a[100501],c[200101];
ll lef1[105001],righ1[100501],lef2[100501],righ2[100501];;

void add(ll x,ll val)
{
	for(;x<=maxx;x+=x&-x)
	  c[x]+=val;
}

ll sum(int x)
{
	ll ans=0;
	for(;x;x-=x&-x)
	  ans+=c[x];
	return ans;
}
int main()
{
	freopen("inhouse.in","r",stdin);
	freopen("inhouse.out","w",stdout);
  scanf("%d",&t);
  while(t--)
  { int n;
  	scanf("%lld",&n);
  	ll ans=0;
	maxx=-1;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),maxx=max(a[i],maxx);
  	for(ll i=1;i<=n;i++)
   {
   	lef1[i]=sum(a[i]-1); 
    lef2[i]=lef1[i];//左邊比他低
   	lef1[i]=i-1-lef1[i];	//左邊比他高
	add(a[i],1);
   }
   memset(c,0,sizeof(c));
   for(ll i=n;i>=1;i--)
   {
   	righ1[i]=sum(a[i]-1);
   	righ2[i]=righ1[i];//右邊比他低
   	righ1[i]=n-i-righ1[i];//右邊比他高
	add(a[i],1);
   }
   for(ll i=2;i<n;i++)
     ans+=(ll)(lef1[i]*righ2[i]),ans+=(ll)(lef2[i]*righ1[i]);//注意這(ll)
   printf("%lld\n",ans);
   memset(c,0,sizeof(c));
  }
}

前面已經提過，你原本以為的int不會爆，但是相乘就可能會GG，是以保險起見還是加上一個(ll)或者

1LL*；不過要加在乘法運算的前面

總結：因為爆int失分高達30，因為闆子忘記敲失分100分。細節處理失分10分。然後魔塔就不說了，直接GG了。這啟示我，int乘法加(ll)是必須的，闆子多去敲敲，不複習就真的GG，功在平時；

細節處理也很重要，思路要更缜密一些。

0704暑假集訓前的歡樂大雜燴總結