NOIP 2013普及组复赛中

全国涌现了2位390分大神

---

1、记数问题

【问题描述】

试计算在区间 1 到 n的所有整数中，数字 x(0 ≤ x ≤ 9)共出现了多少次?例如，在 1到 11 中，即在 1、2、3、4、5、6、7、8、9、10、11 中，数字 1 出现了 4 次。

【输入】

输入文件名为 count.in。

输入共 1 行，包含 2 个整数 n、x，之间用一个空格隔开。

【输出】

输出文件名为 count.out。

输出共 1 行，包含一个整数，表示 x 出现的次数。

【输入输出样例】

count.in

11  1

count.out

4

【数据说明】

对于 100%的数据，1≤ n ≤ 1,000,000，0 ≤ x ≤ 9。 

数据范围也才1——1000000，不大，所以可以直接做。 

#include

using name space std;

int x,r,l,k,ans;

int main(){

    cin>>r>>x;

    for(l=1;l<=r;l++)

    {

        k=l;

        while(k!=0){if(k%10==x)ans++;k/=10;}

    }

    cout<<ans;< p="">

    return 0;

}

---

2、表达式求值

【问题描述】

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

【输入】

输入文件为 expr.in。

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为 0到 2³¹-1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。

【输出】

输出文件名为 expr.out。

输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于 4 位时，请只输出最后 4 位，前导 0不输出。

【输入输出样例 1】

expr.in

1+1*3+4

expr.out

8

【输入输出样例 2】

expr.in

1+1234567890*1

expr.out

7891

【输入输出样例 3】

expr.in

1+1000000003*1

expr.out

4

【数据范围】

对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100;

对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000;

对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。 

读入一个数字读入一个符号（要mod 10000）；根据优先级，先处理乘号；直接累加。 

#include

using name space std;

unsigned long long num[100000];

char sign[100000];

unsigned long long i,l=1,ans;

int main(){

    cin>>num[1];

    while(cin>>sign[l]){

        l++;

        cin>>num[l];

        num[l]%=10000;

    }

    l--;

    for(i=1;i<=l;i++)

    if(sign[i]=='*')

   {num[i+1]=num[i]*num[i+1];num[i]=0;num[i+1]%=10000;}

    for(i=1;i<=l+1;i++)ans+=num[i];

    cout<<ans%10000;< p="">

    return 0;

}

---

3、小朋友的数字

【问题描述】

有 n 个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人)，小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值，输出时保持最大值的符号，将其绝对值对 p 取模后输出。

【输入】

输入文件为 number.in。

第一行包含两个正整数 n、p，之间用一个空格隔开。

第二行包含 n 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。

【输出】

输出文件名为 number.out。

输出只有一行，包含一个整数，表示最大分数对 p 取模的结果。

【输入输出样例 1】

number.in

5  997

1  2  3  4  5

number.out

21

【输入输出样例 2】

number.in

5  7

-1   -1   -1   -1   -1

number.out

-1

【数据范围】

对于 50%的数据，1 ≤ n ≤ 1,000，1 ≤ p ≤ 1,000所有数字的绝对值不超过1000;

对于 100%的数据，1 ≤ n ≤ 1,000,000，1 ≤ p ≤ 10⁹，其他数字的绝对值均不超过10⁹。 

比较easy的一个DP,特殊值就用最大子段和来求，分数不能直接求，要找规律，要么越来越大，要么越来越小，越来越小输出第一个，越来越大输出第n个。时间复杂度O(2n)。 

#include

#include

#include

#define LL long long// 因为这道题有可能会很大的数，用longlong

using name space std;

LL maxx ( LL x, LL y){ return x > y ? x : y; } // 求两个数的最大值

LL n, p, a[1100000];// a是一开始的那一段数

LL b[1100000],c[1100000]; // b是特征值，c是分数

