校历第九周 cf+数云图杯做题笔记

CF1754 A. Technical Support （思维、模拟、贪心）

https://codeforces.com/contest/1754/problem/A

/** @Author: xiao-p* @Date: 2022-10-27 20:31:41* @LastEditors: wzp 304535326@qq.com* @LastEditTime: 2022-10-27 20:46:10* @Description: 304535326@qq.com*/
int main()
{int T;cin >> T;while( T-- ){int n;cin >> n;string s;cin >> s;int qnum=0,anum=0;for (int i = 0; i < s.length(); i++){if(s[i] == 'Q'){qnum++;}else{if(qnum>0)qnum--;}}if(qnum)    cout<<"No\n";else    cout<<"Yes\n";}
}

在最近总是出现类似的题目，如：数云图杯 K.多项式

此类题目最重要的是读懂题目，想出一个完全符合规则的模拟方案。

CF1754 B. Kevin and Permutation (构造、贪心、数学）

https://codeforces.com/contest/1754/problem/B

int main()
{int T;cin >> T;while(T--){int n;cin >> n;int dis = n / 2;int st = 1 + dis ,fi = 1;int cnt=0;while( cnt<n ){cout << st <<" ";st ++;cnt ++;if(cnt<n){cout << fi <<" ";fi++;cnt ++;}}cout<< "\n" ;}
}

因为题面提到了 两个连续数字之间的最小绝对差尽可能最大 ，所以正确的思路（贪心）就应该想到相邻的距离最大就是这个序列长度的一半，所以是 1+n/2 跟 1 对应，然后依次自增至满足条件

数云图杯 K.多项式（思维、模拟、贪心）

https://ac.nowcoder.com/acm/contest/45069/K

/** @Author: xiao-p* @Date: 2022-10-31 18:57:59* @LastEditors: 304535326@qq.com* @LastEditTime: 2022-10-31 19:50:03* 304535326@qq.com* Copyright (c) 2022 by xiao-p e-mail:304535326@qq.com, All Rights Reserved. */
int main ()
{cin >> n;cin >> s;ll zuo=0,you=0;for ( auto i : s){if (i=='(') zuo++;else{if (zuo)    {zuo--; ans ++;}else    ans --;}}cout << ans-zuo ;
}

遍历字符串，有左括号则在“积蓄”中+1，如遇右括号，若有积蓄，则积分+1，积蓄消耗一个 ,注意最后的输出要用积分减去没用到的左括号“积蓄”。

CF1749 A.Cowardly Rooks (贪心、模拟）

void solve ()
{int n,m;cin >> n >> m;int a[10][10] = {0};for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){a[i][j]=1;}}for (int i = 0; i < m; i++){int x,y;cin >> x >> y;for (int j = 1; j <= n; j++){a[x][j] = 0;a[j][y] = 0;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if( a[i][j] == 1){cout << "YES\n";return;}//cout<<a[i][j]<<" ";}cout << endl;}cout<<"NO\n";
}

查询是否有空行或空列，有则YES。复杂度O(m2⋅n2)

鲁莽的交了幸运的过了...

CF1749 B.Death's Blessing (贪心）

https://codeforces.com/contest/1749/problem/B

void solve()
{ll n , i  , tem=0,ma=0;ll ans=0;cin >> n;for ( i=0 ; i < n ; i++) {cin>>tem;ans+=tem;}tem=0;for ( i=0 ; i < n ; i++) {cin >> tem;if(tem>ma)  ma=tem;ans+=tem;}cout << ans-ma << endl ;  
}

贪心的想，让高法力值的怪影响最少的怪，就能达到最优，把最高法力值的怪留到最后杀，那样法力值就会无效。

ans = 怪生命值的总和 + 怪法力值的总和 - 怪最高的法力值

CF1746 B. Rebellion （构造、贪心、双指针）

https://codeforces.com/contest/1746/problem/B

int a[N],b[N];
void solve()
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}int l = 0 , r = n-1 , ans = 0;while(l<r){while(a[l] != 1)    l++;while(a[r] != 0)    r--;if( l < r){swap( a[l], a[r]);ans++;}}cout<< ans <<endl;
}

贪心的想，交换优于删除。

故先从左边找到1，若找到，就从右边找0（贪心的找一个与左边1交换的数），找到则交换，继续重复左边找1的过程。

CF1744 C. Traffic Light (二分、模拟、双指针）

https://codeforces.com/contest/1744/problem/C

void solve1()
{int n;char now;cin >> n >> now;string a;cin >> a;a += a;int ans = 0,tem=0;for (int i = a.length()-1; i >= 0 ; i--){if(a[i] == 'g'){tem = 0 ;}if (a[i] == now){ans = max (ans, tem);}tem++ ;}cout << ans << endl;
}

看到类似的字符串（循环性）问题，就要想到 断环成链

初次做是从左向右找绿灯，TLE

换成从终点（绿灯）走向起点过题

所以遇到这种Target的题还要想到 逆向思维...(比如那些搜索题）