A.2026
%4讨论即可,每4位有2个2,202620262026%4为剩下的单独计算
B：子序列
钦定当前遍历到j
cnt1[i]记录j以前,%6==i的当前下标个数
cnt2[i]记录j以前,%6==i的当前下标两两组合个数
所以cnt2[(6-a[j])%6]即为以当前下标的合法子序列个数
注意是先更新ans再更新cnt2[i]和cnt1[i]
时间复杂度:O(n)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=5e6+10;
int cnt1[10];
int cnt2[10];
int a[N];
void solve(){
int n=0;
for(int i=1;i<=2026;i++){
a[++n]=2;
a[++n]=0;
a[++n]=2;
a[++n]=6;
}
int ans=0;
for(int i=1;i<=n;i++){
int to=(6-a[i])%6;
ans=(ans+cnt2[to])%mod;
for(int j=0;j<6;j++){
cnt2[(a[i]+j)%6]+=cnt1[j];
}
cnt1[a[i]%6]++;
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
C:天气之子
按照题意模拟即可
时间复杂度:O(n)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int a[N];
int sta[N];
int cnt[N];
void solve(){
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sta[a[1]]=1;
cnt[a[1]]=1;
int fir=a[1];
int flag=1;//直接作为上次成功预报的
if(a[1]==1){
ans++;
}else{
flag=0;
}
for(int i=2;i<=n;i++){
if(flag){
if(flag==a[i]){
ans++;
}else{
flag=0;
}
}else{
if(fir==a[i]){
flag=fir;
ans++;
}
}
//cout<<"ans: "<<ans<<'\n';
cnt[a[i]]++;
if(!sta[a[i]])sta[a[i]]=i;
if(cnt[a[i]]>cnt[fir]||cnt[a[i]]==cnt[fir]&&sta[a[i]]>sta[fir]){
fir=a[i];
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
D：自动驾驶
用map判重即可
时间复杂度O(knlog(n)), 转换成4进制的话可以O(kn)
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int>mp;
int cal(string s){
int sum=0;
for(int i=0;i<s.size();i++){
sum=sum*26+(s[i]-'A');
}
return sum;
}
void solve(){
int n,k;
cin>>n>>k;
string s;
cin>>s;
s='!'+s;
int ans=0;
for(int i=1;i<=n-k+1;i++){
string t="";
for(int j=i;j<=i+k-1;j++){
t+=s[j];
}
int num=cal(t);
mp[num]++;
if(mp[num]==2)ans++;
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
E:体育课
杨辉三角,我们来简单证明一下.
从(1,1)开始,想要走到底部必须向右走n-1次,所以(1,1)对于底部的贡献为C(n-1,0)次.以此类推,(1,i)对于底部的贡献为C(n-1,i)次,所以dfs过程中可以直接把底部sum算出来
时间复杂度O(n!)
#include<bits/stdc++.h>
using namespace std;
//#define int long long
int C[15][15];
void init(){
C[0][0]=1;
C[1][0]=1;C[1][1]=1;
for(int i=2;i<=12;i++){
C[i][0]=1;
for(int j=1;j<=i-1;j++){
C[i][j]=C[i-1][j]+C[i-1][j-1];
//cout<<C[i][j]<<'\n';
}
C[i][i]=1;
}
}
int vis[19];
int p[19];
int n,sum;
int flag=0;
void dfs(int pos,int ans){
if(flag)return;
if(ans>sum)return;
if(pos==n+1&&!flag){
if(ans==sum){
for(int i=1;i<=n;i++){
cout<<p[i]<<" ";
}
cout<<'\n';
flag=1;
}
return;
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
vis[i]=1;
p[pos]=i;
dfs(pos+1,ans+C[n-1][pos-1]*i);
vis[i]=0;
}
}
void solve(){
cin>>n>>sum;
if(n==1){
cout<<1;
return;
}
init();
// for(int i=0;i<=4;i++){
// cout<<C[4][i]<<" ";
// }
// cout<<'\n';
dfs(1,0);
//cout<<sum;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
F：手套
配对尽可能多的手套,就是配对min(n,m)对
发现答案单调,允许的最大丑陋程度越大,能配对的数量越多
我们先把两个数组排序,遍历元素数量大小小的数组设为a[i],大的设为b[i],对于每一个a[i],我们尽量让配对他的b[j]在允许的情况下尽量小,因为a[i+1]选的b比a[i]小的话,两者交换必定满足,而反之不一定满足.所以双指针就行
时间复杂度O(nlog(n))
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N],b[N];
int n,m;
int check(int mid){
int l=1;
for(int i=1;i<=n;i++){
while(l<=m&&abs(a[i]-b[l])>mid){
l++;
}
if(l>m)return 0;
l++;
}
return 1;
}
void solve(){
cin>>n>>m;
//默认n<=m
//a服务n
//b服务m
if(n<=m){
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=m;i++){
cin>>b[i];
}
sort(b+1,b+m+1);
}else{
for(int i=1;i<=n;i++){
cin>>b[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=m;i++){
cin>>a[i];
}
sort(a+1,a+m+1);
swap(n,m);
}
int l=0,r=1e9,ans=1e9;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
G：字符串
观察数据范围,猜测大概是O(n^3)的做法.
做这道题你要有一个冒泡排序的前置知识:交换次数为数组中的逆序对个数
定义dp[i][j][k][num]为当前选了i个0,j个1,k个2,当前位(第i+j+k位)选择num
为了转移方程,我们必须枚举上一个状态dp[ii][jj][kk][t],ii,jj,kk都可以直接算出,t的话需要枚举,注意要把不合法的情况,比如t对应的ii/jj/kk==0,或者t==num,都是不合法的
现在我们要计算包括当前位(第i+j+k位)的逆序对个数,我们可以预处理出第pos个0/1/2的位置,然后就可以知道当前(第i+j+k位)在原字符串中对应的下标lock,我们可以通过前缀和算出lock前面有几个0,几个1,几个2,设now为不等于当前位的数值,如果lock前的now个数cnt1 小于当前选了的now的个数cnt2,那么就肯定会产生cnt2-cnt1个逆序对
时间复杂度O(len[0]*len[1]*len[2]*小常数(大约20))
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
//#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=4e2+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
int num[N];
int len[3];
int st[N][3];
int pre[N][3];
int f(int i,int j,int k,int op){
int cnt=0;
int pos=i+j+k-1;
vector<int>tmp(3,0);
int lock;
if(op==0)lock=st[i][op];
if(op==1)lock=st[j][op];
if(op==2)lock=st[k][op];
tmp[0]=i;
tmp[1]=j;
tmp[2]=k;
for(int num=0;num<3;num++){
if(num!=op){
if(pre[lock][num]<tmp[num]){
cnt+=(tmp[num]-pre[lock][num]);
}
}
}
return cnt;
}
void solve(){
string s;
cin>>s;
int n=s.size();
s='!'+s;
for(int i=1;i<=n;i++){
int num=s[i]-'0';
++len[num];
st[len[num]][num]=i;
pre[i][num]++;
for(int j=0;j<3;j++){
pre[i][j]+=pre[i-1][j];
}
}
int dp[len[0]+1][len[1]+1][len[2]+1][3];//就当前而言最后一步的选择
//cout<<len[0]<<" "<<len[1]<<" "<<len[2]<<'\n';
//40的话就非常不合理,为什么这么说呢?
memset(dp,0x3f,sizeof(dp));
//状态转移方程由之前的来,第一步是不需要关注的
if(len[0])dp[1][0][0][0]=0;
if(len[1])dp[0][1][0][1]=0;
if(len[2])dp[0][0][1][2]=0;
//133*133*133*常数
for(int i=0;i<=len[0];i++){
for(int j=0;j<=len[1];j++){
for(int k=0;k<=len[2];k++){
if(i+j+k>=2){
for(int num=0;num<3;num++){
int ii=i;
int jj=j;
int kk=k;
if(num==0)ii--;
if(num==1)jj--;
if(num==2)kk--;
//之前的选择
if(ii>=0&&jj>=0&&kk>=0){
for(int t=0;t<3;t++){
int flag=0;
if(t==0&&ii>=1)flag=1;
if(t==1&&jj>=1)flag=1;
if(t==2&&kk>=1)flag=1;
if(flag&&t!=num){
//相隔必须合法才能接受
//我们可以快速查询出前面本来应该有多少个,本来应该有多少个,现在实际有多少个
int cost=f(i,j,k,num);
dp[i][j][k][num]=min(dp[i][j][k][num],dp[ii][jj][kk][t]+cost);
}
}
}
}
}
}
}
}
int g=500*500;
if(min({dp[len[0]][len[1]][len[2]][0],dp[len[0]][len[1]][len[2]][1],dp[len[0]][len[1]][len[2]][2]})>g){
cout<<-1;
}else{
cout<<min({dp[len[0]][len[1]][len[2]][0],dp[len[0]][len[1]][len[2]][1],dp[len[0]][len[1]][len[2]][2]});
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
H：数列操作
单点修改,可以想到线段树
对于的线段树一个节点对应的区间[l,r]
有三种可能的合法区间最小值
[l,mid]的答案,[mid+1,r]的答案,以及要跨过mid,mid+1的中间区间的答案
我们可以计算出每个区间最左侧的i的下标设为L[i],最右侧的i的下标设为R[i]
我们需要的则是左子树的R数组和右子树的L数组,这样可以使区间最短,并把两个数组分别按照下标降序和升序排序
我们可以先把左子树的R数组全部取完,然后再双指针右子树的L数组,通过双指针可以确定出右子树的L数组取下标前i小的几个数,左子树需要取的数的最小值j.
如果合法(即type==k,type是当前取的区间有几种不同的数),则用pos[j]-pos[i]+1来更新答案ans
时间复杂度O(m*log(n)30log(30))
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=5e4+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
int n,k,m;
struct node{
int ans;
int R[40],L[40];
}tr[N<<2];
int a[N];
int ls(int p){
return p*2;
}
int rs(int p){
return p*2+1;
}
//唯一难点在于pushup
struct group{
int pos,num;
}ll[40],rr[40];
int cnt[40];
bool cmpl(group n1,group n2){
return n1.pos>n2.pos;
}
bool cmpr(group n1,group n2){
return n1.pos<n2.pos;
}
void pushup(int p){
tr[p].ans=min(tr[ls(p)].ans,tr[rs(p)].ans);
int totl=0,totr=0;
for(int i=1;i<=k;i++){
cnt[i]=0;
tr[p].L[i]=min(tr[ls(p)].L[i]==0?inf:tr[ls(p)].L[i],tr[rs(p)].L[i]==0?inf:tr[rs(p)].L[i]);
tr[p].R[i]=max(tr[ls(p)].R[i],tr[rs(p)].R[i]);
if(tr[p].L[i]==inf){
tr[p].L[i]=0;
}
if(tr[ls(p)].R[i])ll[++totl]={tr[ls(p)].R[i],i};
if(tr[rs(p)].L[i])rr[++totr]={tr[rs(p)].L[i],i};
}
sort(ll+1,ll+totl+1,cmpl);
sort(rr+1,rr+totr+1,cmpr);
int type=0;
for(int i=1;i<=totl;i++){
cnt[ll[i].num]++;
type++;
}
int ans=inf;
for(int i=1;i<=totr;i++){
cnt[rr[i].num]++;
if(cnt[rr[i].num]==1){
type++;
}
while(totl>=1&&cnt[ll[totl].num]==2){
cnt[ll[totl].num]--;
totl--;
}
if(type==k&&totl>=1){
ans=min(ans,rr[i].pos-ll[totl].pos+1);
}
}
tr[p].ans=min(tr[p].ans,ans);
}
void build(int p,int s,int t){
memset(tr[p].L,0,sizeof(tr[p].L));
memset(tr[p].R,0,sizeof(tr[p].R));
tr[p].ans=inf;
if(s==t){
tr[p].L[a[s]]=s;
tr[p].R[a[s]]=s;
if(k==1)tr[p].ans=1;
return;
}
int mid=(s+t)>>1;
build(ls(p),s,mid);
build(rs(p),mid+1,t);
pushup(p);
}
void update(int p,int s,int t,int l,int r,int x){
if(l<=s&&t<=r){
memset(tr[p].L,0,sizeof(tr[p].L));
memset(tr[p].R,0,sizeof(tr[p].R));
tr[p].R[x]=s;
tr[p].L[x]=s;
return;
}
int mid=(s+t)>>1;
if(l<=mid){
update(ls(p),s,mid,l,r,x);
}
if(mid+1<=r){
update(rs(p),mid+1,t,l,r,x);
}
pushup(p);
}
void solve(){
cin>>n>>k>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
int op;
cin>>op;
if(op==1){
int p,v;
cin>>p>>v;
update(1,1,n,p,p,v);
}else{
if(tr[1].ans!=inf){
cout<<tr[1].ans<<'\n';
}else{
cout<<-1<<'\n';
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
京公网安备 11010502036488号