2013 ACM/ICPC 成都网络赛解题报告
第三题：HDU 4730 We Love MOE Girls
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4730
水题~~~
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>#include <deque>#include <queue>#include <iterator>#include <stack>#include <map>#include <set>#include <algorithm>#include <cctype>using namespace std;typedef __int64 xiaohao;typedef long long LL;const int N=1090;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;char s[N];char ss[10]="nanodesu";int main(){ int T,se=0; scanf("%d",&T); while(T--) { int m, n; scanf("%s",s); int len=strlen(s); printf("Case #%d: ", ++se); if(len<4) { printf("%s%s\n",s,ss); continue; } if(s[len-1]=='u'&&s[len-2]=='s'&&s[len-3]=='e'&&s[len-4]=='d') { for(int i=0;i<len-4;i++) printf("%c",s[i]); printf("%s\n",ss); continue; } printf("%s%s\n",s,ss); } return 0;}
第四题：HDU 4731 Minimum palindrome
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4731
题解：规律题，我们可以发现当m大于等于3时，abcabcabc……这个串的回文为1，并且字典数最小，
m等以1时，直接输出n个a，
现在要解决的就是m=2的情况：
通过自己再纸上面写可以得出当n大于等于9时，最大的回文为4，要字典数最小，所以前四个都为a，后面也可以找到一个最小循环结：babbaa
但是还要讨论最后还剩余几个，如果是小于等于两个，那么添加2个a，否则按循环结添加。
AC代码：
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>#include <deque>#include <queue>#include <iterator>#include <stack>#include <map>#include <set>#include <algorithm>#include <cctype>using namespace std;typedef __int64 xiaohao;typedef long long LL;const int N=100090;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;const char tab[8][20] ={ "a", "ab", "aab", "aabb", "aaaba", "aaabab", "aaababb", "aaababbb"};int main(){ int T,se=0; scanf("%d",&T); while(T--) { int m, n; scanf("%d%d",&m,&n); printf("Case #%d: ", ++se); if(m>2) { int a = n / 3; int b = n % 3; for(int i=0;i<a;i++) printf("abc"); for(int i=0;i<b;i++) printf("%c",'a'+i); printf("\n"); } else if(m == 1) { for(int i=0;i<n;i++) putchar('a'); printf("\n"); } else { if(n < 9) { printf("%s\n", tab[n-1]); } else { char t[] = "babbaa"; printf("aaaa"); int a = (n-4) / 6; int b = (n-4) % 6; for(int i=0;i<a;i++) printf("babbaa"); if(b <= 2) for(int i=0;i<b;i++) putchar('a'); else for(int i=0;i<b;i++) putchar(t[i]); printf("\n"); } } } return 0;}
第七题：HDU 4734 F(x)
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4734
数位DP。
用dp[i][j][k] 表示第i位用j时f(x)=k的时候的个数，然后需要预处理下小于k的和，然后就很容易想了
dp[i+1][j][k+(1<<i)]=dp[i][j1][k];(0<=j1<=j1)
AC代码：
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>#include <deque>#include <queue>#include <iterator>#include <stack>#include <map>#include <set>#include <algorithm>#include <cctype>using namespace std;typedef __int64 xiaohao;typedef long long LL;const int N=7000;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;int dp[12][12][N];int tsum[12][12][N];int w[20];void init(){ memset(dp,0,sizeof(dp)); dp[0][0][0]=1; int n=10; for(int i=0;i<12;i++) { for(int j=0;j<n;j++) { for(int k=0;k<N-1;k++) { for(int k1=0;k1<n;k1++) { int t1=k+k1*(1<<i); dp[i+1][k1][t1]+=dp[i][j][k]; } } } } memset(tsum,0,sizeof(tsum)); for(int i=1;i<12;i++) { for(int j=0;j<n;j++) { for(int k=0;k<N-1;k++) { tsum[i][j][k]=tsum[i][j][k-1]+dp[i][j][k]; } } }}int f(int x,int fa){ if(x==0) return 0; int len=0; int flag=0; while(x) { w[++len]=x%10; x/=10; } int tsum1=0; for(int i=len;i>=1;i--) { for(int k=0;k<w[i];k++) { tsum1+=tsum[i][k][fa-flag]; } flag+=(w[i])*(1<<(i-1)); if(fa<flag) break; } return tsum1;}int main(){ init(); int cas; while(~scanf("%d",&cas)) { for(int q=1;q<=cas;q++) { int a,b;scanf("%d%d",&a,&b); int len=0; int fa=0; while(a) { int t1=a%10; fa+=(1<<(len))*t1; len++; a/=10; } int ans=f(b+1,fa); printf("Case #%d: %d\n",q,ans); } } return 0;}
第十题：HDU 4737 A Bit Fun
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4737
水题，直接暴力~~~~
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>#include <deque>#include <queue>#include <iterator>#include <stack>#include <map>#include <set>#include <algorithm>#include <cctype>using namespace std;typedef __int64 xiaohao;typedef long long LL;const int N=100090;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;#define Maxn 110000int sa[Maxn];int main(){ int t,n,m; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { int ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&sa[i]); for(int i=1;i<=n;i++) { int ba=0; for(int j=i;j<=n;j++) { ba|=sa[j]; if(ba>=m) break; ans++; } } printf("Case #%d: %d\n",ca,ans); } return 0;}