小白月赛36签到题题解（由易到难E, F, I, B, C, H）

admin管理员组

文章数量:1122850

小白月赛36签到题题解（由易到难E, F, I, B, C, H）

小白月赛36签到题题解（由易到难E, F, I, B, C, H）

小白分数涨了，现在打小白都要掉分了QAQ！

E、皇城PK——传送门

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BrfdYFoj-1627135787203)( “图片标题”)]

感觉这是本次小白最简单的题目了；

题目分析：
个人感觉题目理解上存在歧义，题目说最终总冠军属于最强者，且实力一样强都不能得总冠军（最感觉就是一个人）。就有了两种理解方式；

1、找到所有没有被打败过的人，总冠军的数量就是没有被打败过的人数；
2、如果只有一个人没有被打败，总冠军就属于那个人，若有多个，则总冠军不存在输出0；
（事实证明是第一种理解方式，得亏先试了第一种，不然wa警告）

解题思路：

将所有战斗看作一个拓扑图，a打赢了b即为存在一条从a指向b的边，若存在选手A打败选手B，选手B打败选手C，选手C打败选手A，则成环，只要记录入度，最后只要找到入度为0的点，这些人没输过，就是总冠军。（各位大佬肯定都是一眼看出来，我的思路就图一乐吧）

int in[N];//记录入度int main()
{//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);int n, m;memset(in, 0, sizeof in);scanf("%d%d", &n, &m);int a, b;for(int i = 1; i<=m; i++){scanf("%d%d", &a, &b);in[b]++;}int ans = 0;for(int i = 1; i<=n; i++){if(in[i] == 0){ans++;}}cout<<ans<<endl;return 0;
}

F、象棋——传送门

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-irAdeH7K-1627135787204)( “图片标题”)]

题目分析：
先清楚象棋中炮的定义，隔一个棋子打，且题目表示不能不进行攻击直接移动，看数据范围1e18，太大了，要么是公式，要么就有固定的次数。

1、对于每一个二维矩阵，分割来看，先看每一行，若n>=3，则最左边两个炮可以交替一路向右打过去，直至只剩下这两个炮，此时将n变为2；
2、经过上面的操作，还剩下2*m个炮，同理，对于每一列，最上方两个炮也可以一路向下打，最后剩下两列；

解题思路：
对于每个n，m，若n，m>=3,最后都剩下2*2=4个炮；
若n == 1&&m ==1，就只有一个炮不能攻击；
若n == 1&&m ！=1||m == 1&&n!=1,此时只有一行或一列，只剩两个炮

int main()
{//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);int t;scanf("%d", &t);ll n, m;while(t--){scanf("%lld%lld", &n, &m);if(n>=2&&m>=2) puts("4");else{if(n == 1&&m == 1)puts("1");else puts("2");}}return 0;
}

I、四面楚歌——传送门

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MEVWiZs7-1627135787205)( “图片标题”)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IgnwDwdD-1627135787206)( “图片标题”)]
我也想问这个⏜；

题目分析：
一个n*m的地图，找我方士兵没有被敌方包围的个数；
n和m比较小，乘起来也才1e6，可以使用搜索找，当然不可能从战场内每个我方士兵开始搜索能否到边界，那样太多了，可以反过来想，在边境线上每一个点安排一个人，向战场内部搜索，在不进入敌人包围圈的情况下，看看能找到多少人；

解题思路：

