$NOIP2005$ 题解报告
分类:
IT文章
•
2025-01-22 11:39:01
目录
$Luogu P1051$ 谁拿了最多奖学金$( √ )$
$Luogu P1052$ 过河$( √ )$
$Luogu P1053$ 篝火晚会$( √ )$
$Luogu P1054$ 等价表达式$( √ )$
$Luogu P1051$ 谁拿了最多奖学金
题目传送门
大水题，直接按题意模拟判断即可
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 struct Student{
4 string name;
5 int s1,s2,p;
6 bool west,ganbu;
7 }student[103];
8 int num,maxn=0,sum=0;
9 void count(int x){
10 int ans=0;
11 if(student[x].s1>80&&student[x].p>=1) ans+=8000;
12 if(student[x].s1>85&&student[x].s2>80) ans+=4000;
13 if(student[x].s1>90) ans+=2000;
14 if(student[x].s1>85&&student[x].west) ans+=1000;
15 if(student[x].s2>80&&student[x].ganbu) ans+=850;
16 if(ans>maxn) maxn=ans,num=x;
17 sum+=ans;
18 }
19 int main(){
20 int n;
21 scanf("%d",&n);
22 for(int i=1;i<=n;i++){
23 cin>>student[i].name>>student[i].s1>>student[i].s2;
24 char c;
25 getchar();c=getchar();getchar();
26 if(c=='Y') student[i].ganbu=1;else student[i].ganbu=0;
27 c=getchar();
28 if(c=='Y') student[i].west=1;else student[i].west=0;
29 cin>>student[i].p;
30 count(i);
31 }
32 cout<<student[num].name<<endl<<maxn<<endl<<sum;
33 return 0;
34 }
代码戳这里
$Luogu P1052$ 过河
题目传送门
这题太恶心了$QAQ$，考试的时候要是碰上那就是一个死
首先$DP$还是很容易想的，主要讲一下路径压缩$($为了让数组可以成功开下$)$
以下内容我直接蒯$Luogu$题解了，写得挺好的
然后对于$s==t$的情况，就只有一种距离可以走，我们直接枚举每个石子会不会走到即可
![]()
1 #include<bits/stdc++.h>
2 #define ri register int
3 #define ll long long
4 #define rl register ll
5 #define go(i,a,b) for(ri i=a;i<=b;i++)
6 #define back(i,a,b) for(ri i=a;i>=b;i--)
7 #define g() getchar()
8 #define il inline
9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13 ri w=0,q=1;char ch=g();
14 while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15 while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16 return w*q;
17 }
18 const int N=10002;
19 const int INF=1e9+7;
20 int L,s,t,m,a[102],l[102],f[N];
21 bool tag[N];
22 int main(){
23 //freopen(".in","r",stdin);
24 //freopen(".out","w",stdout);
25 L=fr();s=fr();t=fr();m=fr();
26 go(i,1,m)a[i]=fr();
27 sort(a+1,a+1+m);
28 if(s==t){
29 ri ans=0;
30 go(i,1,m)if(a[i]%s==0)ans++;
31 pf("%d
",ans);return 0;
32 }
33 l[m+1]=min(L-a[m],100);L=0;
34 go(i,1,m)l[i]=min(a[i]-a[i-1],90),L+=l[i],tag[L]=1;
35 L+=l[m+1];
36 go(i,1,L+9){
37 f[i]=INF;
38 go(j,s,t)if(i>=j)f[i]=min(f[i],f[i-j]+(tag[i]==1));
39 }
40 ri mn=INF;
41 go(i,L,L+9)mn=min(mn,f[i]);
42 pf("%d
",mn);
43 return 0;
44 }
代码戳这里
$Luogu P1053$ 篝火晚会
题目传送门
实名吐槽出题人太坑了！
其实意识到题目的真正含义之后就挺好做了，我们先随便造一个目标序列，如果造不出显然就输出$-1$
因为题目要求的移动命令中的序号可以不连续$($坑就坑在没说清楚$QAQ)$，所以我们每次只移动当前不合法的即可，现在我们要算最少有多少个不合法的位置，即算最多有多少个合法的位置。
然后本质上只有两种排列$($就是左右相邻不同$)$，然后我们对于两个序列的每个位置，求出对于$0～n-1$每个移动次数，移动后可以满足有$x$个位置和原序列匹配，求出所有$x$中的最大值，答案即为$n-x$
![]()
1 #include<bits/stdc++.h>
2 #define ri register int
3 #define ll long long
4 #define rl register ll
5 #define go(i,a,b) for(ri i=a;i<=b;i++)
6 #define back(i,a,b) for(ri i=a;i>=b;i--)
7 #define g() getchar()
8 #define il inline
9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13 ri w=0,q=1;char ch=g();
14 while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15 while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16 return w*q;
17 }
18 const int N=50002;
19 int n,l[N],r[N],as1[N],as2[N],mx;
20 int sub1[N],sub2[N];
21 bool vis[N],legal=1;
22 il void build(){
23 as1[1]=1;as1[2]=r[1];vis[1]=vis[r[1]]=1;
24 go(i,2,n-1){
25 if(as1[i-1]==l[as1[i]])as1[i+1]=r[as1[i]],vis[r[as1[i]]]=1;
26 else if(as1[i-1]==r[as1[i]])as1[i+1]=l[as1[i]],vis[l[as1[i]]]=1;
27 else{legal=0;puts("-1");return;}
28 }
29 go(i,1,n)if(!vis[i]){legal=0;puts("-1");return;}
30 mem(vis,0);as2[1]=1;as2[2]=l[1];vis[1]=vis[l[1]]=1;
31 go(i,2,n-1){
32 if(as2[i-1]==l[as2[i]])as2[i+1]=r[as2[i]],vis[r[as2[i]]]=1;
33 else if(as2[i-1]==r[as2[i]])as2[i+1]=l[as2[i]],vis[l[as2[i]]]=1;
34 else{legal=0;puts("-1");return;}
35 }
36 go(i,1,n)if(!vis[i]){legal=0;puts("-1");return;}
37 return;
38 }
39 il void sol(){
40 go(i,1,n){sub1[(as1[i]-i+n)%n]++;sub2[(as2[i]-i+n)%n]++;}
41 go(i,0,n-1)mx=max(mx,max(sub1[i],sub2[i]));
42 pf("%d
",n-mx);return;
43 }
44 int main(){
45 //freopen(".in","r",stdin);
46 //freopen(".out","w",stdout);
47 n=fr();
48 go(i,1,n)l[i]=fr(),r[i]=fr();
49 build();if(legal)sol();
50 return 0;
51 }
代码戳这里
![]()
1 #include<bits/stdc++.h>
2 #define ri register int
3 #define ll long long
4 #define rl register ll
5 #define go(i,a,b) for(ri i=a;i<=b;i++)
6 #define back(i,a,b) for(ri i=a;i>=b;i--)
7 #define g() getchar()
8 #define il inline
9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il ll fr(){
13 rl w=0,q=1;char ch=g();
14 while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15 while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16 return w*q;
17 }
18 const int bas=233;
19 const int mod=998244353;
20 ll n,p[52],hd1,num[52],hd2,Ans,ans[30];
21 il bool cmp(char x,char y){
22 if(x==y)return 1;
23 if(x=='^')return 1;
24 if(x=='*')return y=='^'?0:1;
25 if(x=='+'||x=='-'){
26 if(y=='+'||y=='-')return 1;
27 else return 0;
28 }
29 else return 0;
30 }
31 il ll ksm(rl x,rl y){
32 if(x==1||y==0)return 1;
33 rl as=1;
34 while(y){
35 if(y&1)as=1ll*as*x%mod;
36 x=1ll*x*x%mod;y>>=1;
37 }
38 return as;
39 }
40 il ll cal(rl x,rl y,char c){
41 rl as;
42 if(c=='+')as=(x+y)%mod;
43 if(c=='-')as=(y-x+mod)%mod;
44 if(c=='*')as=x*y%mod;
45 if(c=='^')as=ksm(y,x);
46 return as;
47 }
48 int main(){
49 freopen("1.in","r",stdin);
50 freopen("1.out","w",stdout);
51 char ch=g();bool lst=0;
52 while(ch=='
'||ch=='
')ch=g();
53 while(ch!='
'&&ch!='
'){
54 while(ch==' ')ch=g();
55 if(ch=='
'||ch=='
')break;
56 if(ch=='a')num[++hd2]=bas,lst=0;
57 if(ch<='9'&&ch>='0'){
58 if(lst)num[hd2]=num[hd2]*10+ch-'0';
59 else num[++hd2]=ch-'0',lst=1;
60 }
61 if(ch=='(')p[++hd1]=ch,lst=0;
62 if(ch==')'){while(p[hd1]!='('&&hd1)num[hd2-1]=cal(num[hd2],num[hd2-1],p[hd1]),hd2--,hd1--;hd1--;lst=0;}
63 if(ch=='+'||ch=='-'||ch=='*'||ch=='^'){
64 while(cmp(p[hd1],ch)&&hd1){num[hd2-1]=cal(num[hd2],num[hd2-1],p[hd1]);hd2--;hd1--;}
65 p[++hd1]=ch;lst=0;
66 }
67 ch=g();
68 }
69 while(hd1&&hd2>1){num[hd2-1]=cal(num[hd2],num[hd2-1],p[hd1]);hd2--;hd1--;}Ans=(num[hd2]+mod)%mod;hd2=hd1=0;
70 n=fr();
71 go(i,1,n){
72 ch=g();lst=0;
73 while(ch=='
'||ch=='
')ch=g();
74 while(ch!='
'&&ch!='
'){
75 while(ch==' ')ch=g();
76 if(ch=='
'||ch=='
')break;
77 if(ch=='a')num[++hd2]=bas,lst=0;
78 if(ch<='9'&&ch>='0'){
79 if(lst)num[hd2]=num[hd2]*10+ch-'0';
80 else num[++hd2]=ch-'0',lst=1;
81 }
82 if(ch=='(')p[++hd1]=ch,lst=0;
83 if(ch==')'){while(p[hd1]!='('&&hd1)num[hd2-1]=cal(num[hd2],num[hd2-1],p[hd1]),hd2--,hd1--;hd1--;lst=0;}
84 if(ch=='+'||ch=='-'||ch=='*'||ch=='^'){
85 while(cmp(p[hd1],ch)&&hd1){num[hd2-1]=cal(num[hd2],num[hd2-1],p[hd1]);hd2--;hd1--;}
86 p[++hd1]=ch;lst=0;
87 }
88 ch=g();
89 }
90 while(hd1&&hd2>1){num[hd2-1]=cal(num[hd2],num[hd2-1],p[hd1]);hd2--;hd1--;}
91 if((num[hd2]+mod)%mod==Ans)ans[++ans[0]]=i;hd2=hd1=0;
92 }
93 go(i,1,ans[0])pf("%c",(char)ans[i]+'A'-1);puts("");
94 return 0;
95 }
96 /*
97 注意细节！！！
98 不开ll见祖宗
99 时刻保证栈不能为空，每次记得清空两个栈！两个栈都要清空！
100 读入多加一行判断当前是否为换行，否则会连着读入两个表达式
101 */
