lp2822 NOIP2016 组合数问题

基础数论题。
首先我们知道,任何数的逆元模k,都不可能等于零。
故而我们不必考虑k是否是质数。
然后我们考虑先预处理出哪些\(n,m\)满足\(C_{n}^{m}≡0(mod\ k)\)
接着前缀和即可。
由于\(n,m\)较小,可以考虑用递推。

#include<iostream>
#include<cstdio> 
#include<cstring>
using namespace std;
int sm[2005][2005],C[2005][2005];
int n,m,k;
void prpr(){
    memset(sm,0,sizeof(sm));
    C[0][0]=C[1][1]=1;
    for(int i=1;i<=2000;++i){
        C[i][0]=1,C[i][i]=1;
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
        }
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];
            if(C[i][j]==0){
                ++sm[i][j];
            }
        }
        sm[i][i+1]=sm[i][i];
    }
}
void init(){
    scanf("%d%d",&n,&m);
    printf("%d\n",(m>n)?(sm[n][n]):(sm[n][m]));
}
int main(){
    int T;
    scanf("%d%d",&T,&k);
    prpr();
    while(T--){
        init();
    }
    return 0;
}

 

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,还算小有收获——换教室也太麻了。