【NOIp】NOIp2008

╰半橙微兮° 2023-08-17 16:49 106阅读 0赞

# NOIp2008 #

### [T1 笨小猴][T1] ###

标签：STL

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

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

code

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

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

### [T2 火柴棒等式][T2] ###

标签：没有标签

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

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

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

code

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

求最大值code

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

Max

另附：[搜索题解][Link 1]

### [T3 传纸条][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

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

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 }

早期代码～

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

### [T4 双栈排序][T4] ###

标签：图论，贪心，dp

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

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

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

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

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     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 }

这题看完之后一脸懵，想不到什么正经方法，苦死无果后看题解才恍然大悟，这告诉我们不仅要知道某一算法的应用范围，还要理解算法本质QAQ

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

![1658269-20190903215104034-1792227399.png][]

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

[T1]: https://www.luogu.org/problem/P1125
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/9055c923825841e2b2cb2649e9c0919c.png
[T2]: https://www.luogu.org/problem/P1149
[Link 1]: https://www.luogu.org/blog/user6781/solution-p1149
[T3]: https://www.luogu.org/problem/P1006
[Link 2]: https://www.luogu.org/problem/T35377
[T4]: https://www.luogu.org/problem/P1155
[1658269-20190903215104034-1792227399.png]: /images/20230809/7f044715bf1a4e0cad019ca97dc88b64.png