2024年3月7日发(作者：)
NOIP2013年普及组复赛真题解析
T1 计数问题
解析：
对于 100%的数据，1≤ n ≤ 1,000,000，0 ≤ x ≤ 9。枚举每个数的每一位就行。
程序：
include
#include
using namespace std;
int main(){
int n,x;
cin>>n>>x;
int i,c=0;
for(i=1;i<=n;i++){
int a=i;
while(a!=0){
if(a%10==x)c++;
a/=10;
}
}
cout< return 0; } =================================================== T2 表达式求值 解析： 对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100； 对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000； 对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。 程序： #include #include #include #include #include using namespace std; char last; char c; int x=0; int a=0,b=1; int 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; sum=(sum+a)%10000; b=1; last=0; } else sum+=a;//上一个是加号的情况 } }while(flag==1); printf("%d",sum%10000); return 0; } =================================================== T3 解析： Case 1: 小朋友的特征值分别为 1、3、6、10、15，分数分别为 1、2、5、11、21，最大值 21对 997 的模是 21。 Case 2: 小朋友的特征值分别为-1、-1、-1、-1、-1，分数分别为-1、-2、-2、-2、-2，最大值-1 对 7 的模为-1，输出-1。 对于 50%的数据，1 ≤ n ≤ 1,000，1 ≤ p ≤ 1,000所有数字的绝对值不超过 1000； 对于 100%的数据，1 ≤ n ≤ 1,000,000，1 ≤ p ≤ 10^9，其他数字的绝对值均不超过 10^9。 完全可以读一个算一个，每次把新算出的数值和之前保存的最大值比较，得到新的最大值。特征值和分数都这么处理 程序： #include #include #include #include using namespace std; const long long inf=1000000005; int n,p,a[1000500]; long long su[1000500]={0};//特征值,也可以不要数组 long long scoremx=-inf;//前排最大分数 long long dmx=-inf;//分数加特征值的最大值 long long ans=-inf; int sum1(){//计算特征值。 int i,j; long long s=0; long long mx=-inf; for(i=1;i<=n;i++){ if(s+a[i]>mx)mx=s+a[i]; su[i]=mx; if(s+a[i]>0) s+=a[i]; else s=0; } // for(i=1;i<=n;i++){ su[i]%=p<<1;//防止数据过大 //p<<1可以避免mod时的误差(如果是读一个算一个，数据不会超限制 ,而一次算完的做法就有必要处理一下数据了) } return 0; } int main(){ freopen("","r",stdin); freopen("","w",stdout); int i,j; scanf("%d%d",&n,&p); for(i=1;i<=n;i++)scanf("%d",&a[i]); sum1(); long long score; //1 处理第一个数据 scoremx=su[1]; score=su[1]; dmx=score+su[1]; //end for(i=2;i<=n;i++){ score=dmx; if(dmx>scoremx)scoremx=dmx; if(su[i]+score>dmx)dmx=su[i]+score; } printf("%d",scoremx%p); return 0; } =================================================== T4-车站分级 解析： 对于 20%的数据，1 ≤ n, m ≤ 10； 对于 50%的数据，1 ≤ n, m ≤ 100； 对于 100%的数据，1 ≤ n, m ≤ 1000。 如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠，所以一趟车从始发站到终点站之间，没停的站级别都低于停了的站。 在低级站和高级站之间连线，构成AOV网，利用拓扑排序即可知道总共有多少 级车站。 程序： #include #include #include #include #include using namespace std; int n,m; int a;//[第i趟车次的停靠站数] int s[2000];//[第i趟车次停靠的站] int mp[1200][1200]={0}; int book[1200]; int r[1200],c[1200]; //入度出度 int st[1200]; int ans=0; void rd(){ scanf("%d%d",&n,&m); int i,j,k; for(i=1;i<=m;i++){ memset(book,0,sizeof(book)); scanf("%d",&a); for(j=1;j<=a;j++){ scanf("%d",&s[j]); book[s[j]]=1; } for(k=s[1];k<=s[a];k++)//遍历从始发站到终点站 { if(!book[k]) for(j=1;j<=a;j++) if(!mp[k][s[j]])//从低级连到高级可过，从高级连到低级无误但超时 { mp[k][s[j]]=1;//从低级站到高级站连线 r[s[j]]++;}//入度++ } } } int main(){ // freopen("","r",stdin); // freopen("","w",stdout); rd(); int i,j; int top=0; memset(book,0,sizeof(book)); while(1){//拓扑排序 ans++;//循环次数即为总级数 top=0; for(i=1;i<=n;i++) if(!r[i] && !book[i])//所有没有入度且之前没处理过的点，都是同一级别的 { top++; st[top]=i;//入站 book[i]=1;//标记为已处理 } if(!top)break;//栈为空，说明所有点都排好序了 for(j=1;j<=n;j++) for(i=1;i<=top;i++){ if(mp[st[i]][j]){ mp[st[i]][j]=0; r[j]--; } } if(!top)break; } printf("%d",ans-1); return 0; }
发布评论