NOIp2005

T1 谁拿了最多奖学金

标签：模拟，排序

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

code

 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 过河

标签：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

 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 篝火晚会

标签：模拟

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

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

code

 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 等价表达式

标签：模拟，字符串

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

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

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

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

code（from luogu 题解 @snowbody）

 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("%[^
]",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("%[^
]",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 }