A
手动打表做出映射关系...然后八进制转十进制..
Program:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
ll ans,n,m,k,a[10]={0,1,2,0,3,4,5,6,0,7};
int main()
{
// freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
while (~scanf("%I64d",&n))
{
if (!n) break;
m=n; ans=0; k=1;
while (n)
{
ans+=a[n%10]*k;
n/=10;
k*=8;
}
printf("%I64d: %I64d\n",m,ans);
}
return 0;
}
B
这种题目的第一直觉就是找规律...打出前面一些sum...不难发现当k>12时..在0~k间的real number要么是k/2-1要么是k/2-2...那关键就在于寻找什么时候是-1,什么时候是-2...通过观察可以发现... 每逢平方数...-1,-2就会转变... 并且当 p^2 <= k < (p+1)^2 时..当p为奇数...0~k的real number为k/2-1...p为偶数...其为k/2-2....
能快速得到0~k间real number的个数..剩下的就简单了....
Program:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
int t,n,s[20]={0,0,0,0,0,0,1,1,2,3,4,4,5};
ll a,b,p1,p2;
ll getsum(ll x)
{
if (x<=12) return s[x];
ll m,k;
m=x/2;
k=(ll)sqrt(x);
if (k%2==0) m-=2;
else m-=1;
return m;
}
int main()
{
// freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
scanf("%d",&t);
while (t--)
{
scanf("%I64d%I64d",&a,&b);
a--;
p1=getsum(a);
p2=getsum(b);
printf("%I64d\n",p2-p1);
}
return 0;
}
J
我是用trie树做的...直接用数组标记或者用map也能很和谐吧...
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
struct node
{
int son[10],w;
}p[600005];
int ans,t,n,m,g,c[27]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
char s[5005][10],str[10];
int main()
{
// freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
scanf("%d",&t);
while (t--)
{
int i,h,k,len;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%s",s[i]);
memset(p,0,sizeof(p));
g=0;
while (m--)
{
scanf("%s",str);
len=strlen(str);
h=0;
for (i=0;i<len;i++)
{
if (!p[h].son[c[str[i]-'a']]) p[h].son[c[str[i]-'a']]=++g;
h=p[h].son[c[str[i]-'a']];
}
p[h].w++;
}
for (k=1;k<=n;k++)
{
len=strlen(s[k]);
ans=h=0;
for (i=0;i<len;i++)
{
if (!p[h].son[s[k][i]-'0']) break;
h=p[h].son[s[k][i]-'0'];
}
if (i==len) ans=p[h].w;
printf("%d\n",ans);
}
}
return 0;
}
1007的那个旅行商问题一直WA啊....找不到bug了....前几天刚做过的啊...用16*2^15就可以解决啊...好郁闷....求差错..求强力数据:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
struct node
{
ll t,c,d;
}p[17];
ll arc[105][105],n,m,money,goal,dp[40000][17];
void Floyd()
{
ll k,i,j;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (arc[i][k]!=-1 && arc[k][j]!=-1)
if (arc[i][j]==-1 || arc[i][j]>arc[i][k]+arc[k][j])
arc[i][j]=arc[i][k]+arc[k][j];
return;
}
bool EXE_DP()
{
ll i,j,ans,k,h,x,w,data;
memset(dp,-1,sizeof(dp));
p[0].t=1; p[0].c=p[0].d=0;
w=1;
dp[0][0]=money;
for (k=1;k<=goal;k++)
{
h=k;
x=1;
i=0;
while (h)
{
i++;
if (h%2)
{
w=k-x;
for (j=0;j<=n;j++)
if (dp[w][j]!=-1 && arc[p[j].t][p[i].t]!=-1)
if (dp[w][j]-arc[p[j].t][p[i].t]>=p[i].d)
{
data=dp[w][j]-arc[p[j].t][p[i].t]+p[i].c-p[i].d;
if (dp[k][i]==-1 || dp[k][i]<data) dp[k][i]=data;
}
}
x*=2;
h/=2;
}
}
for (i=0;i<=n;i++)
if (arc[p[i].t][1]!=-1 && dp[goal][i]!=-1 && dp[goal][i]>=arc[p[i].t][1])
return true;
return false;
}
int main()
{
freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
ll t,x,y,h,w;
scanf("%I64d",&t);
while (t--)
{
memset(arc,-1,sizeof(arc));
scanf("%I64d%I64d%I64d",&n,&m,&money);
while (m--)
{
scanf("%I64d%I64d%I64d",&x,&y,&w);
if (arc[y][x]==-1 || w<arc[y][x]);
arc[x][y]=arc[y][x]=w;
}
for (x=1;x<=n;x++) arc[x][x]=0;
Floyd();
scanf("%I64d",&h);
goal=1;
for (x=1;x<=h;x++)
{
scanf("%I64d%I64d%I64d",&p[x].t,&p[x].c,&p[x].d);
goal*=2;
}
n=h;
goal--;
if (EXE_DP()) printf("YES\n");
else printf("NO\n");
}
return 0;
}