多校冲刺 noip 11.06
今天我以为我\(AK\)了，结果又挂分了......
关于我每天都想\(AK\)但是做不到这件事。。。
T1 破门而入
裸的第一类斯特林数，我\(TM\)看了一个小时才看出来
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3005;
const int mod=998244353;
int n,k,dp[N][N],ans;
signed main(){
freopen("broken.in","r",stdin);
freopen("broken.out","w",stdout);
scanf("%lld%lld",&n,&k);
dp[1][1]=1;
fo(i,2,n)fo(j,1,min(i,k))dp[i][j]=(dp[i-1][j]*(i-1)+dp[i-1][j-1])%mod;
fo(i,1,k)ans=(ans+dp[n][i])%mod;
printf("%lld",ans);
return 0;
}
T2 翻转游戏
发现反转的区间左右字母相同的可以删去，那么直接扫一遍就好了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e6+5;
int n,buc[30],ans;char s[N];
signed main(){
freopen("turn.in","r",stdin);
freopen("turn.out","w",stdout);
scanf("%s",s+1);n=strlen(s+1);ans=n*(n+1)/2;
fo(i,1,n)buc[s[i]-'a']++,ans-=buc[s[i]-'a'];
printf("%lld",ans+1);
return 0;
}
T3 奶油蛋糕塔
发现不同的蛋糕只有\(10\)个，最多会奇数个相同的可以直接合并
偶数的话就拆出一个最小的，最多\(20\)个，直接状压就行了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=5e5+5;
int n;
int td[N],tp[N];
int buc[30],num[30],las[30];
int ji[30][3];
int d[30],p[30],cnt;
int dp[1<<20][5],ans;
signed main(){
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
scanf("%d",&n);
memset(las,0x3f,sizeof(las));
fo(i,1,n){
char x[5];
scanf("%d",&td[i]);
scanf("%s",x+1);tp[i]|=(1<<(x[1]-'W'));
scanf("%s",x+1);tp[i]|=(1<<(x[1]-'W'));
buc[tp[i]]+=td[i];
num[tp[i]]++;
las[tp[i]]=min(las[tp[i]],td[i]);
}
fo(i,0,(1<<4)-1){
if(!num[i])continue;
fo(j,0,3)if((i>>j)&1)ji[i][++ji[i][0]]=j;
if(!ji[i][2])ji[i][2]=ji[i][1];
if((num[i]&1)||ji[i][1]==ji[i][2]){
d[++cnt]=buc[i];
p[cnt]=i;
}
else{
d[++cnt]=buc[i]-las[i];
p[cnt]=i;
d[++cnt]=las[i];
p[cnt]=i;
}
}
//cout<<"SB"<<endl;
memset(dp,0x8f,sizeof(dp));
dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=0;
fo(i,0,(1<<cnt)-1){
fo(j,0,3){
if(dp[i][j]<0)continue;
fo(k,1,cnt){
if((i>>k-1)&1)continue;
if(ji[p[k]][1]!=j&&ji[p[k]][2]!=j)continue;
if(ji[p[k]][1]==j)dp[i|(1<<k-1)][ji[p[k]][2]]=max(dp[i|(1<<k-1)][ji[p[k]][2]],dp[i][j]+d[k]);
else dp[i|(1<<k-1)][ji[p[k]][1]]=max(dp[i|(1<<k-1)][ji[p[k]][1]],dp[i][j]+d[k]);
}
ans=max(ans,dp[i][j]);
}
}
printf("%d",ans);
return 0;
}
T4 多重影分身之术
话说我推出\(\mathcal{O(n^2)}\)的转移方程之后
发现和前两天做的某一个\(CF\)d的题非常像，于是开始二分答案
于是我\(check\)的时候错掉了，于是与\(AK\)无缘了
于是我考场后一会就改出来了，并且发现我的\(check\)可以\(\mathcal{O(n)}\)解决，就切掉了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m,man[N],thg[N];
bool check(int x){
int it=0;
fo(i,1,n){
int now=x,las=it+1;
if(now<abs(man[i]-thg[las])&&thg[las]<=man[i])return false;
while(thg[it+1]<man[i])it++;//cout<<it<<endl;
if(thg[las]>=man[i])while(now>=thg[it+1]-man[i]&&it<m)it++;
else while((now>=2*(thg[it+1]-man[i])+(man[i]-thg[las])
||now>=(thg[it+1]-man[i])+2*(man[i]-thg[las]))&&it<m)it++;
if(it==m)return true;
}
if(it==m)return true;
else return false;
}
signed main(){
freopen("duplication.in","r",stdin);
freopen("duplication.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,1,n)scanf("%d",&man[i]);
fo(i,1,m)scanf("%d",&thg[i]);
sort(man+1,man+n+1);
sort(thg+1,thg+m+1);
// fo(i,1,n)cout<<man[i]<<" ";cout<<endl;
// fo(i,1,m)cout<<thg[i]<<" ";cout<<endl;
int l=0,r=1.1e9,mid;
while(l<r){
mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}