本文主要是介绍lives，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
机器人跳跃问题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[100010];int maxh=0;
bool check(int x){for(int i=1;i<=n;i++){x=2*x-a[i];if(x<0)return 0;if(x>maxh)return 1;}
}
int main(){cin>>n;for(int i=1;i<=n;i++)scanf("%d",a+i),maxh=max(maxh,a[i]);int l=1,r=1e5;while(l<r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}cout<<l;
}
四平方和
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;
int main(){int n;cin>>n;for(int a=0;a*a<n;a++){for(int b=a; a*a+b*b <n; b++){for(int c=b; a*a+b*b+c*c<n;c++){int t=n-a*a-b*b-c*c;int d=sqrt(t);if(d*d==t){printf("%d %d %d %d",a,b,c,d);return 0;}}}}
}
本来三重循环是能过的，因为a和b都在较小的时候找到了答案，不过那是以前，不知都什么时候数据加强了，所以只能过10/11
接下来展示O(n^2)的二分法
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e8 + 10;
int h[N];
int main() {int n;cin >> n;//打表，找出1 - n，所有完全平方数两两之和，如果存在只记第一次出现（题目要求找出字典序小的）for (int i = 0; i * i * 2<= n; i++) {for (int j = i; j * j + i * i <= n; j++) {if (!h[i * i + j * j])h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况}}//0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2; for (int i = 0; i * i * 4 <= n; i++) {for (int j = i; j * j + i * i <= n / 2; j++) {int t = n - i * i - j * j;if (h[t]) {int c = h[t] - 1; //防止开根号后因为精度关系,向下取整,例:25 开根号得到4.99999向下取整为4;int d = (sqrt(t - c * c) + 1e-4);printf("%d %d %d %d", i, j, c, d); return 0;}}}return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e8+1;
struct Sum{int s,c,d;bool operator< (const Sum &t)const{if(s!=t.s)return s<t.s;if(c!=t.c)return c<t.c;return d<t.d;}
}sum[N];
int n,m;
int main(){cin>>n;for(int c=0;c*c<=n;c++){for(int d=c;c*c+d*d<=n;d++){sum[m++]={c*c+d*d,c,d};}}sort(sum,sum+m);for(int a=0;a*a<=n;a++){for(int b=a;a*a+b*b<=n;b++){int t=n-a*a-b*b;int l=0,r=m-1;while(l<r){int mid=l+r>>1;if(sum[mid].s>=t)r=mid;else l=mid+1;}if(sum[l].s==t){printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);return 0;}}}
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e8+1;
// struct Sum{
// int s,c,d;
// bool operator< (const Sum &t)const{
// if(s!=t.s)return s<t.s;
// if(c!=t.c)return c<t.c;
// return d<t.d;
// }
// }sum[N];
int sum[N];
int n,m;
int main(){cin>>n;for(int c=0;c*c*2<=n;c++){for(int d=c;c*c+d*d<=n;d++){//sum[m++]={c*c+d*d,c,d};int res=c*c+d*d;if(!sum[res])sum[res]=c+2;}}sort(sum,sum+m);for(int a=0;a*a<=n/4;a++){for(int b=a;a*a+b*b<=n/2;b++){int t=n-a*a-b*b;if(sum[t]){int c=sum[t]-2;int d=sqrt(t-c*c);printf("%d %d %d %d",a,b,c,d);return 0;}```// int l=0,r=m-1;// while(l<r){// int mid=l+r>>1;// if(sum[mid].s>=t)r=mid;// else l=mid+1;// }// if(sum[l].s==t){// printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);// return 0;// }}}
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include<unordered_map>
using namespace std;
#define x first
#define y second
#define PII pair<int,int>
unordered_map<int,PII>s;
int main(){int n;cin>>n;for(int a=0;a*a<=n;a++){for(int b=a;a*a+b*b<=n;b++){int t=a*a+b*b;if(s.count(t)==0)s[t]={a,b};}}for(int a=0;a*a<=n/4;a++){for(int b=a;a*a+b*b<=n/2;b++){int t=n-a*a-b*b;if(s.count(t)){printf("%d %d %d %d",a,b,s[t].x,s[t].y);return 0;}}}
}
用哈希表做的话，要4000多ms更慢了，数据加强了之后就TLE了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int t,n;
int a[N],b[N];bool check(int x){int res=0;for(int i=1;i<=t;i++){res+=(a[i]/x)*(b[i]/x);if(res>=n)return 1;}return 0;
}int main(){cin>>t>>n;for(int i=1;i<=t;i++)cin>>a[i]>>b[i];int l=1,r=1e5;while(l<r){int mid=l+r>>1;if(!check(mid))r=mid;else l=mid+1;}cout<<l-1;//这个题目要我求的答案就是我二分的时候要设的变量，很巧吧很简单吧哈哈哈
}
子矩阵的和
二维前缀和
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,a[1001][1001],t;
long long sum[1001][1001];
int main(){cin>>n>>m>>t;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];sum[i][j]+=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];}}while(t--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;long long ans=sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];cout<<ans<<endl;}}
k倍区间
从O(n^3)——>O(n 2)——>O(n)
**#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long s[1000001],cnt[1000001];
int main(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){scanf("%lld",s+i);s[i]+=s[i-1];}cnt[0]=1;long long res;for(int i=1;i<=n;i++){res+=cnt[s[i]%k];cnt[s[i]%k]++;}cout<<res;
}**
这篇关于lives的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
