Codeforces Round #594 (Div. 2)(A/B/C)

A. Integer Points
Description

DLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew n distinct lines, given by equations y=x+pi for some distinct p1,p2,…,pn. Then JLS drew on the same paper sheet m distinct lines given by equations y=−x+qi for some distinct q1,q2,…,qm . DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.
Input

The first line contains one integer t(1≤t≤1000
1≤t≤1000), the number of test cases in the input. Then follow the test case descriptions. The first line of a test case contains an integer n (1≤n≤1051≤n≤105), the number of lines drawn by DLS.The second line of a test case contains n distinct integers pipi (0≤pi≤1090≤pi≤109) describing the lines drawn by DLS. The integer pi describes a line given by the equation y=x+piy=x+pi. The third line of a test case contains an integer m (1≤m≤1051≤m≤105), the number of lines drawn by JLS. The fourth line of a test case contains m distinct integers qiqi (0≤qi≤1090≤qi≤109) describing the lines drawn by JLS. The integer qi describes a line given by the equation y=−x+qi

y=−x+qi . The sum of the values of n over all test cases in the input does not exceed 105. Similarly, the sum of the values of m over all test cases in the input does not exceed 105 . In hacks it is allowed to use only one test case in the input, so t=1 should be satisfied.
Output

For each test case in the input print a single integer — the number of line pairs with integer intersection points.
Example
Input

3
    3
    1 3 2
    2
    0 3
    1
    1
    1
    1
    1
    2
    1
    1

Output

3
1
0

Note

The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates.

解体思路：容易想到的是利用x=(q-p)/2,y=(p+q)/2,对所有交点进行判断是否为整数，很明显由于数据量过大，超时。第二种方法，通过画图，寻找规律，可以发现当p,q同时为奇数或偶数的时候,交点为整数点。结果需要用long long 存下。

TE代码：

#include <iostream>

#include <cmath>

using namespace std;

double a[];

double b[];

int main()

{

    int t,n,m;

    cin>>t;

    while(t--)

    {

        cin>>n;

        for(int i=;i<n;i++)

            cin>>a[i];

        cin>>m;

        for(int i=;i<m;i++)

            cin>>b[i];

        int k=;

        int cnt=;

        for(int i=;i<n;i++)

        {

            for(int j=;j<m;j++)

            {

                long double tx=(b[j]-a[i])/;

                long double ty=(a[i]+b[j])/;

                long long tmpx=(long long)(b[j]-a[i])/;

                long long tmpy=(long long)(a[i]+b[j])/;

                if(fabs(ty-tmpy)<1e-&&fabs(tx-tmpx)<1e-&&(long long)(a[i]+b[j])%==)

                    cnt++;

            }

        }

        cout<<cnt<<endl;

    }

    return ;

}

AC代码：

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    long long t,n,m,sum1,sum2,sum3,sum4,p,q;

    cin>>t;

    while(t--)

    {

        cin>>n;

        sum1=sum2=sum3=sum4=;

        for(int i=;i<n;i++)

        {

            cin>>p;

            if(p%==)

                sum1++;

            else

                sum2++;

        }

        cin>>m;

        for(int i=;i<m;i++)

        {

            cin>>q;

            if(q%==)

                sum3++;

            else

                sum4++;

        }

        cout<<sum1*sum3+sum2*sum4<<endl;

    }

    return ;

}

巴特西

Codeforces Round #594 (Div. 2)(A/B/C)

最新文章

热门文章