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;
} 第三题：斐波那契数列。矩阵快速幂，3取模
#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;
} 第四题：连续n个数，使得gcd*个数最大。数字变多，gcd非递增。每次保留gcd相同时最远的下标。
#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;
} 
