2023牛客寒假算法基础集训营3
A
给你一个数组，我们可以对这个数进行除二操作如果这个数是偶数，我们需要知道进行若干次操作后n个数的和的最小值
这个我们可以直接模拟，但是如果是0或者是负数，那么我们就不需要进行除二操作了
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n;
int a[maxn];
int fun(int x)
{
if (x&1) return x;
while (x%2==0)
{
x/=2;
if (x==0)return 0;
}
return x;
}
signed main ()
{
cin>>n;
int ans=0;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
if (x<0) ans+=x;
else
{
ans+=fun(x);
}
}
cout<<ans<<'\n';
return 0;
}
B
我们有这么几种积木 1XK（K>=1 k<=(n+1)/2),问我们可以拿任意大小的积木n块，可以组成一个正方形，其中边长最长的是多少
对于这一道题，我是二分来写的
但是这个二分答案的区间一定要找对，我就是没有找对
这个区间我一开始是n/2到n,wa了
后来改成了n/2-1到n，结果过了，差一点，早知道就把范围开大一点了
check函数我们要怎么判断
我们要判断要构造成一个边长为l的正方形，如果它需要的最小的积木大于n,那么就一定是不符合条件的
我们要怎么知道一个边长为l的正方形，其中积木的最长宽度为x,那么我们有这么几种构造方式
然后就可以写代码了
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n;
int mi,mx;
bool check(int l)
{
int x=(n+1ll)/2ll;
int cnt=0;
if (l>x) cnt=l+2ll*(l-x);
else cnt=x;
return cnt<=n;
}
void solve()
{
cin>>n;
if (n==1)
{
cout<<1<<'\n';
return ;
}
if (n==2)
{
cout<<-1<<'\n';
return ;
}
int cnt=(n+1ll)/2ll;
int r=n;
int l=n/2-1;//差一点，真的是差一点，要向下 太难过了，早知道就从1开始也好呀
int ans=-1;
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
C
这一道题是要我们构造一个数组满足下标和值的差要么是2，要么是3，如果构造不出来，那么就输出-1
对于这一个构造
我们可以让四个为一段，如长度为4时
3 4 1 2（i和i+2放在一起，ans[i]=i+2,ans[i+2]=i,那么所有的差值都是2）
那么对于n%4==0,我们可以直接让ans[i]=i+2,ans[i+2]=i
对于n%4==1的情况，我们多出了一个，那么我们可以让前5个变成我们想要的
3 4 5 1 2这前5个是满足条件的，后面在按照四个四个为一段的来构造
如果n%4==2
那么前6个我们可以按照这样的方式来
4 5 6 1 2 3，这6个是满足条件的，后面还是按照四个四个的来
如果n%4==3
那么我们的前11个都是固定的，但是我还发现n=7的时候是不存在的
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 3,4 | 4,5 | 1,5,6 | 1,2,6,7 | 2,3 | 3,4 | 4,5 |
我们可以观察到下标1 2 6 7这四个下标对应的值只有3个，那么就一定是不可以的
对于其他的
我们先构造出前11个下标的值
3 4 5 1 2 9 10 11 6 7 8是满足条件的，后面的按照四个四个的来
#include <bits/stdc++.h>
using namespace std;
int main ()
{
int n;
cin>>n;
if (n<=3)
{
cout<<-1<<'\n';
return 0;
}
map<int,int>ans;
if (n%4==0)
{
for (int i=1;i<=n;i++)
{
if (ans[i]) continue;
ans[i]=i+2;
ans[i+2]=i;
}
}
else if (n%4==1)
{
if ((n-5)%4!=0)
{
cout<<-1<<'\n';
return 0;
}
ans[1]=3;
ans[2]=4;
ans[3]=5;
ans[4]=1;
ans[5]=2;
for (int i=6;i<=n;i++)
{
if (ans[i]) continue;
ans[i]=i+2;
ans[i+2]=i;
}
}
else if (n%4==2)
{
if ((n-6)%4!=0)
{
cout<<-1<<'\n';
return 0;
}
ans[1]=4;
ans[2]=5;
ans[3]=6;
ans[4]=1;
ans[5]=2;
ans[6]=3;
for (int i=7;i<=n;i++)
{
if (ans[i]) continue;
ans[i]=i+2;
ans[i+2]=i;
}
}
else if (n%4==3)
{
if (n<11)
{
cout<<-1<<'\n';
return 0;
}
if ((n-11)%4!=0)
{
cout<<-1<<'\n';
return 0;
}
ans[1]=3;
ans[2]=4;
ans[3]=5;
ans[4]=1;
ans[5]=2;
ans[6]=9;
ans[7]=10;
ans[8]=11;
ans[9]=6;
ans[10]=7;
ans[11]=8;
for (int i=12;i<=n;i++)
{
if (ans[i]) continue;
ans[i]=i+2;
ans[i+2]=i;
}
}
for (int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}
D
这个就是对于此时的一个数x,我们可以减少它的因子，小红先手，谁先减到0谁就输
这个是我最快知道答案的一个博弈了
对于一个奇数，那么它的因子一定也是奇数，那么此时这个人进行操作后是偶数，如果不是1，那么还是一个奇数，如果是1，那么它必败，如果它还有下一步，那么它后面的一个人是偶数，它可以减一把数还变成奇数，那么下一轮此人还是在奇数，知道此人到达1，输了，所以奇数点是必败点，而偶数点一定可以变成奇数，到达必败点，那么偶数必胜
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main ()
{
int n;
cin>>n;
if (n&1)
{
cout<<"yukari\n";
}
else
{
cout<<"kou\n";
}
return 0;
}
E
这个题大意是给你两个点A，B，要我们找到一个整数点C，让ABC成为一个等腰直角三角形，并且AB为斜边
在比赛的时候真是想了好多，还打算求出直线方程，哈哈
后来赛后才知道这个可以用向量的方法求解
根据有两条垂直且长度一样的向量
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main ()
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;//向量垂直乘积为0
int x=x1+x2-(y2-y1);
int y=y1+y2+x2-x1;
if (x&1||y&1)
{
cout<<"No Answer!\n";
}
else
{
cout<<x/2<<" "<<y/2<<'\n';
}
return 0;
}
F
签到题
直接输出42
42
G
有一个字符串，由阿拉伯数字和？ =组成，我们要在？填+或者-或者#满足这个式子即可
a#b 是 a^a %b
对于a^a %b ，为了防止爆long long ,可以变成 a%b ^a %b
然后题目告诉我们？不超过12 ，那么我们可以知道只有 不超过 3^12种不同的方式，所以我们可以一个一个的找
每一个？的符号都试一次
用dfs
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
string s;
int n;
int num[maxn];
char op[maxn];
int ans;
int ksm(int x,int p,int mod)
{
int res=1;
x%=mod;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res;
}
int add(int x,int y)
{
return (x+y);
}
int sub(int x,int y)
{
return (x-y);
}
int get(int x,int y)
{
int res=ksm(x%y,x,y);
return res;
}
bool dfs(int now,int sum)
{
if (now==n+1)
{
if (sum==ans) return true;
return false;
}
op[now]='+';
if (dfs(now+1,add(sum,num[now])))
{
return true;
}
op[now]='-';
if (dfs(now+1,sub(sum,num[now])))
{
return true;
}
op[now]='#';
if (sum<=0||num[now]<=0)
{
return false;
}
if (dfs(now+1,get(sum,num[now])))
{
return true;
}
return false;
}
signed main ()
{
cin>>s;
int tmp=0;
for (int i=0;i<s.size();i++)
{
if (s[i]=='?')
{
num[n]=tmp;
n++;
tmp=0;
}
else if (s[i]=='=')
{
num[n]=tmp;
tmp=0;
}
else
{
tmp=tmp*10+(s[i]-'0');
}
}
ans=tmp;
if (dfs(1,num[0]))
{
cout<<num[0];
for (int i=1;i<=n;i++)
{
cout<<op[i]<<num[i];
}
cout<<"="<<ans<<'\n';
}
else
{
cout<<-1<<'\n';
}
return 0;
}
I
这个题是告诉我们s(n)为n的约数和
然后会给我们一个x,我们要只要一个s(n)=x,如果有输出
对于这一道题，题中提及到如果x是偶数，x-1，x-3中至少一个是素数
那么偶数的时候我们尽量往x-1和x-3构造
如果x-1是素数，x=x-1+1 那么我们只想有1 x-1这两个约数，那么这个数一定是 （x-1)^2
如果x-3是素数，x=x-3+1+2 那么我们只想有1 2 x-3这三个个约数，那么这个数一定是 2（x-3)
但是对于1 3 5 7这几个数一定要记得特判
1 ans=1
3 ans=4
5 ans=-1
7 ans=8
7的时候为1 3 3按照我后面的，其实9是不对的，而是8 1 2 4
如果x是奇数
对于x-1,我们知道一定存在两个素数的和为x-1(偶数)
所以我们只需要遍历所有可能和为x-1的两个数，如果两个都是素数，那么这个就是答案（不可以出现合数，否则会多出其他的约数）
所以我们还需要进行欧拉筛
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
int t,x;
int prime[maxn];
bool is[maxn];
int cnt;
void init()
{
for (int i=2;i<=1e6;i++)
{
if (!is[i])
{
prime[++cnt]=i;
}
for (int j=1;j<=cnt&&i*prime[j]<=1e6;j++)
{
is[i*prime[j]]=true;
if (i%prime[j]==0) break;
}
}
return ;
}
void solve()
{
cin>>x;
if (x==5)
{
cout<<-1<<'\n';
return ;
}
if(x==1){cout<<2<<'\n';return;}//1也要
if(x==3){cout<<4<<'\n';return;}//3的时候要特判，1和2是4
if(x==5){cout<<-1<<'\n';return;}
if(x==7){cout<<8<<'\n';return;}//7的时候为1 3 3按照我后面的，其实9是不对的，而是8 1 2 4
if (x%2==0)
{
int ans;
if (!is[x-1])
{
ans=(x-1ll)*(x-1ll);
cout<<ans<<'\n';
return ;
}
if (!is[x-3])
{
ans=(x-3ll)*2ll;
cout<<ans<<'\n';
return ;
}
}
else
{
for (int i=2;i<=1e6&&x-1-i>=2;i++)
{
if (!is[i]&&!is[x-1-i])
{
int ans=i*(x-1ll-i);
cout<<ans<<'\n';
return ;
}
}
}
cout<<-1<<'\n';
}
signed main ()
{
cin>>t;
init();
while (t--)
{
solve();
}
return 0;
}
K
给你一串数，a1代表第一个第一个素数有a1个，ai代表第i个质数数有ai个
f(i)为前i个数乘积的因子数
我们需要构造一个数组让f(i)的和最大
而对于一个数，我们可以把这个数变成pi^2 pj^3这种形式，这个数的因子数为 （2+1）*（ 3+1）=12
所以我们可以把质数都尽量分开
我们可以把这一个串分成很多段
如
2 3 5 7 2 3 5 2 3
这样
然后我们怎么求f(i)的和呢
然后我们怎么求有多少段呢，每一段的具体长度是多少呢
len怎么求
这里我用了差分，具体看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
const int mod=1e9+7;
int len[maxn];
int n;
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res;
}
int inv(int x)
{
return ksm(x,mod-2);
}
int getsum(int q,int a1,int cnt)
{
int g=ksm(q,cnt)%mod;//g是q^n,
int res=a1%mod*((1-g+mod)%mod+mod)%mod;//1-q^n要大于0
res=(res*inv((1-q+mod)%mod))%mod;
return res%mod;
}
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
len[1]++;//可以放在第一段，到x段都可以，
len[x+1]--;
}
for (int i=1;i<=2e5;i++)//len[i]代表第几段的长度，每一段都是一个等比数列，求len我们用了差分
{
len[i]=len[i-1]+len[i];
}
int a1=1;
int ans=0;
for (int i=1;i<=2e5;i++)//以第i个质数作为第一个，这一个等比数列
{
int q=1LL * (i + 1) * inv(i) % mod;//每一段的长度为len[i]
int cnt=len[i];
int now=a1*q;
ans=(ans+getsum(q,now,cnt)%mod)%mod;
a1=(a1*ksm(q,cnt)%mod)%mod;
}
cout<<ans<<'\n';
return 0;
}