A - Burenka Plays with Fractions

判断对应乘积是否是倍数关系
对应操作最大为2

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;

typedef pair<int,int>PII;

void solve()
{
    int a,b,c,d;cin >> a >> b >> c >> d;
    int res = 0;
    int t1 = a * d,t2 = b * c;
    if(t1 == t2)res = 0;
    else 
    {
        if(t1 == 0 || t2 == 0 || t1 % t2 == 0 || t2 % t1 == 0)res = 1;
        else res = 2;
    }

    cout << res << endl;
}

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

B. Interesting Sum

本题的关键是要知道我们一定能取到最优解的
最优解的结构是:最大值+次大值-最小值-次小值
我们一定能找到一个区间使得里面包含一个最大或次大值和一个最小或次小值,那么剩余的区间内
也是这种情况.2^4种情况模拟一下便知道了

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;

typedef pair<int,int>PII;
int a[N];
void solve()
{
    int n;cin >> n;
    for(int i = 0; i < n; i ++)cin >> a[i];
    sort(a,a + n,greater<int>());
    cout << a[0] + a[1] - a[n - 1] - a[n - 2] << endl;
}

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

C. Corners

考虑每一个2*2的小正方形:
1.如果有4个1,一定会抵消掉两次
2.如果有3个1,一定会抵消掉一次
3.如果有2个1,一定不会影响我们的次数

我们对所有的2*2小方块取一个最小值,从含1量最小的那个小方块入手一定的代价最小的

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
//#define int long long
const int N = 510,INF = 0x3f3f3f3f;

typedef pair<int,int>PII;
char g[N][N];

//计算每一个小正方形内的1的个数
int cal(int x,int y)
{
    int res = 0;
    for(int i = x; i <= x + 1; i ++)
        for(int j = y; j <= y + 1; j ++)
            res += g[i][j] == '1';
    return res;
}

void solve()
{
    int n,m;cin >> n >> m;
    int sum = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++){
        cin >> g[i][j];
        sum += g[i][j] == '1';
    }
    int res = 5;

    for(int i = 0; i < n - 1; i ++)
        for(int j = 0; j < m - 1; j ++)
            res = min(res, cal(i,j));
    if(res == 4)cout << max(0,sum - 2) << endl;
    else if(res == 3)cout << max(0,sum - 1) << endl;
    else cout << sum << endl;
}

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

D1. Xor-Subsequence

题意:给定一个a数组，定义b数组是a的子数组当且仅当b数组由a的下标递增而形成。要求一个美丽的b数组满足  a[bp]^b[p+1]<a[b(p+1)]^b[p],a[i]的范围是0 <= a[i] <= 200，求最长的美丽数列。

由于b是单调递增的所以b(p+1)一定是大于bp的,所以我们一定要通过异或来减小差距,由于a最大是200,
所以我们的b是从(0,400)中转移过来的,暴力dp

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
//#define int long long
const int N = 3e5 + 10,INF = 0x3f3f3f3f;

typedef pair<int,int>PII;
int a[N],f[N];

void solve()
{
    int n;cin >> n;
    for(int i = 0; i < n; i ++)cin >> a[i],f[i] = 1;
    //对于每个i,只能从距离他不超过400的合法位置转移过来
    for(int i = 0; i < n; i ++)
        for(int j = max(0,i - 400); j < i; j ++)//升序
            if((a[j] ^ i) < (a[i] ^ j))f[i] = max(f[i],f[j] + 1);

    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i]);
    cout << res << endl;
}

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