先将边界线染色，然后从边界线上的每一个点向战场内部渗透，看看能找到多少个友军；
可以从（0，0）点开始，用bfs搜索，将战场边境扩大一圈；

 
char f[1010][1010];
int v[1010][1010];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};struct lq{int x, y;
};
queue<lq> q;int bfs(int n,int m){int ans = 0;while(!q.empty())q.pop();lq e;q.push({0,0});v[0][0] = 1;while(!q.empty()){e = q.front();q.pop();for(int i = 0; i<4; i++){int px = e.x+dx[i];int py = e.y+dy[i];if(px<0||px>n||py<0||py>m) continue;if(f[px][py]!='1'&&v[px][py] == 0){if(f[px][py] == '0') ans++;//边搜边记录v[px][py] = 1;q.push({px, py});}}}return ans;
}int main()
{// ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);int n, m;scanf("%d%d", &n, &m);cin.get();for(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){scanf("%c", &f[i][j]);}cin.get();}int ans = bfs(n+1, m+1);cout<<ans<<endl;return 0;
}

B、最短串——传送门

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9bztJz1o-1627135787207)( “图片标题”)]

题目分析：
两个长5000的串，’?'可以当任何字符，求包含s和c的最短串的长度
暴力来求，两个串长5000，O（len^2）应该是可以过的；

解题思路：
首先最长的串为两个字符串的拼接既ans(max) = lenc+lens;
之后将字符串c的最后和字符串s的最前进行比较（此时c在s的左边），每次比较长度为最长为max(lens, lenc);每次将字符串向前进一位，s字符串不动，若能够匹配求一个最小值（注意最小值不能小雨max(lens, lnec)），直到c走到s的右边；
可以看一下图， 比较形象:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WHDypmPT-1627135787208)( “图片标题”)]

int main()
{//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);string s,c;cin>>s>>c;int lens = s.length();int lenc = c.length();int ans = lens+lenc;int res = max(lens, lenc);for(int k = -lenc+1; k<lens; k++){if(k<=0){int t = 1;k = -k;for(int i = 0, j = k; i<lens&&j<lenc; i++, j++){if(s[i] != c[j]&&s[i]!='?'&&c[j]!='?'){t = 0;break;}}if(t == 1)ans = min(ans, max(k+lens,res));k = -k;}else{int t = 1;for(int i = k, j = 0; i<lens&&j<lenc; i++, j++){if(s[i] != c[j]&&s[i]!='?'&&c[j]!='?'){t = 0;break;}}if(t == 1) ans = min(ans, max(k+lenc, res));}}cout<<ans<<endl;return 0;
}

C、杨辉三角——传送门

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XYwF53rg-1627135787208)( “图片标题”)]

解题思路：推一下公式就行了，公式推出来答案就出来了，然后公式实现的时候记得取模；
推公式就直接看这个聚聚的博客吧，比我推的好

const int mod = 99824353;ll qmi(ll a, ll b, ll p)
{ll res = 1 % p;while (b){if (b & 1) res = res * a % p;a = a * (ll)a % p;b >>= 1;}return res;
}int main()
{//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);ll n;cin>>n;if(n == 1) puts("0");else if(n == 2)puts("1");else{n--;ll ans = (n%mod*(n+1)%mod)%mod*qmi(2, n-2, mod)%mod;cout<<ans%mod<<endl;}return 0;
}

H、卷王之王——传送门

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t06PCpqe-1627135787209)( “图片标题”)]
题目分析：
对于一个长为n的数组a，求经过m次修改后数组最后各元素的值；
数据范围比较大，n^2肯定超时；
仅当a[i]<=x时令a[i]+=x，此时a[i]的值至少增加了一倍，每个数最多加 log X 次，则可以用一个小根堆模拟这个过程，每次弹出小于等于x的数；因为最后要按顺序输出，因此还要记录每个数据的顺序；小根堆可用优先队列实现，复杂度为 log n ；
时间复杂堆大概是O(nlog x log n)；

解题思路：
定义一个优先队列（priority_queue）和一个动态数组（vector），将读入的数据存入优先队列，同时存他的序号；最后对于每一个x出队小于等于x的数，将其存入动态数组，对数组中所有的元素加上x，存入优先队列，数组清空，最后按顺序输出；

struct lq{int x, id;bool operator<(const lq &a)const{return x>a.x;}
}f;priority_queue<lq> q;
vector<lq>v;
int ans[100005];int main()
{int n, m;scanf("%d%d", &n, &m);int x;for(int i = 1; i<=n; i++){scanf("%d", &x);q.push({x,i});}while(m--){scanf("%d", &x);if(x == 0)continue;while(!q.empty()&&q.top().x<=x)v.push_back(q.top()),q.pop();int len = v.size();for(int i = 0; i<len; i++){f = v[i];f.x+=x;q.push(f);}v.clear();}while(!q.empty()){f = q.top();q.pop();ans[f.id] = f.x;}for(int i = 1; i<=n; i++){printf("%d ", ans[i]);}return 0;
}

完结撒花，有写的不好的地方还请聚聚们指出！

本文标签： 小白月赛36签到题题解（由易到难EFIbc