2020.03.14 BAPC 2019 Preliminaries
A题
通过分析便可得知，只要找出两行各自的最大值比较就可，若最大值不相同，便不可行。
解题代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cmath> 5 #include <string> 6 #include <cstring> 7 #include <map> 8 using namespace std; 9 const long long N = 1e9 + 7; 10 typedef long long ll; 11 map <char,int> ma; 12 13 int main() 14 { 15 int n,m,nmax = 0,mmax = 0; 16 int num; 17 cin >> n >> m; 18 for(int i = 0;i < n;i++) 19 { 20 scanf("%d",&num); 21 nmax = max (num,nmax); 22 } 23 for(int i = 0;i < m;i++) 24 { 25 scanf("%d",&num); 26 mmax = max (num,mmax); 27 } 28 if(mmax != nmax) 29 cout << "impossible" << endl; 30 else 31 cout << "possible" << endl; 32 33 return 0; 34 }
F题
题目大意：
给你一个n，输出m,k符合n = m 2 - k 2 ,若不存在这样的两个值输出"impossible"，（答案不唯一）。
思路:
很容易想到m2 - k2 = (m-k)(m+k) ，所以令x = m - k ;则有x(x+2k) = n;所以可以从1~n1/2 内遍历更新情况就可。
解题代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cmath> 5 #include <string> 6 #include <cstring> 7 using namespace std; 8 const long long N = 1e6+10; 9 typedef long long ll; 10 int main() 11 { 12 int n,x,k; 13 cin >> n; 14 for(x = 1; x <= sqrt(n);x++) 15 { 16 if(n % x == 0 && (n/x - x) % 2 == 0 ) 17 { 18 k = (n/x - x)/2; 19 break; 20 } 21 } 22 if(x > sqrt(n)) 23 cout << "impossible" << endl; 24 else 25 cout << x+k << " " << k << endl; 26 27 return 0; 28 }
I题
题目大意：
给出长度为n的一组数，找出一个k，使得位置为1~k的平方和 与 位置为k+1~n的和 的乘积最大化。
思路:
解题代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cmath> 5 #include <string> 6 #include <cstring> 7 #include <map> 8 using namespace std; 9 const long long N = 1e9 + 7; 10 typedef long long ll; 11 map <char,int> ma; 12 ll a[1000010]; 13 ll b[1000010]; 14 int main() 15 { 16 int n,num; 17 ll maxnum = -1; 18 scanf("%d",&n); 19 for(int i = 1;i <= n;i++) 20 { 21 scanf("%d",&num); 22 a[i] = a[i-1] + num; 23 b[i] = b[i-1] + num * num; 24 } 25 for(int k = 1;k <= n-1;k++) 26 { 27 ll sum1 = b[k]; 28 ll sum2 = a[n] - a[k]; 29 maxnum = max(maxnum ,sum1*sum2); 30 31 } 32 33 printf("%lld\n",maxnum); 34 return 0; 35 }
