【NOIp】NOIp2005

ゝ一世哀愁。 2023-08-17 16:49 54阅读 0赞

因为立下了死亡flag，所以...

# NOIp2005 #

### [T1 谁拿了最多奖学金][T1] ###

标签：模拟，排序

个人感觉模拟比较好写，排序的话关键字较多，注意下细节

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long
     4 namespace gengyf{
     5     const int maxn=10010000;
     6     inline int read(){
     7         int x=0,f=1;char s=getchar();
     8         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     9         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    10         return x*f;
    11     }
    12     int n,sum,tot,max,c1,c2,x;
    13     char a,b;string name,stu;
    14     int main(){
    15         n=read();
    16         for(int i=1;i<=n;i++){
    17             cin>>name>>c1>>c2>>a>>b>>x;
    18             if(c1>80&&x>=1){
    19                 sum+=8000;
    20             }
    21             if(c1>85&&c2>80){
    22                 sum+=4000;
    23             }
    24             if(c1>90){
    25                 sum+=2000;
    26             }
    27             if(c1>85&&b=='Y'){
    28                 sum+=1000;
    29             }
    30             if(c2>80&&a=='Y'){
    31                 sum+=850;
    32             }
    33             tot+=sum;
    34             if(sum>max){
    35                 stu=name;max=sum;
    36             }
    37             sum=0;
    38         }
    39         cout<<stu<<endl<<max<<endl<<tot<<endl;
    40         return 0;
    41     }
    42 }
    43 int main(){
    44     gengyf::main();
    45     return 0;
    46 }

### [T2 过河][T2] ###

标签：dp，离散化

题意：让青蛙尽量不踩石头，求最少需要的石头数

设f\[i\]为在i点最少踩的石子数，则转移方程为f\[i\]=min(f\[i-j\]+flag\[i\]) flag\[i\]为在i点是否有石子，有为1，没有为0

离散化遵循两点间的距离d大于t时，一定可以由d%t跳过来

最后注意一点“只要青蛙能过桥即可”，所以最后的答案在 l 到 l+t 的范围内取min

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long
     4 namespace gengyf{
     5     inline int read(){
     6         int x=0,f=1;char s=getchar();
     7         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     8         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     9         return x*f;
    10     }
    11     const int maxn=350000;
    12     int a[105],d[105],stone[maxn];
    13     int f[maxn],l,s,t,n;
    14     int main(){
    15         int l,s,t,n;
    16         l=read();s=read();t=read();n=read();
    17         for (int i=1;i<=n;i++){
    18             a[i]=read();
    19         }
    20         sort(a+1,a+n+1);
    21         for (int i=1;i<=n;i++){
    22             d[i]=(a[i]-a[i-1])%2520;
    23         }
    24         for (int i=1;i<=n;i++){
    25             a[i]=a[i-1]+d[i];
    26             stone[a[i]]=1;
    27         }
    28         l=a[n];
    29         for (int i=0;i<=l+t;i++){
    30             f[i]=n;
    31         }
    32         f[0]=0;
    33         for(int i=1;i<=l+t;i++)
    34             for(int j=s;j<=t;j++){
    35                 if(i-j>=0)f[i]=min(f[i],f[i-j]);
    36                 f[i]+=stone[i];
    37             }
    38         int ans=n;
    39         for(int i=l;i<l+t;i++)ans=min(ans,f[i]);
    40         printf("%d",ans);
    41         return 0;
    42     }
    43 }
    44 int main(){
    45     gengyf::main();
    46     return 0;
    47 }

### [ T3 篝火晚会][T3] ###

标签：模拟

题意：给定两个环，可以以环的形式移动数的位置（如：1,2,3,4 移动1,2,3 得 2,3,1,4，a1->a2,a2->a3,a3->a1以此类推，此类移动可以不连续），移动一次的代价为此次移动的数的个数，问最小代价

通过给出的谁想挨着谁的信息构造出一个目标环，一次比较目标环和原始环之间的差取max

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return x*f;
     9     }
    10     const int maxn=5e4+5;
    11     int a[maxn],l[maxn],r[maxn],d[maxn],v[maxn];
    12     int z[maxn],f[maxn],ans,n;
    13     int main(){
    14         n=read();
    15         for(int i=1;i<=n;i++){
    16             l[i]=read();r[i]=read();
    17         }
    18         d[1]=1;d[2]=l[1];v[d[1]]=v[d[2]]=1;
    19         for(int i=2;i<=n-1;i++){
    20             if(d[i-1]==l[d[i]]){
    21                 d[i+1]=r[d[i]];
    22                 v[d[i+1]]=1;
    23             }
    24             else if(d[i-1]==r[d[i]]){
    25                 d[i+1]=l[d[i]];
    26                 v[d[i+1]]=1;
    27             }
    28             else {
    29                 printf("-1");
    30                 return 0;
    31             }
    32         }
    33         for(int i=1;i<=n;i++){
    34             if(!v[i]){
    35                 printf("-1");return 0;
    36             }
    37         }
    38         for(int i=1;i<=n;i++){
    39             z[(d[i]-i+n)%n]++;
    40             f[(d[n-i+1]-i+n)%n]++;
    41         }
    42         for(int i=0;i<n;i++){
    43             ans=max(ans,max(z[i],f[i]));
    44         }
    45         printf("%d",n-ans);
    46         return 0;
    47     }
    48 }
    49 int main(){
    50     gengyf::main();
    51     return 0;
    52 }

