攻打城堡

Tag 二分

思路

首先，题意很清晰，给n个方程： y = l + k*d <=r

然后在满足条件的方程中，给y号位置放置一个盾牌，求问你，哪个位置的盾牌数为奇数（题目限制，奇数的位置最多只有一个）

由于题目限制了奇数盾牌的位置最多只有一个。那么我们就可以如下形式去思考。

首先，我们可以发现，每个点的贡献只有奇和偶两种可能。如果当前有一个数组$a[i]$，$a[i]$记录的值为0号点到i号点盾牌的总数。那么，从奇数盾牌的位置往后的点的盾牌数都将会是奇数，往前都是偶数。由此得到，数组a的奇偶性成线性相关。即可通过二分奇数位置的最小值找到奇数点。

注意：由于数组的位置过大，我们需要通过解方程方程的形式计算$0~i$位置的盾牌数量。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
set<int>s;
int l[N],r[N],d[N],cnt,t,n;
int a[N];
map<int,int>mp,mp2;
int getsum(int x)
{
  int sum=0;
  for(int i=1;i<=n;i++)
  {
    if( l[i]>x ) continue;
    int tor=min( x,r[i] );
    sum+=(tor-l[i])/d[i]+1;
  }
  return sum;
}
int getpos(int x)
{
  int sum=0;
  for(int i=1;i<=n;i++)
  {
    if( l[i]>x ) continue;
    if( (x-l[i])%d[i]==0 ) sum++;
  }
  return sum;
}
int main()
{
  //freopen("9.in","r",stdin);
  cin>>t;
  while(t--)
  {
    cin>>n;
    int dl=1,dr=1,mar=0;
    for(int i=1;i<=n;i++)
    {
      cin>>l[i]>>r[i]>>d[i];
      dr=max(dr,r[i]);
    }
    mar=dr;
    while( dl<=dr )
    {
      int mid=dl+dr>>1;
      if( getsum(mid)&1 ) dr=mid-1;
      else dl=mid+1;
    }
    if( dl>mar )
    {
      cout<<"There's no weakness.\n";
    }
    else{
      cout<<dl<<' '<<getpos(dl)<<endl;
    }
  }
}