The 37th ACM/ICPC Asia Regional Tianjin Site Online Contest - A.B.J


A
手動でテーブルを打ってマッピング関係を作成...次に8進法を10進法に変換する..
Program:
#include
#include
#include
#include
#include
#include
#include
#include
#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
",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
#include
#include
#include
#include
#include
#include
#include
#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
",p2-p1);      }      return 0; }

J
trieの木で作ったのですが...直接配列でマークしたりmapでも調和がとれているでしょう...
#include
#include
#include
#include
#include
#include
#include
#include
#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

1007のあの旅行商の问题はずっとWAです....バグが見つからない....先日やったばかりですね...16*2^15で解決できるでしょう…うっとうしい....エラーを求める..強力なデータを求める:
#include
#include
#include
#include
#include
#include
#include
#include
#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]=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