新生第七场代码

题解

链接：
第七场链接

只需要看着链接然后回来看题解就行，操作不是很熟练。

A 合并数字

思路一：用栈写
n个数据，并且在每次循环的时候读入需要判断的变量x，通过判断1.栈顶元素>x  记录数+1，pop栈顶蒜素元素2.x>栈顶元素，栈顶元素是不需要pop的，此时x没有进栈，只需要记录数+1，一切正常。3.不符合以上两种情况的话，那就是空的或者不是等于1的情况，那就把x压进去。是s

======================================================

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
stack<int>st;
int ans=0;
int n;int x;
int main(){cin>>n;for(int i=0;i<n;i++){cin>>x;while(!st.empty()&&st.top()-x==1){ans++;st.pop();}if(!st.empty()&&x-st.top()==1){ans++;}elsest.push(x);}cout<<ans; return 0;
}

思路二：用数组实现。

#include<iostream>
using namespace std;
int st[100000];
int n,ans=0;
int top=0;
int main(){cin>>n;while(n--){int x;scanf("%d",&x);while(true){if(top && st[top] - x == 1){ans++;top--;continue;}else if(top && st[top] + 1 == x){ans++;}else{st[++top] = x;}break;}}cout<<ans<<endl;return 0;
}

C - Red and Black

本题是DFS模板题目，通过深度优先搜索判断每一个点是不是符合需求，并且回溯之后找出满足条件的点。

本来不是很了解DFS，大概也知道了必须有的条件
1: 上下左右移动的数组坐标
2:bool类型或者int类型的二位或者特定数组用来判断该点（该行）是不是已经查找过。
3:读取当前坐标的下一个坐标，下一个x==nextx=当前坐标+方向坐标【i】【0】，同理nexty同样。
4:特殊情况可以跳出一次循环了，当然还要继续查找。

#include<iostream>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
bool dir[25][25];//用来存已经找过的
char str[25][25];//存每个坐标的
int zou[4][2]={-1,0,1,0,0,-1,0,1};
int n,m,cnt,chux,chuy; 
void dfs(int x,int y){cnt++;dir[x][y]=true;for(int i=0;i<4;i++){int nx=x+zou[i][0],ny=y+zou[i][1];if(nx<1||ny<1||nx>m||ny>n||dir[nx][ny]||str[nx][ny]=='#')continue;dfs(nx,ny);} 
}
int main(){while(scanf("%d%d",&n,&m)){cnt=0;if(n==0&&m==0){break;}memset(dir,0,sizeof dir);for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){scanf(" %c",&str[i][j]);if(str[i][j]=='@'){chux=i,chuy=j;}}}dfs(chux,chuy);printf("%d\n",cnt);}return 0;
} 

