暑期算法训练

A.糖果（Candy)

B.小红的数组重排

C.牛牛与LCM

D.子串

E.勤奋的杨老师

F.清楚姐姐跳格子

G.方块 I

H.PUBG

A.糖果（Candy)

思路：贪心，为了使操作数最少，我们要尽可能的先吃第二个盒子里的糖果，如果还不满足条件就再吃第一个盒子里的糖果。

C++代码：

void solve()
{int n,x;cin>>n>>x;vector<int> v(n);for(auto &t:v) cin>>t;int sum=0;for(int i=0;i+1<n;i++){if(v[i]+v[i+1]>x){int a=v[i]+v[i+1];int cha=a-x;if(v[i+1]>=cha){v[i+1]-=cha;sum+=cha;}else{sum+=cha;v[i]-=cha-v[i+1];v[i+1]=0;}}}cout<<sum;
}

B.小红的数组重排

思路：贪心+排序，首先判断是否存在三个相同的数，因为三个相同的数会产生这种情况a[i]*a[i+1]=a[i+1]*a[i+2]，若存在，则输出NO，反之从小到大排序，若存在两个0，则NO,反之则输出相应序列

C++代码：

const int N=5e5+5;
int a[N],sum[N];
map<int,int> h;void solve()
{  int n,f=0;cin>>n;for(int i=0;i<n;i++) {cin>>a[i];if(h[a[i]]>=2) f=1;h[a[i]]++;}if(f) cout<<"NO";else{sort(a,a+n);if(a[0]==0&&a[1]==0) {cout<<"NO";return ;}cout<<"YES"<<endl;for(int i=0;i<n;i++) cout<<a[i]<<' ';}
}

C.牛牛与LCM

思路：将所有能整除x的数取一个最小公倍数，如果最终结果能被x整除则能够选出若干个数的最小公倍数为x，否则不能

C++代码：

int gcd(int a, int b){ return b?gcd(b, a%b):a;}void solve()
{int n;cin>>n;vector<int> v(n);for(auto &t:v) cin>>t;int x,f=0;cin>>x;int res=1;for(int i=0;i<n;i++){if(x%v[i]==0) res=v[i]*res/gcd(v[i],res);}if(res%x==0) cout<<"Possible";else cout<<"Impossible";}

D.子串

思路：暴力枚举，先枚举每一种进制，再将1~n转换位k进制，用字符串表示

C++代码：

string op="0123456789ABCDEF";string jz(int n,int k)
{string s="";while(n){s+=op[n%k];n/=k;}reverse(s.begin(),s.end());return s;
}
void solve()
{int n,f=0;cin>>n;string p;cin>>p;for(int k=2;k<=16;k++){string s="";for(int i=1;i<=n;i++){s+=jz(i,k);}if(s.find(p)!=-1){f=1;break;}}if(f) cout<<"yes";else cout<<"no";
}

E.勤奋的杨老师

思路：最长上身子序列的长度+最长下降子序列的长度，用朴素做法O(n*n)显然会超时，这里我们需要用到二分来优化，时间复杂度为O(n*logn)

C++代码：

const int N=5e5+5;
int up[N],down[N],n,a[N],r[N],l[N];
void solve()
{cin>>n;for(int i=0;i<n;i++) cin>>a[i];int len=0;for(int i=0;i<n;i++){if(up[len]<=a[i]){up[++len]=a[i];l[i]=len;}else{int pos=upper_bound(up+1,up+len+1,a[i])-up;up[pos]=a[i];l[i]=pos;}}len=0;for(int i=n-1;i>=0;i--){if(down[len]<=a[i]){down[++len]=a[i];r[i]=len;}else{int pos=upper_bound(down+1,down+len+1,a[i])-down;down[pos]=a[i];r[i]=pos;}}int maxd=0;for(int i=0;i<n;i++)maxd=max(maxd,l[i]+r[i]-1);
cout<<maxd;}

F.清楚姐姐跳格子

思路：bfs，先用vector存一下每个点所有的因数，同时因数不大于n(枚举到因数<=n防止超时），然后就是板子了。

const int N=1010;
int dist[N],a[N];
bool st[N];
vector<int> e[N];void solve()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dist[i]=1e18;for(int j=1;j<=a[i]/j&&j<=n;j++){if(a[i]%j==0){e[i].eb(j);if(a[i]/j!=j){if(a[i]/j<=n) e[i].eb(a[i]/j);}}}}queue<int> q;q.push(1);dist[1]=0; st[1]=true;while(q.size()){auto t=q.front(); q.pop();st[t]=true;for(auto v:e[t]){if(!st[t+v]&&t+v<=n&&dist[t+v]>dist[t]+1){dist[t+v]=dist[t]+1;q.push(t+v);}if(t-v>=1&&!st[t-v]&&dist[t-v]>dist[t]+1){dist[t-v]=dist[t]+1;q.push(t-v);}}}cout<<dist[n];
}

G.方块 I

思路：找规律，多模拟几个样例。

const int N=1010;
int a[4];
void solve()
{string s;while(cin>>s){int sum=0,ans=0;a[1]=a[2]=a[3]=0;for(int i=0;i<s.size();i++){if(s[i]=='a'){a[1]++;ans^=1;sum++;}else if(s[i]=='b'){a[2]++;ans^=2;sum++;}else{a[3]++;ans^=3;sum++;}}if(sum==a[1]||sum==a[2]||sum==a[3]) cout<<s.size();else{if(ans==0) cout<<2;else cout<<1;}cout<<endl;}
}

H.PUBG

思路：bfs板子题。

C++代码：

int ne[4][2]={{1,0},{0,1},{-1,0},{0,-1}};const int N=1010;
int a[N][N],n,dist[N][N];
int sx,sy,ex,ey,ans;
bool st[N][N];void solve()
{while(cin>>n){ans=0x3f3f3f3f;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>a[i][j];if(a[i][j]==-1){a[i][j]=0;sx=i,sy=j;}if(a[i][j]==-2){a[i][j]=0;ex=i,ey=j;}}queue<PII> q;q.push({sx,sy});mem(dist,0x3f);dist[sx][sy]=0;while(q.size()){auto t=q.front();q.pop();int x=t.fi,y=t.se;for(int i=0;i<4;i++){int tx=x+ne[i][0],ty=y+ne[i][1];if(tx>=1&&tx<=n&&ty>=1&&ty<=n){if(dist[tx][ty]>dist[x][y]+a[tx][ty]){dist[tx][ty]=dist[x][y]+a[tx][ty];q.push({tx,ty});}}}}cout<<dist[ex][ey]<<endl;}
}