5.6 拼多多笔试

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100500
ll a[MAXN];
int n,m;
ll ans;
int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++)
        scanf("%lld", &a[i]);
    sort(a, a+n);
    ans = 0;
    for(int i = 1 ; i < n ; i++){
        if(a[i] <= a[i-1]){
            ans += 1LL * (a[i-1] - a[i] + 1);
            a[i] = a[i-1] + 1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 1005
int a[MAXN];
bool vis[MAXN];
int n,m;
int ans, sum;
void dfs(int s, int l, int num){
    if(num == 4){
        ans = 1;
        return ;
    }
    if(l == sum)
        dfs(0, 0, num+1);
    for(int i = s ; ans == 0 && i < n ; i++){
        if(vis[i] || l + a[i] > sum)
            continue;
        vis[i] = true;
        dfs(i+1, l + a[i], num);
        vis[i] = false;
    }
    return;
}
int main()
{
    int tt,ca = 1;
    scanf("%d",&tt);
    while(tt--){
        scanf("%d", &n);
        sum = 0;
        ans = 0;
        for(int i = 0 ; i < n ; i++){
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a, a+n);
        if(sum % 4 != 0 || a[n-1] > sum / 4){
            printf("NO\n");
            continue;
        }
        sum /= 4;
        memset(vis, 0, sizeof(vis));
        dfs(0, 0, 0);
        if(ans == 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 1005
int n = 2;
struct mat
{
    int at[5][5];
};
mat mul(mat a,mat b)
{
    mat ret;
    memset(ret.at,0,sizeof(ret.at));
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<n;k++)
        {
            if(a.at[i][k])
            {
                for(int j=0;j<n;j++)
                {
                    ret.at[i][j]+=a.at[i][k]*b.at[k][j];
                    ret.at[i][j] %= 3;
                }
            }
        }
    }
    return ret;
}
mat expo(mat a,int k)
{
    mat e;
    memset(e.at,0,sizeof(e.at));
    for(int i=0;i<n;i++)  e.at[i][i]=1;
    while(k)
    {
        if(k&1)
            e=mul(a,e);
        a=mul(a,a);
        k>>=1;
    }
    return e ;
}
int main()
{
    int tt,ca = 1;
    int k,p,q;
    scanf("%d",&tt);
    mat I;
    I.at[0][0] = 0;
    I.at[0][1] = 1;
    I.at[1][0] = 1;
    I.at[1][1] = 1;
    while(tt--){
        scanf("%d %d %d", &p, &q, &k);
        p %= 3;
        q %= 3;
        mat t = expo(I, k - 1);
        int ans = t.at[1][0] * p + t.at[1][1] * q;
        if(ans  % 3 == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100500
int a[MAXN];
vector<pair<int, int>> b[MAXN];
int n,m;
int ans;
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}
int main()
{
    scanf("%d",&n);
    ll ans = 0;
    for(int i = 0 ; i < n ; i++){
        scanf("%d", &a[i]);
        ans = max(ans, 1LL * a[i]);
    }
    b[0].push_back(make_pair(a[0], 0));
    for(int i = 1 ; i < n ; i++){
        int last = -1;
        for(int j = 0 ; j < b[i-1].size() ; j++){
            int t = gcd(b[i-1][j].first, a[i]);
            int id = b[i-1][j].second;
            if(t == last)
                continue;
            last = t;
            b[i].push_back(make_pair(t, id));
            ans = max(ans, 1LL * t * (i-id + 1));
        }
        b[i].push_back(make_pair(a[i], i));
    }
    printf("%lld\n",ans);
    return 0;
}