A-牛牛的方程式

Solution

对于二元一次不定方程 有解的条件是 。若该方程有解，可将 代换为 ，三元一次方程可以写为 ，此时可将 看做常数系数， 为变量。再次使用判定二元一次方程的方法即可。

综上，有解条件为 。注意特判模数为 的情况。

Code

#include
#include
#include
#define ll long long
using namespace std;
ll T,a,b,c,d;
ll gcd(ll x,ll y){
    if(!y)
        return x;
    return gcd(y,x%y);
}
int main(){
    cin>>T;
    while(T--){
        cin>>a>>b>>c>>d;
        a=gcd(a,b);
        a=gcd(a,c);
        if(a==0&&d!=0)
            cout<<"NO"<<endl;
        else if(a==0&&d==0)
            cout<<"YES"<<endl;
        else if(d%a==0)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

B-牛牛的猜球游戏

Solution

直接思路暴力模拟。考虑优化这个过程。

发现这个操作具有区间可加性，即一个区间操作造成的影响可由子区间的操作得出。因此可用线段树维护。由于 的数据范围，用分块写法简单些。

具体地，将操作序列分成 块，将所有边界为分块端点的区间所发生的变换预处理出来，查询时直接使用即可。

时间复杂度 。

Code

#include
#include
#include
#include
using namespace std;
const int N=1e5+10,M=350;
struct node{
    int x,y;
}a[N];
int n,m,t,ans[10],b[10],L[N],R[N],pos[N],c[M][M][10],d[M][M][10];
void solve(int l,int r){
    int p=pos[l],q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++)
            swap(ans[a[i].x],ans[a[i].y]);
    }
    else{
        for(int i=l;i<=R[p];i++)
            swap(ans[a[i].x],ans[a[i].y]);
        if(p+1<=q-1){
            for(int i=0;i<10;i++)
                b[i]=ans[d[p+1][q-1][i]];
            for(int i=0;i<10;i++)
                ans[i]=b[i];
        }
        for(int i=L[q];i<=r;i++)
            swap(ans[a[i].x],ans[a[i].y]);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;
        R[i]=i*t;
    }
    if(R[t]<n)
        t++,L[t]=R[t-1]+1,R[t]=n;
    for(int i=1;i<=t;i++)
        for(int j=L[i];j<=R[i];j++)
            pos[j]=i;
    for(int i=1;i<=t;i++){
        for(int j=0;j<10;j++)
            c[i][i][j]=j;
        for(int j=i;j<=t;j++){
            for(int k=L[j];k<=R[j];k++)
                swap(c[i][j][a[k].x],c[i][j][a[k].y]);
            for(int k=0;k<=9;k++)
                d[i][j][k]=c[i][j][k],c[i][j+1][k]=c[i][j][k];
        }
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        for(int j=0;j<=9;j++)
            ans[j]=j;
        solve(l,r);
        for(int j=0;j<10;j++){
            cout<<ans[j];
            if(j!=9)
                cout<<" ";
        }
        cout<<endl;
    } 
    return 0;
}

纯暴力待补。