2019牛客暑期多校训练营（第三场）

深藏阁楼爱情的钟 2023-06-04 11:59 21阅读 0赞

## Solutions ##

--------------------

### B：Crazy Binary String ###

题意：

给出$01$串，询问最长的“$01$数量相等”的字串和子序列。

思路：

字串的话，把$0$变成$-1$，求前缀和，如果$sum\[r\]-sum\[l-1\]=0$，说明$01$数量相等。

所以可以跑一遍，$map$找到符合的位置。取最大。

子序列：显示是$2\{\\ast\}min(num\[zero\],num\[one\])$

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=1e5+10;
     4 
     5 int n,sum[maxn];
     6 char s[maxn];
     7 
     8 map<int,int> mp;
     9 int main() {
    10     scanf("%d",&n);
    11     scanf("%s",s+1);
    12     int one=0,zero=0;
    13     for(int i=1;i<=n;i++) {
    14         if(s[i]=='1') one++;
    15         else zero++;
    16         sum[i]=sum[i-1]+(s[i]=='1'?1:-1);
    17     }
    18     mp[0]=0;
    19     int ans=0;
    20     for(int i=1;i<=n;i++) {
    21         if(mp.find(sum[i])!=mp.end()) {
    22             ans=max(ans,i-mp[sum[i]]);
    23         } else mp[sum[i]]=i;
    24     }
    25     printf("%d %d\n",ans,min(one,zero)*2);
    26     return 0;
    27 }

### D：Big Integer ###

题意：

$A\\left(i^j\\right)$表示$i^j$个$1$，求$A\\left(i^j\\right)\\equiv0mod\\ p$有多少对

*  $1\\leq\\ i\\leq\\ n$
 *  $1\\leq\\ j\\leq\\ m$
 *  $p$为质数

思路：

$1111$可写为$\\frac\{ \{10\}^n-1\}9$，则可以转化为

$$\\frac\{ \{10\}^n-1\}9\\equiv0mod\\ p$$

$$\\left(\{10\}^n-1\\right)\\ast\\ inv\\left(9\\right)\\equiv0mod\\ p$$

若$p=2或5$，明显答案为$0$，

若$p$与$9$互质，$inv\\left(9\\right)\\neq0$，

所以 $$\{10\}^n-1\\equiv0mod\\ p$$

即 $$\{10\}^n\\equiv1mod\\ p$$

由欧拉定理得$\\varphi\\left(p\\right)$必定满足，但不一定是最小的。

所以我们可以求得最小循环节$x$，复杂度$O\\left(\\sqrt\{p\}log\\ p\\right)$

转化为有多少对$x\\mid\{i^j\}$

考虑固定$j$

对$x$进行质因数分解，

$x=p\_1^\{ax\_1\}\\ast\\ p\_2^\{ax\_2\}\\ast\\ldots\\ast\\ p\_k^\{ax\_k\}$

那么$i$的每种质因子的个数至少有$\\lceil\\frac\{ax\}j\\rceil$

令$g=p\_1^\{\\lceil\\frac\{ax\_1\}j\\rceil\}\\ast\\ p\_2^\{\\lceil\\frac\{ax\_2\}j\\rceil\}\\ast\\ldots\\ast\\ p\_k^\{\\lceil\\frac\{ax\_k\}j\\rceil\}$，$g\\mid\\ i$

在$n$的范围内有$\\lceil\\frac\{n\}g\\rceil$个。

$g$随着$j$的改变而改变。

令$mx=max\\left(ax\_1,ax\_2,\\ldots\\,ax\_k\\right)$，若$j\\geq\\ mx$，对后面的$j$，影响不会改变。有$\\left(m-j\\right)\\ast\\lceil\\frac\{n\}g\\rceil$个。

考虑$p=3$与$9$不互质，根据整除$3$的性质，有$n\\setminus3\\ast\\ m$个，（数字之和为$3$的倍数）

