题目链接：https://vjudge.net/contest/147561#problem/A
题意：除法运算，abcde / fghij = n，从小到大输出，其中abcdefghij为0~9的不重复数字。
分析：
1、从小到大其实就是一大就跟着大。
2、不用枚举0~9的全排列，只用枚举其中一个数fghij即可，算出abcde，看是不是0~9都有。
Tip: sprintf(*,格式输入,*);用法，把目标数据转成char * 型。
#include <bits/stdc++.h> using namespace std; int main()
{
//freopen("in.txt","r",stdin);
int n;
int kase = ;
while(scanf("%d",&n),n)
{
if(kase++)
puts("");
int cnt = ;
char buf[];
for(int fghij=;; fghij++)
{
int abcde = fghij*n;
sprintf(buf,"%05d%05d",abcde,fghij);
if(strlen(buf)>) break;
sort(buf,buf+); bool flag = true;
for(int i=; i<; i++)
if(buf[i]!=i+'')
{
flag = false;
break;
} if(flag)
{
cnt ++;
printf("%05d / %05d = %d\n",abcde,fghij,n);
} } if(cnt==)
printf("There are no solutions for %d.\n",n);
}
return ;
}
题目链接：https://vjudge.net/contest/147561#problem/B
题意：最大乘法，要你找出一个连续子序列乘积最大。
分析：打算枚举起点，终点，求和，肯定是TLE，利用前缀和的思想修改一下，变成前缀积。
#include <bits/stdc++.h>
#include <algorithm> using namespace std; int x[]; int main()
{
int n;
int cases = ;
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<n; i++)
scanf("%d",&x[i]); long long ans = ;
for(int i=; i<n; i++) {
long long tmp = ;
for(int j=i; j<n; j++)
{
tmp = tmp*(long long)x[j];
ans = max(ans,tmp);
}
}
printf("Case #%d: The maximum product is %lld.\n\n",cases++,ans); }
return ;
}
题目链接：https://vjudge.net/contest/147561#problem/C
题意：分数拆分。(x>=y) 找出所有 x,y，使得 1/k = 1/x + 1/y;
分析：由于是两个数的和，起点很容易知道，就是从 k 开始，但是不能够一直枚举下去，总要有一个结束点，这个结束点就是 2k，1/x + 1/y <= 2/y; 就有 y<=2k;
#include <bits/stdc++.h> using namespace std; int main()
{ int k;
while(scanf("%d",&k)!=EOF) {
vector<int> ansx,ansy;
int cnt = ;
for(int y=k+;y<=*k;y++) {
if((y*k)%(y-k)==)
{
cnt ++;
int x = y*k/(y-k);
ansx.push_back(x);
ansy.push_back(y);
//printf("1/%d = 1/%d + 1/%d\n",k,x,y);
}
}
printf("%d\n",cnt);
for(int i=;i<cnt;i++)
printf("1/%d = 1/%d + 1/%d\n",k,ansx[i],ansy[i]);
}
return ;
}
题目链接：https://vjudge.net/contest/147561#problem/D
题意：素数环。
分析：http://www.cnblogs.com/TreeDream/p/5712621.html
枚举每一个位置，这个时候就要回溯了。
#include <stdio.h>
#include <string.h> int prime[]= {}; ///是素数就是0
bool vis[];
int ans[];
int n; void dfs(int k)
{
if(k==n+)
{
for(int i = ; i <=n; i++)
{
if(i!= ) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
return ;
}
else if(k==n)
{
for(int i=; i<=n; i++)
{
if(!vis[i]&&!prime[ans[k-]+i]&&!prime[i+ans[]])
{
ans[k] = i;
vis[i]=true;
dfs(k+);
vis[i] = false;
}
}
}
else
{
for(int i=; i<=n; i++)
{
if(!vis[i]&&!prime[ans[k-]+i])
{
ans[k] = i;
vis[i]=true;
dfs(k+);
vis[i] = false;
}
}
}
} int main()
{
//freopen("in.txt","r",stdin);
int kase = ;
///打出40个素数来
for(int i=; i<; i++)
if(!prime[i])
for(int j=i*i; j<; j+=i)
prime[j] = ; int Case = ;
while(scanf("%d",&n)!=EOF)
{
if(kase>) printf("\n");
memset(vis,false,sizeof(vis));
memset(ans,,sizeof(ans));
printf("Case %d:\n",Case++);
ans[] = ;
vis[] = true;
dfs();
kase++;
} return ;
}
题目链接：https://vjudge.net/contest/147561#problem/E
题意：困难的串，有相邻的重复子串的就不是困难的串。输入n ,l，l 为可供你多少个字符选择，找出困难串里面的字典序第 n 的串。
分析：
枚举当前位置的字符，但是你要查是否有连续子串，然后状态转移到下一个位置，至于字典序的问题，只要每次从A开始就行了，当有了n 个，就输出。
#include <bits/stdc++.h> using namespace std; int n,l;
int cnt;
int s[]; int dfs(int cur)
{
if(cnt++==n)
{
for(int i=; i<cur; i++)
{
if(i%==&&i>) puts("");
else if(i%==&&i>) printf(" ");
printf("%c",'A'+s[i]);
}
printf("\n%d\n",cur);
return ;
} for(int i=; i<l; i++)
{
s[cur] = i;
int ok = ;
for(int j=; j*<=cur+; j++)
{
int equal = ;
for(int k=; k<j; k++)
{
if(s[cur-k]!=s[cur-k-j])
{
equal = ;
break;
}
}
if(equal) {
ok = ;
break;
}
}
if(ok) if(!dfs(cur+)) return ;
}
return ;
} int main()
{
while(scanf("%d%d",&n,&l),n)
{
cnt = ;
dfs();
} return ;
}