Modified LCS

Input

Output

Sample Input

3
5 3 4 15 3 1
10 2 2 7 3 3
100 1 1 100 1 2

Sample Output

4
3
50
超时代码，因为K很大

 1 /*****************
 2 f1+(k1-1)*d1=f2+(k2-1)*d2
 3 =>  (k1-1)*d1+(k2-1)*(-d2)=f2-f1;
 4 =>  d1*x+y*(-d2)=f2-f1   d1=>[0,n1-1]  d2=>[0,n2-1]
 5 求在给定范围内解的个数
 6 *********************/
 7 #include"iostream"
 8 #include"cstdio"
 9 #include"cstring"
10 #include"cmath"
11 #include"algorithm"
12 using namespace std;
13 typedef long long ll;
14 void exgcd(ll n,ll m,ll &x,ll &y,ll &d)
15 {
16     if(!m){
17         x=1;y=0;d=n;
18     }
19     else{
20         exgcd(m,n%m,y,x,d);
21         y-=(n/m)*x;
22     }
23 } 
24 int main()
25 {
26     ll f1,n1,d1,f2,n2,d2,i,j,t;
27     cin>>t;
28     while(t--)
29     {
30         ll x,y,tmp,d;
31         //cin>>n1>>f1>>d1>>n2>>f2>>d2;
32         scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2);
33         exgcd(d1,-d2,x,y,d);
34         f2-=f1;
35         if(f2%d){
36             //cout<<"0"<<endl;
37             puts("0");
38             continue;
39         }
40         x=x*(f2/d);
41         y=y*(f2/d);
42         //接下来  逼近[0,n1-1],[0,n2-1] 
43         ll t1=d2/(abs(d));
44         ll t2=d1/(abs(d));
45         if(x<0||y<0)
46         {
47             int i=1;
48             while(1)
49             {
50                 if(x+t1*i>=0&&y+t2*i>=0)
51                     break;
52                 i++;
53             }
54             x=x+t1*i;
55             y=y+t2*i;
56         }
57         else
58         {
59             int i=1;
60             while(1)
61             {
62                 if(x-t1*i<0||y-t2*i<0)
63                     break;
64                 i++;
65             }
66             x=x-t1*(i-1);
67             y=y-t2*(i-1);    
68         }
69         if(x>(n1-1)||y>(n2-1))
70         {
71             //cout<<"0"<<endl;
72             puts("0");
73             continue;
74         }
75         int ans=1;
76         while(1)
77         {
78             if(x+t1*ans>(n1-1)||y+t2*ans>(n2-1))
79                 break;
80             ans++;
81         }
82         cout<<ans<<endl;
83         //printf("%lld
",ans);
84     }
85     return 0;
86 }

View Code

AC代码

/*****************
f1+(k1-1)*d1=f2+(k2-1)*d2
=>  (k1-1)*d1+(k2-1)*(-d2)=f2-f1;
=>  d1*x+y*(-d2)=f2-f1   d1=>[0,n1-1]  d2=>[0,n2-1]
求在给定范围内解的个数
*********************/
#include"iostream"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"algorithm"
using namespace std;
typedef long long ll;
void exgcd(ll n,ll m,ll &x,ll &y,ll &d)
{
    if(!m){
        x=1;y=0;d=n;
    }
    else{
        exgcd(m,n%m,y,x,d);
        y-=(n/m)*x;
    }
} 
int main()
{
    ll f1,n1,d1,f2,n2,d2,i,j,t;
    cin>>t;
    while(t--)
    {
        ll x,y,tmp,d;
        //cin>>n1>>f1>>d1>>n2>>f2>>d2;
        scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2);
        exgcd(d1,-d2,x,y,d);
        f2-=f1;
        if(f2%d){
            //cout<<"0"<<endl;
            puts("0");
            continue;
        }
        x=x*(f2/d);
        y=y*(f2/d);
        //接下来  逼近[0,n1-1],[0,n2-1] 
        ll t1=d2/(abs(d));
        ll t2=d1/(abs(d));
        if(x<0||y<0)
        {
            int i=1;
            while(1)
            {
                if(x+t1*i>=0&&y+t2*i>=0)
                    break;
                i++;
            }
            x=x+t1*i;
            y=y+t2*i;
        }
        else
        {
            int i=1;
            while(1)
            {
                if(x-t1*i<0||y-t2*i<0)
                    break;
                i++;
            }
            x=x-t1*(i-1);
            y=y-t2*(i-1);    
        }
        if(x>(n1-1)||y>(n2-1))
        {
            //cout<<"0"<<endl;
            puts("0");
            continue;
        }
        int ans=1;
    /*    while(1)
        {
            if(x+t1*ans>(n1-1)||y+t2*ans>(n2-1))
                break;
            ans++;
        }
    */
    //  这样避免超时 
        ll a,b;
        a=(n1-1-x)/t1;
        b=(n2-1-y)/t2;
        cout<<min(a,b)+1<<endl;
    }
    return 0;
}