防线

输入文件的第一行是一个整数 T，表示有 T 组互相独立的测试数据。
每组数据的第一行是一个整数 N。
之后 N 行，每行三个整数 $S_i$ ， $E_i$ ， $D_i$ ，代表第 i 组防具的三个参数。

对于每组测试数据，如果防线没有破绽，即所有的位置都有偶数个防具，输出一行 “There’s no weakness.”（不包含引号）
否则在一行内输出两个空格分隔的整数 P 和 C，表示在位置 P 有 C 个防具。当然 C 应该是一个奇数。

C++14(g++5.4) 解法, 执行用时: 88ms, 内存消耗: 4836K, 提交时间: 2020-05-18 18:45:54

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int t,n;
struct sed
{
	int s,e,d;
}a[N];
ll get(int mid)
{
	ll res=0;
	for(int i=1;i<=n;i++)
	if(a[i].s<=mid){
		res+=(min(a[i].e,mid)-a[i].s)/a[i].d+1;
	}
	return res;
}

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int l=0,r=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].d),r=max(r,a[i].e);
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(get(mid)&1)r=mid;
			else l=mid+1;
		}
		auto sum=get(r)-get(r-1);
		if(sum%2)printf("%d %lld\n",r,sum);
		else printf("There's no weakness.\n");
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 140ms, 内存消耗: 5108K, 提交时间: 2023-07-17 08:17:03

#include<bits/stdc++.h>
using namespace std;
long long n,s[1000001],e[1000001],d[1000001];
inline long long check(long long x){
	long long ans=0;
	for(register int i=1;i<=n;++i)if(min(e[i],x)>=s[i])ans+=(min(e[i],x)-s[i])/d[i]+1;
	return ans;
}
int main(){
	long long t;scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		for(register int i=1;i<=n;++i)scanf("%lld%lld%lld",&s[i],&e[i],&d[i]);
		long long l=0,r=0x7fffffff;
		while(l<r){
			long long mid=l+r>>1;
			if(check(mid)&1)r=mid;
			else l=mid+1;
		}
		(l==0x7fffffff)?puts("There's no weakness."):printf("%lld %lld\n",l,check(l)-check(l-1));
	}
}

C++ 解法, 执行用时: 248ms, 内存消耗: 2760K, 提交时间: 2022-07-27 09:45:48

#include<bits/stdc++.h>
using namespace std;
int main(){
  int T; cin >> T;
  while (T--) {
    int N; cin >> N;
    vector<array<int, 3>> A(N);
    for (auto &[S,E,D]: A) cin >> S >> E >> D;
    int P = 0;
    for (auto [S,E,D]: A) {
      while (S <= E)  P^=S, S+=D;
    }
    int C = 0;
    for (auto [S,E,D]: A)  C += S <= P && P <= E && (P-S)%D == 0;
    if (P) cout << P << " " << C << endl;
    else cout << "There's no weakness." << endl;
  }
}

详情