NOIP1997普及组

1224 -- 【NOIP1997普及组T1】棋盘问题

设有一个N*M方格的棋盘(1<=N<=100,1<=M<=100)

求出该棋盘中包含有多少个正方形、多少个长方形(不包括正方形)。

例如:当 N=2, M=3时: ![]()

正方形的个数有8个:即边长为1的正方形有6个;

边长为2的正方形有2个。

长方形的个数有10个:

即 2*1的长方形有4个:![]()

1*2的长方形有3个:![]()

3*1的长方形有2个:![]()

3*2的长方形有1个:![]()
如上例:输入:2 3

输出:8 10

//一开始没有思路,后来发现直接循环就可以了嘛,判断坐标
//循环顺序不要搞错了

#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;stack&gt;
#include&lt;cstdio&gt;
#include&lt;queue&gt;
#include&lt;map&gt;
#include&lt;vector&gt;
#include&lt;set&gt;
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//一开始没有思路,后来发现直接循环就可以了嘛,判断坐标 
//循环顺序不要搞错了 
int main(){
    int n,m;
    cin&gt;&gt;n&gt;&gt;m;
    int zheng=0,chang=0;
    for(int i=0;i&lt;=n;i++){  //从0开始!!!!!!!! 
        for(int j=0;j&lt;=m;j++){
            for(int z=i+1;z&lt;=n;z++){
                for(int l=j+1;l&lt;=m;l++){
                    int c1=z-i;
                    int c2=l-j;
                    if(c1==c2) zheng++;
                    else chang++;
                }
            }
        }
    }
    cout&lt;&lt;zheng&lt;&lt;&quot; &quot;&lt;&lt;chang&lt;&lt;endl;
return 0;
}

1225 -- 【NOIP1997普及组T2】三角形

将1,2,······,9共9个数排成下列形态的三角形。
![]()
其中:a~i分别表示1,2,······,9中的一个数字,并要求同时满足下列条件:
(1)a < f < i;
(2)b < d, g < h, c < e
(3)a+b+d+f=f+g+h+i=i+e+c+a=P
程序要求:
根据输入的边长之和P
输出所有满足上述条件的三角形的个数以及其中的一种方案。
若有多种方案输出字典序最小的那种。若无解输出NO。

//数据规模小,可以直接枚举搜索

#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;stack&gt;
#include&lt;cstdio&gt;
#include&lt;queue&gt;
#include&lt;map&gt;
#include&lt;vector&gt;
#include&lt;set&gt;
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//数据规模小,可以直接枚举搜索
int flag[12],res[12],b[12],p;
int judge(int step,int x) { //x是放置的数字,step是位置,函数是用来判断能不能放的
    if(flag[x]==1) return 0;
    if(step==2||step==3||step==7) return 1;//因为对这三个位置没有要求
    if(step==4) return x&gt;b[2];
    if(step==5) return x&gt;b[3];
    if(step==6) return (x&gt;b[1])&amp;&amp;(x+b[1]+b[2]+b[4]==p);
    if(step==8) return x&gt;b[7];
    if(step==9) return (x&gt;b[6])&amp;&amp;(x+b[1]+b[3]+b[5]==p)&amp;&amp;(b[6]+b[7]+b[8]+x==p);
}
int ans=0;
void dfs(int step) {
    if(step&gt;=9) {
        ans++;
        if(ans==1) { //保存第一次
            for(int i=1; i&lt;=9; i++) res[i]=b[i];
            return;
        }
    }
    for(int i=1; i&lt;=9; i++) {
        if(judge(step+1,i)) { //如果可以放
            flag[i]=1;
            b[step+1]=i;
            dfs(step+1);
            flag[i]=0;
        }
    }
}
int main() {
    cin&gt;&gt;p;
    for(int i=1; i&lt;=9; i++) {
        flag[i]=1;
        b[1]=i; //从不同初值开始尝试:数据规模小
        dfs(1);
        flag[i]=0; //回溯
    }
    if(ans==0) {
        cout&lt;&lt;&quot;NO&quot;&lt;&lt;endl;
        return 0;
    } else {
        cout&lt;&lt;ans&lt;&lt;endl;
        //for(int i=1;i&lt;=9;i++) cout&lt;&lt;res[i]&lt;&lt;&quot; &quot;;
        cout&lt;&lt;res[1]&lt;&lt;endl;
        cout&lt;&lt;res[2]&lt;&lt;&quot; &quot;&lt;&lt;res[3]&lt;&lt;endl;
        cout&lt;&lt;res[4]&lt;&lt;&quot; &quot;&lt;&lt;res[5]&lt;&lt;endl;
        cout&lt;&lt;res[6]&lt;&lt;&quot; &quot;&lt;&lt;res[7]&lt;&lt;&quot; &quot;&lt;&lt;res[8]&lt;&lt;&quot; &quot;&lt;&lt;res[9]&lt;&lt;endl;
    }
    return 0;
}

