A 伟大奋斗(签到题)
应该是响应20大，所以一道非常简单的签到题
B 可莉的五子棋(签到题，模拟)
链接：https://ac.nowcoder.com/acm/contest/43937/B
可莉最近沉迷于蒙德五子棋，她在棋盘上放了一些棋子。
蒙德五子棋的规则如下。
给定一个n*m的棋盘。棋盘上有两种棋子“1”和“2”，其中每种棋子分别计算得分。
假如相同种类的五个棋子连成相邻的一行，一列，或斜对角线的情况，每有五个这样的棋子，该种类棋子加1分。
可莉已经把她的棋子都摆在了棋盘上。
但是可莉不太聪明的样子，她希望你，聪明的旅行者，告诉她，她两种棋子的得分。
解析：
一道正常逻辑的模拟，有人用搜索做，但我个人觉得搜索不是很合适，
直接模拟各个方向凑成五个就算一分，然后遍历矩阵，重点在于，该棋子向右成五连等于第五个棋子向左成五连所以最后，每个棋子只需要判断，上，右，左上，右上，四个方向就可以或者你也可以判断下，左，左下，右下这里需要注意一点就是，不要越界，要限制好范围，暴力模拟直接过。
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[1005][1005];
bool shang(int i,int j){
//cout<<endl<<s[i][j]<<s[i-1][j]<<s[i-2][j]<<s[i-3][j]<<s[i-4][j]<<endl;
if(s[i][j]==s[i-1][j]&&s[i][j]==s[i-2][j]&&s[i][j]==s[i-3][j]&&s[i][j]==s[i-4][j]){
// cout<<"成功一次"<<endl;
return true;
}
return false;
}
bool zuoshang(int i,int j){
if(s[i][j]==s[i-1][j-1]&&s[i][j]==s[i-2][j-2]&&s[i][j]==s[i-3][j-3]&&s[i][j]==s[i-4][j-4]){
return true;
}
return false;
}
bool youshang(int i,int j){
if(s[i][j]==s[i-1][j+1]&&s[i][j]==s[i-2][j+2]&&s[i][j]==s[i-3][j+3]&&s[i][j]==s[i-4][j+4]){
return true;
}
return false;
}
bool you(int i,int j){
if(s[i][j]==s[i][j+1]&&s[i][j]==s[i][j+2]&&s[i][j]==s[i][j+3]&&s[i][j]==s[i][j+4]){
return true;
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
int result1=0;
int result2=0;
for(int i=0;i<n;i++){
cin>>s[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i>=4){
if(shang(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
if(j>=4){
if(zuoshang(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
}
}
if(m-j>=5){
if(you(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
if(i>=4)
if(youshang(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
}
}
}
printf("%d %d",result1,result2);
return 0;
}
E 病毒危机(模拟)
链接：https://ac.nowcoder.com/acm/contest/43937/E
你是旅行者，由于未知原因，你穿越到了提瓦特，遇到了各种各样的角色，游历了风格各异的地方，成为了战力第一。但可怕的是，你为这个世界带来了一种本不属于这个世界的L病毒，这种L病毒传染性强，一旦这种病毒散播开来，后果不堪设想。
我们可以认为，如果旅行者去过一个地点，则到过该地点的人们全部都会被感染L病毒。现在找到了n个人（其中第1个人是旅行者，是初始感染了L病毒的人），分别得知了n个人到过的地方。注意，被旅行者感染的人没有感染别人的能力。你需要计算出最坏情况下，也就是最后的感染L病毒人数。
解析：
这题wa了两次不太都是细节格式问题，不太应该QAQ
第一个是感染者，他去过的地方，别人再去都会被感染，但是别人没有感染其他人的能力，所以也是一个非常简单的模拟，记录第一个人去过的地方，然后遍历其他人去过的地方，当检测到其他人去过第一个人去过的地方时，就记录一下，然后退出循环，因为此人已经被感染了，无需再往下判断，节省时间，就ac了
#include<bits/stdc++.h>
using namespace std;
map<int,int> p;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int result=1;
int t;
scanf("%d",&t);
for(int i=0;i<t;i++){
int temp;
scanf("%d",&temp);
p[temp]++;
}
if(n==1){
printf("%d",result);
return 0;
}
n--;
while(n--){
int t2;
scanf("%d",&t2);
int s[t2];
//cout<<"t值"<<t2<<endl;
for(int i=0;i<t2;i++){
scanf("%d",&s[i]);
}
for(int i=0;i<t2;i++){
if(p[s[i]]>0){
// cout<<temp2<<"被感染"<<endl;
result++;
break;
}
}
}
printf("%d",result);
return 0;
}
F 互质(找规律)
链接：https://ac.nowcoder.com/acm/contest/43937/F 来源：牛客网
琴团长提出了T次询问，每次询问给出一个正整数n，询问雷泽是否存在一个正整数x，满足x大于等于n/4向上取整，小于等于n/2向下取整，且x与n互质。
雷泽并不会数学，于是便向你求助。
解析：
这道题看别人wa了那么多次就能看出来不是暴力能过的，我个人当场分析是，因为他超时了，所以说明肯定找到最后那个数字了，又因为，只要输出一个就行，所以我从后面判断，然后判断区间发现如果是偶数的话，右区间肯定不行，那就右区间减一，然后举例子10以内的就有减一也不可以的，有一个6，他只能做到减一，所以特殊判断下，其他的那就再减二，判断一下。试了好多次没找到不符合条件的，然后一狠心试了下就过了，主要还是在能看出这道题肯定是一道规律题，不可能是从头到尾找，又因为肯定是有人从头到尾超时，所以从尾开始往前找。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
if(n==4){
printf("1\n");
continue;
}
if(n==6){
printf("-1\n");
continue;
}
if(__gcd(n/2,n)==1){
printf("%lld\n",n/2);
}else if(__gcd(n/2-1,n)==1){
printf("%lld\n",n/2-1);
}else if(__gcd(n/2-2,n)==1){
printf("%lld\n",n/2-2);
}else{
printf("-1\n");
}
}
}
G 栈与公约数(模拟剪枝)
链接：https://ac.nowcoder.com/acm/contest/43937/G
初始有一个为空的栈，进行q次操作，操作分为以下四种：
1.在栈顶放入一个元素x
2.删除栈顶元素（数据保证此时栈内至少有一个元素）
3.查询栈顶元素
4.将栈顶的k个元素修改成他们的最大公约数(数据保证k不超过栈中元素数量)（比如栈内元素是4，2，将栈顶的2个元素修改成他们的最大公约数，栈内元素是2，2）
解析：
这道题开始暴力超时，但是找公约数实在没能力再优化，又过了那么多，所以我开始想的是把k存一下，只真正改一个数，如果他弹栈了，那就检测K，是否在他弹出前让他的后一个等于他，感觉思路没问题，但交了试了下还是超时，就没办法了，已经想放弃了，然后队员学弟比较Nice，他发现只要求出最大公约数是1了，那么所有的最大公约数只能是1，就没有必要再求下去了，然后加了个1的优化，就过了......（这时候已经封榜了，说实话这道题卡这么久，我心态已经有点崩了，但队员给力这道题过了，瞬间就活了，然后我就把F互质过了，封榜又过了两题）
#include<bits/stdc++.h>
using namespace std;
int s[200000];
int indext=-1;
int gcd(int a,int b){
return b==0 ? a:gcd(b,a%b);
}
int main(){
int q;
scanf("%d",&q);
while(q--){
int op;
scanf("%d",&op);
if(op==1){
int temp;
scanf("%d",&temp);
//cout<<"sda:"<<temp<<endl;
s[++indext]=temp;
}else if(op==2){
s[indext--];
}else if(op==3){
printf("%d\n",s[indext]);
}else if(op==4){
int k;
scanf("%d",&k);
int temp;
temp=s[indext];
for(int i=1;i<k;i++){
temp=gcd(temp,s[indext-i]);
if(temp==1)break;
}
for(int i=0;i<k;i++){
s[indext-i]=temp;
}
}
}
return 0;
}
M 画画(矩阵找规律)
链接：https://ac.nowcoder.com/acm/contest/43937/M
小筱有一块画布，画布是一个N×NN \times NN×N的网格。最先开始画布上的每个格子都是白色，小筱想要把一些格子涂黑，完成一幅黑白的画。由于小筱很喜欢黑色，所以她希望使得尽量多的格子变成黑色。同时她希望对于第i行/列上的黑色格子数量与i的奇偶性相同(行与列编号为[0...N−1])。 现在请你帮助小筱画出一幅符合要求的画，其中黑色用1表示，白色用0表示。
解析：
这道题的话，看完题发现是一个正方形矩阵，然后奇偶行列分别都要满足要求，就说明0的位置肯定不是随便的，然后其实能感觉出来是一道找规律的题，开始就可以画着试试看能不能找到规律
答案解析给的是：首先把矩阵全赋1，然后把对角线上的元素间隔改0就行
但我们当时画了几次，开始拿小数字试，发现0的位置好像有规律和对角线有关，然后我们发现的规律是：如果n是偶数，那么0就在i,j相等且为奇数的位置，如果n是奇数，那么就是i+j等于n-1且i,j都为偶数的位置(这里注意一点就是编号是从0到n-1)，可能有一点绕，但其实和答案应该是一样的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(n%2==0)
{
if(i%2!=0&&j%2!=0&&i==j) printf("0");
else printf("1");
}
else
{
if(i+j==n-1&&i%2==0&&j%2==0) printf("0");
else printf("1");
}
}
printf("\n");
}
}
return 0;
}
Comments NOTHING