• 2022/8/3

    活动地址：CSDN21天学习挑战赛

    Problem - 1326D1 - Codeforces双指针

     很明显我们要设l，r分别作为头尾指针，如何s[l]==s[r],就r--,l++,如不等就要分开考虑了，分别枚举l和r就行，一开始我这脑子竟然还想要双重循环暴力，，，

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 1e5+5;
    5. ll t;
    6. string s;
    7. bool pd(string ss){
    8.     string s2=ss;
    9.     reverse(ss.begin(), ss.end());
    10.     return s2==ss;
    11. }
    12. int main(){
    13.     
    14.   std::ios::sync_with_stdio(false);
    15.   cin.tie(0);
    16.   cout.tie(0);
    17.     cin>>t;
    18.     while(t--){
    19.         cin>>s;
    20.         ll ans=0;
    21.         string tmp;
    22.         string res;
    23.         string sl="",sr="";
    24.         ll l=0,r=s.size()-1;
    25.         while(l<=r){
    26.             if(s[l]==s[r]){
    27.                 if(l
    28.                     sl+=s[l];sr=s[r]+sr;
    29.                     l++;r--;
    30.                 }
    31.                 else{
    32.                     sl+=s[l];l++;
    33.                 }
    34.                 tmp=sl+sr;
    35.                 if(anssize()){
    36.                     ans=tmp.size();
    37.                     res=tmp;
    38.                 }
    39.                 }
    40.             else{
    41.                 ll x=l;string sx=sl;
    42.                 while(x
    43.                     sx+=s[x];
    44.                     tmp=sx+sr;
    45.                    // cout<
    46.                     if(pd(tmp)){
    47.                         if(anssize()){
    48.                             ans=tmp.size();
    49.                             res=tmp;
    50.                         }
    51.                     }
    52.                     x++;
    53.                 }
    54.                 ll y=r;string sy=sr;
    55.                 while(y>l){
    56.                     sy=s[y]+sy;
    57.                     tmp=sl+sy;
    58.                     if(pd(tmp)){
    59.                         if(anssize()){
    60.                             ans=tmp.size();
    61.                             res=tmp;
    62.                         }
    63.                     }
    64.                     y--;
    65.                 }
    66.                 break;
    67.             }
    68.         }
    69.         cout<
    70.     }
    71.     system("pause");
    72.     return 0;
    73. }

    1371D - Grid-00100

    只要看出规律来就好办了，最好的贪心方式就是一开始先填对角线的，然后每次位置加1即可，这题竟然1600，，，

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 1e5+5;
    5. ll t,n,k,a[305][305],b[305],r[305],c[305];
    6. int main(){
    7.     scanf("%lld",&t);
    8.     while(t--){
    9.         scanf("%lld%lld",&n,&k);
    10.         for(int i=1;i<=n;i++)
    11.         for(int j=1;j<=n;j++) a[i][j]=0;
    12.         for(int i=1;i<=n;i++) b[i]=i,r[i]=c[i]=0;
    13.         ll x=1;
    14.         while(k){
    15.                 a[x][b[x]]=1;
    16.                 b[x]++;
    17.                 if(b[x]>n) b[x]=1;
    18.                 x++;
    19.                 if(x>n) x=1;
    20.                 k--;
    21.         }
    22.         for(int i=1;i<=n;i++){
    23.             for(int j=1;j<=n;j++){
    24.                 r[i]+=a[i][j];
    25.                 c[j]+=a[i][j];
    26.             }
    27.         }
    28.         ll maxr=0,minr=1e18,maxc=0,minc=1e18;
    29.         for(int i=1;i<=n;i++){
    30.            // cout<
    31.             maxr=max(maxr,r[i]);minr=min(minr,r[i]);
    32.             maxc=max(maxc,c[i]);minc=min(minc,c[i]);
    33.         }
    34.         printf("%lld\n",(maxr-minr)*(maxr-minr)+(maxc-minc)*(maxc-minc));
    35.         for(int i=1;i<=n;i++){
    36.             for(int j=1;j<=n;j++) printf("%lld",a[i][j]);
    37.             printf("\n");
    38.         }
    39.     }
    40.     system("pause");
    41.     return 0;
    42. }

    P3521 [POI2011]ROT-Tree Rotations - 洛谷 | 线段树合并

    可以看成是每个叶节点就是一个权值线段树，合并左右子树只会对跨子树的逆序对产生影响，所以合并时取交换前和交换后的最小值就可以了，这题另外一个难点可能就是输入了，，

    题解 P3521 【[POI2011]ROT-Tree Rotations】 - 一个NSOIer的博客 - 洛谷博客

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. ll n,cnt,u,v,ans;
    6. struct node{
    7.     ll l,r,size;
    8. }t[N*20];
    9. void pushup(ll p){t[p].size=t[t[p].l].size+t[t[p].r].size;}
    10. ll update(ll l ,ll r,ll k){
    11.     ll p=++cnt;
    12.     if(l==r){t[p].size++;return p;}
    13.     ll mid=l+r>>1;
    14.     if(k<=mid) t[p].l=update(l,mid,k);
    15.     else t[p].r=update(mid+1,r,k);
    16.     pushup(p);
    17.     return p;
    18. }
    19. ll merge(ll x,ll y,ll l,ll r){
    20.     if(!x||!y) x|=y;
    21.     else if(l==r){t[x].size+=t[y].size;}
    22.     else{
    23.         u+=t[t[x].r].size*t[t[y].l].size;//交换前的逆序对数
    24.         v+=t[t[x].l].size*t[t[y].r].size;//交换后的逆序对数
    25.         ll mid=l+r>>1;
    26.         t[x].l=merge(t[x].l,t[y].l,l,mid);//继续向下面操作，合并左右子节点
    27.         t[x].r=merge(t[x].r,t[y].r,mid+1,r);
    28.         pushup(x);
    29.        
    30.     } 
    31.     return x;
    32. }
    33. ll dfs(){
    34.     ll val,p;
    35.     scanf("%lld",&val);
    36.     if(val) p=update(1,n,val);
    37.     else{
    38.         ll ls=dfs(),rs=dfs();//获取左右子树的根节点
    39.         u=0,v=0;
    40.         p=merge(ls,rs,1,n);//合并左右子树
    41.         ans+=min(u,v);
    42.     }
    43.     return p;
    44. }
    45. int main(){
    46.     scanf("%lld",&n);
    47.     dfs();
    48.     printf("%lld\n",ans);
    49.     system("pause");
    50.     return 0;
    51. }

    P3224 [HNOI2012]永无乡 - 洛谷 | 线段树合并

    第一次自己做出合并的题目来，并查集维护连通性的同时进行线段树的合并，每个岛就是一棵线段树，查询的时候也是直接查自己的祖先，即findd(x)

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. ll n,m,cnt,s[100005],rt[300005],ma[100005];
    6. ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
    7. struct node{
    8.     ll l,r,val;
    9. }t[N*20];
    10. void pushup(ll p){t[p].val=t[t[p].l].val+t[t[p].r].val;}
    11. void update(ll l,ll r,ll &p,ll k){
    12.     if(!p) p=++cnt;
    13.     if(l==r){t[p].val++;return;}
    14.     ll mid=l+r>>1;
    15.     if(k<=mid) update(l,mid,t[p].l,k);
    16.     else update(mid+1,r,t[p].r,k);
    17.     pushup(p);
    18. }
    19. void merge(ll &x,ll y){
    20.     if(!x||!y) x|=y;
    21.     else{
    22.         t[x].val+=t[y].val;
    23.         merge(t[x].l,t[y].l);
    24.         merge(t[x].r,t[y].r);
    25.         pushup(x);
    26.     }
    27. }
    28. ll query(ll l,ll r,ll p,ll k){
    29.     if(l==r) return l;
    30.     ll mid=l+r>>1;
    31.     if(k<=t[t[p].l].val) return query(l,mid,t[p].l,k);
    32.     else return query(mid+1,r,t[p].r,k-t[t[p].l].val);
    33. }
    34. int main(){
    35.     scanf("%lld%lld",&n,&m);
    36.     for(int i=1;i<=n;i++){
    37.         ll x;
    38.         scanf("%lld",&x);
    39.         update(1,n,rt[i],x);
    40.         ma[x]=i;
    41.         s[i]=i;
    42.     }
    43.     for(int i=1;i<=m;i++){
    44.         ll u,v;
    45.         scanf("%lld%lld",&u,&v);
    46.         ll x=findd(u),y=findd(v);
    47.         if(x==y) continue;
    48.         s[y]=x;
    49.         merge(rt[x],rt[y]);
    50.     }
    51.    // cout<
    52.     ll q;
    53.     scanf("%lld",&q);
    54.     while(q--){
    55.         char ch[3];
    56.         ll x,y;
    57.         scanf("%s%lld%lld",ch,&x,&y);
    58.         if(ch[0]=='Q'){
    59.             ll ans=0; 
    60.             if(x<1||t[rt[findd(x)]].valn){printf("-1\n");continue;}
    61.             ans=query(1,n,rt[findd(x)],y);
    62.             printf("%lld\n",ma[ans]);
    63.         }
    64.         else{
    65.             ll xx=findd(x),yy=findd(y);
    66.             if(xx==yy) continue;
    67.             s[yy]=xx;
    68.             merge(rt[xx],rt[yy]);
    69.         }
    70.         //cout<
    71.     }
    72.     system("pause");
    73.     return 0;
    74. }

    P1600 [NOIP2016 提高组] 天天爱跑步 - 洛谷 | 线段树合并

    每个人的路径要是一个一个看的话时间复杂度太高了，考虑树上差分，这样考虑两个端点就可以了，一般的情况下，一般都是s->lca,然后再lca->t,先考虑s,假设dep[j]

    dep[s]=dep[j]+w[j]，

    则在树上的体现就是dep[s]+1,查询的时候只需要查dep[j]+w[j]出现了几次就可以；再考虑t，假设dep[j]>dep[t],则有

    （dep[s]-dep[lc])+dep[y]-dep[lc]+w[j]=dep[j];

    lc是s,t的lca，因为是从s走过来的，所以要减去s到lca的这段,y是深度小于t的点，意思就是从lca->t的过程中有一个点y满足这个式子就可以，最后dfs遍历一遍求出答案就行了

    题解 P1600 【天天爱跑步】 - Robin12138 的博客 - 洛谷博客

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. ll n,m,w[300005];
    6. //链式前向星
    7. ll head[300005],cnt;
    8. struct Edge{
    9.     ll from,to,next;
    10. }edge[300005*2];
    11. void addedge(ll from, ll to){
    12.     edge[++cnt].from = from;
    13.     edge[cnt].to = to;
    14.     edge[cnt].next =head[from];
    15.     head[from] = cnt;
    16. }
    17. //lca
    18. ll son[300005],f[300005],siz[300005],top[300005],dep[300005];
    19. void dfs1(ll u,ll fa){
    20.     siz[u]=1;f[u]=fa;dep[u]=dep[fa]+1;
    21.     for(int i=head[u];i;i=edge[i].next){
    22.         ll j=edge[i].to;
    23.         if(j==fa) continue;
    24.         dfs1(j,u);
    25.         siz[u]+=siz[j];
    26.         if(siz[son[u]]
    27.     }
    28. }
    29. void dfs2(ll u,ll topx){
    30.     top[u]=topx;
    31.     if(son[u]) dfs2(son[u],topx);
    32.     for(int i=head[u];i;i=edge[i].next){
    33.         ll j=edge[i].to;
    34.         if(j!=f[u]&&j!=son[u]) dfs2(j,j);
    35.     }
    36. }
    37. ll lca(ll x,ll y){
    38.     while(top[x]!=top[y]){
    39.         if(dep[top[x]]swap(x,y);
    40.         x=f[top[x]];
    41.     }
    42.     return dep[x]
    43. }
    44. //线段树
    45. ll rt[600005],ct,ans[300005];
    46. struct node{
    47.     ll l,r,val;
    48. }t[600005*40];
    49. void pushup(ll p){t[p].val=t[t[p].l].val+t[t[p].r].val;}
    50. void update(ll l,ll r,ll &p,ll k,ll v){
    51.     if(!p) p=++ct;
    52.     if(l==r){t[p].val+=v;return;}
    53.     ll mid=l+r>>1;
    54.     if(k<=mid) update(l,mid,t[p].l,k,v);
    55.     else update(mid+1,r,t[p].r,k,v);
    56.     pushup(p);
    57. }
    58. void merge(ll &x,ll y,ll l,ll r){//检查了半天没加取址符号，我这个老六
    59.     if(!x||!y) x|=y;
    60.     else if(l==r) t[x].val+=t[y].val;
    61.     else{
    62.         ll mid=l+r>>1;
    63.         merge(t[x].l,t[y].l,l,mid);
    64.         merge(t[x].r,t[y].r,mid+1,r);
    65.         pushup(x);
    66.     }
    67. }
    68. ll query(ll l,ll r,ll p,ll k){
    69.     if(l==r) return t[p].val;
    70.     ll mid=l+r>>1;
    71.     if(k<=mid) return query(l,mid,t[p].l,k);
    72.     else return query(mid+1,r,t[p].r,k);
    73. }
    74. void dfs(ll u){
    75.     for(int i=head[u];i;i=edge[i].next){
    76.         ll j=edge[i].to;
    77.         if(j==f[u]) continue;
    78.         dfs(j);
    79.         merge(rt[u],rt[j],1,n<<1);
    80.     }
    81.     if(w[u]&&n+dep[u]+w[u]<=2*n) ans[u]+=query(1,n<<1,rt[u],n+dep[u]+w[u]);
    82.     ans[u]+=query(1,n<<1,rt[u],n+dep[u]-w[u]);
    83. }
    84. int main(){
    85.     scanf("%lld%lld",&n,&m);
    86.     for(int i=1;i
    87.         ll u,v;
    88.         scanf("%lld%lld",&u,&v);
    89.         addedge(u,v);addedge(v,u);
    90.     }
    91.     dfs1(1,0);dfs2(1,1);
    92.     for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    93.     for(int i=1;i<=m;i++){
    94.         ll x,y;
    95.         scanf("%lld%lld",&x,&y);
    96.         ll lc=lca(x,y);
    97.         //cout<<"ssss"<
    98.         update(1,n<<1,rt[x],n+dep[x],1);
    99.         update(1,n<<1,rt[y],2*dep[lc]-dep[x]+n,1);
    100.         //(dep[y]-dep[lc])-dep[lc]-(dep[x]-dep[lc])=dep[j]-w[j];
    101.         update(1,n<<1,rt[lc],n+dep[x],-1);
    102.         update(1,n<<1,rt[f[lc]],2*dep[lc]-dep[x]+n,-1);
    103.     }
    104.     dfs(1);
    105.     for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    106.     system("pause");
    107.     return 0;
    108. }

    ​

  • 相关阅读:
    C++ explicit的作用
    TRC天然拟胆碱生物碱丨艾美捷TRC盐酸乙环胺
    102.网络游戏逆向分析与漏洞攻防-ui界面的设计-反隐身功能的界面设计与实现（有不使用MFC生成，自己手写代码创建复选框与事件的例子）
    HTML进阶
    java计算机毕业设计郑州卷烟厂库存管理系统源程序+mysql+系统+lw文档+远程调试
    如何制定有效的项目进度计划——甘特图
    【AcWing16】【LeetCode】并查集Union Find-128/130/*1020-学完广度优先/深度优先要回来再看
    21GA-ELM，遗传算法优化ELM预测，并和优化前后以及真实数值进行对比，确定结果，基于MATLAB平台，程序已经调通，可以直接运行，需要直接拍下。
    RISC-V内核中科蓝讯BT8922开发
    用 Three.js 创建一个酷炫且真实的地球
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126151157