1 //#define DEBUG
     2 #include<bits/stdc++.h>
     3 using namespace std;
     4 const int N=100010;
     5 const int inf=0X3f3f3f3f;
     6 const long long INF = 0x3f3f3f3f3f3f3f3f;
     7 const double eps = 1e-6;
     8 const double pi = acos(-1.0);
     9 //const int mod = 1000000007;
    10 typedef long long ll;
    11  
    12 int q_pow(int a,int b,int p) {
    13     int tmp=a%p;
    14     int ans=1;
    15     while(b) {
    16         if(b&1) ans=1ll*ans*tmp%p;
    17         tmp=1ll*tmp*tmp%p;
    18         b=b>>1;
    19     }
    20     return ans;
    21 }
    22  
    23 int main() {
    24     #ifdef DEBUG
    25     freopen("in.txt","r",stdin);
    26     #endif
    27     int _,p,n,m;
    28     for(scanf("%d",&_);_;_--) {
    29         scanf("%d%d%d",&p,&n,&m);
    30         if(p==2||p==5) {
    31             puts("0");
    32             continue;
    33         }
    34         if(p==3) {
    35             printf("%lld\n",1ll*n/3*m);
    36             continue;
    37         }
    38         int D=p-1,x=D;
    39         for(int i=1;i*i<=D;i++) {
    40             if(D%i) continue;
    41             if(q_pow(10,i,p)==1) x=min(x,i);
    42             if(q_pow(10,D/i,p)==1) x=min(x,D/i);
    43         }
    44         vector<pair<int,int>> factor;
    45         int maxx=-1;
    46         for(int i=2;i*i<=x;i++) {
    47             if(x%i==0) {
    48                 int cnt=0;
    49                 while(x%i==0) {
    50                     cnt++;
    51                     x/=i;
    52                 }
    53                 maxx=max(maxx,cnt);
    54                 factor.push_back({i,cnt});
    55             }
    56         }
    57         if(x>1) factor.push_back({x,1});
    58        // puts("***");
    59         ll ans=0;
    60         for(int j=1;j<=m;j++) {
    61             ll g=1;
    62             for(auto it:factor) {
    63                 int t=(it.second+j-1)/j;
    64                 while(t--) {
    65                     g=g*(it.first);
    66                 }
    67             }
    68             ans+=n/g;
    69             if(j>=maxx) {
    70                 ans+=(m-j)*(n/g);
    71                 break;
    72             }
    73         }
    74         printf("%lld\n",ans);
    75     }
    76 }

### F：Planting Trees ###

题意：

给出$n\\times\\ n$的矩阵，和一个$m$，求最大的子矩阵，要求子矩阵的最大值和最小值差值小于等于$m$。

思路：

枚举上下边界，然后单调队列处理左右边界。

把每一列的最大值、最小值记下来，然后用单调队列维护，如果差值大于$m$就往右移动。

1 //#define DEBUG
     2 #include<bits/stdc++.h>
     3 using namespace std;
     4 const int N=100010;
     5 const int inf=0X3f3f3f3f;
     6 const long long INF = 0x3f3f3f3f3f3f3f3f;
     7 const double eps = 1e-6;
     8 const double pi = acos(-1.0);
     9 const int mod = 1000000007;
    10 typedef long long ll;
    11 
    12 int a[610][610];
    13 int b1[610],b2[610];
    14 int q1[610],q2[610],l1,l2,r1,r2;
    15 
    16 int main() {
    17     #ifdef DEBUG
    18     freopen("in.txt","r",stdin);
    19     #endif
    20     int _;
    21     for(scanf("%d",&_);_;_--) {
    22         int n,m,ans=0;
    23         scanf("%d%d",&n,&m);
    24         for(int i=1;i<=n;i++) {
    25             for(int j=1;j<=n;j++)
    26                 scanf("%d",&a[i][j]);
    27         }
    28         for(int i=1;i<=n;i++) {
        //上界
    29             for(int j=1;j<=n;j++) b1[j]=b2[j]=a[i][j]; //初始化
    30             for(int j=i;j<=n;j++) {
        // 下界
    31                 for(int k=1;k<=n;k++) b1[k]=min(b1[k],a[j][k]),b2[k]=max(b2[k],a[j][k]); //维护
    32                 l1=l2=1;r1=r2=0;
    33                 if((j-i+1)*n<=ans) continue; //剪枝
    34                 for(int w=1,k=1;k<=n;k++) {
        //左右边界
    35                     while(l1<=r1&&b1[q1[r1]]>=b1[k]) --r1; //单调增
    36                     q1[++r1]=k;
    37                     while(l2<=r2&&b2[q2[r2]]<=b2[k]) --r2; //单调减
    38                     q2[++r2]=k;
    39                     while(w<=k&&b2[q2[l2]]-b1[q1[l1]]>m) {
    40                         w++;
    41                         while(l1<=r1&&q1[l1]<w) ++l1;
    42                         while(l2<=r2&&q2[l2]<w) ++l2;
    43                     }
    44                     if((j-i+1)*(n-w+1)<=ans) break;
    45                     if(w<=k) ans=max(ans,(j-i+1)*(k-w+1));
    46                 }
    47             }
    48         }
    49         printf("%d\n",ans);
    50     }
    51 }

