慢慢写，尽量全部写完

习题传送门

目录

1001 方块与收纳盒

简单斐波那契模型

#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[100];
signed main(){
    int t;scanf("%lld",&t);
    f[0] = f[1] = 1;
    for (int i=2;i<=80;i++) f[i] = f[i-1] + f[i-2];
    while (t--){
        int n;scanf("%lld",&n);
        printf("%lld\n",f[n]);
    }
}

1002 舔狗舔到最后一无所有

转移方程很简单，个人觉得有点难想。

定义f[i][j]为第i天去第j家店的方案数。对于第i天而已，如果选择去了第0家店，那么对于前i-1天和前i-2天，就只能去第1家店或第2家店，即能够到f[i][0]的路径数为到达f[i-1][1]、f[i-1][2]、f[i-2][1]、f[i-2][2]的路径数总和，于是可以写出转移方程：

f[i][0] = (f[i-1][1] + f[i-1][2] + f[i-2][1] + f[i-2][2]) % mod;

f[i][1] = (f[i-1][0] + f[i-1][2] + f[i-2][0] + f[i-2][2]) % mod;

f[i][2] = (f[i-1][1] + f[i-1][0] + f[i-2][1] + f[i-2][0]) % mod;

同时发现，对于每一天的总方案数：

f[i][0]+f[i][1]+f[i][2] = (f[i-1][0]+f[i-1][1]+f[i-1][2])*2%mod + (f[i-2][0]+f[i-2][1]+f[i-2][2])*2%mod;

故我们可以直接优化成一维数组。

//未优化代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int f[N][3];
signed main(){
	int t;scanf(" %lld",&t);
    f[1][0] = 1,f[1][1] = 1,f[1][2] = 1;
    f[2][0] = 3,f[2][1] = 3,f[2][2] = 3;
	for (int i=3;i<=1e5;i++){
        f[i][0] = (f[i-1][1] + f[i-1][2] + f[i-2][1] + f[i-2][2]) % mod;
        f[i][1] = (f[i-1][0] + f[i-1][2] + f[i-2][0] + f[i-2][2]) % mod;
        f[i][2] = (f[i-1][1] + f[i-1][0] + f[i-2][1] + f[i-2][0]) % mod;
    }
    while (t--){
        int n;scanf(" %lld",&n);
        printf("%lld\n",(f[n][0]+f[n][1]+f[n][2])%mod);
    }
}


//优化代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int dp[N];
signed main(){
	int t;scanf(" %lld",&t);
	dp[1] = 3,dp[2] = 9;
	for (int i=3;i<=1e5;i++){
		dp[i] = (dp[i-1]*2%mod + dp[i-2]*2%mod) % mod;
	}
	while (t--){
		int n;scanf(" %lld",&n);
		printf("%lld\n",dp[n]);
	}
}

1003 可爱の星空

很有趣的题目。

可以设i个点的贡献为f[i],如果i是偶数，那么i连通块可以分成两个大小相等的偶数连通块，有f[i] = f[i/2] * 2;如果i是奇数，那么i连通块可分为一奇一偶大小相差为1的连通块，有f[i] = f[i/2] + f[i/2+1] + 1。 因为i特别大，所以我采用了记忆化搜索。

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,int>mp;
int deal(int x){
	if (x==0||x==1) return 0ll;
	if (mp[x]) return mp[x];
	if (x%2ll) mp[x] = deal(x/2ll) + deal(x/2ll+1ll) + 1ll;
	else mp[x] = 2ll * deal(x/2ll);
	return mp[x];
}
signed main(){
	int t;
	while (scanf("%lld",&t)!=EOF){
		while (t--){
			int n;scanf("%lld",&n);
			printf("%lld\n",deal(n));
		}	
	}
}

1004 数字三角形

规律题。

#include <bits/stdc++.h>
using namespace std;
signed main(){
	int n;scanf(" %d",&n);
	int cnt = 1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=i;j++){
			printf("%4d",cnt);
			cnt++;
		}
		printf("\n");
	}
}

1005 花店橱窗

写了很久的题目。

所有的花束在放入花瓶时必须保持其标识数的顺序是本题解题点。

定义dp[i][j]为选了第i行j列的花能获得的最大值。暴力枚举上一行的最大值，全部枚举找到最大值累加即为答案。

