$Luogu\ P1005$ 矩阵取数游戏
又是讨厌的高精，我调了好久$QAQ$
设$f[i][j]$表示某一行状态变为$[i,j]$时的最大答案，直接从$f[i-1][j],f[i][j+1]$转移
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 const int N=82; 19 struct node{ 20 int s[50]; 21 }f[N][N],c[N],ans; 22 int a[N],n,m; 23 il void Mem(node &x,ri y){go(i,0,40)x.s[i]=y;return;} 24 il node mul(node x,int y){ 25 int len=x.s[0]+3,z=0; 26 node as;Mem(as,0); 27 go(i,1,len){ 28 as.s[i]=x.s[i]*y+z; 29 z=as.s[i]/10;as.s[i]%=10; 30 } 31 while(!as.s[len])len--;as.s[0]=len; 32 return as; 33 } 34 il node add(node x,node y){ 35 int len=0,z=0; 36 node as;Mem(as,0); 37 while(len<x.s[0]||len<y.s[0]){ 38 len++;as.s[len]=x.s[len]+y.s[len]+z; 39 z=as.s[len]/10;as.s[len]%=10; 40 } 41 while(z)as.s[++len]=z,z=as.s[len]/10,as.s[len]%=10; 42 as.s[0]=len;return as; 43 } 44 il node Max(node x,node y){ 45 if(x.s[0]>y.s[0])return x; 46 if(x.s[0]<y.s[0])return y; 47 back(i,x.s[0],1){ 48 if(x.s[i]>y.s[i])return x; 49 if(x.s[i]<y.s[i])return y; 50 } 51 return x; 52 } 53 il void MEM(){go(i,1,m)back(j,m,i)go(k,0,28)f[i][j].s[k]=0;return;} 54 int main(){ 55 freopen("1.in","r",stdin); 56 freopen("1.out","w",stdout); 57 n=fr();m=fr(); 58 c[0].s[0]=1;c[0].s[1]=1; 59 go(i,1,m)c[i]=mul(c[i-1],2); 60 go(n0,1,n){ 61 MEM(); 62 go(i,1,m)a[i]=fr(); 63 go(i,1,m)back(j,m,i){ 64 if(i-1>=1)f[i][j]=Max(f[i][j],add(f[i-1][j],mul(c[m-j+i-1],a[i-1]))); 65 if(j+1<=m)f[i][j]=Max(f[i][j],add(f[i][j+1],mul(c[m-j+i-1],a[j+1]))); 66 } 67 node mx;Mem(mx,0); 68 go(i,1,m){ 69 mx=Max(mx,add(f[i][i],mul(c[m],a[i]))); 70 } 71 ans=add(ans,mx); 72 } 73 if(ans.s[0]==0)puts("0"); 74 back(i,ans.s[0],1)pf("%d",ans.s[i]);puts(""); 75 return 0; 76 }
$Luogu\ P1097$ 统计数字
排序后直接统计即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 long long b[200002]; 5 struct num{ 6 int s,x; 7 }a[10002]; 8 int main(){ 9 int tot=1,i; 10 scanf("%d",&n); 11 for(i=1;i<=n;i++) 12 scanf("%lld",&b[i]); 13 sort(b+1,b+n+1); 14 a[tot].s=b[1],a[tot].x++; 15 for(i=2;i<=n;i++){ 16 if(b[i]!=b[i-1]) a[++tot].s=b[i],a[tot].x++; 17 else a[tot].x++; 18 } 19 for(i=1;i<=tot;i++) 20 printf("%d %d\n",a[i].s,a[i].x); 21 return 0; 22 }
$Luogu\ P1098$ 字符串的展开
非常简单，直接模拟展开即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 char s1[10000],s2[102]; 4 int p1,p2,p3,len=0; 5 bool same(char x,char y){ 6 if(x>='0'&&x<='9'&&y>='0'&&y<='9') return 1; 7 if(x>='a'&&x<='z'&&y>='a'&&y<='z') return 1; 8 return 0; 9 } 10 void work(int i){ 11 int l=len+1,r; 12 if(s2[i]>='0'&&s2[i]<='9'){ 13 if(p1==1||p1==2) 14 for(int j=s2[i]+1;j<s2[i+2];j++) 15 for(int k=1;k<=p2;k++) 16 s1[++len]=j; 17 } 18 else{ 19 if(p1==1) 20 for(int j=s2[i]+1;j<s2[i+2];j++) 21 for(int k=1;k<=p2;k++) 22 s1[++len]=j; 23 if(p1==2) 24 for(int j=s2[i]+1;j<s2[i+2];j++) 25 for(int k=1;k<=p2;k++) 26 s1[++len]=j-32; 27 } 28 if(p1==3) 29 for(int j=s2[i]-'0'+1;j<s2[i+2]-'0';j++) 30 for(int k=1;k<=p2;k++) 31 s1[++len]='*'; 32 r=len; 33 if(p3==1) return ; 34 if(p3==2){ 35 char ss[r+5]; 36 for(int j=l;j<=r;j++) 37 ss[j]=s1[r-j+l]; 38 for(int j=l;j<=r;j++) 39 s1[j]=ss[j]; 40 } 41 return; 42 } 43 int main(){ 44 cin>>p1>>p2>>p3; 45 getchar(); 46 cin>>s2; 47 for(int i=0;i<strlen(s2);i++){ 48 if(s2[i]=='-'){ 49 if(!same(s2[i-1],s2[i+1])||s2[i+1]<=s2[i-1]||s2[i+1]==s2[i-1]+1){ 50 if(s2[i+1]!=s2[i-1]+1) s1[++len]=s2[i]; 51 continue; 52 } 53 work(i-1); 54 } 55 else s1[++len]=s2[i]; 56 } 57 for(int i=1;i<=len;i++) 58 cout<<s1[i]; 59 cout<<endl; 60 return 0; 61 }
$Luogu\ P1099$ 树网的核