【NOIp】NOIp2007

NOIp2007

T1 统计数字

标签：排序

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

code

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 字符串的展开

标签：模拟，字符串

细节！

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

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

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

其余的按题意模拟即可

code（好像是很久之前写的

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 矩阵取数游戏

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

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 }

T4 树网的核

标签：dp

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

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