NOIP2013普及组

T1】记数问题

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

其实这个问题也很经典了。。。

别想很复杂，其实打暴力完全OK

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

#include<cstdio>

#include<queue>

#include<map>

#include<vector>

#include<set>

using namespace std;

const int maxn=1010;

const int INF=0x3fffffff;

int n,x;

int main(){

	cin>>n>>x;

	int ans=0;

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

		int temp=i;

		while(temp){

			if(temp%10==x) ans++;

			temp/=10;

		}

	}

	cout<<ans<<endl;

return 0;

}

T2】表达式求值

这种题也是经典题

但是这下面是一种很...奇妙的做法

在加法那里处理还没处理完的乘法

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

#include<cstdio>

#include<queue>

#include<map>

#include<vector>

#include<set>

using namespace std;

const int maxn=1010;

const int INF=0x3fffffff;

//简单化的表达式求值

//只有加、乘

/*

stack<long long> num;

stack<char> op;

char a[100001];

int lev(char x){ //计算优先级

	if(x=='+') return 1;

	if(x=='*') return 2;

	return 0;

}

void js(stack<long long> &num,stack<char> &op){

	int y=num.top();

	num.pop();

	int x=num.top();

	num.pop();

	char xx=op.top();

	op.pop();

	if(xx=='+') num.push((x+y)%10000);

	else num.push((x*y)%10000);

}

*/

//下面的这个写法不知道为什么超时了

//管他的，用一种简单的特殊写法

int last;

char c;

int x,a=0,b=1,sum=0;

int main(){

	int i,j;

	bool flag=1;

	do{

		if(cin>>c);

		else{

			flag=0;

			c='+'; //在最后补一个+号

		}

		if(c>='0'&&c<='9'){

			x=x*10+c-'0';

		}

		else{

			a=x;

			x=0;

		}

		if(c=='*'){

			last=1;

			b=(a*b)%10000; //处理乘数

		}

		if(c=='+'){

			if(last){

				a=(a*b)%10000; //a是另一个乘数

				sum=(sum+a)%10000;

				b=1;

				last=0;

			}

			else sum+=a;

		}

	}while(flag);

	cout<<sum%10000<<endl;

	return 0;

} 

/*

int main(){

	scanf("%s",a+1);

	int len=strlen(a+1);

	bool flag=0;

	long long temp=0;

	for(int i=1;i<=len;i++){

		if(a[i]>='0'&&a[i]<='9'){

			temp=temp*10+a[i]-'0';

			flag=true;

		}

		else{

		if(flag){

			num.push(temp);

			temp=0;

			flag=false;

		}

		while(!op.empty()&&(lev(op.top())>=lev(a[i]))) js(num,op);

		op.push(a[i]);

		}

	}

	if(flag){

		num.push(temp);

		temp=0;

		flag=false;

	}

	while(!op.empty()){

		js(num,op);

	}

	cout<<num.top()%10000<<endl;

return 0;

}

*/

T3 小朋友的数字

这道题涉及到一个细节，取余所导致的结果不同和太大值之间的问题

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

#include<cstdio>

#include<queue>

#include<map>

#include<vector>

#include<set>

using namespace std;

const int maxn=1000001;

const int INF=0x3fffffff;

long long res[maxn],d[maxn],dp[maxn];

//d[i]是特征值，res是得分,dp是前i项的和，dp[i]=max(0,dp[i-1])+x

//d[i]=max(d[i-1],dp[i]) res[i]=max(res[i-1],res[i-1]+d[i-1])

long long n,p;

//但是注意结果有20分拿不到，因为数据范围，如果在计算过程种可能会超过Long long,所以必须边算边取模

//但是取模就无法比较最大值，所以不能直接用Max，但是从第二个人开始分数是没有下降的，所以再运算过程种如果超过Longlong就可以去模

//因为res[1]是不超过long long的，所以在运算过程中一旦超过long long就说明是最大的是res[n]， 

int main(){

	cin>>n>>p;

	int x;

	dp[0]=0;

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

		cin>>x;

		 dp[i]=max(0LL,dp[i-1])+x;  //0后面要加LL

		if(i==1) {

			d[i]=dp[i];

		}

		else{

			d[i]=max(d[i-1],dp[i]);

		}

	}

	res[1]=d[1];

	res[2]=d[1]+dp[1];

	bool flag=0; //判断在n>=3的过程中，有没有超过long long

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

		res[i]=max(res[i-1],res[i-1]+d[i-1]);

		if(res[i]>1e9){

			flag=1;

			res[i]=res[i]%p;

		}

	}

	 if(flag) cout<<res[n]%p<<endl;

	 else cout<<max(res[1],res[n])%p<<endl;

return 0;

}

T4】车站分级

想不到是考图吧哈哈哈，但是这道题的连线端点要注意，从小的指向大的，是在从经过的车站之间没停靠的车站都是明确小于的，所以可以连线

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

#include<cstdio>

#include<queue>

#include<map>

#include<vector>

#include<set>

using namespace std;

const int maxn=1010;

const int INF=0x3fffffff;

//这道题是考图，经过大于等于比当前等级的车站，就能总结出比当前等级小的和大的，让小的指向大的

//再拓扑排序，及查找深度，就能够得出至少深度得多少

int n,m;

int to[maxn],in[maxn],mapp[maxn][maxn];

int temp[maxn],vis[maxn];

int main(){

	cin>>n>>m;

	int num;

	for(int i=1;i<=m;i++){

		cin>>num;

		int x,t=0,l,r;

		memset(temp,0,sizeof(temp));

		memset(vis,0,sizeof(vis));

		memset(to,0,sizeof(to));

		for(int j=1;j<=num;j++){

			cin>>x;

			if(j==1) l=x;

			if(j==num) r=x;

			temp[j]=x;vis[x]=1;

		}

		for(int z=l;z<=r;z++){

			if(vis[z]==0){

				to[++t]=z;

			}

		}

		//把小的都指向大的

		for(int j=1;j<=t;j++){

			for(int z=1;z<=num;z++) mapp[to[j]][temp[z]]=1;

		}

	}

	//下面初始化入度

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

		in[i]=0;

		for(int j=1;j<=n;j++) if(mapp[j][i]) in[i]++;

	}

	int ans=1;

	memset(temp,0,sizeof(temp));

	while(true){

		bool f=0;

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

			temp[i]=in[i];

		}

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

			if(temp[i]==0) {

				for(int j=1;j<=n;j++){

					if(mapp[i][j]){

						mapp[i][j]=0;

						in[j]--;

					}

				}

			}

			else f=1; //如果没有说明还需要继续循环

		}

		if(f==0) break; //如果没有更新了就可以退出

			ans++;

	}

	cout<<ans<<endl;

return 0;

}

巴特西

NOIP2013普及组

T1】记数问题

T2】表达式求值

T3 小朋友的数字

T4】车站分级

最新文章

热门文章