lp5006 空间复杂度

一道大力模拟题。
凡是模拟题都可以考虑面向对象。
当然面向对象在速度上有劣势,但是显然是更清晰的。


#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
struct Ans{
    int HP,STR,DEF;
};
char MAP[105][105];
int enemyHP,enemySTR,enemyDEF;
class Player{
    private:
        int HP;
        int STR;
        int DEF;
        int X;
        int Y; 
    public:
        inline void playerReset(int _X,int _Y,int _STR,int _DEF){
            X=_X,Y=_Y,STR=_STR,DEF=_DEF;
            HP=0;
        }
        inline Ans playerQuery(){
            return (Ans){HP,STR,DEF};
        }
        inline void eventQ(){
            STR+=5;
        }
        inline void eventY(){
            DEF+=5;
        }
        inline void eventR(){
            HP=(HP>10)?(HP-10):0;
        }
        inline void eventM(){
            int monsterDamage;
            monsterDamage=Max(1,((enemyHP+Max(1,STR-enemyDEF)-1)/(Max(1,STR-enemyDEF)))*(Max(1,enemySTR-DEF)));
            HP+=monsterDamage;
        }
        inline void playerGetEvent(){
            switch(MAP[X][Y]){
                case '.':{
                    return;
                    break;
                }
                case 'M':{
                    eventM();
                    break;
                }
                case 'R':{
                    eventR(); 
                    break;
                }
                case 'Q':{
                    eventQ();
                    break;
                }
                case 'Y':{
                    eventY();
                    break;
                }
            }
        }
        inline void playerMove(char moveOperator){
            int _DX,_DY;
            switch(moveOperator){
                case 'W':{
                    _DX=0;
                    _DY=-1;
                    break;
                }
                case 'E':{
                    _DX=0;
                    _DY=1;
                    break;
                }
                case 'N':{
                    _DX=-1;
                    _DY=0;
                    break;
                }
                case 'S':{
                    _DX=1;
                    _DY=0;
                    break;
                }
            }
            X+=_DX,Y+=_DY;
            playerGetEvent(); 
        }
};
int n,m,q;
Player player;
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        cin>>MAP[i]+1;
    }
    scanf("%d%d%d",&enemyHP,&enemySTR,&enemyDEF);
    int x,y,d,e;
    scanf("%d%d%d%d%d",&x,&y,&d,&e,&q);
    player.playerReset(x,y,d,e);
    char ch[5];
    Ans nw;
    for(int i=1;i<=q;++i){
        cin>>ch;
        if(ch[0]=='M'){
            cin>>ch;
            player.playerMove(ch[0]);
        }else if(ch[0]=='Q'){
            nw=player.playerQuery();
            printf("%d %d %d\n",nw.HP,nw.STR,nw.DEF);
        }
    }
}
int main(){
    init();
    return 0;
}

 

lp1850 NOIP2016 换教室

一道优\(d\acute{u}\)秀\(li\acute{u}\)的期望DP。
简述题意:
原有一个包括\(n\)个节点的路径,你可以用\(m\)次操作,每一次操作可以把第\(i\)个节点从\(c_{i}\)换到\(b_{i}\)。
对于每一次操作,有\(p_{i}\)的概率成功。求最优决策下路径长度的期望。

