• CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)——A、B、C


    比赛链接:https://codeforces.com/contest/1750

    A: 

     题意:给定长度为N的序列,你可以执行以下操作任意次

    1:选择三个下标 i,j,k(1

    2:如果ai>ak,ai=ai+aj,否则swap(aj,ak)

    问能否将序列换成不降序列

    分析:其实看样例也能发现规律。那就是,序列的第一个元素为1,就能实现,否则就不能实现。

    证明:我们发现,如果序列第一个元素为1,则一定是整个序列最小的数,所以就可以一直交换aj和ak,那么我们肯定是能够将序列转变为不降序列的。如果序列第一个元素不为1,则最小的元素一定在后面(除了第一个位置的任意位置),那么我们是不可能通过操作将1放在第一个位置上的,因此就不能实现不降序列。即证!

    代码:

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N=2e5+10;
    5. int a[N];
    6. inline void solve(){
    7. int n;cin>>n;
    8. for(int i=1;i<=n;i++) cin>>a[i];
    9. if(a[1]==1) cout<<"Yes\n";
    10. else cout<<"No\n";
    11. }
    12. signed main(){
    13. int t;cin>>t;
    14. while(t--) solve();
    15. }

     B:  

    题意:给定一个长度为n的01串,定义一个串的价值为:如果串中存在0和1,那么价值为0和1个数的乘积,否则是某一种数数量的平方。求原串的某一连续子串的最大价值。

    分析:我们发现,最大值只有三种情况才能取得:

    (我们定义一个串中0的个数为a,1的个数为b)

    1:max=a*b

    2:max=x*x  (x为串中0连续的最大长度)

    3:max=y*y(y为串中1连续的最大长度)

    所以我们只需要枚举串中这三个值即可

    代码:

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N=2e5+10;
    5. string s;
    6. inline void solve(){
    7. int n;cin>>n>>s;
    8. int a=0,b=0;
    9. for(int i=0;i<=n-1;i++)
    10. if(s[i]=='0') a++;
    11. else b++;
    12. int maxx=a*b;
    13. a=0,b=0;int x,y;
    14. for(int i=0;i<=n-1;){
    15. while(s[i]=='0') a++,i++;
    16. x=a*a;a=0;
    17. while(s[i]=='1') b++,i++;
    18. y=b*b;b=0;
    19. maxx=max(maxx,max(x,y));
    20. }
    21. cout<"\n";
    22. }
    23. signed main(){
    24. int t;cin>>t;
    25. while(t--) solve();
    26. }

    C: 

    题意:给定两个长度都为n的01串a和b。每次我们可以对串进行操作,每次操作选择一段区间[l, r],使得a串[l, r]范围内的01翻转,b串除了[l, r]范围内的01翻转,请问能否将ab串置0,并输出方案。

    分析:这里引用splay的题解吧,讲的挺好的。

    代码: 

    1. #include
    2. #define int long long
    3. using namespace std;
    4. typedef pair<int,int> PII;
    5. const int N=2e5+10;
    6. inline void solve(){
    7. int n;cin>>n;
    8. string s1,s2;cin>>s1>>s2;
    9. s1="*"+s1;s2="*"+s2;
    10. int cnt=0,cnt1=0,cnt2=0;
    11. for(int i=1;i<=n;i++){
    12. if(s1[i]==s2[i]){//统计相同位置的字符情况
    13. if(s1[i]=='0') cnt1++;//为0的个数
    14. else cnt2++;//为1的个数
    15. }
    16. else cnt++;//统计相同位置不同字符的个数
    17. }
    18. if(cnt!=0&&cnt!=n){
    19. cout<<"NO\n";return;
    20. }
    21. if(cnt1==n){//全为0的情况
    22. cout<<"YES\n";
    23. cout<<"0\n";
    24. return;
    25. }
    26. if(cnt2==n){//全是1
    27. cout<<"YES\n";
    28. cout<<2<<"\n";
    29. cout<<1<<" "<<1<<"\n";
    30. cout<<2<<" "<"\n";
    31. return;
    32. }
    33. vectorans;
    34. int cur=0;
    35. if(cnt) cur++;
    36. for(int i=1;i<=n;i++){
    37. if(s1[i]=='1'){
    38. ans.push_back({i,i});
    39. cur++;
    40. }
    41. }
    42. if(cur&1){
    43. ans.push_back({1,1});
    44. ans.push_back({2,n});
    45. ans.push_back({1,n});
    46. }
    47. cout<<"YES\n";
    48. cout<size()<<"\n";
    49. for(auto i:ans) cout<" "<"\n";
    50. }
    51. signed main(){
    52. int t;cin>>t;
    53. while(t--) solve();
    54. }

  • 相关阅读:
    quinn源码解析:QUIC数据包是如何发送的
    Python 爬虫 NO.1 URI和URL
    Spring RCE 漏洞 CVE-2022-22965复现分析
    冲刺学习-MySQL-基础
    CentOS 7 调优之周期性的访问中断
    VMware虚拟机-Ubuntu设置共享文件夹(超详细)
    【设计模式深度剖析】【10】【行为型】【状态模式】
    康力源体育IPO过会:年营收7亿 衡墩建控制98%股权
    你不知道的大像素全景,在行业应用中竟如此重要
    springboot 注入配置文件中的集合 List
  • 原文地址:https://blog.csdn.net/YuDuna/article/details/127733813