### G：Removing Stones ###

题意：

给出$n$堆石子，每次可以选非空且不同的两堆，然后各取一个石子，此操作可以进行任意次，很明显只要数量为偶数，Mark必定可以完成，现在问你有多少个区间$\\left(l,r\\right)$，Mark可以完成。

思路：

很明显题目可以转化为求多少个这样的区间$\\left(l,r\\right)$：

$$max\_\{l\\leq\\ i\\leq\\ r\}\\ \\leq\\ \\sum\_\{i=l\}^ra\_i$$

可以用$RMQ$查询最大值，前缀和查询区间和，考虑计数，可以分治。

每次在小区间枚举一个端点，在大区间二分另一个端点

比如左边区间小，就在右边二分找另一个端点。

记最值下标为$k$，则需满足$2\\ast\\ a\[k\]\\leq\\ sum\[r\]-sum\[l-1\]$

枚举左边，所以$sum\[r\]\\geq\\ 2\\ast\\ a\[k\]+sum\[l-1\]$，找第一个大于$2\\ast\\ a\[k\]+sum\[l-1\]$的位置

若右边区间小，同理。

1 //#define DEBUG
     2 #include<bits/stdc++.h>
     3 using namespace std;
     4 const int N=300010;
     5 const int inf=0X3f3f3f3f;
     6 const long long INF = 0x3f3f3f3f3f3f3f3f;
     7 const double eps = 1e-6;
     8 const double pi = acos(-1.0);
     9 const int mod = 1000000007;
    10 typedef long long ll;
    11 
    12 ll sum[N],ans;
    13 int n,lg[N],a[N],dp[N][20];
    14 
    15 void rmq() {
    16     lg[0]=-1;
    17     for(int i=1;i<=n;i++) {
    18         lg[i]=(i&(i-1))?lg[i-1]:lg[i-1]+1;
    19         dp[i][0]=i;
    20     }
    21     for(int j=1;j<=lg[n];j++) {
    22         for(int i=1;i+(1<<j)-1<=n;i++)
    23             dp[i][j]=a[dp[i][j-1]]>a[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
    24     }
    25 }
    26 
    27 int query(int l,int r) {
    28     int k=lg[r-l+1];
    29     return (a[dp[l][k]]>a[dp[r-(1<<k)+1][k]])?dp[l][k]:dp[r-(1<<k)+1][k];
    30 }
    31 
    32 
    33 int bs1(int l,int r,ll v) {
    34     if(sum[r]<v) return r+1;
    35     int res=-1,mid;
    36     while(l<=r) {
    37         mid=(l+r)>>1;
    38         if(sum[mid]>=v) {
    39             res=mid;
    40             r=mid-1;
    41         } else l=mid+1;
    42     }
    43     return res;
    44 }
    45 
    46 int bs2(int l,int r,ll v) {
    47     if(sum[l-1]>v) return l-1;
    48     int res=-1,mid;
    49     while(l<=r) {
    50         mid=(l+r)>>1;
    51         if(sum[mid-1]<=v) {
    52             res=mid;
    53             l=mid+1;
    54         } else r=mid-1;
    55     }
    56     return res;
    57 }
    58 
    59 void work(int l,int r) {
    60     if(r-l+1<=1) return ;
    61     if(r-l+1==2) {
    62         if(a[l]==a[r]) ans++;
    63         return;
    64     }
    65     int k=query(l,r);
    66     if(k-l<r-k) {
    67         for(int i=l;i<=k;i++) {
    68             int j=bs1(k,r,2ll*a[k]+sum[i-1]);
    69             ans+=(r-j+1);
    70         }
    71     } else {
    72         for(int i=k;i<=r;i++) {
    73             int j=bs2(l,k,sum[i]-2ll*a[k]);
    74             ans+=(j-l+1);
    75         }
    76     }
    77     work(l,k-1);
    78     work(k+1,r);
    79 }
    80 
    81 
    82 int main() {
    83     #ifdef DEBUG
    84     freopen("in.txt","r",stdin);
    85     #endif
    86     int _;
    87     for(scanf("%d",&_);_;_--) {
    88         scanf("%d",&n);
    89         sum[0]=0;
    90         for(int i=1;i<=n;i++) {
    91             scanf("%d",&a[i]);
    92             sum[i]=sum[i-1]+a[i];
    93         }
    94         rmq();
    95         ans=0;
    96         work(1,n);
    97         printf("%lld\n",ans);
    98     }
    99 }

### H：Magic Line ###

题意：

给出平面上$n$个点，要画一条直线，把这些点划分为数量相等的两部分。

思路：

对$x,y$双关键字排序，然后取中间(偏左)的那个点，然后稍微偏一点即可。(两个纵坐标加的数不要互为相反数，刁钻一点)

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=10010;
     4 
     5 int _,n;
     6 struct Point{
     7     int x,y;
     8     bool operator < (const Point &b)const {
     9         return x<b.x||(x==b.x&&y<b.y);
    10     }
    11 }p[maxn];
    12 
    13 int main() {
    14     for(scanf("%d",&_);_;_--) {
    15         scanf("%d",&n);
    16         for(int i=1;i<=n;i++) {
    17             scanf("%d%d",&p[i].x,&p[i].y);
    18         }
    19         sort(p+1,p+n+1);
    20         printf("%d %d %d %d\n",p[n/2].x-1,p[n/2].y+99999999+1,p[n/2].x+1,p[n/2].y-99999999);
    21     }
    22 }

### J：LRU management ###

题意：

给出一个容器，最多放$m$块，然后一些列操作，

$opt=1$，不改变序列，

如果能找到，根据v的值，输出它前后或者本身的$data$。

$opt=0$，改变序列，

如果能找到，输出它的$data$，并把它移动到末尾，

如果找不到，输出$v$值，并把它加入末尾。

如果某一步大于容器大小，就把第一个移出。

思路：

数组模拟双向链表+$trie$树映射 或 $unorderedmap+list$ 具体见题解代码

（数组模拟就是爽）

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N=5e5+10;
     4 
     5 int trie[N*10][10],pointer[N*10];
     6 int pos[N*10],tot;
     7 
     8 int L[N],R[N],data[N];
     9 int st,ed,size;
    10 
    11 void Insert(int x,int v) {
    12     data[x]=v;
    13     if(!st) st=ed=x;
    14     else L[R[ed]=x]=ed,ed=x;
    15     ++size;
    16 }
    17 
    18 void Erase(int x) {
    19     int pre=L[x],bak=R[x];
    20     if(pre) R[pre]=bak;
    21     if(bak) L[bak]=pre;
    22     data[x]=L[x]=R[x]=0;
    23     if(st==x) st=bak;
    24     if(ed==x) ed=pre;
    25     --size;
    26 }
    27 
    28 void trieInsert(char* s,int it) {
    29     int p=1;
    30     for(int i=0;s[i];i++) {
    31         int &t=trie[p][s[i]-'0'];
    32         if(!t) pos[t=++tot]=0;p=t;
    33     }
    34     pos[pointer[it]=p]=it;
    35 }
    36 
    37 int trieFind(char *s) {
    38     int p=1;
    39     for(int i=0;s[i]&&p;i++) {
    40         int t=trie[p][s[i]-'0'];
    41         p=t;
    42     }
    43     return pos[p];
    44 }
    45 
    46 
    47 int main() {
    48     int _;
    49     for(scanf("%d",&_);_;_--) {
    50         int q,m;
    51         scanf("%d%d",&q,&m);
    52         pointer[tot=1]=0;
    53         st=ed=size=0;
    54         int number=0;
    55         while(q--) {
    56             int opt,v;char s[12];
    57             scanf("%d%s%d",&opt,s,&v);
    58             int it=trieFind(s);
    59             if(opt==1) {
    60                 if(it==0||L[it]==0&&v==-1||R[it]==0&&v==1)
    61                     puts("Invalid");
    62                 else {
    63                     if(v==-1) it=L[it];
    64                     if(v==1) it=R[it];
    65                     printf("%d\n",data[it]);
    66                 }
    67             } else {
    68                 if(it) {
    69                     v=data[it];
    70                     Erase(it);
    71                 } else if(size==m){
    72                     pos[pointer[st]]=0;
    73                     Erase(st);
    74                 }
    75                 Insert(++number,v);
    76                 trieInsert(s,number);
    77                 printf("%d\n",v);
    78             }
    79         }
    80         for(int i=1;i<=tot;i++) {
    81             for(int k=0;k<10;k++) trie[i][k]=0;
    82             pos[i]=0;
    83         }
    84         while(st) Erase(st);
    85     }
    86     return 0;
    87 }

$unorderedmap+list$

学到了$map$里放迭代器，用$decltype(list)::iterator$，以及$prev和next$

1 //#define DEBUG
     2 #include<bits/stdc++.h>
     3 using namespace std;
     4 const int N=100010;
     5 const int inf=0X3f3f3f3f;
     6 const long long INF = 0x3f3f3f3f3f3f3f3f;
     7 const double eps = 1e-6;
     8 const double pi = acos(-1.0);
     9 const int mod = 1000000007;
    10 typedef long long ll;
    11  
    12 int main() {
    13     #ifdef DEBUG
    14     freopen("in.txt","r",stdin);
    15     #endif
    16     int _;
    17     for(scanf("%d",&_);_;_--) {
    18         list<pair<ll,ll>> list;
    19         unordered_map<ll,decltype(list)::iterator> map;
    20         int q,m;
    21         scanf("%d%d",&q,&m);
    22         while(q--) {
    23             int opt;
    24             ll v;
    25             char s[15];
    26             scanf("%d%s%lld",&opt,s,&v);
    27             ll id;
    28             sscanf(s,"%lld",&id);
    29             id+=1ll*10000000000*strlen(s)+id;
    30             if(opt==0) {
    31                 auto it=map.find(id);
    32                 if(it!=map.end()) {
    33                     auto p=map[id];
    34                     v=p->second;
    35                     //map.erase(p->first);
    36                     list.erase(p);
    37                 }
    38                 list.push_back({id,v});
    39                 map[id]=prev(list.end());
    40                 if(list.size()>m) {
    41                     auto p=list.begin();
    42                     map.erase(p->first);
    43                     list.pop_front();
    44                 }
    45                 printf("%lld\n",v);
    46             } else {
    47                 bool ok=true;
    48                 auto it=map.find(id);
    49                 if(it==map.end()) ok=false;
    50                 else {
    51                     auto p=map[id];
    52                     if(v==-1) {
    53                         if(p==list.begin()) ok=false;
    54                         else printf("%lld\n",prev(p)->second);
    55                     } else if(v==1) {
    56                         if(next(p)==list.end()) ok=false;
    57                         else printf("%lld\n",next(p)->second);
    58                     } else printf("%lld\n",p->second);
    59                 }
    60                 if(!ok) puts("Invalid");
    61             }
    62         }
    63     }
    64 }

转载于:https://www.cnblogs.com/ACMerszl/p/11253377.html