首先考虑到是稠密图,故考虑用邻接矩阵来处理。不过需要注意读入时应当取较小值,以及每个点到其本身的距离为\(0\)
首先用\(Floyd\)预处理出所有点之间的距离。然后我们定义\(f_{i,j,k}\)表示,当前在决定第\(i\)个节点,已经使用了\(j\)次机会,当前选择为\(k\)时的期望路径长度。
那么我们考虑转移。
对于每一个状态,我们有两种选择:使用机会或者不使用机会。故而我们尝试推理状态转移方程:
首先,如果不使用机会的话,有两种情况可以转移过来,分别是,上一次使用了机会,或者上一次没有使用机会,故:
$$f_{i,j,0}=Min(f_{i-1,j,0}+mp_{c_{i-1},c_{i}},$$
$$f_{i-1,j,1}+mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}));$$
如果在这个点使用机会且成功的话,则有:
$$f_{i,j-1,1}=Min(f_{i-1,j-1,0}+mp_{c_{i-1},d_{i}}*p_{i}+mp_{c_{i-1},c_{i}}*(1-p_{i}),$$
$$f_{i-1,j-1,1}+m(p_{d_{i-1},d_{i}}*p_{i-1}+mp_{c_{i-1},d_{i}}*(1-p_{i-1}))*p_{i}+$$
$$(mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}))*(1-p_{i});$$
然后,只需要走到终点即可,因此:
$$ Ans=Min(f_{N,i,j})\ (i\in [0,M],j\in [0,1])$$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int mp[305][305],N,M,V,E;
int c[2005],d[2005];
double p[2005],f[2005][2005][2];
void init(){
    memset(mp,0x3f,sizeof(mp));
    scanf("%d%d%d%d",&N,&M,&V,&E);
    for(int i=1;i<=N;++i){
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%d",&d[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%lf",&p[i]);
    }
    int u,v,w;
    for(int i=1;i<=E;++i){
        scanf("%d%d%d",&u,&v,&w);
        mp[u][v]=Min(mp[u][v],w),mp[v][u]=Min(mp[u][v],w);
    }
    for(int i=1;i<=V;++i){
        mp[i][i]=0;
    }
    for(int k=1;k<=V;++k){
        for(int i=1;i<=V;++i){
            for(int j=1;j<=V;++j){
                mp[i][j]=Min(mp[i][j],mp[i][k]+mp[k][j]); 
            }
        }
    }
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<=1;++k){
                f[i][j][k]=1000007;
            }
        }
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=N;++i){
        for(int j=0;j<=M;++j){
            f[i][j][0]=Min(f[i-1][j][0]+mp[c[i-1]][c[i]],f[i-1][j][1]+mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]));
            if(!j){
                continue;
            }
            f[i][j][1]=Min(f[i-1][j-1][0]+mp[c[i-1]][d[i]]*p[i]+mp[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1]+(mp[d[i-1]][d[i]]*p[i-1]+mp[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+(mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i]));
        }
    }
    double ans=1000007;
    for(int i=0;i<=M;++i){
        for(int j=0;j<2;++j){
            ans=Min(ans,f[N][i][j]);
        }
    }
    /*
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<2;++k){
                printf("%.2lf ",f[i][j][k]);
            }
            printf("|");
        }
        puts("");
    }
    */
    printf("%.2lf",ans);
}
int main(){
    init();
    return 0;
}

 

lp1983 NOIP2013 车站分级

看到\(DAG\),立刻可以考虑上一个拓扑排序。
将偏序关系转化为邻接矩阵即可。

#include<iostream>
#include<cstdio>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,s[1005][1005],in[1005],ans=0;
bool map[1005][1005],a[1005],d[1005],used[1005];
queue <int> q;

void re(){
	while(1){
		bool bo=0;
		for(int i=1;i<=n;i++){
			if(!in[i]&&!used[i]){
				q.push(i);
				used[i]=1;
				bo=1;
			}
		}
		if(!bo){
			break;
		}
		while(!q.empty()){
			int p=q.front();
			q.pop();
			for(int i=1;i<=n;i++){
				if(map[p][i]){
					map[p][i]=0;
					in[i]--;
				}
			}
		}
		ans++;
	}
}

int init(){
	memset(in,0,sizeof(in));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&s[i][0]);
		memset(a,0,sizeof(a));
		for(int j=1;j<=s[i][0];j++){
			scanf("%d",&s[i][j]);
			a[s[i][j]]=1;
		}
		for(int j=s[i][1];j<=s[i][s[i][0]];j++){
			if(!a[j]){
				for(int k=1;k<=s[i][0];k++){
					//map(i,j)表示i<j
					if(!map[j][s[i][k]]){
						map[j][s[i][k]]=1;
						in[s[i][k]]++;
					}
				}
			}
		}
	}
}

int main(){
	init();
	re();
	printf("%d",ans);
}

 

 

ABC113

第一次尝试打\(AtCoder\),考前紧张刺激地对着\(google\)学日语,不过真正到了开考了还是英语读起来比较靠谱。

\(Beginner\)的比赛还是比较水的,我涨了\(400pts\),似乎是\(Beginner\)能涨到的最高分了?不太清楚。

