http://www.kuangbinoj.com:8080/contest.php?cid=1007
E,G 据说是final题，先不碰了，留坑待填
巨巨的解题报告：http://blog.csdn.net/zkxwhanybz828/article/details/44877759
A老师的方程，复杂模拟
将左边的系数和常数，与右边的系数和行数算出来就可以了
注意浮点数误差 ， -0.000要输出0.000
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; char s[10000],tmp[10000]; int check(char *s,int i) { if(s[i]=='+')return 1; if(s[i]=='-')return 2; if(s[i]=='=')return 3; if(s[i]>='0'&&s[i]<='9')return 4; return 0; } void inti() { int k=0; if(tmp[0]!='-')s[k++]='+'; for(int i=0;tmp[i];i++) { if(tmp[i]=='='&&tmp[i+1]!='-') { s[k++]='='; s[k++]='+'; } else if(tmp[i]=='+'&&tmp[i+1]=='-') { s[k++]='-'; i++; } else if(!check(tmp,i)&&(i==0||tmp[i-1]=='+'||tmp[i-1]=='-'||tmp[i-1]=='=')) { s[k++]='1'; s[k++]=tmp[i]; } else s[k++]=tmp[i]; } s[k]='\0'; } void work() { string x=""; for(int i=0;s[i];i++) { if(!check(s,i)) { while(s[i]&&!check(s,i))x+=s[i++]; break; } } // puts(s); // cout<<x<<endl; int _; for(int i=0;s[i];i++)if(s[i]=='=') { _=i; break; } int x1=0,x2=0,y1=0,y2=0; int t=0; int i=0; for(int i=0;i<_;) { if(s[i]=='+'||s[i]=='-') { sscanf(&s[i],"%d",&t); i++; while(check(s,i)==4)i++; // printf(" ** %c t=%d ",s[i],t); if(s[i]&&!check(s,i)) { x1+=t; } else y1+=t; // printf("x1=%d y1=%d\n",x1,y1); } else i++; } for(int i=_+1;s[i];) { if(s[i]=='+'||s[i]=='-') { sscanf(&s[i],"%d",&t); i++; while(s[i]&&check(s,i)==4)i++; // printf(" ** %c t=%d ",s[i],t); if(s[i]&&!check(s,i)) { x2+=t; } else y2+=t; // printf("x2=%d y2=%d\n",x2,y2); } else i++; } if(y1-y2==0)printf("%s=0.000\n",x.c_str()); else printf("%s=%.3lf\n",x.c_str(),(y1-y2)*1.0/(x2-x1)); } int main() { int T; scanf("%d",&T); getchar(); while(T--) { gets(tmp); inti(); work(); } } /* -3x+6x+200-x-500=x x+-5x-200x+5=-x 20x+-x+5=9 xxx+30xxx=-xxx */
B 最大乘积和，dp
dp[i][j] 表示前i个数用k个乘号得到的最大乘积
状态转移方程 dp[i][j]=max{dp[k][j-1]*mul[k+1][i], j<=k<i} , mul[i][j]表示i,j之间的数字
#include<iostream> #include<cstdio> using namespace std; #define ll long long char s[50]; ll dp[50][10];//dp[i][j]前i个数用j个乘号的最大乘积 ll mul[50][50];//mul[i][j]从i到j的数转化为数字的值 int main() { int n,p; while(~scanf("%d%d",&n,&p)) { scanf("%s",s+1); for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { ll sum=0; for(int k=i;k<=j;k++)sum=sum*10+s[k]-'0'; mul[i][j]=sum; } } for(int i=1;i<=n;i++)dp[i][0]=mul[1][i]; for(int j=1;j<=p;j++) { for(int i=j+1;i<=n;i++) { dp[i][j]=-1; for(int k=j;k<i;k++) { dp[i][j]=max(dp[i][j],dp[k][j-1]*mul[k+1][i]); } } } printf("%lld\n",dp[n][p]); } return 0; }
C dfs/状压dp
dfs 只要暴力就看好了
主要 baa 与 aac 接龙最长为baaac，接龙后长度要尽量长！
如果没有接龙，输出最长的那条包含首字母的单词
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s[30][100]; bool vis[30]; int ma; int n; int check(char *s1,char *s2) { int len1=strlen(s1); int len2=strlen(s2); for(int i=len1-1;i>=1;i--) { int k=0; while(i+k<len1&&k<len2-1) { if(s1[i+k]!=s2[k]) break; else k++; } if(i+k==len1)return k; } return -1; } void dfs(int k,int len) { int flag=1; for(int i=0;i<n;i++) { if(!vis[i]) { int t=check(s[k],s[i]); if(t!=-1) { // printf("** %d %d %d %d\n",k,i,len,t); flag=0; vis[i]=true; dfs(i,len+strlen(s[i])-t); vis[i]=false; } } } if(flag) { if(len>ma)ma=len; } } int main() { while(~scanf("%d",&n)) { memset(vis,false,sizeof(vis)); char op[2]; for(int i=0;i<n;i++)scanf("%s",s[i]); scanf("%s",op); ma=0; for(int i=0;i<n;i++) { if(s[i][0]==op[0]) { vis[i]=true; dfs(i,strlen(s[i])); vis[i]=false; } } printf("%d\n",ma); } return 0; }
这题xiaoxin巨用状压写的50行代码，不懂，留坑待填
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[1100000][21],len[25],g[25][25]; char s[25][125]; int main() { int maxx,i,j,n,doit,k,x,flag,size,pre,now; char c; while (~scanf("%d",&n)) { for (i=0;i<n;i++) { scanf("%s",s[i]); len[i]=strlen(s[i]); } scanf("%*c%c",&c); memset(g,-1,sizeof(g)); for (i=0;i<n;i++) for (j=0;j<n;j++) { doit=-1; for (k=1;k<len[i];k++) { if (len[i]-k>=len[j]) continue; flag=1; for (x=k;x<len[i];x++) if (s[i][x]!=s[j][x-k]) flag=0; if (flag) doit=k; } if (doit!=-1) g[i][j]=len[j]-len[i]+doit; } memset(dp,-1,sizeof(dp)); size=(1<<n)-1; for (i=1;i<=size;i++) for (j=0;j<n;j++) if (i&(1<<j)) { pre=(i^(1<<j)); if (pre==0&&s[j][0]==c) dp[i][j]=len[j]; for (k=0;k<n;k++) if (j!=k&&(i&(1<<k))==0&&g[j][k]!=-1&&dp[i][j]!=-1){ now=(i|(1<<k)); dp[now][k]=max(dp[i][j]+g[j][k],dp[now][k]); } } maxx=0; for (i=0;i<=size;i++) for (j=0;j<n;j++) maxx=max(maxx,dp[i][j]); printf("%d\n",maxx); } }
//D dp、这题dfs也可以过 ，留坑待填
http://blog.csdn.net/athenaer/article/details/8265234
http://www.cnblogs.com/sprayoflearn/archive/2010/11/16/1878741.html
http://max.book118.com/html/2012/0319/1333401.shtm
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; int n,k,ans; int f[250][10]; int main() { while(~scanf("%d%d",&n,&k)){ for (int i=0;i<=n;i++) f[i][1]=1; for (int i=2;i<=k;i++) for (int j=0;j<=n-k;j++) { if (i>j) f[j][i]=f[j][i-1]; else f[j][i]=f[j][i-1]+f[j-i][i]; } printf("%d\n",f[n-k][k]); } }
dfs：
F 约数 kmp next数组的应用，最小循环节
abcdabcd 的约数是 abcd abcdabcd
aaaa 的约数是 a aa aaaa 他们没有公约数
没有公约数输出0
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #define N 100010 using namespace std; int Next[N]; char s[N],t[N]; int getans(int x,int y) { // printf("%d %d\n",x,y); if(x>y)x^=y^=x^=y; int cnt=0; for(int i=1;i<=x;i++) { if(x%i==0&&y%i==0){ cnt++; } } return cnt; } int getNext(char *t,int tlen) { int j,k; j=0;k=-1;Next[0]=-1; while(t[j]) { if(k==-1||t[j]==t[k])Next[++j]=++k; else k=Next[k]; } if(tlen%(tlen-Next[tlen])==0&&Next[tlen]!=0) return tlen-Next[tlen]; else return tlen; } bool check(char *s,char *t,int k) { for(int i=0;i<k;i++) { if(s[i]!=t[i])return false; } return true; } int main() { // printf("%d\n",getans(20,30)); while(~scanf("%s%s",s,t)) { int slen=strlen(s); int tlen=strlen(t); int sc=getNext(s,slen); int tc=getNext(t,tlen); // printf("%d %d\n",sc,tc); // printf("%d\n",getans(slen/sc,tlen/tc)); if(sc==tc&&check(s,t,sc)) { printf("%d\n",getans(slen/sc,tlen/tc)); } else printf("0\n"); } } /* abcabcabcabcabc abcabc abcdabcd aaaa */