「BZOJ2299」[HAOI2011] 向量
Description
给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。
说明：这里的拼就是使得你选出的向量之和为(x,y)
Input
第一行数组组数t，(t<=50000)
接下来t行每行四个整数a,b,x,y (-2*109<=a,b,x,y<=2*109)
Output
t行每行为Y或者为N，分别表示可以拼出来，不能拼出来
Sample Input
3
2 1 3 3
1 1 0 1
1 0 -2 3
Sample Output
Y
N
Y
题解
orz wulala
注意到题目中相当于有4种操作
x或y +-2a
x或y +-2b
x+a，y+b
x+b，y+a
而3，4操作最多用1次，枚举3，4使用或不使用然后裴蜀定理判定即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; ll a,b,x,y,d; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } bool jud(ll x,ll y) { return x%d==0&&y%d==0; } int main() { T=read(); while(T--) { a=read(),b=read(),x=read(),y=read(); d=gcd(2*a,2*b); if(jud(x,y)||jud(x+a,y+b)||jud(x+b,y+a)||jud(x+a+b,y+a+b))puts("Y"); else puts("N"); } return 0; } |
Subscribe
计数器 9300516
OI 课件=>
OI 课件=>