A. Maximum Increase
题意：
找 最长的 连续的严格上升的子序列，输出它的长度。
解题：
因为要求连续，所以一边扫一遍统计就可以。
事后觉得我写的麻烦了些o(╯□╰)o。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> using namespace std; int a[100010]; int main() {int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}int s=0,e=0,ans = 1;for(int i=1;i<n;i++){if(a[i]>a[i-1]){e++; ans = max(e-s+1,ans); } else {s=i;e=i;}}printf("%d\n",ans);return 0; }
B. Powers of Two
题意：
给定长度为 n 的序列，找出有多少对数相加的和 属于 2 的 x 次幂 。
解题：
先预处理出 2的 x 次幂放在数组， 序列另用一个 map 容器存并记录个数。
然后用 2的 x 次幂 减去序列各元素 ，查找 map 容器里是否有与之对应的数出现。
出现的次数就是对数。
需要注意，如果差和减数一样，则要减 1，即它自己。
最后答案 除 2，因为如果存在满足条件的数，两两之间会又算一遍 。
（写的时候蠢蠢的之前没注意看数据范围= =，结果都懂得...）
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<map> #define ll __int64 using namespace std; map<ll,int>m; ll a[100010]; int main() {ll e[50]={1,1};int cnt=0;for(int i=1;i<50;i++){if((e[i-1]*2) > (1e9+1e9) ) break;e[i] = e[i-1]*2 ;cnt++;}int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%I64d",&a[i]);m[a[i]]++;}sort(a,a+n);ll ans = 0;for(int i=1;i<=cnt;i++){for(int j=0;j<n;j++){if(a[j] >= e[i]) break;ll x = e[i]-a[j];if(x==a[j]) ans += ( m[x]- 1 );else ans += m[x];} }cout<<ans/2<<endl; }
C. Cellular Network
题意：
n 个城市， m 个塔，在一条直线上，每个塔可以给附近的城市提供网络，
求所有城市都能够覆盖网络的情况下，塔与城市间的最短的距离。
第一行输入 n ，m ；表示城市与塔的数量；
随后 n 个数 与 m 个数， 表示城市和塔的坐标。
解题：
扫一遍城市的坐标，二分找到离此城市最近的那座塔，（就是跟此城市坐标最近的一个数），
这样得到的距离是最近的，不断更新即可。
不知道是我自己问题还是二分就这样 o(╯□╰)o ，自己二分找到的总是第一个大于或等于城市坐标的数，
所以还要和前一个位置的数再比一下。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #define ll __int64 using namespace std; const int maxn = 100010; int n,m; ll c[maxn],t[maxn], dis = 0;; int main() {t[0] = -1e9;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%I64d",&c[i]);for(int i=1;i<=m;i++)scanf("%I64d",&t[i]);ll ans = 0;for(int i=0;i<n;i++){int l = 1, r = m;while(l<r){ int mid = (l+r)/2;if(t[mid]>=c[i]) r=mid;else l = mid+1;} ll a2 = abs(t[l] - c[i]);if(l-1>0){ll a1 = abs(t[l-1]-c[i]); ans = max(ans, min(a1,a2)); }else ans = max(ans, a2); }cout<<ans<<endl;return 0; }