大家好，又见面了，我是你们的朋友全栈君。

NOIp2008

T1 笨小猴

标签：STL

用一个map存字母到数字(出现次数)的映射

由于数据范围很小，可以不用线性筛直接${\sqrt{n}}$即可

code

<span role="heading" aria-level="2">【NOIp】NOIp2008

 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     int maxx,minn=999;char word[101];
11     map<char,int>m;
12     bool prime(int x){
13         for(int i=2;i<=sqrt(x);i++){
14             if(x%i==0){
15                 return 0;
16             }
17         }
18         return 1;
19     }
20     int main(){
21         cin>>word;
22         int l=strlen(word);
23         for(int i=0;i<l;i++){
24             m[word[i]]++;
25             maxx=max(maxx,m[word[i]]);
26         }
27         for(int i=0;i<l;i++){
28             minn=min(minn,m[word[i]]);
29         }
30         if(maxx==0||maxx==1){
31             printf("No Answer\n");
32             return 0;
33         }
34         if(maxx-minn==1||maxx-minn==0){
35             printf("No Answer\n0");
36             return 0;
37         }
38         if(prime(maxx-minn)){
39             printf("Lucky Word\n");
40             printf("%d\n",maxx-minn);
41         }
42         else {
43             printf("No Answer\n0");
44         }
45         return 0;
46     }
47 }
48 int main(){
49     gengyf::main();
50     return 0;
51 }

我觉得我就是个笨小猴，minn忘赋初值WA了一次，没特判1又WA了一次，太zz了

T2 火柴棒等式

标签：没有标签

直接枚举i,j从1到最大值,如果组成i,j,i+j的火柴棒总数恰好等于n-4统计答案+1

这道题唯一可说的就是怎么找最大值，因为现在还不知道最大值，所以枚举的范围要稍微开大一点（1e3,1e4这种

然后把n从1到24跑一遍，记录下i，j的最大值maxx，再用maxx替换掉刚才的范围最大值

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     int n,s[10]={6,2,5,5,4,5,6,3,7,6},ans;
11     int match(int x){
12         int tmp=0;
13         if(x<10)return s[x];
14         while(x!=0){
15             int xx=x%10;
16             tmp+=s[xx];
17             x/=10;
18         }
19         return tmp;
20     }
21     int main(){
22         n=read();
23         for(int i=0;i<=999;i++)
24             for(int j=0;j<=999;j++){
25                 int k=i+j;
26                 if(match(i)+match(j)+match(k)==n-4){
27                     ans++;
28                 }
29             }
30         printf("%d",ans);
31         return 0;
32     }
33 }
34 int main(){
35     gengyf::main();
36     return 0;
37 }

求最大值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     int n,s[10]={6,2,5,5,4,5,6,3,7,6},ans,maxx=0;
11     int match(int x){
12         int tmp=0;
13         if(x<10)return s[x];
14         while(x!=0){
15             int xx=x%10;
16             tmp+=s[xx];
17             x/=10;
18         }
19         return tmp;
20     }
21     int main(){
22         n=read();//输入n为0
23         while(n!=25){
24             n++;
25             for(int i=0;i<=999;i++)
26                 for(int j=0;j<=999;j++){
27                     int k=i+j;
28                     if(match(i)+match(j)+match(k)==n-4){
29                         maxx=max(maxx,max(i,j));
30                         ans++;
31                     }
32                 }
33         }
34         printf("%d",maxx);
35         return 0;
36     }
37 }
38 int main(){
39     gengyf::main();
40     return 0;
41 }

Max

另附：搜索题解

T3 传纸条

标签：dp

把两张纸条看成都从左上传下来

3维的转移比较好想

情况只有四种：

第一张从上边来，第二张从上边来

第一张从上边来，第二张从左边来

第一张从左边来，第二张从上边来

第一张从左边来，第二张从左边来

f[i][j][k]表示现在位置的横纵坐标之和为i，第一张的纵坐标为j，第二张的纵坐标为k

所以方程为

第一张从上边来，第二张从上边来 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k-1)+a[j][i-j]+a[k][i-k]}