具体看代码。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e9 + 7;
int n,m;
int a[110][110],dp[110][110];
int vis[110][110];
void print(int x,int y){//输出路径
    if (y==1){
        return;
    }
    print(vis[y][x],y-1);
    printf("%d ",vis[y][x]);
}
signed main(){
    scanf(" %d%d",&n,&m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            scanf(" %d",&a[i][j]);
            dp[i][j] = a[i][j];
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=i;j<=m;j++){//为什么从第i列开始？因为第i-1列已经确定
            int t = 0;
            int maxn = -MAXN;
            for (int k=j-1;k>=i-1;k--){//寻找i-1行的最大值 同样注意遍历范围
                if (maxn<=dp[i-1][k]){
                    t = k;
                    maxn = dp[i-1][k];
                }
            }
            if (maxn!=-MAXN) dp[i][j] += maxn,vis[i][j] = t;//记录路径
        }
    }
    int pos = 0,ans = -MAXN;
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    for (int i=n;i<=m;i++){
        if (ans<dp[n][i]){
            ans = dp[n][i];
            pos = i;
        }
    }
    printf("%d\n",ans);
    print(pos,n);
    printf("%d\n",pos);
}

1006 免费馅饼

很好的题目，可惜题面有锅。

用a[i][j]记录j位置i秒到达最底下的馅饼的分数，f[i][j]定义为j坐标前i秒带来的最大贡献。

发现f[i][j]只有可能从f[i-1][j]、f[i-1][j-1]、f[i-1][j-2]、f[i-1][j+1]、f[i-1][j+2]转移过来。

输出要按从左到右，题目没有说明，导致我WA了n发。。

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
int f[1100][110],a[1100][110];
int p[1100][110];
int dy[] = {-2,-1,0,1,2};//从左到右 注意这个顺序不能变！
int w,h,n,ans;
int t,x,v,wi,st;
void print(int xi,int yi){//路径输出
    if (xi==0) return;
    print(xi-1,yi+p[xi][yi]);
    if (xi==1) p[xi][yi] = st - yi;
    printf("%lld\n",-p[xi][yi]);
}

signed main(){
	scanf(" %lld%lld",&w,&h);
	while (scanf(" %lld%lld%lld%lld",&t,&x,&v,&wi)!=EOF){
        if((h-1)%v)continue;
		int ti = t + (h-1)/v;
		a[ti][x] += wi;
		n = max(ti,n);
	}
	int ans_x,ans_y;
	st = w / 2 + 1;//初始位置正中间
	memset(f,-INF,sizeof(f));
    f[0][w/2+1]=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=w;j++){
            for (int k=0;k<5;k++){//枚举路径
		         int pos=j+dy[k];
                if(pos>=1&&pos<=w){
                    int qi = f[i-1][pos] + a[i][j];
                    if(f[i][j]<qi){
                        f[i][j]=qi;
                        p[i][j]=dy[k];//记录路径
                    }
                }
	        }
		}
	}
    for(int i=1;i<=w;i++){
        if(f[n][i]>ans){
            ans=f[n][i];
            ans_y=i;
        }
    }
	cout<<ans<<'\n';
	print(n,ans_y);
}

1007 钉子和小球

待补

1008 [NOIP2002]过河卒

f[i][j]为到达i行j列的总方案,mp[i][j]记录这个点是否走过。

无脑地把马能到的和它自身的点的mp置1即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y;
int f[110][110],mp[110][110];
int dx[] = {-2,-2,-1,-1,1,1,2,2,-1,0};
int dy[] = {-1,1,-2,2,-2,2,-1,1,0,-1};
bool check(int x,int y){
    return x < 0 || x > n || y < 0 || y > m || mp[x][y];
}
int dfs(int xi,int yi){
    if (f[xi][yi]) return f[xi][yi];
    //cout<<xi<<" "<<yi<<endl;
    for (int i=8;i<=9;i++){//枚举卒的路径
        int xx = xi + dx[i],yy = yi + dy[i];
        if (check(xx,yy)) continue;
        f[xi][yi] += dfs(xx,yy);
    }
    return f[xi][yi];
}
signed main(){
    scanf(" %lld%lld%lld%lld",&n,&m,&x,&y);
    mp[x][y] = 1;
    for (int i=0;i<8;i++){//枚举马能到的八个方向
        int xx = x + dx[i],yy = y + dy[i];
        mp[xx][yy] = 1;
    }
    f[0][0] = 1;
    cout<<dfs(n,m);
}

1009 [NOIP2008]传球游戏

1010 「木」迷雾森林

1011 [NOIP2004]合唱队形

1012 [NOIP1999]拦截导弹

1013 数学考试

1014 小A买彩票

1015 购物

1016 牛牛的旅游纪念品

1017 [NOIP2001]装箱问题

1018 [NOIP2005]采药

1019 [NOIP2006]开心的金明