int main (){

    int i, j;

    scanf ( "%lld%lld", &n,&p);

    for ( i = 1; i <= n; i ++ )

     scanf( "%lld", &a[i] );

    b[1] = a[1];

    LL now = maxx ( a[1], 0 ); // 看看第一个数是正数还是负数，如果是负数，则忽略这一个数，免得使统计的数变小

    for ( i = 2; i <= n; i ++ ){

        b[i]= b[i - 1]; // 先等于前面的特征值

        now+= a[i]; // 把这个累加值加上当前小孩子手上的数字

        b[i] = maxx ( now, b[i] ); // 看看是前面特征值的大还是累加值大

        if( now < 0 ) now = 0; // 如果累加值比0小，那又把它变成0，重新累加

    }

    c[1] = b[1];

    c[2] = c[1] + b[1]; // c1和c2是固定的，可以现在前面算

    int ok = 0; // ok就是看是最后的值更大些还是第一个更大些

    LL tmp = c[1];

    for ( i = 2; i < n; i ++ ){

        tmp += maxx ( b[i], 0ll );

        if ( tmp >= 0 ){ // 如果这个累加值比0大，那么就证明会累加越来越大

            ok = 1;

            break;

        }

    }

    for ( i = 3; i <= n; i ++ )

     c[i]= ( c[i - 1] + maxx ( b[i - 1], 0ll )) % p; // 求每个人分数的最大值

    if ( ok ) // 如果最后的大些

     printf ( "%dn", int ( c[n] ) );// 输出最后的

    else // 如果第一个大些

     printf ( "%dn", int ( c[1] % p) );// 输出第一个

    return 0; 

}

---

4、车站分级

【问题描述】

一条单向的铁路线上，依次有编号为 1, 2, ..., n 的 n个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求:如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)

例如，下表是 5 趟车次的运行情况。其中，前 4趟车次均满足要求，而第 5 趟车次由于停靠了 3 号火车站(2级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

图2013P

现有 m 趟车次的运行情况(全部满足要求)，试推算这 n个火车站至少分为几个不同的级别。

【输入】

输入文件为 level.in。

第一行包含 2 个正整数 n, m，用一个空格隔开。

第 i + 1 行(1 ≤ i ≤ m)中，首先是一个正整数 si(2 ≤ si ≤ n)，表示第 i趟车次有 si 个停靠站；接下来有 si 个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

【输出】

输出文件为 level.out。

输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。

【输入输出样例】

level.in

9  2

4  1  3  5  6

3  3  5  6

level.out

2

level.in

9  3

4  1  3  5  6

3  3  5  6

3  1  5  9 

level.out

3

【数据范围】

对于 20%的数据，1 ≤ n, m ≤ 10;

对于 50%的数据，1 ≤ n, m ≤ 100;

对于 100%的数据，1 ≤ n, m ≤ 1000。 

拓扑排序模板，只要在拓扑排序的过程中找到不能删除的，需要的层次就++。 

#include

#include

#include

#include

using name space std;

const int MAX_N = 2002;

int N,M;int P;

int s[MAX_N]; 

int level[MAX_N]; 

int infor[MAX_N][MAX_N];

vectord[MAX_N]; 

vectorp[MAX_N]; 

int adj[MAX_N][MAX_N];

int con[MAX_N];

void init()

{

    int i,j,k;

    scanf("%d%d",&N,&M);

    memset(adj,-1,sizeof(adj));

    P=N;

    for (i=1;i<=M;i++)

    {

        scanf("%d",&s[i]);

        for(j=1;j<=s[i];j++)

        scanf("%d",&infor[i][j]);

        if(infor[i][s[i]]-infor[i][1]+1==s[i]) continue;

        for(j=infor[i][1],k=1;j<=infor[i][s[i]];j++)

        {

            if(j==infor[i][k]) {p[i].push_back(j);k++;}

            else{d[i].push_back(j);} 

        }

        P++; 

        for(j=0;j< p="">

        adj[d[i][j]][P]=0,con[P]++;

        for(j=0;j

< p="">

        adj[P][p[i][j]]=1,con[p[i][j]]++;

    }

    for (i=1;i<=P;i++)

    level[i]=1;

}

int find_zero()

{

    int i;

    for (i=1;i<=P;i++)

    if (con[i]==0) return i;    

    return -1;

}

void work()

{

    int i,j,k;

    for (i=1;i<=P;i++)

    {

        k=find_zero();

        if (k==-1)return ; 

        for(k<=N?j=N+1:j=1;k<=N?j<=P:j<=N;j++)

        if(adj[k][j]!=-1) 

        {    

            level[j]=max(level[j],level[k]+adj[k][j]);

            adj[k][j]=false;

            con[j]--; 

        }

        con[k]=-1;

    }

}

void put()

{

    int i;

    int ans = 0;

    for (i=1;i<=P;i++)

    ans  = max(ans,level[i]); 

    printf("%d",ans);

}

int main()

{

    init();

    work();

    put();

    return 0;

}

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com