A — Burenka Plays with Fractions
思路：数论 O(1)
见题解
题解：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 1e5 + 10;
LL T, a, b, c, d;
LL gcd(LL x, LL y)
{
return y == 0 ? x : gcd(y, x % y);
}
int main()
{
cin >> T;
while (T--)
{
cin >> a >> b >> c >> d;
if(1.0*a/b == 1.0*c/d) //若两分数值相等，无需操作
{
cout<<'0'<<endl;
continue;
}
if(a==0||c==0) //若任何一个分子为0，给另一个分数的分母乘以0，1次即可
{
cout<<'1'<<endl;
continue;
}
LL x = (LL)b*c,y = (LL)d*a; //给分数a/b的分子乘以(b*c),给分数c/d的分子乘以(d*a),这样二者就相等了
if(x%y == 0 || y % x == 0 ) //如果二者存在整除关系，eg.x = k*y,则等价于给一个分子乘以k，给另一个分子乘以1(不乘),1次即可
{
cout<<'1'<<endl;
}
else cout<<'2'<<endl; //否则就需要两次乘法操作
}
return 0;
}
B — Interesting Sum
思路：贪心、找规律、构造 O(n)
找到最大值，最小值，次大值，次小值，两个(大-小)的和即为答案
找规律题
题解
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 1e5 + 10;
int T,n;
int a[N];
int main()
{
cin>>T;
while(T--)
{
int Max1 = 0,Max2 = 0,Min1 = 0x3f3f3f3f,Min2 =0x3f3f3f3f;
cin>>n; //找到最大值，最小值，次大值，次小值，两个(大-小)的和即为答案
//找规律题，我也不太会证明
for(int i = 0;i<n;i++)
{
cin>>a[i];
if(a[i] > Max1)
{
Max2 = Max1;
Max1 = a[i];
}
else if(a[i] > Max2)
{
Max2 = a[i];
}
if(a[i] < Min1)
{
Min2 = Min1;
Min1 = a[i];
}
else if(a[i] < Min2)
{
Min2 = a[i];
}
}
cout<<(LL)(Max1 - Min1) + (Max2 - Min2)<<endl;
}
return 0;
}
C — Corners
思路：贪心 O(nm)
- 每次对存在'1'的2*2方格操作时，最少消除一个1，最多消除三个1。要得到最多操作次数，就要确定操作顺序，尽量使每次操作消除的'1'的个数最少
- 我们可以找全图所有存在'1'的且含'1'的个数最少的2*2方格，从此方格开始进行操作，计cnt为方格中1的个数
当cnt = 1时，只能进行一次操作
当cnt = 2时，无论1在同一行、列 或者 对角线，均可以实现两次操作消除两个'1'
当cnt = 3时，第一次操作最少只能去掉两个'1',第二次操作只能去掉一个'1'
当cnt = 4时，第一次操作最少只能去掉三个'1'，第二次操作只能去掉一个'1' - 对含'1'最少的方格操作完后，我们发现四种情况均会留下两个同行、列相邻的0，使得我们可以实现对所有剩余的'1'，一次操作消除1个'1',从而最大化操作次数
题解
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 510;
int a[N][N];
int n,m,T;
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
string t;
int cnt1 = 0;//全图中1的个数
for(int i = 0;i<n;i++)
{
cin>>t;
for(int j = 0;j<t.size();j++)
{
a[i][j] = t[j] - '0';
if(a[i][j]) ++cnt1;
}
}
if(cnt1 == 0) //没有1，无法操作
{
cout<<'0'<<endl;
continue;
}
if(cnt1 == n*m) //全为1，属于cnt = 4的情形，第一次操作去掉3个'1'，亏损2个
{
cout<<cnt1 - 2<<endl;
continue;
}
int Min1 = 0x3f3f3f3f; //找全图所有存在'1'的且含'1'的个数最少的2*2方格中'1'的个数
for(int i = 0;i<n-1;i++)
{
for(int j = 0;j<m-1;j++)
{
int t = 0;
t += a[i][j] + a[i+1][j] + a[i][j+1] + a[i+1][j+1];
if(t>0) Min1 = min(Min1,t);//注意：t必须大于0
}
}
int ans = 0;
if(Min1<=2) ans = cnt1; //cnt = 1 or 2,第一次操作可以只去掉一个'1'，不存在1的个数的亏损
else if(Min1 == 3) ans = cnt1 - 1;//cnt = 3，第一次操作最少去掉两个'1',亏损1个
else ans = cnt1 - 2; //cnt = 4,第一次操作最少去掉3个'1'，亏损2个
cout<<ans<<endl;
}
return 0;
}
D1. Xor-Subsequence (easy version)
思路：二维DP O(N*256)
题解
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int a[N],f[N];
int n,T;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i = 0;i<n;i++)
{
cin>>a[i];
}
int ans = 0;
for(int i = 0;i<n;i++) //枚举下标
{
f[i] = 1;
for(int j = i >> 19 << 19 ;j<i;j++) //枚举b序列的下标 2^8 = 256 > 200
{
if((a[j] ^ i) < (a[i] ^ j)) f[i] = max(f[i],f[j] + 1);
ans = max(ans,f[i]);
}
}
cout<<ans<<endl;
}
return 0;
}