1226 -- 【NOIP1997普及组T3】街道问题

设有一个N*M(l<= N<=30, l<= M<= 30)的街道(如图一):
![]()
规定行人从A(1,1)出发,在街道上只能向东或北方向行走。
图二为N=3,M=3的街道图,从A出发到达B共有6条可供行走的路径:
![]()
1. A-A1-A2-A5-B
2. A-A1-A4-A5-B
3. A-A1-A4-A7-B
4. A-A3-A4-A5-B
5. A-A3-A4-A7-B
6. A-A3-A6-A7-B
若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的的街道)不让行人通行,如图一中用“*”表示的部分。
此矩形障碍区域用2对顶点坐标给出,图一中的2对顶点坐标为:(2,2),(8,4),此时从A出发到达B的路径仅有两条。
程序要求
任务一:给出N,M后,求出所有从A出发到达B的路径的条数。
任务二:给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,Y1),
(X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。

#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;stack&gt;
#include&lt;cstdio&gt;
#include&lt;queue&gt;
#include&lt;map&gt;
#include&lt;vector&gt;
#include&lt;set&gt;
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
int a[50][50];
int flag,n,m,num=0;
int vis[50][50];
int sx,sy,ex,ey;
int diss[2][2]={{0,1},{1,0}};
long long f[31][31]; 
void dfs(int x,int y){
    if(x==n&amp;&amp;y==m){
        num++;
        return;
    }
    for(int i=0;i&lt;2;i++){
        int xx=x+diss[i][0],yy=y+diss[i][1];
        if(xx&gt;=1&amp;&amp;xx&lt;=n&amp;&amp;yy&gt;=1&amp;&amp;yy&lt;=m&amp;&amp;vis[xx][yy]==0){
            vis[xx][yy]=1;
            dfs(xx,yy);
            vis[xx][yy]=0;
        }
    }
}
int main(){
    cin&gt;&gt;flag&gt;&gt;n&gt;&gt;m;
    if(flag==1){ ///任务1:就是简单的递推 
        for(int i=1;i&lt;=n;i++){
            for(int j=1;j&lt;=m;j++){
                if(i==1&amp;&amp;j==1) f[i][j]=1;
                else if(i==1) f[i][j]=f[i][j-1];
                else if(j==1) f[i][j]=f[i-1][j];
                else f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        cout&lt;&lt;f[n][m];
    }
    else{
        cin&gt;&gt;sx&gt;&gt;sy&gt;&gt;ex&gt;&gt;ey;
        for(int i=1;i&lt;=n;i++){
            for(int j=1;j&lt;=m;j++){
                if(i&gt;=sx&amp;&amp;i&lt;=ex&amp;&amp;j&gt;=sy&amp;&amp;j&lt;=ey) {   //任务二也是枚举,只是有些地方要设为0 
                    f[i][j]=0;
                    continue;
                }
                else if(i==1&amp;&amp;j==1) f[i][j]=1;
                else if(i==1) f[i][j]=f[i][j-1];
                else if(j==1) f[i][j]=f[i-1][j];
                else f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        cout&lt;&lt;f[n][m]&lt;&lt;endl;
    }
return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。