Hao Yin Jian 寒假第一周

题目链接: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 ;
}
上一篇:SQL Server 2008 报表服务入门【转】


下一篇:异常SRVE0199E