• Codeforces Round 895 (Div. 3)

    A.每次最多能把差缩小2*c克，向上取整

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,mod=998244353;
    4. #define int long long
    5. using node=tuple<int,int,int,int>;
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8.  
    9. int n,m,q;
    10. int a[N];
    11. void solve()
    12. {
    13.      int a,b,c;cin>>a>>b>>c;
    14.      cout<<(abs(a-b)+2*c-1)/(2*c)<<"\n";
    15. }
    16. signed  main() {
    17.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    18.     int t=1;
    19.     cin>>t;
    20.     while(t--) solve();
    21.     
    22. }
    23.

    B.直接枚举每个格子能走多大

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,M=2*N,mod=998244353;
    4. #define int long long
    5.  
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8. int a[N],b[N];
    9. int n, m;
    10.  
    11. void solve()
    12. {
    13.     cin>>n;
    14.     for(int i=1;i<=n;i++){
    15.         cin>>a[i]>>b[i];
    16.     }
    17.     int mx=1000000,mn=0;
    18.     for(int i=1;i<=n;i++)
    19.     {
    20.         mx=min(mx,a[i]+((b[i]-1)/2));
    21.     }
    22.     cout<<mx<<"\n";
    23. }
    24. signed  main() {
    25.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    26.     int t=1;
    27.     cin>>t;
    28.     while(t--) solve();
    29.     
    30. }
    31.

    C.首先容易构造的是gcd=2,相当于是一个偶数/2，那么这种情况要特判

    l==r，只能找他的质因子了，

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,M=2*N,mod=998244353;
    4. #define int long long
    5.  
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8. int a[N],b[N];
    9. int n, m;
    10.  
    11. void solve()
    12. {
    13.     int l,r;cin>>l>>r;
    14.     if(l==r)
    15.     {
    16.         for(int i=2;i<=l/i;i++){
    17.             if(l%i==0){
    18.                 int x=l/i;
    19.                 cout<<x<<" "<<l-x<<"\n";
    20.                 return ;
    21.             }
    22.         }
    23.         cout<<"-1\n";
    24.         return ;
    25.     }
    26.         for(int i=l;i<=r;i++)
    27.         {
    28.            if(i%2==0&&i!=2){
    29.                cout<<i/2<<" "<<i/2<<"\n";
    30.                return ;
    31.            }
    32.         }
    33.     
    34.     cout<<"-1\n";
    35. }
    36. signed  main() {
    37.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    38.     int t=1;
    39.     cin>>t;
    40.     while(t--) solve();
    41.     
    42. }
    43.

    D.容斥原理

    a+b-a*b，特判另一个数包含另一个数的集合就行

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,M=2*N,mod=998244353;
    4. #define int long long
    5.  
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8. int a[N],b[N];
    9. int n, m;
    10. int gcd(int a, int b)  // 欧几里得算法
    11. {
    12.     return b ? gcd(b, a % b) : a;
    13. }
    14. int lcm(int a,int b){
    15.     return a*b/gcd(a,b);
    16. }
    17. void solve()
    18. {
    19.     cin>>n;
    20.     int x,y;cin>>x>>y;
    22.     if(x%y==0)
    23.     {   int z=n/y-n/x;
    24.         cout<<-((z+1)*z)/2<<"\n";
    25.     }
    26.     else if(y%x==0)
    27.     {
    28.         int z=n/x-n/y;
    29.         cout<<((n-z+1+n)*z)/2<<"\n";
    30.     }
    31.     else if(x!=1&&y!=1&&x!=y){
    32.         int now=n/(lcm(x,y));
    33.         int z=n/x-now;
    34.         int res=(n-z+1+n)*z/2;
    35.         z=n/y-now;
    36.  
    37.         res-=((z+1)*z)/2;
    38.         cout<<res<<"\n";
    39.     }
    40.     else cout<<"-1\n";
    41. }
    42. signed  main() {
    43.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    44.     int t=1;
    45.     cin>>t;
    46.     while(t--) solve();
    47.     
    48. }
    49.

    E.直接线段树维护区间0的异或和 和 1的异或和，翻转操作就是互换而已

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,mod=998244353;
    4. #define int long long
    5.  
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8. struct node{
    9.     int l,r;
    10.     int s0,s1,w,add;
    11. }tr[N*4];
    12. int n,m,q;
    13. int a[N],b[N];
    14. string s;
    15. void pushup(int u){
    16.     tr[u].s0=tr[u<<1].s0^tr[u<<1|1].s0;
    17.     tr[u].s1=tr[u<<1].s1^tr[u<<1|1].s1;
    18. }
    19. void pushdown(int u){
    20.     if(tr[u].add){
    21.         tr[u<<1].add^=1;
    22.         tr[u<<1|1].add^=1;
    23.         swap(tr[u<<1].s0,tr[u<<1].s1);
    24.         swap(tr[u<<1|1].s0,tr[u<<1|1].s1);
    25.     }
    26.     tr[u].add=0;
    27. }
    28. void build(int u,int l,int r){
    29.     tr[u]={l,r,0,0,0,0};
    30.     if(l==r){
    31.         tr[u].w=b[l];
    32.         if(b[l]==1) tr[u].s1=a[l];
    33.         else tr[u].s0=a[l];
    34.     }
    35.     else{
    36.         int mid=l+r>>1;
    37.         build(u<<1,l,mid);
    38.         build(u<<1|1,mid+1,r);
    39.         pushup(u);
    40.     }
    41. }
    42. void modify(int u,int l,int r){
    43.     if(tr[u].l>=l&&tr[u].r<=r)
    44.     {
    45.         tr[u].add^=1;
    46.         swap(tr[u].s1,tr[u].s0);
    47.     }
    48.     else{
    49.         pushdown(u);
    50.         int mid=tr[u].l+tr[u].r>>1;
    51.         if(l<=mid) modify(u<<1,l,r);
    52.         if(r>mid) modify(u<<1|1,l,r);
    53.         pushup(u);
    54.     }
    55. }
    56. // node query(int u,int l,int r){
    57. //     if(tr[u].l>=l&&tr[u].r<=r){
    58. //         return tr[u];
    59. //     }
    60. //     else{
    61. //         pushdown(u);
    62. //         node res={0,0,0,0,0};
    63. //         int mid=tr[u].l+tr[u].r>>1;
    64. //         if(l<=mid){
    65. //             res=query(u<<1,l,r);
    66. //         }
    67. //         if(r>mid) modify(u<<1|1,mid+1,r);
    68.     
    69. //     }
    70. // }
    71. void solve()
    72. {
    73.     cin>>n;
    74.     for(int i=1;i<=n;i++) cin>>a[i];
    75.     cin>>s;
    76.     s="?"+s;
    77.     for(int i=1;i<=n;i++) b[i]=s[i]-'0';
    78.     build(1,1,n);
    79.     int q;cin>>q;
    80.     while(q--){
    81.         int op;
    82.         cin>>op;
    83.         if(op==1){
    84.             int l,r;cin>>l>>r;
    85.             modify(1,l,r);
    86.         }
    87.         else{
    88.             int x;cin>>x;
    89.             if(x==1) cout<<tr[1].s1<<" ";
    90.             else cout<<tr[1].s0<<" ";
    91.         }
    92.     }
    93.     cout<<"\n";
    94. }
    95. signed  main() {
    96.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    97.     int t=1;
    98.     cin>>t;
    99.     while(t--) solve();
    100.     
    101. }
    102.

    F.画图样例其实可以知道，按照拓扑序直接处理即可，最后会有多个环，每个环的贡献最大是让一个点贡献不能*2，其他都可以

    我写的比较麻烦，先拓扑序把不是环的点先存了，再把每个环tarjan缩点，然后单独处理每个环，每个环算完出发点后又dfs存答案0.0

    所以用了dfs+拓扑排序+tarjan

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,M=2*N,mod=998244353;
    4. #define int long long
    5.  
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8. int a[N],b[N];
    9. int n, m;
    10. int G[N];
    11. int dfn[N], low[N], timestamp;
    12. int stk[N], top;
    13. bool in_stk[N],Size[N];
    14. int id[N], scc_cnt;
    15. vector<int> g[N];
    16. int din[N],dout[N];
    17. void tarjan(int u)
    18. {
    19.     dfn[u] = low[u] = ++ timestamp;
    20.     stk[ ++ top] = u, in_stk[u] = true;
    21.   
    22.         int j = G[u];
    23.         if (!dfn[j])
    24.         {
    25.             tarjan(j);
    26.             low[u] = min(low[u], low[j]);
    27.         }
    28.         else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    29.     
    30.  
    31.     if (dfn[u] == low[u])
    32.     {
    33.         ++ scc_cnt;
    34.         int y;
    35.         do {
    36.             y = stk[top -- ];
    37.             in_stk[y] = false;
    38.             id[y] = scc_cnt;
    39.           
    40.         } while (y != u);
    41.     }
    42. }
    43. void solve()
    44. {
    45.     cin>>n;
    46.     top=timestamp=scc_cnt=0;
    47.     for(int i=0;i<=n;i++){
    48.         G[i]=0;
    49.         g[i].clear();
    50.         low[i]=dfn[i]=id[i]=0;
    51.         in_stk[i]=false;
    52.         din[i]=dout[i]=0;
    53.      
    54.     }
    55.     for(int i=1;i<=n;i++){
    56.         cin>>a[i];
    57.        G[i]=a[i];
    58.        din[a[i]]++;
    59.     }
    60.     for(int i=1;i<=n;i++) cin>>b[i];
    61.     for(int i=1;i<=n;i++)
    62.     {
    63.         if(!dfn[i]) tarjan(i);
    64.     }   
    65.     queue<int> q;
    66.       vector<int> res;
    67.     for(int i=1;i<=n;i++) if(din[i]==0) q.push(i);
    68.     while(q.size()){
    69.         auto t=q.front();
    70.         q.pop();res.push_back(t);
    71.         int v=G[t];
    72.         if(--din[v]==0){
    73.             q.push(v);
    74.         }
    75.     }
    76.  
    77.     for(int i=1;i<=n;i++){
    78.     
    79.         g[id[i]].push_back(i);
    80.     }
    81.     
    82.     vector<bool> st(n+10,false);
    83.     function<void(int)> dfs=[&](int u){
    84.         if(st[u]) return ;
    85.         st[u]=true;
    86.         res.push_back(u);
    87.         dfs(G[u]);
    88.     };
    89.  
    90.     for(int i=1;i<=scc_cnt;i++)
    91.     {
    92.         if(g[i].size()==1) continue;
    93.         else{
    94.             sort(g[i].begin(),g[i].end());
    95.             m=g[i].size();
    96.             int now=0,mx=0,idx=0;
    97.             
    98.             for(auto x:g[i]) now+=2*b[x];
    99.             for(int x:g[i])
    100.             {
    101.                 if(mx<now-b[x]) idx=x,mx=max(mx,now-b[x]);
    102.             }
    103.             dfs(G[idx]);
    104.         }
    105.     }
    106.     for(auto x:res) cout<<x<<" ";
    107.     cout<<"\n";
    108.  
    109. }
    110. signed  main() {
    111.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    112.     int t=1;
    113.     cin>>t;
    114.     while(t--) solve();
    115.     
    116. }
    117.

    G.首先把左右两边的1去掉没用，

    然后思考中间的值，因为处理完后左右两边一定不是1，所以如果区间乘大于1e9

    说明至少有60个2相乘，那么中间的1肯定也只能要

    然后如果不大于

    那么说明中间区间的数加起来不大于60（去掉中间是1的数）

    那么直接枚举左右端点即可

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10,M=2*N,mod=998244353;
    4. #define int long long
    5.  
    6. typedef long long LL;
    7. typedef pair<int, int> PII;
    8. int a[N],b[N];
    9. int n, m;
    10.  
    11. void solve()
    12. {
    13.     cin>>n;
    14.     for(int i=1;i<=n;i++) cin>>a[i];
    15.     int l=1,r=n;
    16.     while(a[l]==1&&l<r){
    17.         l++;
    18.     }
    19.     while(a[r]==1&&l<r){
    20.         r--;
    21.     }
    22.     int res=1;
    23.     for(int i=l;i<=r;i++){
    24.         res*=a[i];
    25.         if(res>1e9){
    26.             cout<<l<<" "<<r<<"\n";
    27.             return ;
    28.         }
    29.     }
    30.     int idx=0,sum=0;
    31.     for(int i=1;i<=n;i++){
    32.         if(a[i]>1) b[++idx]=i;
    33.         sum+=a[i];
    34.     }
    35.     int ans=sum,ansl=1,ansr=1;
    36.     for(int i=1;i<=idx;i++){
    37.         res=1;
    38.         l=b[i];
    39.         int s=0;
    40.         for(int j=i;j<=idx;j++){
    41.             res*=a[b[j]];
    42.             r=b[j];
    43.             s+=a[b[j]];
    44.             int val=sum-s-(r-l+1-(j-i+1))+res;
    45.             if(val>ans){
    46.                 ans=val;
    47.                 ansl=l,ansr=r;
    48.             }
    49.         }
    50.     }
    51.     cout<<ansl<<" "<<ansr<<"\n";
    52. }
    53. signed  main() {
    54.     cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    55.     int t=1;
    56.     cin>>t;
    57.     while(t--) solve();
    58.     
    59. }
    60.

  • 相关阅读:
    云计算与大数据第5章 云计算安全题库及答案
    一文掌握Python多线程与多进程
    可完全替代FTP的文件传输工具大集合
    轻松使用androidstudio交叉编译libredwg库
    阅读 | 001《人工智能导论》（一）绪论及知识表示篇
    nodejs+vue面向中小学课堂教学辅助软件系统的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计
    ANR问题的分析与解决思路
    上门预约按摩家政小程序开发；
    智慧安防视频监控系统EasyCVR平台突然运行异常，是什么原因？
    Idea怎么配置Maven才能优先从本地仓库获取依赖
  • 原文地址：https://blog.csdn.net/qq_61657632/article/details/132770010