【NOIp】NOIp2007

川长思鸟来 2023-08-17 16:49 93阅读 0赞

# NOIp2007 #

### [T1 统计数字][T1] ###

标签：排序

这题没啥可写的......一遍排序统计次数就行了

code

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     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     int n,ans=1;
    12     int a[200005];
    13     int main(){
    14         n=read();
    15         for(int i=1;i<=n;i++){
    16             a[i]=read();
    17         }
    18         sort(a+1,a+1+n);
    19         for(int i=2;i<=n;i++){
    20             if(a[i]==a[i-1])ans++;
    21             else{
    22                 printf("%d %d\n",a[i-1],ans);
    23                 ans=1;
    24             }
    25         }
    26         printf("%d %d",a[n],ans);
    27         return 0;
    28     }
    29 }
    30 int main(){
    31     gengyf::main();
    32     return 0;
    33 }

### [T2 字符串的展开][T2] ###

标签：模拟，字符串

细节！

<1>当出现"5-x"这种一边是数字一边是字母的时候直接输出

<2>首尾是"-"时原样输出

<3>两个或多个连着的"-"时也是原样输出

其余的按题意模拟即可

code（好像是很久之前写的

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

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<string>
     6 #include<algorithm>
     7 using namespace std;
     8 string word;
     9 bool flag;
    10 char ans[1000000];
    11 int p1,p2,p3,len;
    12 char check(char c) {
    13     if (p1==1) return tolower(c);
    14     else if (p1==2) return toupper(c);
    15     else return '*';
    16 }
    17 int main(){
    18     cin>>p1>>p2>>p3;
    19     cin>>word;
    20     len=word.length();
    21     for(int i=0;i<=len;++i){
    22         int cnt=0;
    23         if(word[0]=='-'){
    24             if(flag);
    25             else{
    26                 cout<<'-'; 
    27                 flag=1;
    28                 continue;
    29             }
    30         }
    31         if(word[i]=='-'){
    32             if(word[i-1]>=word[i+1]||(word[i-1]>=48&&word[i-1]<=57&&word[i+1]>=65)||word[i-1]=='-'||word[i+1]=='-'){
    33                     cout<<word[i]; 
    34                     continue;
    35                 }
    36             if(p3==1){
    37                 for(int j=word[i-1]+1;j<word[i+1];++j){
    38                     for(int k=1;k<=p2;++k){
    39                         ans[++cnt]=j;
    40                     }
    41                 }
    42                 for(int q=1;q<=cnt;++q){
    43                     cout<<check(ans[q]);
    44                 }
    45             }
    46             if(p3==2){
    47                 for(int j=word[i+1]-1;j>=word[i-1]+1;--j){
    48                     for(int k=1;k<=p2;++k){
    49                         ans[++cnt]=j;
    50                     }
    51                 }
    52                 for(int q=1;q<=cnt;++q) {
    53                     cout<<check(ans[q]);
    54                 }
    55             }
    56         }
    57         else cout<<word[i];
    58     }
    59     return 0;
    60 }

### [T3 矩阵取数游戏][T3] ###

标签：dp，高精度

\_\_int128乱搞

可以发现行与行之间无关，所以对每一行区间dp求最大值再相加即可

f\[i\]\[j\]=max(f\[i\]\[j-1\],f\[i+1\]\[j\])对于区间\[i,j\]只能从\[i+1,j\]或\[i,j+1\]转移

先取后面的为f\[i\]\[j-1\]即f\[i\]\[j-1\]\*2+a\[j\]\*2相当于把以后要取的所有数\*2，也就是那个什么乘2^i

先取前面的同理 f\[i+1\]\[j\]\*2+a\[i\]\*2

所以转移方程为f\[i\]\[j\]=max(f\[i+1\]\[j\]\*2+a\[i\]\*2,f\[i\]\[j-1\]\*2+a\[j\]\*2)

会爆long long 需要高精，我太懒了写的\_\_in128

code

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

### [T4 树网的核][T4] ###

标签：dp

我只会辣鸡n^3做法(因为好想啊QAQ

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 inf=0x3f3f3f3f;
    11     const int N=310;
    12     int m[N][N],n,s,ans=inf;
    13     int main(){
    14         n=read();s=read();
    15         for(int i=1;i<=n;i++)
    16             for(int j=1;j<=n;j++){
    17                 m[i][j]=inf;
    18                 if(i==j)m[i][j]=0;
    19             }
    20         for(int i=1;i<n;i++){
    21             int x,y,z;
    22             x=read();y=read();z=read();
    23             m[x][y]=min(z,m[x][y]);
    24             m[y][x]=m[x][y];
    25         }
    26         for(int k=1;k<=n;k++)
    27             for(int i=1;i<=n;i++)
    28                 for(int j=1;j<=n;j++){
    29                     if(m[i][k]==inf||m[k][j]==inf)continue;
    30                     else m[i][j]=min(m[i][k]+m[k][j],m[i][j]);
    31                 }
    32         int l,r,len=0;
    33         for(int i=1;i<=n;i++)
    34             for(int j=1;j<=n;j++){
    35                 if(m[i][j]>=inf||m[i][j]<=len)continue;
    36                 len=m[i][j];
    37                 l=i;r=j;
    38         }
    39         for(int i=1;i<=n;i++){
    40             if(m[l][i]+m[i][r]!=len)continue;
    41             for(int j=1;j<=n;j++){
    42                 if(m[l][j]+m[r][j]!=len)continue;
    43                 if(m[i][j]>s)continue;
    44                 int ecc=-inf;
    45                 for(int k=1;k<=n;k++){
    46                     ecc=max(ecc,m[i][k]+m[j][k]-m[i][j]>>1);
    47                 }
    48                 ans=min(ans,ecc);
    49             }
    50         }
    51         printf("%d",ans);
    52         return 0;
    53     }
    54 }
    55 int main(){
    56     gengyf::main();
    57     return 0;
    58 }

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

![1658269-20190902215755382-1890657527.png][]

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

[T1]: https://www.luogu.org/problem/P1097
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/daa24317e989400c903c35a203657409.png
[T2]: https://www.luogu.org/problem/P1098
[T3]: https://www.luogu.org/problem/P1005
[T4]: https://www.luogu.org/problem/P1099
[1658269-20190902215755382-1890657527.png]: /images/20230809/3a03ec7b4a3a4c2abd23e8966cf96c21.png