A题
传送门
题意简述：给一个数列，问有多少个峰值点（同时比两边都大/小的点）
思路：按照题意模拟。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=1005;
int n,a[N];
int main(){
n=read();
int cnt=0;
for(ri i=1;i<=n;++i){
a[i]=read();
}
for(ri i=2;i<n;++i){
if(a[i]>a[i-1]&&a[i]>a[i+1])++cnt;
if(a[i]<a[i-1]&&a[i]<a[i+1])++cnt;
}
cout<<cnt;
return 0;
}
B题
传送门
题意简述：有一个机器人按照UDLRUDLRUDLR四种指令上下左右移动，有一些指令可能是错的，机器人如果只按照正确的指令走最后会回到原点，问最多有多少个指令是正确的。
思路：显然对于正确的指令L,RL,RL,R个数相等，U,DU,DU,D个数相等。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
return getchar();
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=105;
int n;
char s[N];
int main(){
n=read();
int cnt1=0,cnt2=0,cnt3=0,cnt4=0;
scanf("%s",s+1);
for(ri i=1;i<=n;++i){
if(s[i]=='L')++cnt1;
if(s[i]=='R')++cnt2;
if(s[i]=='U')++cnt3;
if(s[i]=='D')++cnt4;
}
cout<<min(cnt1,cnt2)*2+min(cnt3,cnt4)*2;
return 0;
}
C题
传送门
题意简述：
给一个字符串SSS,一个字符ccc为kkk好的当SSS的所有长度为kkk的子串都包含这个字符，问最小的kkk满足存在至少有一个字符是kkk好的。
思路：显然可以二分答案，然后随便checkcheckcheck一下。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
return getchar();
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=100005;
int n,k;
char s[N];
inline bool check(const int&k){
for(ri i=0;i<26;++i){
bool f=1;
int last=0;
for(ri last=0,j=1;j<=n;++j){
if(j-last==k)if(s[j]-'a'!=i){f=0;break;}
if(s[j]-'a'==i)last=j;
}
if(f)return 1;
}
return 0;
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
int l=1,r=n,ans=n;
while(l<=r){
int mid=l+r>>1;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
return 0;
}
D题
传送门
题意简述：给出n,kn,kn,k，问有多少nnn个数排列至少有n−kn-kn−k个位置满足ai=ia_i=iai=i。
思路：考虑dpdpdp,fi,jf_{i,j}fi,j表示至少有jjj个位置满足ak≠ka_k=\not kak≠k的iii个数排列的数量。
然后从fi,j−2/j−1/jf_{i,j-2/j-1/j}fi,j−2/j−1/j转移过来即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int N=1005;
int n,k;
ll f[N][N];
int main(){
n=read(),k=read();
f[0][0]=1;
for(ri i=1;i<=n;++i){
f[i][0]=1;
for(ri j=1;j<=k;++j){
f[i][j]=f[i-1][j]+f[i-1][j-1]*(j-1);
if(j>=2)f[i][j]+=f[i-1][j-2]*(i-j+1);
}
}
ll ans=0;
for(ri i=0;i<=k;++i)ans+=f[n][i];
cout<<ans;
return 0;
}
E题
传送门
题意简述：给出nnn个数aia_iai和一个模数m,n≤35,ai,m≤1e9m,n\le35,a_i,m\le1e9m,n≤35,ai,m≤1e9，每个数可以选或者不选，问选出来的数模mmm得到的最大值是多少。
思路：考虑双向搜索之后去重并排序，然后用双指针或者lowerboundlower_boundlowerbound查询答案。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
tr1::unordered_map<int,bool>vis1,vis2;
typedef long long ll;
const int N=40;
int n,mod,val[N];
vector<int>A,B;
inline void solve1(){
int pos=1;
vis1[0]=1,A.push_back(0);
while(pos<=n){
for(ri i=0,up=A.size()-1;i<=up;++i)if(!vis1[(val[pos]+A[i])%mod])vis1[(val[pos]+A[i])%mod]=1,A.push_back((val[pos]+A[i])%mod);
if(!vis1[val[pos]])vis1[val[pos]]=1,A.push_back(val[pos]);
pos+=2;
}
sort(A.begin(),A.end());
}
inline void solve2(){
int pos=2;
vis2[0]=1,B.push_back(0);
while(pos<=n){
for(ri i=0,up=B.size()-1;i<=up;++i)if(!vis2[(val[pos]+B[i])%mod])vis2[(val[pos]+B[i])%mod]=1,B.push_back((val[pos]+B[i])%mod);
if(!vis2[val[pos]])vis2[val[pos]]=1,B.push_back(val[pos]);
pos+=2;
}
sort(B.begin(),B.end());
}
int main(){
n=read(),mod=read();
for(ri i=1;i<=n;++i)val[i]=read()%mod;
solve1(),solve2();
int ans=0,N=A.size()-1,M=B.size()-1;
for(ri i=0;i<=N;++i){
ans=max(ans,(A[i]+B[M])%mod);
if(A[i]+B[M]>mod-1){
int pos=lower_bound(B.begin(),B.end(),mod-A[i]-1)-B.begin();
while(~pos&&B[pos]>mod-A[i]-1)--pos;
if(pos==-1)continue;
ans=max(ans,(A[i]+B[pos])%mod);
}
}
cout<<ans;
return 0;
}
F题
传送门
题意简述：平面上有n,n≤500n,n\le500n,n≤500个点按凸多边形排列，现在让你把它们连成一棵树，有一些边不能用，边与边不能相交，问方案数。
思路：
考虑dpdpdp，fl,rf_{l,r}fl,r表示这一段按照题意连成一棵树的方案数。
然后对于fl,rf_{l,r}fl,r可以通过枚举一个iii，使得l,l+r,...,il,l+r,...,il,l+r,...,i这些点只有iii跟rrr连边来转移，这个时候发现i+1,i+2,..,r−1i+1,i+2,..,r-1i+1,i+2,..,r−1的连法有点窒息，于是我们再开一个数组gl,rg_{l,r}gl,r专门处理这个转移即可。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int N=505,mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=add(a,b);}
int n,f[N][N],g[N][N],ans=0,Trans[N][N];
inline int trans(int x,int y){return Trans[x>n?x-n:x][y>n?y-n:y];}
inline int dfs(int l,int r);
inline int calc(int l,int r){
if(~g[l][r])return g[l][r];
if(l==r)return g[l][r]=trans(l-1,l)+trans(r,r+1);
g[l][r]=0;
update(g[l][r],dfs(l-1,r));
update(g[l][r],dfs(l,r+1));
for(ri i=l;i<r;++i)update(g[l][r],mul(dfs(l-1,i),dfs(i+1,r+1)));
return g[l][r];
}
inline int dfs(int l,int r){
if(~f[l][r])return f[l][r];
if(l==r)return f[l][r]=1;
if(l==r-1)return f[l][r]=trans(l,r);
f[l][r]=dfs(l,r-1)*trans(r-1,r);
for(ri tmp1,tmp2,tmp3,i=l;i<r-1;++i)if(trans(i,r))update(f[l][r],mul(dfs(l,i),calc(i+1,r-1)));
return f[l][r];
}
int main(){
n=read();
memset(f,-1,sizeof(f)),memset(g,-1,sizeof(g));
for(ri i=1;i<=n;++i)for(ri j=1;j<=n;++j)Trans[i][j]=read();
cout<<dfs(1,n);
return 0;
}
G题
传送门
题意简述：给你nnn个点的无向完全图，每个点有点权，边权为连接的两个点的点权异或值。
问这张图的最小生成树。
思路：考虑到按位贪心的正确性是显然的，于是我们用相当于在01trie01trie01trie上面走的方式进行分治，每次统计将两棵子树合并的贡献时把左子树插入一棵01trie01trie01trie，然后右子树去查询取最值即可。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int N=2e5+5;
int n,a[N],atmp[2][N];
namespace trie{
int son[N*30][2],rt,tot;
inline void build(int p){son[p][0]=son[p][1]=0;}
inline void init(){build(rt=tot=1);}
inline void insert(int x){
for(ri t,p=rt,i=30;~i;--i){
if(!son[p][t=(x>>i)&1])build(son[p][t]=++tot);
p=son[p][t];
}
}
inline int query(int x){
int ret=0;
for(ri p=rt,t,i=30;~i;--i){
if(son[p][t=(x>>i)&1])p=son[p][t];
else ret|=1<<i,p=son[p][t^1];
}
return ret;
}
}
inline ll solve(int l,int r,int dep){
if(dep==-1||l>r)return 0;
int tp[2];
tp[0]=tp[1]=0;
int ret=0;
for(ri t,i=l;i<=r;++i)++tp[t=(a[i]>>dep)&1],atmp[t][tp[t]]=a[i];
if(tp[0]&&tp[1]){
ret=1<<(dep+1);
trie::init();
for(ri i=1;i<=tp[0];++i)trie::insert(atmp[0][i]);
for(ri i=1;i<=tp[1];++i)ret=min(ret,trie::query(atmp[1][i]));
}
for(ri i=l;i<=l+tp[0]-1;++i)a[i]=atmp[0][i-l+1];
for(ri i=l+tp[0];i<=r;++i)a[i]=atmp[1][i-l-tp[0]+1];
return solve(l,l+tp[0]-1,dep-1)+ret+solve(l+tp[0],r,dep-1);
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
cout<<solve(1,n,30);
return 0;
}