\(ABC113 A – Discount Fare\)
打卡题,没什么可说的。
\(ABC113 B – Palace\)
大力模拟即可。
\(ABC113 C – ID\)
排序。善用STL可以高效得分。
\(ABC113 D – Number of Amidakuji\)
一道有一定难度的DP题。
\(f_{i,j}\)表示,走到\(f_{i,j}\)并用完横杠的方案数。
然后我们可以发现,这种方案数是可以直接计算出来的——具体来说要乘上一个斐波那契数。这是因为放置东西的时候不能同行。
可以类比爬楼梯问题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 A - Discount Fare
*/ 
long long x,y;
void init(){
    scanf("%lld%lld",&x,&y);
    printf("%lld",x+(y>>1));
}
int main(){
	init();
	return 0;
}

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 B - Palace
*/ 
int n,loc[100005];
double t,a,h[100005];
inline double cmp(int a,int b){
    return h[a]<h[b];
} 
void init(){
    scanf("%d",&n);
    scanf("%lf%lf",&t,&a);
    for(int i=1;i<=n;++i){
        scanf("%lf",&h[i]);
        h[i]=t-h[i]*0.006;
        h[i]-=a;
        h[i]=(h[i]<0)?(-h[i]):h[i];
        loc[i]=i;
    }
    sort(loc+1,loc+1+n,cmp);
    printf("%d",loc[1]);
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 C - ID
*/ 
int n,m;
struct data{
    int a;
    int b;
    int id;
}tl[100005];
vector<data> nl[100005];
inline bool cmp(const data &a,const data &b){
    return a.b<b.b;
}
inline bool cmp2(const data &a,const data &b){
    return a.id<b.id;
}
void init(){
    scanf("%d%d",&n,&m);
    int x,y;
    data nw;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        nw.b=y;
        nw.id=i;
        nw.a=x;
        nl[x].push_back(nw);
    }
    for(int i=1;i<=n;++i){
        sort(nl[i].begin(),nl[i].end(),cmp);
    }
    int tp=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<nl[i].size();++j){
            nl[i][j].b=j+1;
            tl[++tp]=nl[i][j];
        }
    }
    sort(tl+1,tl+1+m,cmp2);
    for(int i=1;i<=m;++i){
        printf("%.6d%.6d\n",tl[i].a,tl[i].b);
    }
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
#define MOD 1000000007
/*
ABC113 D - Number of Amidakuji
*/
//w 棍子,k 列数。 
long long h,w,k;
long long ans=0;
long long f[105][10];
long long fib[1005];
//Y取X的情况。 
void init(){
    scanf("%lld%lld%lld",&h,&w,&k);
    memset(f,0,sizeof(f));
    fib[1]=fib[2]=1;
    for(int i=3;i<=1000;++i){
        fib[i]=(fib[i-1]+fib[i-2])%MOD;
    }
    f[0][1]=1;
    for(int i=1;i<=h;++i){
        for(int j=1;j<=w;++j){
            if(j>1){
                f[i][j]=(f[i][j]+(f[i-1][j-1]*fib[w-j+1]*fib[j-1])%MOD)%MOD;
            }
            if(j<w){
                f[i][j]=(f[i][j]+(f[i-1][j+1]*fib[w-j]*fib[j])%MOD)%MOD;
            }
            f[i][j]=(f[i][j]+(f[i-1][j]*fib[j]*fib[w-j+1])%MOD)%MOD;
        }
    }
    printf("%lld",f[h][k]);
}
int main(){
	init();
	return 0;
}

 

NOIP2018 Day -4

停课第六天。距离NOIP2018还有5天。

做模拟赛做得有点混乱。

打了一下洛谷的比赛,再做了一下NOIP2016,还算小有收获——换教室也太麻了。

lp1563 NOIP2016 玩具谜题

一道简单的大力模拟题。

#include<iostream>
#include<cstdio>
using namespace std;

char ch[100005][15];
int typ[100005];
int n,m;
void init(){
    scanf("%d%d",&n, &m);
    for(int i=1;i<=n;++i){
        scanf("%d",&typ[i]);
        cin>>ch[i];
    }
    int x,v,p=1;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&v);
        x^=typ[p];
        if(x){
            p+=v;
            p=(p-1)%n+1;
        }else{
            p-=v;
            p=(p+n-1)%n+1;
        }
    }
    puts(ch[p]);
}
int main(){
    init();
    return 0;
}

 

sp7586 NUMOFPAL

