网站页脚怎么做,仕德伟做的网站图片怎么修,营销型网站的建设和运营,成都旅游最佳季节一、题解#xff1a;
1.A-[NOIP2005]校门外的树_24级新生数组字符串训练题 (nowcoder.com)
这题常见的解法有两种#xff1a;
第一种是这道题我们可以直接按照题目意思枚举
#includebits/stdc.h
#define int long long
using namespace std;int road[10010];sig…一、题解
1.A-[NOIP2005]校门外的树_24级新生数组字符串训练题· (nowcoder.com)
这题常见的解法有两种
第一种是这道题我们可以直接按照题目意思枚举
#includebits/stdc.h
#define int long long
using namespace std;int road[10010];signed main()
{int l,m;cinlm;for(int i1;im;i){int l,r;cinlr;for(int il;ir;i)road[i]1;}int ans0;for(int i0;il;i)if(!road[i])ans;coutans;return 0;
}
第二种用了差分算法这个算法与前缀和算法互逆关于算法的知识可以看一下这个视频
STUACM-算法入门-前缀和与差分(含二维)_哔哩哔哩_bilibili
代码如下
#includealgorithm
#includeiostream
#includecstring
#includevector
#includemap
using namespace std;
typedef long long ll;const int N200010;
int a[N],b[N];void insert(int x,int y)
{b[x]--;b[y1];
}void solve()
{int n,k;cinnk;while(k--){int x,y;cinxy;insert(x,y);}int ans0;for(int i1;in;i)b[i]b[i-1];for(int i0;in;i)if(b[i]0)ans;coutn1-ansendl;
}int main()
{int _;_1;while(_--){solve();}return 0;
}
2、B-比较月亮大小_24级新生数组字符串训练题· (nowcoder.com)
如果只有一天的话只能判断0和15这两个特殊元素,其他的都不能判断如果有两天以上的话只用看最后两天可以了这种情况只有14,15需要特判。代码如下
#includeiostream
using namespace std;int temp[1000];int main()
{int n;cinn;for(int i1;in;i)cintemp[i];if(n1){if(temp[n]15)coutDOWNendl;else if(temp[n]0)coutUPendl;else cout-1endl;}else if(temp[n]15temp[n-1]14)coutDOWNendl;else if(temp[n]temp[n-1])coutUPendl;else if(temp[n]temp[n-1])coutDOWNendl;return 0;
}
3、C-数列下标_24级新生数组字符串训练题· (nowcoder.com)
方法一按照题目意思模拟用数组存储答案
#includebits/stdc.h
#define int long long
using namespace std;int a[10010],b[10010];signed main()
{int n;cinn;for(int i1;in;i)cina[i];for(int i1;in;i){int temp0;//判断是否有满足条件的数for(int ji;jn;j){if(a[j]a[i]){b[i]j;break;}}}for(int i1;in;i)coutb[i] ;return 0;
}
方法二可以用单调栈的方法写有兴趣的同学可以自己去了解。
4、D-求逆序数_24级新生数组字符串训练题· (nowcoder.com)
本题根据数据范围判断可以有两种解法第一种是根据题目暴力枚举O(n^2)
二是利用归并排序的特性求得O(nlogn);
第二种做法采用了分治的思想非常经典首先看归并排序的流程
1.划分区间 [l,mid] ,[ mid1,r];
2.递归排序(不断减小问题的规模)
3.归并将左右两个区间合二为一
一个逆序对是指一对数其中前面的元素严格大于后面的数那么根据归并排序的过程我们可以将逆序对分成三类
1.两个数都在左边
2.两个数都在右边
3.两个数分别在左右两边
其实质就是计算第三种逆序对因为左右两边的逆序对随着递归最终都会分解成第三种情况。 方法二为基本归并排序算法
方法一代码
#includebits/stdc.h
#define int long long
using namespace std;int a[10010];signed main()
{int n,ans0;cinn;for(int i1;in;i)cina[i];for(int i1;in;i){for(int ji1;jn;j){if(a[i]a[j])ans;}}coutans;return 0;
}
方法二代码:
#includeiostream
using namespace std;
int ans0;int temp[2010],a[2022];void merge_sort(int q[],int l,int r)
{if(lr)return ;int mid(lr)1;merge_sort(q,l,mid);merge_sort(q,mid1,r);int il,jmid1,k0;while(imidjr){if(q[i]q[j])ansmid-i1,temp[k]q[j];else temp[k]q[i];}while(imid)temp[k]q[i];while(jr)temp[k]q[j];for(int i0,jl;jr;j,i)q[j]temp[i];
}int main()
{int n;cinn;for(int i0;in;i)cina[i];merge_sort(a,0,n-1);coutansendl;return 0;
}
5、E-[NOIP2015]扫雷游戏_24级新生数组字符串训练题· (nowcoder.com)
注意要判断八个方向
#includealgorithm
#includeiostream
#includecstring
#includevector
#includemap
using namespace std;
typedef long long ll;const int N110;
char f[N][N];int dx[]{-1,0,1,0,1,1,-1,-1},dy[]{0,1,0,-1,1,-1,1,-1};void check(int x,int y)
{int cnt0;for(int i0;i8;i){int xxxdx[i],yydy[i]y;if(f[xx][yy]*)cnt;}f[x][y]0cnt;
}void solve()
{int a,b;cinab;for(int i1;ia;i)for(int j1;jb;j)cinf[i][j];for(int i1;ia;i){ for(int j1;jb;j){if(f[i][j]!*)check(i,j);printf(%c,f[i][j]);}coutendl;}
}int main()
{int _;_1;while(_--){solve();}return 0;
}
6、A-[NOIP2008]笨小猴_24级新生数组字符串训练题 (nowcoder.com)
用数组记录所有出现过的字母的次数排序得到答案再判断质数0不是质数注意看清题目只有是的时候输出答案否则一律输出0
#includebits/stdc.h
#define int long long
using namespace std;int num[29];bool isprime(int x)
{if(!x||x1)return false;for(int i2;ix/i;i){if(x%i0)return false;}return true;
}signed main()
{string s;cins;int maxn0,minn1e12;for(int i0;is.size();i){if(s[i]As[i]Z)s[i]a-A;num[s[i]-a];}for(int i0;i25;i){maxnmax(maxn,num[i]);if(num[i])minnmin(minn,num[i]);}int ansmaxn-minn;if(!isprime(ans)) coutNo Answerendl0;else coutLucky Wordendlans;return 0;
}
7、B-数独合理吗_24级新生数组字符串训练题 (nowcoder.com)
简单模拟用一个数组记录数字出现的次数即可记得每次检查前要初始化这个数组代码如下
#includealgorithm
#includeiostream
#includecstring
#includevector
#includemap
using namespace std;
typedef long long ll;const int N10;
int shu[N][N],ha[10];
bool flag11,flag21,flag31;void init()
{for(int i1;i10;i)ha[i]0;
}bool check3(int x,int y)
{for(int ix;ix2;i)for(int jy;jy2;j){ha[shu[i][j]];if(ha[shu[i][j]]1)return false;}return true;
}void check1()
{for(int i1;i9;i){init();for(int j1;j9;j){ha[shu[i][j]];if(ha[shu[i][j]]1)flag1false;}} for(int i1;i9;i){init();for(int j1;j9;j){ha[shu[j][i]];if(ha[shu[j][i]]1)flag2false;}}
}void check2()
{for(int i1;i9;i3)for(int j1;j9;j3){init();if(!check3(i,j))flag3false;}
}void solve()
{for(int i1;i9;i)for(int j1;j9;j)cinshu[i][j];/*检查行和列*/check1();/*检查宫*/check2();if(flag1flag2flag3)coutYESendl;else coutNOendl;
}int main()
{int _;_1;while(_--){solve();}return 0;
}
8、珂朵莉的假toptree (nowcoder.com)
c有个to_string函数很方便
#includebits/stdc.h
#define int long long
using namespace std;signed main()
{int n;cinn;string s;int cnt0;for(int i1;i1000;i){sto_string(i);}couts[n-1];return 0;
}
9、D-[NOIP2012]Vigenegrave;re 密码_24级新生数组字符串训练题 (nowcoder.com)
首先按照题目初始化密码表然后根据规则去翻译即可。代码如下
#includeiostream
#includecstring
using namespace std;
const int N100010;char map[26][26];
char key[110],text[1010];void init()
{for(int i0;i26;i){char baseAi;for(int j0;j26;j){char nowbasej;if(now-A26)now-26;map[i][j]now;}}
}int main()
{init();cinkeytext;int lstrlen(key),llstrlen(text);for(int i0;ill;i){char akey[i%l];char btext[i];if(aaaz)aA-a;if(babz)bA-a;char ans;for(int j0;j26;j)if(map[j][a-A]b)ansjA;if(text[i]atext[i]z)ansa-A;printf(%c,ans);}return 0;
}
有兴趣的同学还可以去试一下这道题潜伏者 (nowcoder.com)
10、E-上三角矩阵判定_24级新生数组字符串训练题 (nowcoder.com)
设行数为i,那么要满足题目意思的话只要每行前i-1个元素全为0即可否则不满足条件。
#includebits/stdc.h
using namespace std;int f[11][11];signed main()
{int n;cinn;for(int i1;in;i)for(int j1;jn;j)cinf[i][j];bool ff1;for(int i1;in;i)for(int j1;ji-1;j){if(f[i][j])ff0;}if(ff)coutYES;else coutNO;return 0;
}
