牛客六

1.B爱恨的纠葛（先将ab排序，再二分查找ab元素间差值最小的一对，再从a和c中找出对应下标（因为第二个数组不能动），再交换a的两个下标位置的值）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1000005];
 4 int b[1000005];
 5 int c[1000005];
 6 void solve(int n)
 7 {
 8     for(int i=1;i<=n;i++)
 9     {
10         cin>>a[i];
11     }
12     for(int i=1;i<=n;i++)
13     {
14         cin>>b[i];
15         c[i] = b[i];
16     }
17     sort(a+1,a+n+1);
18     sort(b+1,b+n+1);
19     int l   = 1 ,r   = 1;
20     int p1 = 0, p2 = 0;
21     int Min = 0x3f3f3f;
22     while(l<=n && r<=n)
23     {
24         if(abs(a[l]-b[r])<Min)
25         {
26             p1 = a[l];
27             p2 = b[r];
28             Min = abs(a[l]-b[r]);
29         }
30         if(a[l]<b[r])
31         {
32             l++;
33         }
34         else
35         {
36             r++;
37         }
38     }
39     int x = 1;
40     for(int i=1;i<=n;i++)
41     {
42         if(p1==a[i])
43         {
44             x = i;
45             break;
46         }
47     }
48     int y = 1;
49     for(int i=1;i<=n;i++)
50     {
51         if(p2 == c[i])
52         {
53             y = i;
54             break;
55         }
56     }
57     swap(a[x],a[y]);
58     for(int i=1;i<=n;i++)
59     {
60         cout<<a[i]<<" ";
61     }
62 }
63 signed main() {
64     ios::sync_with_stdio(0);
65     cin.tie(0) , cout.tie(0);
66     int n;
67     cin>>n;
68     solve(n);
69     return 0;
70 }

2.C心绪的解剖（用一个数组存斐波那契数列，通过big函数找出剩下的最大的斐波那契数，再递归直到left为0，将这些数存入数组，如果数组空间小于等于三，说明成立，缺位用0补位即可，如果大于三则不成立输出-1）

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define N 91
 4 using namespace std;
 5 int b;
 6 ll b1[1000];
 7 long long fib[N]={1,2};
 8 void fi()
 9 {
10     for (int i = 2; i < N; i++)
11         fib[i] = fib[i - 2] + fib[i - 1];
12 }
13 int big(long long n)
14 {
15     int k;
16     for (k = 0; k < N; k++)
17         if (fib[k + 1] > n)return k;
18     return 0;
19 }
20 void solu(long long n, bool first)
21 {
22     int k;
23     if(big(n))k= big(n);
24     long long left = n - fib[k];
25     if (first)
26     {
27         if (!left)
28         {
29             b1[b++]=n;
30             return;
31         }
32         if (left>0)
33             solu(left, false);
34         b1[b++]=fib[k];
35     }
36     else
37     {
38         if (left>0)
39             solu(left, false);
40         b1[b++]=fib[k];
41     }
42 }
43 int main()
44 {
45     fi();
46     int T;
47     cin >> T;
48     while (T--)
49     {
50         long long n;
51         cin >> n;
52         b=0;
53         solu(n, true);
54         if(b==3)
55         {
56             for(int i=0;i<3;i++)cout<<b1[i]<<" ";
57         }
58         else if(b<3)
59         {
60             for(int i=0;i<b;i++)cout<<b1[i]<<" ";
61             for(int i=0;i<3-b;i++)cout<<0<<" ";
62         }
63         else cout<<-1<<endl;
64         cout << endl;
65     }
66     return 0;
67 }

3.I时空的交织（该题是很典型的求子矩阵最大和问题，但是由于空间限制，只能通过线性求最大子序列来求）

空间小的常规做法

#include <bits/stdc++.h>空间超了
using namespace std;
const int N=10001;
#define int long long
int a[N][N],f[N],d[N];
signed main()
{
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1), b(m + 1);
    vector<vector<int>> c(n + 1, vector<int>(m + 1));
    vector<vector<int>> sum(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for(int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            c[i][j]=a[i]*b[j];
            c[i][j] +=c[i-1][j];
        }
    int ans=-2e9;
    for (int i=1;i<=n;i++)
        for (int k=1;k<=i;k++)
        {
            memset(f,0,sizeof f);
            memset(d,0,sizeof d);
            for (int j=1;j<=m;j++)
            {
                f[j]=c[i][j]-c[i-k][j];
                d[j]=max(d[j-1]+f[j],f[j]);
                ans=max(ans,d[j]);
            }
        }
    cout<<ans;
    return 0;
}

该题做法

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int a[100000],b[100000];
 5 signed main()
 6 {
 7      int m,n;
 8      cin>>n>>m;
 9      int p,q;
10      int Max1=LLONG_MIN,Min1=LLONG_MAX ;
11      for(int i=0;i<n;i++)
12      {
13          cin>>a[i];
14          if(i<1)p=a[i],q=a[i];
15          else p=max(a[i],p+a[i]),q=min(a[i],q+a[i]);
16          Max1=max(p,Max1),Min1=min(q,Min1);
17      }
18     int Max2=LLONG_MIN,Min2=LLONG_MAX ;
19     for(int i=0;i<m;i++)
20     {
21         cin>>b[i];
22         if(i<1)p=b[i],q=b[i];
23         else p=max(b[i],p+b[i]),q=min(b[i],q+b[i]);
24         Max2=max(p,Max2),Min2=min(q,Min2);
25     }
26     int end=LLONG_MIN;
27     end=max({end,Max1*Max2,Max1*Min2,Min1*Max2,Min1*Min2});
28     cout<<end<<endl;
29     return 0;
30 }