还有一种BFS的做法`

#include <iostream>
#include <cstring>
#include <queue>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;int n, m, bx, by, cnt, nx, ny;
char str[25][25];
bool det[25][25];
int nt_sp[4][2] = {-1,0,1,0,0,1,0,-1};
struct node{int x, y;
};
queue <node> q;
bool bdy(int x, int y){return (x <= n && x >= 1 && y <= m && y >= 1);
}
void bfs(int x ,int y){while(!q.empty()) q.pop();det[x][y] = true;q.push({x, y});while (!q.empty()){node now = q.front();for (int i = 0; i < 4; i ++){nx = now.x + nt_sp[i][0], ny = now.y + nt_sp[i][1];if(!det[nx][ny] && bdy(nx, ny) && str[nx][ny] == '.'){cnt ++;det[nx][ny] = true;q.push({nx,ny});}}q.pop();}}
int main(){ios;while (cin >> m >> n && m && n){cnt = 1;memset(det, false, sizeof det);for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++){cin >> str[i][j];if (str[i][j] == '@')bx = i, by = j;}bfs(bx, by);cout << cnt << endl;}return 0;
}

D-game23

类似于质因子分解，取余后判断即可

#include<iostream>
using namespace std;
int main(){int a,b,cnt=0;scanf("%d%d",&a,&b);if(b%a!=0){printf("-1\n");}else{b=b/a;while(b%3==0){b=b/3;cnt++;}while(b%2==0){b=b/2;cnt++;}if(b>1){printf("-1\n");}elseprintf("%d\n",cnt);}return 0;
}

好吧 太多了

E-棋子问题

类似于上边C的DFS把

#include<iostream>
using namespace std;
int n,k;
char a[10][10];
int visited[10];//visited数组记录在前h-1行第几列已经放入棋子了
int cont=0;//cont代表种数
int way=0;
void dfs(int h)//h代表行数 ? way代表选择放入棋子的个数
{
if(way==k)//当放入的棋子数等于给定需要放入的棋子数时 ? 方案数加1
{
cont++;
return ;}if(h>=n)//当所搜索的行数大于棋盘时 ? 直接返回return ;for(int i=0;i<n;i++)//在第h行中从第一个位置开始列举{if(!visited[i]&&a[h][i]=='#')//当前h-1行中第i列中已经放入了棋子 ?那么第h行就不用放了 ?因为棋子不能放在同一行 同一列
{visited[i]=1;way++;
dfs(h+1);visited[i]=0;//还原 ?假如第0行有两个# ?当从第0行的第一个#开始往下走时,假设第2行中有且只有一个#，并且不与第一行中的任意一个在同一列，那么在往下way--;//走时就会把这个#标记 ?当递归返回到第一行第一个#时 ?i会++ ?到第一行的第2个# ?函数继续会继续往下走 ，到达第2行的那个#，因为在第一行第一个#那条路径中//已经走过了第2行的那个#(因为第2行只有一个#并且这个#所在的列数不与第一行两个#重合)，如果不把第一次走过第二行的#的标记消除 ?那么这次路径就不会再过第二行的
//这个# ?那么可选路径少了 ?肯定不对了
}
}dfs(h+1);
}int main()
{
while (cin>>n>>k){
if(n==-1&&k==-1)break ;for(int i=0;i<n;i++)
for(int j=0;j<n;j++)cin>>a[i][j];dfs(0);
cout<<cont<<endl;
memset(visited,0,sizeof(visited));cont=0;
way=0;}}

F 超级跳跳跳

好像有个名词叫做 上升子序列
只是知道一个原始数组map里面数据是不变的，
备用数组dp里面数据是更新的，也就是存取每一位更新了的加的，
然后最后读取dp里面的数字找出来跳的最大的。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<limits.h>
using namespace std;
int map[1010];
int dp[1010];
int main()
{int n;while(~scanf("%d",&n)&&n!=0){for(int i=1;i<=n;i++)scanf("%d",&map[i]);for(int i=1;i<=n;i++)dp[i]=map[i];for(int i=1;i<=n;i++){for(int j=1;j<=i-1;j++)if(map[j]<map[i]&&dp[j]+map[i]>dp[i])dp[i]=dp[j]+map[i];}int max=-1;for(int i=1;i<=n;i++)if(dp[i]>max)max=dp[i];printf("%d\n",max);}
}

G-Primes

这一题一开始以为输出必须是先读取很多数字，一下子出全部的呢，没想到还是可以一个一个出的。
这个题目的细节是终止条件是小于等于0，盲目的用EOF会错误的。

第一种：读一个出一个

#include <iostream>
#include <algorithm>
#include <string>#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;int N;
bool div(int N){for(int i = 2;i*i<=N;i++){if(N%i == 0) return false;}return true;
}
int main(){int kase = 0;while(scanf("%d",&N)){if(N == 1 || N == 2) {printf("%d: no\n",++kase);continue;}if(N <=0) break;if(div(N)) printf("%d: yes\n",++kase);else printf("%d: no\n",++kase);}return 0;
}

第二，读完了再出：

#include <stdio.h>
int main()
{int a[255],i,j=0,k,z=1;for(i=0;i<250;i++){scanf("%d",&a[i]);if(a[i]<=0)break;j++;//}//用循环判断 for(i=0;i<j;i++){for(k=2;k<=a[i];k++){if(a[i]%k==0)break;}if(a[i]!=2&&a[i]==k){printf("%d: yes\n",z);}elseprintf("%d: no\n",z);z++;}return 0;}
//最好不要用翻译。。我把yes翻译成是的

H - WeirdSort

大概这个题目就是大佬说的CF？？
一开始题都没读懂，我滴妈，什么跳来跳去的。。。
思路：a数组是正常的，
但是又给的一个P数组代表着，
你只能移动P数组对对应每个数据在a中的位置i和位置i+1，并且让每个这种类似的数据都保证是**！增 !**,然后只有p里面的存在的能这样交换，
通过一次次交换，
最终再次判断a中的数据是不是每个都是递增的！

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int a[N],p[N];  //定义成全局变量 直接就可以在构造的函数中使用数组的大小了不用传过来 
int n,m,t;
bool panding(){while(true){int count=0;for(int i=1;i<=m;i++){int idx=p[i];if(a[idx]>a[idx+1]){swap(a[idx],a[idx+1]);count=1;}}if(!count)break;}for(int i=1;i<n;i++)if(a[i]>a[i+1])return false;return true;}int main(){cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>p[i];}if(panding()) printf("YES\n");elseprintf("NO\n"); }return 0; 
}

I-大数取余数改版

#include<iostream>
#include<math.h>
using namespace std;
int k,n,a,b;
long long fun(){long long r=0,tim=0;while(true){r=(r*10+b)%a;tim++;if(r==0)break;}return tim;}int main(){cin>>n;while(n--){cin>>a>>b;long long res=fun();printf("Case %d: %lld\n",++k,res);}return 0;
} 

L - Dead Pixel

一个坏点把上下左右分成四块，然后找出最大的就行！

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{int t;cin>>t;int a,b,x,y;while(t--){cin>>a>>b>>x>>y;int s1=a*y;int s2=b*x;int s3=a*(b-y-1);int s4=b*(a-x-1);s2=max(s1,s2);s4=max(s3,s4);cout<<max(s2,s4)<<endl;}return 0;
}

额，只会这么多了，唉。谢谢。 可以看一下大佬的
神的题解