链接

HDU-6560

题意

一排电台，坐标从1到n，每个电台有辐射范围\(rad_i\)，保证左边界非严格递增，即\(i-rad_i+1<=i+1-rad_{i+1}+1\)，
对于每个电台i要找一个点k，k要满足以下条件
1.\(k<i\)，且k在i的辐射范围内
2.存在j，k和i都在j的辐射范围内，且kj间距离大于等于ji间距离
求每个i能找到的k的个数的异或和

思路

一开始以为是贪心，但是不对劲，这不是放电台，是给定所有电台找符合条件的点，看了题解才知道是数学题
根据题目条件可以列出以下不等式
1.\(k <= j < i\)
2.\(k >= i - rad_i + 1 >=1\)
3.\(k >= j - rad_j + 1 >=1\)
4.\(i <= j + rad_j -1\)
5.\(j - k >= i - j >=1\)
6.\(i - rad_i +1 <= i + 1 - rad_{i+1} + 1\)
整理后得，
1.\(k <= j\)
2.\(k >= i - rad_i + 1\)
3.\(k <= 2 * j - i <= 2 * (i - 1) - i = i - 2\)
最后得，
k的范围是\([i - rad_i + 1, i - 2]\)
所以对于每一个i，能找到的k的个数为\(max(rad_i-2,0)\)

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;

const int M = int(1e6) + 5;
const int mod = int(1e9) + 7;

int a[M];
int main(){
    int t;
    cin>>t;
    for(int kase=1;kase<=t;kase++){
        int ans=0;
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(i>=2){
                ans^=max(a[i]-2,0);
            }
        }
        printf("Case %d: %d\n",kase,ans);
    }
    return 0;
}

2018CCPC吉林赛区 F - The Hermit

原文：https://www.cnblogs.com/harutomimori/p/12872990.html