【牛客练习赛64】前三题题解

A

解法：贪心，构造
题意：给定了n个1,m个2,k个4，构造一个n+m+k的序列，求1412的子序列最多个数。
思路：很显然，将1分为两堆，把所有的4都放进两堆的中间，所有的2放在最右边时，能获得最多的1412子序列个数，例如1412,1144112,144122,...

最终输出 $(n/2)*(n-n/2)*m*k$
代码如下:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<fstream>
#define mmset(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

inline char nc()
{
    static char buf [100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    static char c=nc();
    int x=0,f=1;
    for(;c>'9'||c<'0';c=nc())
        if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=nc())
        x=(x<<3)+(x<<1)+c-48;
    return x*f;
}


const int N = 2e1 + 10;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;


int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    int t;
    LL n, m, k, ans;
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        ans = 0;
        if(n < 2|| m < 1|| k < 1)    //这一步其实不必要
            cout << 0 << endl;
        else{
            LL tmp = n / 2;
            n -= tmp;
            ans = n * tmp * m * k;
            cout << ans << endl;
        }
    }
    return 0;
}

B

思路：统计每一个点的度数，那么距离该点为2的个数为与它相连的点的度数减1之和或者说与它相连的点的度数之和减去相连点的个数。
代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<fstream>
#define mmset(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

inline char nc()
{
    static char buf [100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    static char c=nc();
    int x=0,f=1;
    for(;c>'9'||c<'0';c=nc())
        if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=nc())
        x=(x<<3)+(x<<1)+c-48;
    return x*f;
}

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int tree[N];
struct node{
    int x, y;
}root[N];
LL ans[N];

int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    int t, x, y;
    cin >> t;
    for(int i = 1;i < t;i++){
        cin >> root[i].x >> root[i].y;
        tree[root[i].x]++;
        tree[root[i].y]++;
    }
    for(int i = 1;i < t;i++){
        ans[root[i].x] += tree[root[i].y] - 1;
        ans[root[i].y] += tree[root[i].x] - 1;
    }
    for(int i = 1;i <= t;i++)
        cout << ans[i] << endl;
    return 0;
}

C

解法：数学
思路:看到这条式子 $\begin{matrix} \sum_{l=1}^n\sum_{r=l}^n\sum_{i=l}^r\sum_{j=i}^r a_i*a_j mod 1e9+7\end{matrix}$ ，第一反应可能会觉得头大。那么来化简一下。

假设 $n=4$

$l=1$ 时，可以写出 $a_1*(a_1 + a_1 + a_2 + a_1 + a_2 + a_3 + a_1 + a_2 + a_3 + a_4) + a_2 * (a_2 + a_2 + a_3 + a_2 + a_3 + a_4) + a3 * (a_3 + a_3 + a_4) + a_4 * a_4$

化简一下就得到， $a_1 * (4 * a_1 + 3 * a_2 + 2 * a_3 + 1 * a_4) + a_2 * (3 * a_2 + 2 * a_3 + 1 * a_4) + a_3 * (2 * a_3 + 1 * a_4) + a_4 * a_4$

同理， $l=2$ 时，可以得到 $a_2 * (3 * a_2 + 2 * a_3 + 1 * a_4) + a_3 * (2 * a_3 + 1 * a_4) + a_4 * a_4$

$l=3$ 就有 $a_3 * (2 * a_3 + 1 * a_4) + a_4 * a_4$

$l=4$ 就有 $a_4*_4$
整理一下变成 $1 * a_1*(4 * a_1 + 3 * a_2 + 2 * a_3 + 1 * a_4) + 2 * a_2 * (3 * a_2 + 2 * a_3 + 1 * a_4) + 3 * a_3 * (2 * a_3 + 1 * a_4) + 4 * a_4 * a_4$

可以发现这个式子就变成了 $\begin{matrix} \sum_{i=1}^n a_i * \sum_{j=i}^n ((n-j+1)*a_j) \end{matrix}$

那么这道题就完成了，可以用前缀和来处理 $\begin{matrix} \sum_{j=i}^n ((n-j+1)*a_j) \end{matrix}$

代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<fstream>
#define mmset(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

inline char nc()
{
    static char buf [100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    static char c=nc();
    int x=0,f=1;
    for(;c>'9'||c<'0';c=nc())
        if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=nc())
        x=(x<<3)+(x<<1)+c-48;
    return x*f;
}

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
LL a[N];
LL b[N];
LL s[N];

int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // freopen("1.in","r", stdin);
    // freopen("out.out","w", stdout);
    LL n, ans = 0;
    cin >> n;
    s[0] = 0;
    for(LL i = 1;i <= n;i++){
        cin >> a[i];
        b[i] = ((n-i+1) * a[i]) % MOD;     //求(n-i+1)*ai
        s[i] = (b[i] + s[i-1]) % MOD;    //前缀和处理
    }
    for(LL i = 1;i <= n;i++){
        LL cnt = s[n] - s[i-1] + MOD; 
        /*血泪教训，因为在计算前缀和的时候取了模，那么前缀和数组里的数组不再成单调，就可能最后一项减去i-1项时出现负数，导致最后结果算错，加上1个MOD就能处理掉负数的情况*/
        ans = (ans + (i * (a[i] * cnt % MOD) % MOD) % MOD) % MOD;
    }
    cout << ans << endl;
    return 0;
}