第一张从上边来，第二张从左边来 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k)+a[j][i-j]+a[k][i-k]}

第一张从左边来，第二张从上边来 f(i,j,k)=max{f(i,j,k),f(i-1,j,k-1)+a[j][i-j]+a[k][i-k]}

第一张从左边来，第二张从左边来 f(i,j,k)=max{f(i,j,k),f(i-1,j,k)+a[j][i-j]+a[k][i-k]}

但是！它不够优秀！

我们使用滚动数组

可以发现i只会由i-1转移过来，所以可以把第一维省去

j,k都是从更小j,k的转移而来，所以将j,k倒序枚举防止在转移前被修改

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int f[201][201],a[201][201];
 5 int maxx(int a,int b,int c,int d){
 6     if(a<b)a=b;
 7     if(c>a)a=c;
 8     if(d>a)a=d;
 9     return a;
10 }
11 int main(){
12     int n,m;
13     scanf("%d%d",&n,&m);
14     for(int i=1;i<=n;i++)
15       for(int j=1;j<=m;j++){
16           scanf("%d",&a[i][j]);
17       }
18     f[1][2]=a[1][2]+a[2][1];
19     for(int k=4;k<n+m;++k)
20       for(int i=n;i>0;--i)
21         for(int j=n;j>i;--j){
22             f[i][j]=maxx(f[i][j],f[i-1][j-1],f[i-1][j],f[i][j-1])+a[i][k-i]+a[j][k-j];
23             if(i==j)f[i][j]-=a[i][k-i];
24         }
25     int ans=0;
26     for(int i=1;i<=n;i++)
27       for(int j=1;j<=n;j++){
28           ans=max(f[i][j],ans);
29       }
30     printf("%d\n",f[n-1][n]);
31     return 0;
32 }

早期代码～

附：大教室中传纸条（数据加强版）

T4 双栈排序

标签：图论，贪心，dp

先跑一遍dp判断那些不能在同一个栈里

我们发现如果有三个位置i,j,k满足i<j<k且a[k]<a[i]<a[j]是不可行的显然

再将不能共存的i,j连边，进行二分图染色，如果不能染说明不存在可行解

又因为要求字典序最小，所以尽量先放S1

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     int f[1010],n,a[1010],color[1010];
11     struct edge{
12         int nxt,to;
13     }e[1010];
14     int head[1010],cnt,s1[1010],s2[1010];
15     void add(int from,int to){
16         e[++cnt].to=to;e[cnt].nxt=head[from];
17         head[from]=cnt;
18     }
19     bool dfs(int u,int c){
20         color[u]=c;
21         for(int i=head[u];i;i=e[i].nxt){
22             int to=e[i].to;
23             if(color[to]==color[u])return false;
24             if(!color[to]&&!dfs(to,3-c))return false;
25         }
26         return true;
27     }
28     int main(){
29         n=read();
30         for(int i=1;i<=n;i++){
31             a[i]=read();
32         }
33         f[n]=a[n];
34         for(int i=n-1;i>=1;i--){
35             f[i]=min(f[i+1],a[i]);
36         }
37         for(int i=1;i<=n;i++)
38             for(int j=i+1;j<=n;j++){
39                 if(a[i]<a[j]&&f[j]<a[i]){
40                     add(i,j);add(j,i);
41                 }
42             }
43         for(int i=1;i<=n;i++){
44             if(!color[i]&&!dfs(i,1)){
45                 printf("0");
46                 return 0;
47             }
48         }
49         int c1=0,c2=0,now=1;
50         for(int i=1;i<=n;i++){
51             if(color[i]==1){
52                 s1[++c1]=a[i];printf("a ");
53             }
54             else {
55                 s2[++c2]=a[i];printf("c ");
56             }
57             while(s1[c1]==now||s2[c2]==now){
58                 if(s1[c1]==now){
59                     printf("b ");c1--;
60                 }
61                 else {
62                     printf("d ");c2--;
63                 }
64                 now++;
65             }
66         }
67         return 0;
68     }
69 }
70 int main(){
71     gengyf::main();
72     return 0;
73 }