牛客多校一
A
假设数组a和b前m个数的rmq相等，即所有区间最小值相同
新加入一个数，多了m+1个区间，只需要考虑新增的区间
找到第m+1左边第一个比它小的数，设它的位置是p
小于等于p的位置rmq的值和第m+1个数就没关系了
大于p的位置rmq结果显然是第m+1个数
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (500000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
int a[maxn],b[maxn];
int s1[maxn],s2[maxn],p1,p2;
int main()
{
while(RD1(n)!=EOF)
{
p1=p2=0;
for(int i=1;i<=n;i++)RD1(a[i]);
for(int i=1;i<=n;i++)RD1(b[i]);
int ans=0;
for(int i=1;i<=n;i++){
while(p1&&a[s1[p1]]>a[i])p1--;
while(p2&&b[s2[p2]]>b[i])p2--;
if(p1!=p2)break;
else
{
ans=i;
s1[++p1]=i,s2[++p2]=i;
}
}
printf("%d\n",ans);
}
return 0;
} C
总体思路先从大到小排序，再贪心，具体思路参考https://blog.csdn.net/dxyinme/article/details/96455593
关键细节
ai取值是离散的，而pi是连续的，因此先将整个式子扩大m倍。
当m不能再将所有前面的数削减到当前数a[st]时，确定了前st-1个数由m弥补。
m可能会剩余rem，这时候要均摊，即前面每个数等于a[st-1]-rem/st（以整数形式通分）
最终式子
通分后
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (10000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m;
int a[maxn];
int main()
{
while(RD2(n,m)!=EOF)
{
for(int i=0;i<n;i++)RD1(a[i]);
sort(a,a+n,greater<int>());
int st;
int d=0;
for(st=1;st<n;st++)
{
int t=(a[st-1]-a[st])*st;
if(d+t>m)break;
else d+=t;
}
int rem=m-d;
//see(rem),see(st),NL;
ll num1=1LL*(a[st-1]*st-rem)*(a[st-1]*st-rem);
for(int i=st;i<n;i++)num1+=1LL*a[i]*a[i]*st;
ll num2=1LL*st*m*m;
ll g=__gcd(num1,num2);
num1/=g,num2/=g;
if(num2==1)printf("%lld\n",num1);
else printf("%lld/%lld\n",num1,num2);
}
return 0;
} E
关键思路：前a+b个字母，a个A，b个B，a-b<=n，否则a-b>n，a>n,剩下能用的a‘<m,凑BA的时候就不够了
同理，b-a<=m
然后用到卡特兰数的'折线形式'
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (5000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m;
ll fac[maxn]={1};
ll qpow(ll a,ll k)
{
ll res=1;
while(k){
if(k&1)res=res*a%mod;
k>>=1,a=a*a%mod;
}return res;
}
ll c(int n,int m)
{
if(n==m||m==0)return 1;
if(m>n)return 0;
return fac[n]*qpow(fac[m],mod-2)%mod*qpow(fac[n-m],mod-2)%mod;
}
int main()
{
for(ll i=1;i<=4000;i++)fac[i]=fac[i-1]*i%mod;
while(RD2(n,m)!=EOF)
{
cout<<((c(n*2+m*2,m+n)-c(n*2+m*2,m-1)-c(n*2+m*2,n-1))%mod+mod)%mod<<endl;
}
return 0;
} H
给定一个n个数的集合，求所有异或和为0的子集的大小之和
技巧多，思维量巨大
总体思路是，考虑单点贡献，只要check当前这个元素是否能由剩下的n-1个元素表示，并且这剩下的n-1个元素能构成为0的集合个数
程序优化的时候用到了类似矩阵秩的性质，即线性基集合的大小始终不变
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (100000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
ll a[maxn];
ll v[70];
ll v1[70];
ll v2[70];
vector<int>r;
void show(ll*v)
{
for(int i=0;i<64;i++)see(i),see(v[i]),NL;
}
bool insert(ll x,ll*vv)
{
for(int i=60;i>=0;i--)
{
if(!(x&(1LL<<i)))continue;
if(!vv[i]){vv[i]=x;return 1;}
else x^=vv[i];
}return 0;
}
ll qpow(ll a,ll k)
{
ll res=1;while(k)
{
if(k&1)res=a*res%mod;
a=a*a%mod,k>>=1;
}return res;
}
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
while(RD1(n)!=EOF)
{CLR(v),CLR(v1);r.clear();
int cnt=0;
int c2=0;
for(int i=1;i<=n;i++)RDL1(a[i]);
for(int i=1;i<=n;i++)
{
int t=insert(a[i],v);
if(!t)c2+=insert(a[i],v1);
else r.push_back(i);
cnt+=t;
}
ll ans=n-cnt;
ll delt=0;
if(n>cnt)delt=qpow(2,n-cnt-1)%mod;
if(delt==0){printf("0\n");continue;}
for(int i=0;i<r.size();i++)
{
memcpy(v2,v1,sizeof(v1));
int c3=c2;
for(int j=0;j<r.size();j++)
{
if(j==i)continue;
c3+=insert(a[r[j]],v2);
}
if(!insert(a[r[i]],v2)) ans++;
}
printf("%lld\n",ans*delt%mod);
}
return 0;
} 牛客多校四
A
这里用两次dfs比较简单
先把有人的点存x[]数组，去重排序
从x里挑一个点p1，dfs，找到在x里和它最远的点p2，
再从p2dfs，找到x里找和它最远的点，此时的距离就是x[]里的点构成子树的直径
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (100000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,k;
int head[maxn],to[maxn<<1],pre[maxn<<1],tot;
bool tg[maxn];
int x[maxn];
int dis1[maxn],dis2[maxn];
void adde(int u,int v)
{
to[++tot]=v,pre[tot]=head[u],head[u]=tot;
}
void dfs1(int u,int f)
{
for(int i=head[u];i;i=pre[i])
{
int v=to[i];if(v==f)continue;
dis1[v]=dis1[u]+1;dfs1(v,u);
}
}
void dfs2(int u,int f)
{
for(int i=head[u];i;i=pre[i])
{
int v=to[i];if(v==f)continue;
dis2[v]=dis2[u]+1;dfs2(v,u);
}
}
int main()
{
RD2(n,k);for(int i=1;i<n;i++)
{
int u,v;RD2(u,v);adde(u,v),adde(v,u);
}
for(int i=0;i<k;i++)
{
RD1(x[i]);
}
sort(x,x+k);k=unique(x,x+k)-x;
if(n==1){printf("0");return 0;}
dfs1(x[0],0);
//for(int i=0;i<k;i++)see(x[i]),see(dis1[x[i]]),NL;
int ed=0;
for(int i=1;i<k;i++)
{
if(dis1[x[i]]>dis1[x[ed]])ed=i;
}
dfs2(x[ed],0);
int ans=0;
for(int i=0;i<k;i++)
{
ans=max(ans,dis2[x[i]]);
}
printf("%d",(ans+1)/2);
return 0;
} D
疯狂分类讨论，详细思路见题解
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (3000000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n;
ll a1[100],a2[100];
int main()
{
int ttt;RD1(ttt);while(ttt--)
{
RDL1(n);int p1=0,p2=0;
if(n%3==0){cout<<"1 "<<n<<endl;continue;}
cout<<"2 ";
for(int i=0;i<=60;i++)
{
if(n&(1LL<<i))
{
ll r=(1LL<<i)%3;
if(r==1)a1[p1++]=(1LL<<i);
else a2[p2++]=(1LL<<i);
}
}
if(n%3==1)
{
if(p1&&p2)
{
ll x1=a1[0]|a2[0];
ll x2=n&(~a1[0]);
cout<<x1<<' '<<x2<<endl;
}
else if(p1)
{
ll x1=a1[0]|a1[1]|a1[2];
ll x2=n&(~a1[0]);
cout<<x1<<' '<<x2<<endl;
}
else
{
ll x1=a2[0]|a2[1]|a2[2];
ll xx=a2[0]|a2[1];
ll x2=n&(~xx);
cout<<x1<<' '<<x2<<endl;
}
}
else
{
if(p1&&p2)
{
ll x1=a1[0]|a2[0];
ll x2=n&(~a2[0]);
cout<<x1<<' '<<x2<<endl;
}
else if(p1)
{
ll x1=a1[0]|a1[1]|a1[2];
ll xx=a1[0]|a1[1];
ll x2=n&(~xx);
cout<<x1<<' '<<x2<<endl;
}
else
{
ll x1=a2[0]|a2[1]|a2[2];
ll x2=n&(~a2[0]);
cout<<x1<<' '<<x2<<endl;
}
}
}
return 0;
} 牛客多校五
G
s比t长的时候用组合数计算，数字开头为0的情况减掉
s和t一样长的时候用类似lcs的做法。
设dp[i][j]是s的前i位中与t的前j位中相同的子序列个数（不一定以s[i]结尾）
坑：预处理dp[i][0]=1
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1000000+10)
#define maxn (3000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (998244353)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m;
char s[maxn],t[maxn];
ll dp[maxn][maxn];
ll fac[maxn];
void init()
{
fac[0]=1;
for(int i=1;i<=3000;i++)fac[i]=fac[i-1]*i%mod;
for(int i=0;i<=3000;i++)dp[i][0]=1;
}
ll qpow(ll a,ll k)
{
ll res=1;while(k)
{
if(k&1)res=res*a%mod;
a=a*a%mod;
k>>=1;
}return res;
}
ll c(int n,int m)
{
if(m>n)return 0;
return fac[n]*qpow(fac[m],mod-2)%mod*qpow(fac[n-m],mod-2)%mod;
}
void show()
{//see(n),see(m),NL;
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)see(i),see(j),see(dp[i][j]),NL;
}
}
int main()
{
int ttt;
init();
RD1(ttt);while(ttt--)
{
ll ans=0;
RD2(n,m);scanf("%s%s",s+1,t+1);
for(int j=1;j<=m;j++)
for(int i=j;i<=n;i++)
{
dp[i][j]=dp[i-1][j];
if(s[i]==t[j])dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
else if(s[i]>t[j])
ans=(ans+dp[i-1][j-1]*c(n-i,m-j)%mod)%mod;
}
for(int i=m+1;i<=n;i++)
{
ans=(ans+c(n,i))%mod;
for(int j=1;j+i-1<=n;j++)if(s[j]=='0')
ans=(ans+mod-c(n-j,i-1))%mod;
}
//show();
cout<<ans<<endl;
}
return 0;
} 
京公网安备 11010502036488号