求一个字符串的回文子串个数。
凡是这类问题,优先考虑麻辣烫。
我们可以发现,依据题意,任意两个对称轴不同的回文串,都是「本质不同」的。
并且,每个回文串,和它对称轴相同的所有子串都必然是回文串。
故而我们先用麻辣烫处理,然后统计一遍即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,f[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(i<mx){
			f[i]=Min(f[(nw<<1)-i],f[nw]-(i-nw));
		}else{
			f[i]=1;
		}
		while(s[i+f[i]]==s[i-f[i]]){
			++f[i];
		}
		if(i+f[i]>mx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int ans=0;
	for(int i=1;i<=n;++i){
		ans+=f[i]/2;
	} 
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

 

lp4555 国家集训队 最长双回文串

一开始以为是和最长双倍回文串一样的题,不过仔细看一下发现还是简单很多。
总之是麻辣烫(Manacher)的模板题。

Manacher是一\(O(n)\)种处理回文子串的通用方法。
具体来说,对于任意回文串,以它的对称轴为对称轴的所有子串都是回文串;不以它的对称轴为对称轴的所有子串都是对称的。
因此,我们可以分别考虑用着两种情况,使得我们只需要双指针扫一遍即可。
我们记\(f[i]\)表示,以第\(i\)个点为对称轴,最长的回文串半径。
首先我们维护当前对称轴\(mid\)以及当前右端点\(mx\),那么对于第一种情况,只需要拓展右端点即可。
下面我们考虑第二种情况。
首先,对于当前点\(i\),总是有\(i>mid\)。
那么,如果\(i<mx\),那么显然,在对称轴的另一边的点\(j=mid-(i-mid)\),在\(mx\)的范围内,两者必然是拥有共同的子串的。
这样算法就设计完了。

因为是双指针移动,所以复杂度是对的。
然后呢,对于每一个位置\(i\),我们考虑,维护\(l_{i}\)和\(r_{i}\),分别表示,\(i\)所在的回文串中最左的左端点和最右的右端点。
那么,\(ans=Max(r_{i}-l_{i})\)
处理方法的话,维护一个双指针即可。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int n,f[200005],l[200005],r[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(imx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int nw=1;
	for(int i=1;i<=n;++i){
		while(nw<=i+f[i]-1){
			l[nw]=i;
			++nw;
		}
	}
	nw=n+1;
	for(int i=n;i>=1;--i){
		while(nw>=i-f[i]+1){
			r[nw]=i;
			--nw;
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,r[i]-l[i]);
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp3960 NOIP2018 列队

我没有脸把这篇文章称作是「我」的题解。
难度非常的大。
说实话根本不知道怎么写,也无法理解。
再一次感受到人和巨神的区别。

「人跟人之间是有差距的。」

实在是无法理解,所以只能抄小粉兔的题解了。
可能等到我的能力有提升了之后才能理解这道题的正解吧。
话说有个sm打成了rt卡了我半天。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lwbt(_A) ((_A)&(-(_A)))


int q,loc[300005];
long long n,m,X[300005],Y[300005],ans[300005],arr[900005];
int len[300005],len2[300005],h[300005],tr[900005];
inline void add(int *_H,int _L,int _X,int _A){
    while(_X<=_L){
        _H[_X]+=_A;
        _X+=lwbt(_X);
    }
}
inline bool cmp(const int &_A,const int &_B){
    return (X[_A]==X[_B])?(_A<_B):(X[_A]<X[_B]);
}
inline int srch(int *_H,int _L,int _X){
    int l=1,r,mid,sm,rt;
    while((l<=_L)&&(_H[l]<_X)){
        l<<=1,rt=l;
    }
    r=l;
    sm=_H[l>>=1];
    while(l+1<r){
        mid=(l+r)>>1;
        if(mid>_L||_H[mid]+sm>=_X){
            r=mid,rt=mid;
        }else{
            l=mid,sm+=_H[l];
        }
    }
    rt=r;
    return rt;
}
int st[300005],tp=0;
void init(){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=q;++i){
        scanf("%lld%lld",&X[i],&Y[i]);
        loc[i]=i;
    }
    sort(loc+1,loc+1+q,cmp);
    for(int i=1;i<m;++i){
        add(tr,m-1,i,1);
    }
    for(int i=1;i<=n;++i){
        len[i]=m-1;
    }
    for(int i=1;i<=q;++i){
        if(X[loc[i-1]]!=X[loc[i]]){
            while(tp){
                add(tr,m-1,st[tp--],1);
            }
        }
        if(Y[loc[i]]>len[X[loc[i]]]){
            continue;
        }
        int pos=srch(tr,m-1,Y[loc[i]]);
        ans[loc[i]]=(X[loc[i]]-1)*m+pos;
        add(tr,m-1,pos,-1);
        st[++tp]=pos;
        --len[X[loc[i]]];
    }
    int it=0;
    for(int i=1;i<=n;++i){
        while(it<=q&&X[loc[it]]<i){
            ++it;
        }
        h[i]=it-1;
    }
    h[n+1]=q;
    memset(tr,0,sizeof(tr));
    for(int i=1;i<=n;++i){
        len[i]=0,len2[i]=m-1;
    }
    len[n+1]=n;
    for(int i=1;i<=n;++i){
        add(tr+h[n+1],n+q,i,1);
        arr[q+i]=i*m;
    }
    for(int i=1;i<=q;++i){
        if(ans[i]){
            int pos=srch(tr+h[n+1],n+q,X[i]);
            add(tr+h[n+1],n+q,pos,-1);
            add(tr+h[n+1],n+q,++len[n+1],1);
            arr[h[n+1]+len[n+1]]=ans[i];
            add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);
            arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];
            --len2[X[i]];
        }else{
            int pos=srch(tr+h[n+1],n+q,X[i]);
            add(tr+h[n+1],n+q,pos,-1);
            add(tr+h[n+1],n+q,++len[n+1],1);
            if(Y[i]!=m){
                int pos2=srch(tr+h[X[i]],h[X[i]+1]-h[X[i]],Y[i]-len2[X[i]]);
                add(tr+h[X[i]],h[X[i]+1]-h[X[i]],pos2,-1);
                ans[i]=arr[h[X[i]]+pos2];
                add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);
                arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];
            }else{
                ans[i]=arr[h[n+1]+pos];
            }
            arr[h[n+1]+len[n+1]]=ans[i];
        }
    }
    for(int i=1;i<=q;++i){
        printf("%lld\n",ans[i]);
    }
} 
int main(){
    init();
    return 0;
}

 

