小白月赛36签到题题解（由易到难E, F, I, B, C, H）
小白分数涨了，现在打小白都要掉分了QAQ！
E、皇城PK——传送门
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BrfdYFoj-1627135787203)(https://uploadfiles.nowcoder.com/images/20210717/189136626_1626488395683/4926D1D218A76D66F7727C416BF073F2 “图片标题”)]
感觉这是本次小白最简单的题目了；
题目分析：
个人感觉题目理解上存在歧义，题目说最终总冠军属于最强者，且实力一样强都不能得总冠军（最感觉就是一个人）。就有了两种理解方式；
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;
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-irAdeH7K-1627135787204)(https://uploadfiles.nowcoder.com/images/20210717/189136626_1626489600689/15C050D51058D9EB401D1DFCFCBD9D6D “图片标题”)]
题目分析：
先清楚象棋中炮的定义，隔一个棋子打，且题目表示不能不进行攻击直接移动，看数据范围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)(https://uploadfiles.nowcoder.com/images/20210717/189136626_1626490480933/50D0A50BEA8F75165A0263E446CC90F3 “图片标题”)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IgnwDwdD-1627135787206)(https://uploadfiles.nowcoder.com/images/20210717/189136626_1626490516153/7DBC639393B71AD79F6E1E2EC8CDD828 “图片标题”)]
我也想问这个?；
题目分析：
一个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)(https://uploadfiles.nowcoder.com/images/20210717/189136626_1626491391675/B53B07770FB40B3AA5AE327D76FDE943 “图片标题”)]
题目分析：
两个长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)(https://uploadfiles.nowcoder.com/images/20210718/189136626_1626568838281/0166A3EFADBC7FCE08046A862D5EFAD2 “图片标题”)]
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)(https://uploadfiles.nowcoder.com/images/20210718/189136626_1626568939373/55AC7B68D2D9DB17AE49B297C86AA079 “图片标题”)]
解题思路：推一下公式就行了，公式推出来答案就出来了，然后公式实现的时候记得取模；
推公式就直接看这个聚聚的博客吧，比我推的好https://blog.nowcoder.net/n/6ce84c94f0bd404cbc75617904eecf91
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)(https://uploadfiles.nowcoder.com/images/20210718/189136626_1626570076506/5C21B3BADCC925D521491F61E656D6BA “图片标题”)]
题目分析：
对于一个长为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;
}
完结撒花，有写的不好的地方还请聚聚们指出！
|