題目描述

The Hermit stands alone on the top of a mountain with a lantern in his hand. The snow-capped mountain range symbolises the Hermit's spiritual achievement, growth and accomplishment.
Hehas chosen this path of self-discovery and， asa result, has reached a heighted state of awareness.

dhh loves to listen to radio. There are? radio stations on a number axis, and the i-th station is located at xi=i. The broadcasting scope of the i-th station is radi, which means stations in the interval [i - radi?+ 1,i + radi?- 1]? can receive the signal from the i-th station.?For some unknown reason, the left boundary that can receive the i-th station's signal is non-descending, which means i - radi + 1≤ i + 1 - radi+1?+ 1.
Now dhh wants to listen to the radio from station i, and he finds that the station k, satisfying both of the following conditions, can receive perfect signal from the station i:?
·k < i and station k can receive station i's signal.?
·There exists another station j(k≤j＜i) such that station? and? can both receive the signal from station j and the distance between station k and j is greater than or equal to the distance between station j and i.?
Now dhh wonders for each station i, how many stations can receive the perfect signal from station i.

?

輸入

The first line of the input contains one integer T≤20, denoting the number of testcases. Then T testcases follow. For each testcase:
·The first line contains one positve integer N.
·The second line contains N positive integers rad1, rad2 ，…， radN.
It’s guaranteed that 1≤N≤106?, i-radi+1≥1 and i + radi-1≤N

?

輸出

For the k-th testcase, output “Case k： ans” in one line, where ans represents the xor result of answer for each radio station i.
xor is a bitwise operation, which takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same.

?

樣例輸入

2 7 1 2 3 4 3 2 1 10 1 1 2 3 4 4 3 2 2 1

樣例輸出

Case 1: 2 Case 2: 0

題意：

有n個電臺位于一維坐標軸上,第i個電臺 位置xi=i，輻射半徑（即的電臺都會被i覆蓋，即收到i的信息），滿足

定義“完美接收”：如果電臺k在電臺i的左邊（k<i）,i覆蓋k,并且存在電臺j滿足k<=j<i,j到k的距離>=i到j的距離，j覆蓋k,那么k可以對i的信號“完美接收”。

對每個i,求出有多少個這樣的k，這個值設為。

對求異或和。

思路：

對于每個i，在它左邊的范圍內的電臺，除了它本身和它左邊第一個外，都可以完美接收i的信號。

為什么呢？

我們找的k應滿足：

1. k<i

2. i覆蓋k

3.?存在電臺j滿足

3.1 k<=j<i

3.2 j到k的距離>=i到j的距離

3.3 j覆蓋k

我們讓j=i-1，那么，對于??<=k<=i-2(自然滿足1? 2? 3.1) 的電臺，

有j-k=(i-1)-k>=1,i-j=i-(i-1)=1（所以滿足3.2）

因為對所有的 i 滿足?（這就說明如果k<i,i覆蓋k，那么對任意k<=j<=i，滿足j覆蓋k）

所以3.3也滿足。

?

至于i本身和i-1,顯然都不能完美接收i的信號。

?

所以??= i左邊覆蓋的電臺數-2

對求異或和就ok啦。

代碼：

#include<iostream> #include<cstdio> using namespace std; const int N=1e6+100; long long a[N]; long long ans; int main(){int t,n;scanf("%d",&t);for(int ca=1;ca<=t;++ca){scanf("%d",&n);ans=0;for(int i=0;i<n;++i)scanf("%lld",&a[i]);for(int i=2;i<n;++i)if(a[i]>2)ans^=(min(a[i],i+1ll)-2);printf("Case %d: %lld\n",ca,ans);}return 0; }

總結

以上是生活随笔為你收集整理的【ccpc2018吉林F题】THE HERMIT （思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。