停课第五天。

停课第五天,距离NOIP2018还有 8 天。

我好菜啊。

时间是这个世界上最残酷的变量。

今天没有做什么事,就做了一套模拟赛。其他的时间都在处理一些与本文主题无关的事。

lp3959 NOIP2017 宝藏

我们首先,如果两个点之间有连多条边,肯定只有最短的那条最优。
那么我们进行状压,对于某一个状态\(S_{0}\),我们维护它的所有拓展的集合\(T_{S_{1}}\)
然后,记\(f_{i,k}\)表示,当前状态为\(i\),当前的深度为\(k\)时的最小花费。
这样拓展,每一次拓展都相当于把深度加深了一层,因此就可以不要花费太多的精力去考虑\(k\)对贡献的影响。
而,从某一个根开始拓展,即相当于\(f_{(1<<i),0}\)
于是我们便可以开始DP。每一次拓展都会将可行集合纳入范围。这样拓展的花费也是可以被轻松计算出来的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[1<<12][12],usf[1<<12];
int mp[15][15];
void init(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        --u,--v; 
        mp[u][v]=Min(mp[u][v],w);
        mp[v][u]=Min(mp[v][u],w);
    }
    const int MAX=1<<n;
    for(int i=1;i<MAX;++i){
        for(int j=0;j<n;++j){
            if((i|(1<<j))!=i){
                continue;
            }
            for(int k=0;k<n;++k){
                if(mp[j][k]!=0x3f3f3f3f){
                    usf[i]|=(1<<k);
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i){
        mp[i][i]=0;
        f[1<<i][0]=0;
    }
    long long sm,nw,x;
    for(int i=2;i<MAX;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if(((usf[i]|j)!=usf[i])){
                continue;
            }
            sm=0,nw=i^j;
            for(int k=0;k<n;++k){
                if((nw>>k)&1){
                    x=0x3f3f3f3f;
                    for(int l=0;l<n;++l){
                        if((j>>l)&1){
                            x=Min(x,mp[l][k]);
                        }
                    }
                    sm+=x;
                }
            }
            for(int k=1;k<n;++k){
                f[i][k]=Min(f[i][k],f[j][k-1]+sm*k);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;++i){
        ans=Min(ans,f[MAX-1][i]);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}

 

lp4578 FJOI2018 所罗门王的宝藏

首先,我们可以知道,令每一行、列数字的变化为\(dx_{i},dy_{i}\),那么对于\(z_{i,j}\),一定有:
$$dx_{i}+dy_{j}=z_{i,j}$$
对这个线性方程组变形,我们可以发现,如果指定序列合法,那么:
$$ \forall x ,z_{x,j_{1}}-z_{x,j_{2}}=dy_{j_{1}}-dy_{j_{2}} $$
$$ \forall y ,z_{i_{1},y}-z_{i_{2},y}=dx_{i_{1}}-dx_{i_{2}} $$
而,当\(dx\)和\(dy\)的相对关系不矛盾时,一定可以导出一个符合题意的矩阵。
因此,我们对于每组\(x,y\),统计它们的相对关系即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k; 
int dx[1005][1005],dy[1005][1005];
bool visx[1005][1005],visy[1005][1005];
int x[1005],y[1005],z[1005];
void init(){
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    memset(visx,0,sizeof(visx));
    memset(visy,0,sizeof(visy));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    int nw;
    for(int i=1;i<k;++i){
        for(int j=i+1;j<=k;++j){
            if(x[i]==x[j]&&y[i]==y[j]&&z[i]!=z[j]){
                puts("No");
                return; 
            }
            if(x[i]==x[j]){
                nw=y[i]>y[j]?z[j]-z[i]:z[i]-z[j];
                if(visx[y[i]][y[j]]&&dx[y[i]][y[j]]!=nw){
                    puts("No");
                    return;
                }
                dx[y[i]][y[j]]=dx[y[j]][y[i]]=nw;
                visx[y[i]][y[j]]=visx[y[j]][y[i]]=1; 
            }
            if(y[i]==y[j]){
                nw=x[i]>x[j]?z[j]-z[i]:z[i]-z[j];
                if(visy[x[i]][x[j]]&&dy[x[i]][x[j]]!=nw){
                    puts("No");
                    return;
                }
                dy[x[i]][x[j]]=dy[x[j]][x[i]]=nw;
                visy[x[i]][x[j]]=visy[x[j]][x[i]]=1; 
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(dx[i][i]||dy[i][i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
} 

 

lp3953 NOIP2017 逛公园

容易知道,对于每个点,最多只能偏移50。
由此可以跑记忆化搜索:\(f_{i,j}\)表示,在第i个点,比最短路长了j时的方案数。
那么,我们倒着搜即可。
具体来说,定义\(dn_{x}\)表示\(x->u\)的最短路。
那么我们可以得到状态转移方程:
$$f_{u,k}=\sum_{v,v\in S,st: \forall x \in S,x_{u}=u}f_{v,k-dn_{v}+dn_{u}-w}$$
答案为\(f_{1,K}\)
几个细节:
e[i].nxt不应写作e[i].v
不要使用长得差不多的变量。

#include<iostream>
#include<cstdio>
#include<queue> 
#include<cstring>
using namespace std;
struct ee{
    int v;
    int w;
    int nxt;
}e[400005];
int h[100005],h2[100005],et=0,n,m,K,p,dis[100005],dn[100005],f[100005][51];
bool usd[100005][51];
inline void add(int *_H,const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,_H[u]};
    _H[u]=et;
}
struct cmp2{
    inline bool operator ()(const int &X,const int &Y)const{
        return dn[X]>dn[Y];
    }
};
void dij2(){
    priority_queue< int,vector<int>,cmp2 > q;
    memset(dn,0x3f,sizeof(dn));
    dn[n]=0;
    q.push(n);
    int nw;
    while(!q.empty()){
        nw=q.top();
        q.pop();
        for(int i=h2[nw];i;i=e[i].nxt){
            if(dn[e[i].v]>dn[nw]+e[i].w){
                dn[e[i].v]=dn[nw]+e[i].w;
                q.push(e[i].v);
            }
        }
    }
}
int dfs(int u,int k){
    if(usd[u][k]){
        return -1;
    }
    if(f[u][k]){
        return f[u][k];
    }
    usd[u][k]=1;
    if(u==n){
        f[u][k]=1;
    }
    int X,sm;
    for(int i=h[u];i;i=e[i].nxt){
        //e[i].v不能写成e[i].nxt 
        sm=dn[e[i].v]-dn[u]+e[i].w;
        if(sm>k){
            continue;
        }
        X=dfs(e[i].v,k-sm);
        if(X==-1){
            return f[u][k]=-1;
        }
        f[u][k]+=X;
        f[u][k]%=p;
    }
    usd[u][k]=0;
    return f[u][k];
}
void init(){
    memset(h,0,sizeof(h));
    memset(h2,0,sizeof(h2));
    scanf("%d%d%d%d",&n,&m,&K,&p);
    et=0;
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(h,u,v,w);
        add(h2,v,u,w);
    }
    dij2();
    memset(f,0,sizeof(f));
    memset(usd,0,sizeof(usd));
    printf("%d\n",dfs(1,K));
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

停课第四天。

停课第四天。距离NOIP2018还有9天。

只剩⑨天了,状态却还没有。

做了两套模拟赛的题,两套都有一定的难度。其中一题甚至是往年省选题。不过难度确实没有省选那么高。

lp3958 NOIP2017 奶酪

简单结论+并查集+大力模拟
注意并查集不要写挂。
另:记住long double的范围小于long long

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

#define eps 1E-9
long long n,h,r;
inline double clac(const long long &x1,const long long &y1,const long long &z1,const long long &x2,const long long &y2,const long long &z2){
    return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
long long f[1005],x[1005],y[1005],z[1005];
inline long long fa(const long long &x){
    return (f[x]==x)?(x):(f[x]=fa(f[x]));
}
inline void uni(const long long &x,const long long &y){
    (fa(x)==fa(y))?0:f[fa(x)]=fa(y);
}
bool up[1005],dn[1005];
void init(){
    scanf("%lld%lld%lld",&n,&h,&r);
    memset(up,0,sizeof(up));
    memset(dn,0,sizeof(dn));
    for(int i=1;i<=n;++i){
        f[i]=i;
    }
    long long nx,ny,nz;
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld",&nx,&ny,&nz);
        x[i]=nx;
        y[i]=ny;
        z[i]=nz;
        if(z[i]<=r){
            dn[i]=1;
        }
        if(h-z[i]<=r){
            up[i]=1;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(fa(i)==fa(j)){
                continue;
            }
            if((double)(r*2)>=clac(x[i],y[i],z[i],x[j],y[j],z[j])){
                uni(i,j);
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(!dn[i]){
            continue;
        }
        for(int j=1;j<=n;++j){
            if(!up[j]){
                continue;
            }
            if(fa(i)==fa(j)){
                puts("Yes");
                return;
            }
        }
    }
    puts("No");
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp3952 NOIP2017 时间复杂度

魔鬼的大力模拟题。
千万要注意大小写。
注意数字、字符串转化。这个细节困扰了我很久。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
bool usd[30];
//lv==-1:这层循环根本不会被执行。 
struct data{
    int lv;
    int x;
}st[105];
int tp=0,n,slv=0,nlv=0,ans=0;
char ch[105];
inline int cg(){
    int _X=0,_BS=10,i=0;
    while(ch[i]<'0'||ch[i]>'9'){
        ++i;
    }
    while(ch[i]>='0'&&ch[i]<='9'){
        _X*=_BS;
        _X+=((ch[i]-'0'));
        ++i;
    }
    return _X;
}
void init(){
    scanf("%d",&n);
    memset(usd,0,sizeof(usd));
    tp=0,nlv=0;
    int ss,tt;
    cin>>ch;
    if(ch[2]=='1'){
        slv=0;
    }else{
        slv=cg();
    }
    st[0].lv=0;
    st[0].x=-1;
    bool bo=0; 
    for(int i=1;i<=n;++i){
        cin>>ch;
        if(ch[0]=='E'){
            if(!tp){
                bo=1;
            }else{
                nlv=Max(nlv,st[tp].lv);
                usd[st[tp].x]=0;
                --tp;
            }
        }else{
            cin>>ch;
            ++tp;
            if(usd[ch[0]-'a']){
                bo=1;
            }else{
                usd[ch[0]-'a']=1;
                st[tp].x=ch[0]-'a';
            }
            memset(ch,0,sizeof(ch));
            cin>>ch;
            if(ch[0]=='n'){
                ss=100000;
            }else{
                ss=cg();
            }
            memset(ch,0,sizeof(ch));
            cin>>ch;
            if(ch[0]=='n'){
                tt=100000;
            }else{
                tt=cg();
            }
            memset(ch,0,sizeof(ch));
            if(st[tp-1].lv==-1){
                st[tp].lv=-1;
                continue;
            }
            if(ss>tt){
                st[tp].lv=-1;
            }else if(ss==tt||(tt!=100000)){
                st[tp].lv=st[tp-1].lv;
            }else if(tt==100000){
                st[tp].lv=st[tp-1].lv+1;
            }
        }
    }
    if(tp||bo){
        puts("ERR");
        return;
    }
    if(nlv==slv){
        puts("Yes");
    }else{
        puts("No");
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

CF510C

因为维护的是偏序关系,很容易可以发现是拓扑排序裸题。
一个字母写错了调了半天。
可以用堆维护字典序。


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int in[30],n,len[1005],at=0,ss[30];
bool mp[30][30];
char ch[105][105];
char ans[30];
inline void CMP(const int &A,const int &B){
    int le=Min(len[A],len[B]);
    for(int i=1;i<=le;++i){
        if(ch[A][i]!=ch[B][i]){
            if(!mp[ch[A][i]-'a'][ch[B][i]-'a']){
                mp[ch[A][i]-'a'][ch[B][i]-'a']=1;
                ++in[ch[B][i]-'a'];
            }
            return;
        }
    }
    if(len[A]>len[B]){
        puts("Impossible");
        exit(0);
    }
}
priority_queue< int,vector<int>,greater<int> > q;
inline void srt(){
    for(int i=0;i<26;++i){
        if(!in[i]){
            q.push(i);
        }
    }
    int p;
    while(!q.empty()){
        p=q.top();
        q.pop();
        ans[++at]=p+'a';
        for(int i=0;i<26;++i){
            if(mp[p][i]){
                --in[i];
                if(!in[i]){
                    q.push(i);
                }
            }
        }
    }
    if(at<26){
        puts("Impossible");
        exit(0);
    }
    ans[++at]='\0';
}
void init(){
    scanf("%d",&n);
    memset(mp,0,sizeof(mp));
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;++i){
        cin>>ch[i]+1;
        len[i]=strlen(ch[i]+1);
    }
    for(int i=1;i<n;++i){
        CMP(i,i+1);
    }
    srt(); 
    cout<<ans+1;
}
int main(){
    init();
    return 0;
}

 

lp4568 JLOI2011 飞行路线

首先看到点数,就考虑拆点。
把每一个点拆成k个点,分别表示已经吃了k次免费午餐的距离。
然后大力跑堆优化dij即可。可以用pair加伪函数套STL。
特别要注意是小根堆。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B)) 

struct ee{
    int v;int w;int nxt;
}e[100005];
int h[10005],et=0,f[10005][12],n,m,k,s,t;
inline void add(const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}
typedef pair<int,int> pii;
struct cmp{
	bool operator ()(const pii &A,const pii &B){
		return f[A.first][A.second]>f[B.first][B.second];
	}
};
priority_queue<pii,vector<pii>,cmp> q;
void bfs(int s){
    pii p(s,0);
    q.push(p);
    while(!q.empty()){
        p=q.top();
        q.pop();
        for(int i=h[p.first];i;i=e[i].nxt){
            if(f[e[i].v][p.second]>f[p.first][p.second]+e[i].w){
                f[e[i].v][p.second]=f[p.first][p.second]+e[i].w;
                q.push((pii){e[i].v,p.second});
            }
            if(p.second+1<=k){
                if(f[e[i].v][p.second+1]>f[p.first][p.second]){
                    f[e[i].v][p.second+1]=f[p.first][p.second];
                    q.push((pii){e[i].v,p.second+1});
                }
            }
        }
    }
}
void init(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&t);
    memset(f,0x3f,sizeof(f));
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(u==v){
            continue;
        }
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<=k;++i){
        f[s][i]=0;
    }
    bfs(s);
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;++i){
        ans=Min(ans,f[t][i]);
    }
    printf("%d",ans);
    
}
int main(){
    init();
    return 0;
}