A题
题意：让你找出唯一的一个四位数，满足对话时的要求。
思路：因为是4位数，可以直接从1000-9999遍历一遍，判断是否有唯一的数能满足所有条件，如果不是唯一的或者没有满足条件的数就输出Not sure。特别丑的代码附上。。。
#include<stdio.h>
int a[],b[],c[];
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==)break;
int i,flag=,ans,j,k;
for(i=;i<=n;i++)
scanf("%d%d%d",a+i,b+i,c+i);
for(i=;i<=;i++)
{
int a1,a2,a3,a4,i1,i2,i3,i4,bx=,cx=,flg=;///ax代表a[i]的第x个数，ix代表i的第x个数
for(j=;j<=n;j++)
{
bx=;cx=;
a1=a[j]/;
a2=(a[j]/)%;
a3=(a[j]/)%;
a4=a[j]%;
i1=i/;
i2=(i/)%;
i3=(i/)%;
i4=i%;
if(a1==i1)///先判断位置正确的
cx++;
if(a2==i2)
cx++;
if(a3==i3)
cx++;
if(a4==i4)
cx++;
if(a1==i1)///这里如果判和i中的一个数相等，就让i中的那个数为11，就不会再和下个数匹配了，防止出现当类似ai=1111，i=1234的时候a1,a2,a3,a4都和i1匹配成功的情况。
{
bx++;
i1=;
}
else if(a1==i2)
{
bx++;
i2=;
}
else if(a1==i3)
{
bx++;
i3=;
}
else if(a1==i4)
{
bx++;
i4=;
}
if(a2==i1)
{
bx++;
i1=;
}
else if(a2==i2)
{
bx++;
i2=;
}
else if(a2==i3)
{
bx++;
i3=;
}
else if(a2==i4)
{
bx++;
i4=;
}
if(a3==i1)
{
bx++;
i1=;
}
else if(a3==i2)
{
bx++;
i2=;
}
else if(a3==i3)
{
bx++;
i3=;
}
else if(a3==i4)
{
bx++;
i4=;
}
if(a4==i1)
{
bx++;
i1=;
}
else if(a4==i2)
{
bx++;
i2=;
}
else if(a4==i3)
{
bx++;
i3=;
}
else if(a4==i4)
{
bx++;
i4=;
}
if(bx!=b[j]||cx!=c[j])
{
flg=;
break;
}
}
if(flg)
{ ans=i;
flag++;
}
}
if(flag==)
printf("%d\n",ans);
else
printf("Not sure\n");
}
}
AC代码
B题
题意：打老鼠，在某一个时刻把所有的老鼠打下去。
思路：对于一个[l,r]区间，一定是从最左或者最右开始打，因为如果你从中间开始打，最后还是要经过最左最右，这时候中间位置会经过两次，所以中间开始一定不是最优方案。这样的话问题就变成了一个区间dp，dp[l][r][1]代表从右边开始打完[l,r]区间的老鼠，dp[l][r][0]代表从左边开始打完[l,r]区间的老鼠，这样的话有状态转移方程：
dp[l][r][0]=min(dp[l+1][r][0]+d[l+1]-d[l],dp[l-1][r][1]+d[r]-d[l])
dp[l][r][1]=min(dp[l][r-1][0]+d[r]-d[l],dp[l][r-1][1]+d[r]-d[r-1])
然后开个数组记忆走过的路线
#include<stdio.h>
#include<string.h>
const int INF=;///INF判断能不能在老鼠爬起来之前打完
int t[],d[];
int dp[][][];///dp[i][j][0]代表打完[i,j]区间的老鼠并且停留在左端点用的时间
///dp[i][j][1]代表打完[i,j]区间的老鼠并且停留在右端点用的时间
int route[][][];///记录路线的数组为0代表往右走遇见第一个冒出头的老鼠。
int main() ///为1代表往左走遇见第一个冒出头的老鼠。
{
int n;
while(~scanf("%d",&n))
{
int i,j,l,r,temp;
for(i=;i<=n;i++)
scanf("%d",t+i);
for(i=;i<=n;i++)
scanf("%d",d+i);
memset(dp,,sizeof(dp));
for(l=;l<=n;l++)
{
for(i=;i<=n-l+;i++)
{
j=i+l-;
if(dp[i+][j][]+d[i+]-d[i]<=dp[i+][j][]+d[j]-d[i])
{
dp[i][j][]=dp[i+][j][]+d[i+]-d[i];
route[i][j][]=;
}
else
{
dp[i][j][]=dp[i+][j][]+d[j]-d[i];
route[i][j][]=;
}
if(t[i]<=dp[i][j][])
dp[i][j][]=INF;
if(dp[i][j-][]+d[j]-d[i]<=dp[i][j-][]+d[j]-d[j-])
{
dp[i][j][]=dp[i][j-][]+d[j]-d[i];
route[i][j][]=;
}
else
{
dp[i][j][]=dp[i][j-][]+d[j]-d[j-];
route[i][j][]=;
}
if(t[j]<=dp[i][j][])
dp[i][j][]=INF;
}
}
if(dp[][n][]<INF)///判断起始位置
{
temp=route[][n][];
printf("");
l=,r=n;
}
else if(dp[][n][]<INF)
{
temp=route[][n][];
printf("%d",n);
l=,r=n-;
}
else
{
printf("Mission Impossible\n");
continue;
}
while(l<=r)///路线查找
{
if(temp==)
{
temp=route[l][r][];
printf(" %d",l++);
}
else
{
temp=route[l][r][];
printf(" %d",r--);
}
}
printf("\n");
}
}
AC代码
C题
题意：一堆单词，找到第一个为B开头的单词，用其他单词和它连接，使得最后一个连接的单词末尾为M。
思路：直接暴力深搜就好了
#include<stdio.h>
#include<string.h>
char a[][];///储存字符串
int dfs(int fi,int count)
{
int i,flag=;
char temp=a[fi][];
a[fi][]='';///首字母标记为0，就可以避免单词被重复使用
if(a[fi][strlen(a[fi])-]=='m')
return ;
for(i=;i<count;i++)
if(a[fi][strlen(a[fi])-]==a[i][])
{
if(dfs(i,count))
return ;
}
a[fi][]=temp;///回溯还原首字母
return ;
}
int main()
{
int n=,i,j,k;
while(~scanf("%s",a[++n]))
{
if(a[n][]=='')
{
int flag=;
for(i=;i<n;i++)
{
if(a[i][]=='b')
{
if(dfs(i,n))
{
flag=;
break;
}
}
}
if(flag)
printf("Yes.\n");
else printf("No.\n");
n=;///字符串重新输入
}
}
}
AC代码
D题
题意：第一天给一颗糖，第二、三天给两颗糖，第四、五、六天给三颗糖......以此类推
思路：模拟这个给糖的方法来写
第一颗糖 一
第二颗糖 二 三
第三颗糖 四 五 六
第四颗糖 七 八 九 十
以此类推
从这上面我们可以发现当第n天为1 3 6 10的时候，第二天糖都会多给一个，很容易看出1 3 6 10是一个二阶等差数列，通项公式为an=n*(n+1)/2，由此就可以写出下面的代码。
#include<stdio.h>
int main()
{
int n;
while(~scanf("%d",&n))
{
int ans=,i,r=;
if(n==)break;
for(i=;i<=n;i++)
{
if(i>r*(r+)/)///判断给的糖数是否要增加
r++;
ans+=r;
}
printf("%d %d\n",n,ans);
}
}
AC代码
E题
题意：给你一个1-500000内数字，让你把它所有的因数加起来，求出加起来之后的数。
思路：这个题的询问次数很多，一个一个算的话很容易超时，所有我们这里可以进行一个因子和打表的预处理。
#include<stdio.h>
int a[];
int main()
{
int i,j;
for(i=;i<=;i++)
{
for(j=i*;j<=;j+=i)
a[j]+=i;
}
int t;
scanf("%d",&t);
while(t--)
{
int c;
scanf("%d",&c);
printf("%d\n",a[c]);
}
}
AC代码