### [T4 等价表达式 ][T4 _] ###

标签：模拟，字符串

思路简单，但实现较烦（调了1个小时没过QAQ，重构抄题解）

显然如果将任意a赋值带入后结果均相等，则等价，所以只需多取几组a检验是否相等即可

将a代入计算结果时找\[l,r\]区间内最低级的运算符递归计算两边

另外可能出现a^10^10这种情况，注意取模

code（from luogu 题解 @[snowbody][]）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstring>
     3 #include <cstdio>
     4 
     5 #define MX 55
     6 #define oo 10020123
     7 #define MD 100000007
     8 
     9 using namespace std;
    10 
    11 typedef long long ll;
    12 
    13 ll qpw(ll x,ll t){ll ans=1;for(int i=1;i<=t;i++)ans=ans*x%MD;return ans;}
    14 
    15 ll calc(char *str,int l,int r,ll a)
    16 {
    17     int prio=0,mnpos=MX,mn=+oo,cnt=0,p[MX],num=0;
    18     memset(p,0x3f,sizeof(p));
    19     for(int i=r;i>=l;i--)
    20     {
    21         if(str[i]==')')prio+=100;
    22         if(str[i]=='(')prio-=100;
    23         if(str[i]=='^')p[i]=prio+3,cnt++;
    24         if(str[i]=='*')p[i]=prio+2,cnt++;
    25         if(str[i]=='+')p[i]=prio+1,cnt++;
    26         if(str[i]=='-')p[i]=prio+1,cnt++;
    27         if(mn>p[i])mn=p[i],mnpos=i;
    28     }
    29     if(cnt==0)
    30     {
    31         for(int i=l;i<=r;i++)if(str[i]=='a')return a;
    32         for(int i=l;i<=r;i++)if(isdigit(str[i]))num=num*10+str[i]-'0';
    33         return num;
    34     }
    35     else
    36     {
    37         if(str[mnpos]=='^')return qpw(calc(str,l,mnpos-1,a),calc(str,mnpos+1,r,a));
    38         if(str[mnpos]=='*')return (calc(str,l,mnpos-1,a)*calc(str,mnpos+1,r,a))%MD;
    39         if(str[mnpos]=='+')return (calc(str,l,mnpos-1,a)+calc(str,mnpos+1,r,a))%MD;
    40         if(str[mnpos]=='-')return (calc(str,l,mnpos-1,a)-calc(str,mnpos+1,r,a))%MD;
    41     }
    42     return 0;
    43 }
    44 
    45 int main()
    46 {
    47     int len[27],n,ans[15];
    48     char str[27][MX];    
    49     scanf("%[^\r]",str[0]),getchar();
    50     len[0]=strlen(str[0]);
    51     scanf("%d",&n),getchar();
    52     for(int i=1;i<=n;i++)
    53     {
    54         scanf("%[^\r]",str[i]),getchar();
    55         len[i]=strlen(str[i]);
    56     }
    57     for(int i=0;i<=10;i++)ans[i]=calc(str[0],0,len[0]-1,i-5);
    58     for(int i=1;i<=n;i++)
    59     {
    60         int f=1;
    61         for(int j=0;j<=10;j++)
    62             if(ans[j]!=calc(str[i],0,len[i]-1,j-5))
    63                 {f=0;break;}
    64         if(f)printf("%c",'A'+i-1);
    65     }
    66     return 0;
    67 }

--------------------

![1658269-20190830233945235-2104453494.png][]

转载于:https://www.cnblogs.com/gengyf/p/11434073.html

[T1]: https://www.luogu.org/problem/P1051
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/8b5242f8da244e69bfbf5e5bc181a9dc.png
[T2]: https://www.luogu.org/problem/P1052
[T3]: https://www.luogu.org/problem/P1053
[T4 _]: https://www.luogu.org/problem/P1054
[snowbody]: https://www.luogu.org/space/show?uid=41155
[1658269-20190830233945235-2104453494.png]: /images/20230809/7582f64f2eb5465ba1aabf5bcbaf12b5.png