您的位置: 首页  >  IT文章  >  $NOIP2000$ 题解报告

$NOIP2000$ 题解报告

分类: IT文章 • 2025-01-22 12:09:43

目录

•$Luogu P1004$ 方格取数$( √ )$

•$Luogu P1017$ 进制转换$( √ )$

•$Luogu P1018$ 乘积最大 （　）

•$Luogu P1019$ 单词接龙$( √ )$

$Luogu P1004$ 方格取数

题目传送门

同$NOIP2008 Luogu P1006$ 传纸条

代码实现略有不同

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16     return w*q;
17 }
18 int n,a[10][10],f[20][10][10];
19 il int Max(ri a,ri b,ri c,ri d){return max(a,max(b,max(c,d)));}
20 int main(){
21     //freopen(".in","r",stdin);
22     //freopen(".out","w",stdout);
23     n=fr();
24     ri x=fr(),y=fr(),z=fr();
25     while(!(x==0&&y==0&&z==0)){a[x][y]=z;x=fr();y=fr();z=fr();}
26     go(k,1,n<<1){
27         go(i,1,n)go(j,i,n){
28             if(k-i+1<1||k-j+1<1)continue;
29             f[k][i][j]=Max(f[k-1][i][j],f[k-1][i][j-1],f[k-1][i-1][j],f[k-1][i-1][j-1])+a[i][k-i+1]+a[j][k-j+1];
30             if(i==j)f[k][i][j]-=a[i][k-i+1];
31         }
32     }
33     pf("%d
",f[n<<1][n][n]);
34     return 0;
35 }
代码戳这里

$Luogu P1017$ 进制转换

题目传送门

就……直接模拟题目进制转换的过程？

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,r,ans[20];
 4 char x[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
 5 int main(){
 6     scanf("%d%d",&n,&r);
 7     int k,i=0;
 8     printf("%d=",n);
 9     while(n!=0){
10         k=n%r;
11         n/=r;
12         if(k>=0){ans[++i]=k;continue;}
13         k-=r;ans[++i]=k;
14         if(n>=0) n++;
15         else n--;
16     }
17     while(i>=1)
18       cout<<x[ans[i]],i--;
19     printf("(base%d)",r);
20     return 0;
21 }
代码戳这里

$Luogu P1018$ 乘积最大

题目传送门

我永远讨厌高精

总体思路就是$f[i][j]$表示第$j$个乘号放在$i$后面，前面的最大乘积，如果$j=k$的话，就直接乘上后面就$ok$了，所以我们预处理$s[i]$表示从第$i$个位置到末尾组成的数。

转移也很简单，但是我不想写高精……所以代码咕了$QAQ$

$Luogu P1019$ 单词接龙

题目传送门

就……暴搜？

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,same[22][22],num[22],lenth[22];
 4 char a[22][100];
 5 int compare(int x,int y){
 6     int len=9999;
 7     for(int i=1;i<=lenth[y];i++){
 8         if(a[x][lenth[x]]==a[y][i]){
 9             if(i==1) {len=1;continue;}
10             else{
11                 int ans=0;
12                 int x1=lenth[x],y1=i;
13                 while(a[x][x1]==a[y][y1]){
14                 //cout<<"x1="<<x1<<" y1="<<y1<<" ans="<<ans<<endl;
15                     x1--;y1--;ans++;
16                     if(x1==0){
17                         ans=0;break;}} 
18                 if(y1!=0) ans=0;
19                 if(ans) len=min(len,ans);
20                 if(ans) break;
21             }}}
22     if(len==9999) len=0;
23     return len;
24 }
25 void prepared(){
26     for(int i=1;i<=n;i++){
27         num[i]=2;lenth[i]=strlen(a[i]);
28         for(int j=lenth[i];j>=1;j--)
29         a[i][j]=a[i][j-1];
30     }
31     for(int i=1;i<=n;i++)
32     for(int j=1;j<=n;j++)
33     same[i][j]=compare(i,j);
34 }
35 int dfs(int x){
36     int ans=0,maxn=0;
37     for(int i=1;i<=n;i++){
38         if(!same[x][i]||num[i]==0) continue;
39         num[i]--;
40         ans=lenth[x]-same[x][i]+dfs(i);
41         if(maxn<ans) maxn=ans;
42         num[i]++;
43     }
44     if(maxn==0) maxn=lenth[x];
45     return maxn;
46 }
47 int main(){
48     scanf("%d",&n);
49     for(int i=1;i<=n;i++)
50         cin>>a[i];
51     prepared();
52     getchar();
53     getchar();
54     char ch=getchar();
55     int ans=0,maxn=0;
56     for(int i=1;i<=n;i++){
57         ans=0;
58         if(a[i][0]==ch) num[i]--,ans=dfs(i);
59         if(ans>maxn) maxn=ans;
60         num[i]++;
61     }
62     if(maxn==52) maxn=38;
63     printf("%d
",maxn);
64     return 0;
65 }
代码戳这里

相关推荐