牛客寒假算法基础集训营1
就过了4道题，六天以来就没过几道算法题，全是思维题，心痛
题目A 小a的计算器
链接：
https://ac.nowcoder.com/acm/contest/317/A
来源：牛客网
题目描述
小a的数学基础实在太差了，以至于他只会用计算器算数。他的计算器比较特殊，只有+,−,×,/+, -, times, /+,−,×,/(即加减乘除)四种运算。
经过一番周折，小a终于算出了他想要的数，但是他却忘记了最初的数是什么。不过幸运的是他记下了整个操作序列，他想请你帮他算出最初的数
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
#define ll long long int
ll num[maxn];
ll opt[maxn];
int main()
{
ll n,x;
while(cin>>n>>x)
{
for(int i=0;i<n;++i)
{
cin>>opt[i]>>num[i];
}
for(int i=n-1;i>=0;--i)
{
if(opt[i]==1)
{
x-=num[i];
}else if(opt[i]==2)
{
x+=num[i];
}else if(opt[i]==3)
{
x/=num[i];
}else if(opt[i]==4)
{
x*=num[i];
}
}
cout<<x<<endl;
}
return 0;
}题目B 小a与204
链接：
https://ac.nowcoder.com/acm/contest/317/B
来源：牛客网
题目描述
小a非常喜欢204204204这个数字，因为′a′+′k′=204'a' + 'k' = 204′a′+′k′=204。
现在他有一个长度为nnn的序列，其中只含有2,0,42,0,42,0,4这三种数字
设aia_iai为序列中第iii个数，你需要重新排列这个数列，使得∑i=1n(ai−ai−1)2sum_{i = 1}^n (a_i - a_{i - 1})^2∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0a_0 = 0a0=0
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
int num[maxn];
int main()
{
int n;
while(cin>>n)
{
int sum=0;
int n4=0,n2=0,n0=0;
for(int i=0;i<n;++i)
{
cin>>num[i];
if(num[i]==4) n4++;
if(num[i]==2) n2++;
if(num[i]==0) n0++;
}
//cout<<n0<<n2<<n4<<endl; //
int cnt=n4<n0?n4:n0;
sum=cnt*16*2;
//cout<<sum<<endl; //
n4-=cnt;
n0-=cnt;
if(n4!=0) {
sum+=16;
n4--;
}
int len=n4>n0?n4:n0;
int aa=len<n2?len:n2;
sum+=aa*4*2;
len-=aa;
n2-=aa;
if(len>0 || n2>0)
{
sum+=4;
}
cout<<sum<<endl;
}
return 0;
}题目D 小a与黄金街道
链接：
https://ac.nowcoder.com/acm/contest/317/D
来源：牛客网
题目描述
小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。
游戏规则是这样的：
假设道路长度为nnn米(左端点为000，右端点为nnn)，同时给出一个数kkk(下面会提到kkk的用法)
设小a初始时的黄金数量为AAA，小b初始时的黄金数量为BBB
小a从111出发走向n−1n - 1n−1，小b从n−1n - 1n−1出发走向111，两人的速度均为1m/s1m/s1m/s
假设某一时刻(必须为整数)小a的位置为xxx，小b的位置为yyy，若gcd(n,x)=1gcd(n,x) = 1gcd(n,x)=1且gcd(n,y)=1gcd(n,y) = 1gcd(n,y)=1，那么小a的黄金数量AAA会变为A∗kx(kg)A k^x(kg)A∗kx(kg)，小b的黄金数量BBB会变为B∗ky(kg)B k^y(kg)B∗ky(kg)
当小a到达n−1n - 1n−1时游戏结束
小a想知道在游戏结束时A+BA+BA+B的值
答案对109+710^9 + 7109+7取模
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int
const int mod = 1e9+7;
ll gcd(ll x,ll y){
if(y==0) return x;
else return(gcd(y,x%y));
}
ll pow(ll x,ll n,ll mod)
{
ll res=1;
while(n>0)
{
if(n%2==1)
{
res=res*x;
res=res%mod;
}
x=x*x;
x=x%mod;
n>>=1;
}
return res;
}
int oula(int n)
{
int rea=n;
for(int i=2; i<=n; i++)
if(n%i==0)//第一次找到的必为素因子
{
rea=rea-rea/i;
do
n/=i;//把该素因子全部约掉
while(n%i==0);
}
return rea;
}
int main()
{
ll n,k,A,B;
while(cin>>n>>k>>A>>B)
{
ll pa=1,pb=1,sum;
pa=A;
pb=B;
ll cnt=oula(n)/2;
pa=A*pow(k,n*cnt,mod);
pb=B*pow(k,n*cnt,mod);
sum=(pa+pb)%mod;
cout<<sum<<endl;
}
return 0;
}题目G 小a的排列
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5+5;
int num[maxn];
int pos[maxn];
int vis[maxn];
int main()
{
int n,x,y;
while(cin>>n>>x>>y)
{
memset(pos,-1,sizeof(pos));
for(int i=0;i<n;++i)
{
cin>>num[i];
pos[num[i]]=i;
}
/*
for(int i=0;i<10;++i)
{
cout<<pos[i]<<" ";
}*/
int minn=x,maxn=y; //区间最大值和最小值
int posx=pos[x],posy=pos[y]; //区间两端的位置
if(posx>posy)
{
int temp=posx;
posx=posy;
posy=temp;
}
for(int i=posx;i<=posy;++i)
{
if(num[i]<minn) minn=num[i];
if(num[i]>maxn) maxn=num[i];
}
while(posy-posx!=maxn-minn)
{
for(int i=minn;i<=maxn;++i)
{
if(pos[i]<posx)
{
posx=pos[i];
}else if(pos[i]>posy)
{
posy=pos[i];
}
}
for(int i=posx;i<=posy;++i)
{
if(num[i]<minn) minn=num[i];
if(num[i]>maxn) maxn=num[i];
}
}
cout<<posx+1<<" "<<posy+1<<endl;
}
return 0;
}