给出两个分数a/b,c/d的四个数,每次可以向其中一个数乘任意一个数,问最少使得两分数相等的操作次数。
思路:对于分数相等,可以化为a*d==c*b,若满足条件,直接输出0;对于两分数其中一个为0时,输出1,两数乘积有倍数关系也是1,否则为2。
AC Code:
- #include
-
- typedef long long ll;
- int t;
- ll a,b,c,d;
-
- int main(){
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- std::cin>>t;
- while(t--){
- std::cin>>a>>b>>c>>d;
- if(a*d==b*c) std::cout<<0<<'\n';
- else if(a==0||c==0) std::cout<<1<<'\n';
- else if(a*d%(b*c)==0||b*c%(a*d)==0) std::cout<<1<<'\n';
- else std::cout<<2<<'\n';
- }
- return 0;
- }
os:赛时被一下子卡住了。。。
给出一个序列,从其中任选一个区间,该区间的值为该区间最大数-最小数+除去该区间剩余数字中的最大数-最小数,问该值最大是多少。
思路:两个最大数的最大值是数组的最大和次大值,两个最小数最小是数组中的最小值和次小值,可以证明总是可以取到这四个值。
AC Code:
- #include
-
- typedef long long ll;
- const int N=1e5+5;
- const int mod=998244353;
- int t,n;
- ll a[N];
-
- int main(){
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- std::cin>>t;
- while(t--){
- std::cin>>n;
- for(int i=1;i<=n;i++){
- std::cin>>a[i];
- }
- std::sort(a+1,a+1+n);
- ll ans=a[n]+a[n-1]-a[1]-a[2];
- std::cout<
'\n'; - }
- return 0;
- }
给出一个矩阵,该矩阵由0和1组成,每次可以选择一个L型,至少包含一个1,将其中的数全都赋成0,最多可以操作几次。
思路:找到0分布最多的位置,这样对1的浪费最少,若最多0的位置有1个0,则要多花费一个1;若没有0,则要多花费2个0,否则对0的利用达到最大化。
AC Code:
- #include
-
- typedef long long ll;
- const int N=505;
- const int mod=998244353;
- int t,n,m;
- char a[N][N];
-
- int main(){
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- std::cin>>t;
- while(t--){
- std::cin>>n>>m;
- int cnt=0;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- std::cin>>a[i][j];
- if(a[i][j]=='1') cnt++;
- }
- }
- int ans=0;
- for(int i=1;i
- for(int j=1;j
- int cc=0;
- if(a[i][j]=='0') cc++;
- if(a[i+1][j]=='0') cc++;
- if(a[i][j+1]=='0') cc++;
- if(a[i+1][j+1]=='0') cc++;
- ans=std::max(ans,cc);
- }
- }
- if(ans==1){
- std::cout<
-1<<'\n'; - }
- else if(ans==0){
- std::cout<
-2<<'\n'; - }
- else std::cout<
'\n'; - }
- return 0;
- }
D1. Xor-Subsequence (easy version)
给出数组a,要求找到一个最长的下标子序列b,使得在b范围内满足
思路:可以类比最长上升子序列来写DP,但是n^2显然不行,考虑优化。因为a数组中的值最大为200,则当在a中位置相差很远时,这个不等式的结果是一定的。所以DP转移时不需要枚举太靠前的位置,具体距离来说,200最多二进制为时2^7=128,异或的结果最多是把二进制7位所有的0改为1,最多为256,当然大一些也问题不大,枚举计算即可。
AC Code:
- #include
-
- typedef long long ll;
- int t,n;
-
- int main(){
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- std::cin>>t;
- while(t--){
- std::cin>>n;
- std::vector<int>a(n+1,0),f(n+1,0);
- for(int i=0;i
- std::cin>>a[i];
- }
- for(int i=0;i
- f[i]=1;
- for(int j=std::max(0,i-256);j
- if((a[i]^j)>(a[j]^i))
- f[i]=std::max(f[i],f[j]+1);
- }
- }
- std::cout<<*max_element(f.begin(),f.end())<<'\n';
- }
- return 0;
- }
os:看了好久的题解QWQ
-
相关阅读:
苍穹外卖(一)
React 状态管理 - Redux 进阶(上)
158_模型_Power BI 使用 DAX + SVG 打通制作商业图表几乎所有可能
天翼物联发布5G纺织行业定制专网
反射课后习题及做题记录
A*学习和修改
阿里云启动实例进入了急救模式解决办法
数据结构-顺序表
VR全景:为户外游玩体验插上科技翅膀
APP推广ZB简介
-
原文地址:https://blog.csdn.net/m0_62289613/article/details/126451393