小白月赛36签到题题解(由易到难E, F, I, B, C, H)
吐个小槽:昨晚边打边吃外卖,太激动把面大翻了,打完还去吃了个宵夜;
小白分数涨了,现在打小白都要掉分了QAQ!
E、皇城PK——传送门
感觉这是本次小白最简单的题目了;
题目分析:
个人感觉题目理解上存在歧义,题目说最终总冠军属于最强者,且实力一样强都不能得总冠军(最感觉就是一个人)。就有了两种理解方式;
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、象棋——传送门
题目分析:
先清楚象棋中炮的定义,隔一个棋子打,且题目表示不能不进行攻击直接移动,看数据范围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、四面楚歌——传送门
我也想问这个⏜;
题目分析:
一个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、最短串——传送门
题目分析:
两个长5000的串,'?'可以当任何字符,求包含s和c的最短串的长度
暴力来求,两个串长5000,O(len^2)应该是可以过的;
解题思路:
首先最长的串为两个字符串的拼接既ans(max) = lenc+lens;
之后将字符串c的最后和字符串s的最前进行比较(此时c在s的左边),每次比较长度为最长为max(lens, lenc);每次将字符串向前进一位,s字符串不动,若能够匹配求一个最小值(注意最小值不能小雨max(lens, lnec)),直到c走到s的右边;
可以看一下图, 比较形象:
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、杨辉三角——传送门
解题思路:推一下公式就行了,公式推出来答案就出来了,然后公式实现的时候记得取模;
推公式就直接看这个聚聚的博客吧,比我推的好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、卷王之王——传送门
题目分析:
对于一个长为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; }
完结撒花,有写的不好的地方还请聚聚们指出!