【LGR-179-Div.2】复旦勰码 3 月月赛 II ZHYOI Round 4（A~B）

T431492 农场

有n个农场，告诉你农场的对角顶点坐标，农场都是矩阵。

要找出一个最大的矩阵（平行于x和y轴）把所有农场都圈起来。

那就保证最下面的点和最上面的点，最左边的点，最右边的点都能被圈到。

用l,r,u,d，来表示四个方向能衍生的最长距离，答案就是(r-l)*(u-d)

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int n;
    cin>>n;

    int l,r,u,d;
    cin>>l>>u>>r>>d;
    if(r<l)swap(l,r);
    if(u<d)swap(u,d);

    per(i,1,n-1){
        per(j,1,2){
            int x,y;
            cin>>x>>y;

            l=min(l,x);
            r=max(r,x);
            u=max(u,y);
            d=min(d,y);
        }
    }

    cout<<(r-l)*(u-d);
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

T431493 线性变换

可以对x进行操作（x>=0时才能操作），x=ax-b，进行0次及以上操作，问x的最小值。

分类讨论：

当a=0，x=-b，答案在 x 和 -b 中选一个最小的。

当a=1，x=x-b，每次操作取决于b。

          若b>0，则x可以变小，且b的整数倍次会减掉，即x-=(x/b)*b，然后再减一次b让x<0即可。

          若b<=0，x不会变得更小。

当a=-1，x=-x-b，x = -(-x-b)-b = x，答案在 x 和 -x-b 中选一个最小的               

考虑是否有先变大再变小的情况，只能由a变换符号得到，只有负数才能变成正数，再变成负数。

而负数不可以执行操作，故操作之后值变大就可以停止循环。       

|a|>=2时，显然会给 x 带来指数级的变化，每次都 *2*2*2 很快就会运算结束，暴力穷举1000次。 

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int x,a,b;
    cin>>x>>a>>b;

    if(a==0){
        cout<<min(x,-b)<<endl;
    }else if(a==1){
        if(b<=0){
            cout<<x<<endl;
        }else{
            x-=(x/b)*b;
            while(x>=0)x-=b;
            cout<<x<<endl;
        }
    }else if(a==-1){
        cout<<min(x,-x-b)<<endl;
    }else{
        int ans=x;
        per(i,1,1000){
            x=a*x-b;
            if(x>=ans)break;
            ans=x;
            if(ans<0)break;
        }
        cout<<ans<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}