10-13-宀

#1MYC模拟赛

$tips:$暴力搜加剪枝。

T1

$Meet\, in\, Middle$，

当发现暴搜的指数在$20\backsim 40$时，尝试此方法。

在左面搜并维护差值，在右面搜并查找差值。

话说我用 unordered_map 套 set 过了……

#include <unordered_map>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
#define N 22

using namespace std;

int nn,arr[N],mid,ans;
unordered_map <int,set<int> >val;
bool is_v[2048][2048];
void ledfs(int nid,int pos,int atot,int btot){
	if(nid>mid){
		val[atot-btot].insert(pos);
		return ;
	}
	ledfs(nid+1,pos<<1  ,atot         ,btot);
	ledfs(nid+1,pos<<1|1,atot+arr[nid],btot);
	ledfs(nid+1,pos<<1|1,atot         ,btot+arr[nid]);
}
void ridfs(int nid,int pos,int atot,int btot){
	if(nid>nn){
		if(val.find(atot-btot)!=val.end())
			for(auto &i:val[atot-btot]){
				if(!is_v[i][pos]){
					is_v[i][pos]=1;
					ans++;
				}
			}
		return ;
	}
	ridfs(nid+1,pos<<1  ,atot         ,btot);
	ridfs(nid+1,pos<<1|1,atot+arr[nid],btot);
	ridfs(nid+1,pos<<1|1,atot         ,btot+arr[nid]);
}
int main(){
	val.rehash(2333333);
	scanf("%d",&nn);
	mid=nn/2;
	for(int i=1;i<=nn;i++)
		scanf("%d",arr+i);
	ledfs(1    ,0,0,0);
	ridfs(mid+1,0,0,0);
	printf("%d\n",ans-1);
}

T2

不会，咕掉了。

T3

暴力剪枝可过。

正解也不正经，随机化加剪枝。

总之剪枝就是了。

#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#define N 11111

using namespace std;

int pn,mod,bn;
int wi[N],dat[N],ans=INT_MAX;
bool is_ok(int lim){
	int nget=0,nbn=1;
	for(int i=1;i<=pn;i++){
		if(dat[i]>lim)return 0;
		if(nget+dat[i]>lim){nget=0;nbn++;}
		nget+=dat[i];
	}
//	cout<<lim<<" "<<nbn<<endl;
	return nbn<=bn;
}
int solve(){
	int l=0,r=INT_MAX-1;
	while(l<r){
//		cout<<l<<" "<<r<<endl;
		int mid=(l+r)>>1;
		if(is_ok(mid))r=mid;
		else l=mid+1;
	}
	return l;
}
int main(){
//	freopen("moiezen.in" ,"r",stdin);\
//	freopen("moiezen.out","w",stdout);
	scanf("%d%d%d",&pn,&mod,&bn);
	for(int i=1;i<=pn;i++)
		scanf("%d",wi+i);
	for(int x=0;x<mod;x++){
		for(int i=1;i<=pn;i++)
			dat[i]=(wi[i]+x)%mod;//cout<<dat[i]<<" ";
		if(!is_ok(ans))continue;
//		cout<<endl;
		ans=min(ans,solve());
	}
	printf("%d\n",ans);
}

 #2 CSDP-S模拟

我$DP$好菜啊……

T1

$Dp$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 2222
#define L 111111
#define LL long long

using namespace std;

const int Mod=1e9+7;
LL dp[N][N];
int tol,nol;
LL ans=0;
char st[L];
int main(){
	int ln=0,rn=0;
	scanf("%d%d%s",&tol,&nol,st);
	dp[0][0]=1;
	for(int i=1;i<=tol-nol;i++){
		dp[i][0]=dp[i-1][1];
		for(int j=1;j<=i;j++)
			dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%Mod;
	}
	for(int i=0;i<nol;i++){
		if(st[i]=='(') rn++;
		else           rn--;
		ln=min(ln,rn);
	}
	ln=-ln;
	for(int i=ln;i<=tol-nol;i++) {
		for(int j=ln;j+rn<=tol-nol;j++) {
			ans=(ans+(dp[i][j]*dp[tol-nol-i][j+rn]%Mod))%Mod;
		}
	}
	printf("%lld\n",ans);
}

T2

Dp

T3

性质图论题

很好奇为啥有时候就有一个圈在这里转，我也没添加啊$QAQ \Longrightarrow$