http://hihocoder.com/problemset/problem/
#1870 : Jin Yong’s Wukong Ranking List
我是每加1个点就dfs判断1次。
正解是拓扑排序。。。
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=; bool vis[maxn];
char str[maxn][maxn],a[maxn],b[maxn],result1[maxn],result2[maxn];
vector<int>e[maxn];
int r; void dfs(int d)
{
vector<int>::iterator j;
vis[d]=;
for (j=e[d].begin();j!=e[d].end();j++)
if (!vis[*j])
dfs(*j);
else
{
r=;
return;
}
} int main()
{
int n,i,j,k,g;
while (~scanf("%d",&n))
{
for (i=;i<=*n;i++)
e[i].clear();
g=;
r=;
for (i=;i<=n;i++)
{
scanf("%s%s",a,b);
for (j=;j<=g;j++)
if (strcmp(str[j],a)==)
break;
if (j==g+)
{
g++;
strcpy(str[g],a);
} for (k=;k<=g;k++)
if (strcmp(str[k],b)==)
break;
if (k==g+)
{
g++;
strcpy(str[g],b);
} e[j].push_back(k); memset(vis,,sizeof(vis));
if (r==)
{
dfs(k);
if (r==)
{
strcpy(result1,a);
strcpy(result2,b);
}
}
} if (r==)
printf("0\n");
else
printf("%s %s\n",result1,result2);
}
return ;
}
#1871 : Heshen's Account Book
把所有内容放入字符串里，再判断。
挺多细节要考虑的，代码下方有自己编的若干数据。
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=2e5;
const int maxsinlen=;
const int maxlen=1e3+;
const int maxtotallen=3e5;
const int maxline=2e2+; char num[maxn][maxsinlen];
char str[maxtotallen],s[maxlen],c;
int gx[maxline]; int main()
{
int g=,len,line=,ind=,pos=,i,j,k;
bool vis=;
strcpy(str,"");
while (gets(s))
{
strcat(str,s);
strcat(str,"\n");
}
len=strlen(str); for (i=;i<len;i++)
{
if (str[i]=='\n')
{
line++;
if (i== || str[i-]<'' || str[i-]>'' || str[i+]<'' || str[i+]>'')
{
if (vis && i>ind)
{
// strncpy(num[g++],str+ind,i-ind);
///delete ' ','\n'
k=;
for (j=ind;j<i;j++)
if (str[j]>='' && str[j]<='')
num[g][k++]=str[j];
num[g][k]=;
if (!(k> && num[g][]==''))
{
g++;
gx[pos]++;
}
}
vis=;
ind=i+;
pos=line;
}
}
else if (str[i]==' ')
{
if (vis && i>ind)
{
// strncpy(num[g++],str+ind,i-ind);
///delete ' ','\n'
k=;
for (j=ind;j<i;j++)
if (str[j]>='' && str[j]<='')
num[g][k++]=str[j];
num[g][k]=;
if (!(k> && num[g][]==''))
{
g++;
gx[pos]++;
}
}
vis=;
ind=i+;
pos=line;
}
else
{
if (str[i]<'' || str[i]>'')
vis=;
}
} if (g>=)
printf("%s",num[]);
for (i=;i<g;i++)
printf(" %s",num[i]);
printf("\n"); for (i=;i<line;i++)
printf("%d\n",gx[i]);
return ;
}
/**
12
34
56
78
900 --- 003
004
005
1 006 a ---
''' 23 123
123 123 adssa q3qe
qw 1
qw123
12 ''' --- 1234
123 --- 1234
12 34 --- 1 2 3 as 4 --- 12
3
4
5a --- 00 --- 0 --- 0
12 --- 0
12asdb --- '''
0
a
0 0 0 0 12 0 01 100 10 01 0
0 ''' **/
#1873 : Frog and Portal
重现赛时，看错题了，难受。
告诫自己：比赛时，一定要认真读题，认真分析数据！
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAr0AAAFaCAYAAAATjeV/AAAQ60lEQVR4nO3diZIixxmFUbVi3v+V225LWAxiKahc/rx5ToQiJHumuyBr+SpJ4Ov7v/4AAIBgf87eAAAA6E30AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEE/0AgAQT/QCABBP9AIAEO/X7A3o5evr6////v39PXFLAACYzUwvAADxRC8AAPFELwAA8UQvAADxRC8AAPFELwAA8UQvAADxRC8AAPEio/f6iykAACAyegEA4JroBQAgXlz0WtoAAMCtuOgFAIBbUdFrlhcAgHuiohcAAO6Jj97v7+/ZmwAAwGTx0QsAAL9mb0AL1vICK7k+Z3k1CmCM5aP3TPA++rsuQgAAWZaP3lcuYXsbss9i+dHf+eT3XghpAIB5hkXv0RnZEXHYajnEo5coLbfgrN1umnZ7vACMNyR6e0Rmy5/xKFh//v2di6/YBV5xngCYo3v0nj3Bf/L33wnVVjNKLmQAAHUNX9N7LzLPzK4e+fkt/uxZZx8Xe/nZV3a9kdrpONnpsd6ypAUYrWv09jip9V472yI2rO8F7nE+yOfj6KCubtHb6uT+6KTh4gEAwFFRH1n26q76SCi3nOUFeMS54h+ei7VYmsKqyn0N8acHT4uDTvACwGd+rqFehaWyEjO978Zii7vMI19WUfVNcQAww6OobfmGdOilW/RedvjWd32jPvO3xVIJgAvnDFb3bB++fRO48KWiocsbVnnpw4EKAM/9XCuvr5dHXkFlLat021FT1vR++gT2fuJvD+Db3/1o8EUyrSWdZPDGn10kH7dH9+HdwvdZG6zuduY+Qfc1vY+WOcz+il9fL8wqBFIW4wmZWi7pmL08JLV7hs30vvomttv//fafWY5+zFnqDgLA+5Jvbl49tuTHPsKlJ2Z2xe2ylZQxHbq8odWTNvPJN0MMvMN5YA/G+bHkiaEePXL5mbNDMyl2L4Z/ZNnZr/kdOQDvrsN79c5WANjV7Jfse+kZvrTVPHpbfO/4iME+E96pd6wAnCdY2r2fB1oq941sVZ0JeAc48MO5gN3Y56mkxDeytXBkhvnTpRXPDloHNMDe0l/9O/v4zi5rhFa6Ru9lJ78Ow9k7/tlInb39ANSVPhGS/vjINmSmt3cojgpRHzAPwDUTIa95jqii+Zred9awrhyNK287AIwgeKmk2xvZen949eiPLnPgAvCMyZDfuW5STdflDb1PALNOME5sAPAe105m85FlAPCBHWcyjz5m74GhItH7ggMX+toxHGBllvyxqpjP6QWopsU3VMJsjz5n92j42vepwkzvGxy40JdjjFWl77u+XZQEohegE5FAmnf2aaFMNZY3PGHNEjPY77K46JPGPs2qRC8U5uIC9bgxhTVZ3nCQ+GAEF1NYj+sDrMFMLzCVYABgBDO9D5hxYzYxSKqk86vjFNZhpveOpBMya3EBJZ3zKzCL6D1AiAD0seL5dcVtBixveMnJDaAP51dgJNELwBCWNgAziV4AhjPLC4wmegEAiCd6b3j5DaA951ZgNtELAEA80XvldibCmjOA9pxbgRl8Ti8A3QldYDYzvQ84QQMA5DDTe0XoAgBkMtMLAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQLxfszcA+NzX19dv//39/T1pSwCgNtELi7sO3Z8IFr4A8G+WN8DCbgP3579vZ38BANELAMAGRC+Eucz2Xv5hL8Yc4D5reiGQdb6whstNimMU+hO9sAEX1n1cZvqN9TrurcU3ftCe6IVwl4unl72hnsvxeRu5blygPWt6IYSo5cKneKzPGEJ7ZnohgFkhyHAbuo5taEf0wsLMBGUzvvt4tO7ePgDtiF5YiDe77OPsDJ9YWofZXBhD9MIiXBj34JM29nB9U/JsrH0aB7QjemEBLWb9XDTrM057MM4wh+iFwsz67cE484zZXmhD9EJBImgfYmYPR5czAP2IXiiq1YVRVNXU88bGm9hqcQxCDaIXiml5gXSxrWfULL5xr8ExCHWIXiiix+yci20tIwJIZNVhLKAW0QsFuDhCFsc01CN6AQboHUHe/FiH4IWaRC9AZz0jSOzWInihLtELk3mnfbbewSuw9mCc4TzRCxOJFt7l816PG3V8GRNYg+iFSQQv77CMoTbjAvWJXoDi3CABnPfn7A2AHYmY2n7Gp8Va67PjfNmO3faVlda57zg+sCrRy5ZWuqgyXoWIucRUhW1ZkRgFboleGMzFeA/GGaAW0QtQjGBeg3GCtYheIM7qy1eEFEB7ohegMTOA+YwxrMdHllGSCwqfsu/Ud2Qm/tGfMbbAp0QvQEOi+7Vnz48v4QB6sbwBiDE7OGf//hTVn0PjDGsSvTCQi+U6fsZp9TfEAfAPyxuAJRwN0Os/5wZjLSvcFK6wjcB9ohcGcbE859U6UM8ttNHyFQ7HJZWIXrYjkADua/1GQm9MpBLRCwAHJN4w387qtn58l58nfqlA9DLUOy+bHfmzTqAA7xsdodfx67zNLKKXoY6e7JwYYS8+KWOc2bOuzu/M4iPLKKvHRdDJFmr6OS5bHputj/O0c8esx3IZZzc5zCB6KSnp4gIAzCd6gaWlzcAB0IfoZRviiJ7sXwC1iV5gaT1DU8TyczPjhqY963qZQfSyBRct4FPOHZBB9AIAEE/0UpbZFWCm1FeILC1gV6IXAIB4ohcGSZwx4h/GF6A20Uu81JcoAYDjRC/RBC8A8EP0Ek3wAp9If6PXO29mS38u2IfoBQAgnugFgA0dme21RIwkv2ZvAABUs3voXWJ49+eBLGZ6AYB/6Rm8ZpCZQfQCABBP9AIAEE/0AgD/13vpgaUNzOKNbHDC0c+vdIIHenh1Dnp17rl8goNzFDsQvfCGTz+k/fbvucBAPWcDcoZX23T9mB792evwFcAkE73wQo9vIzpyIaIuM/wZ3j22V7x5vd7Ge4/38v+/8w1tsKqv7xWOWpjgyAXg6OHT8mcxx9kgML419Aq7Fcf33qyu9bwkE71w49lFsdXhMuJ3cJ5AytHqxnPFJRDPXEfoiFegRC8ziV7426OLWe9DZNbv5bFWYZMWSKvqdYylHLv3YrdHnApeZhO98EeNi9ez9XaM0XMG3uz+HCOOK8fuMaKX2UQv26t0waoQ37sa9dwb4zFmHNeVziWVXJ4XzwWziV62VfkCVXnbEgmkLDOfW+P6O7O7VCJ62dIKF6YVtjHB7I+hMs5tVXg+K2wD8G++hhj+qHlB+tmmex8nRDuzg/fR7zTObdw7hmb9XmMK84letlMhdJiv0n5gH2xDWALPiF62Uil0jjJj1F7F/cA4n2NMgVdEL9uoeFE8ysWzncr7gXH+jDEFjhC9bKnSRfEoF8/zKsfRhXE+Z4UxBeYQvWxhxNdrjrDytldT+bmsvG3VrHhTsOI2QwLRS7zkC0zyY2tt5edq5W0fqfLNQuVtg12IXraScOFJeAyzrfAcrrCNACsRvUTbYYZsh8d4VsJzlPAYWltt2dL1NhpPGE/0so0VLopHJT2W0VZ67lbaVoDqRC/AIswOAnxO9BJrtZc+3+Wl0mNW3w9W3GYec9zCPKIXgOWsfjMDjCd6AQCIJ3qBWCmzgV4SBzhP9BIpJXZeEUMAcIzoBQAgnugFACCe6AUAIJ7oBQAgnugFYDnJb1AF+hC9ACxtpU8u2eWTZaAi0QsAQDzRCwBAPNFLpF2+tMFLpc+l7AfG+b7Vxtc4wlyiFwCAeKIXgAiVZ3srbxvsQvQC0VZ7CfzWits80orLBFbcZkggeom1euy8Yn3gfozzaxWP9YrbBDsSvcBWVgqQlbZ1ptubgUrP2+22uHGBeUQv26h0ITwr6bGMkBAaCY+hp4rhK3ihFtFLtB0uMjs8xtYqBNErK2xjNY4F4BnRy1YSQiLhMcywchCtvO0z/RwrM46Xe7/XGMJ8opd4yReb5MfWW+Wbh8rbVt29Y2Lk83nvdzlOoQbRy3ZWDoqVt72Cius+b5khPG9W+ApeqO3r2xHJJlaPidW3v5Kqz2XV7VrVo9Bt/byO+j3AOaKXrawaFatud2XVntNq25OkV5SKXViL5Q1sZYWXt19xQe1j5r6w4n64kkfHzOUNZ+88/6/+juMT6jLTy3ZWW3dnBrCfCvtChW3YSa8bDGMG9YletrRCaKywjSlmPNfGd76zAWy8YC2il21Vjo7K25bKm572djSAjROsS/SyvWrLBwTvPM/Cp9ebnlr8bABeE73wR43QrLAN/OXVrN/RcWn1cwA4T/TC32a97Ozl7rq86Qkgh+iFGyNehvZS91paxa+xBZhH9MIDrV+aPhJODsc1eNMTwHpEL7ww4osDHIYA0Nev2RsA1V0HacsAFroAMI7ohTd8+jXGAhcA5hK9cIKYBYA1/Dl7AwAAoDfRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwBAPNELAEA80QsAQDzRCwAM8fX19b9/YIZfszcAYHVHLuLf398DtgRquT02HAfMJHoBTvi5qB+5kB/9c8x37ybG2L3PPk81ohfgQy7qme6NqbGG9VnTC/Cmy7pEEbSPn7G2FvU4xwcVmekFeJOLOTwmeKnKTC8A0ITgpTLRCwBAPNELAEA80QsAQDxvZAPo6PKOf+sc9/Lskx7sCzCH6AXoTOTs4Tp0dxxzb2KjOtEL0IkIyPLqs3p3Huvbfd1Xc1OR6AXoQPDmMq6/uxe8r54jX/TBDKIXOhM/e7GGlx29u7TjMmvuOGEk0QvQgNhlR2f2++vlIo4bRhC9AB/w8iy7azFTe/n7Zn0ZQfRCZ17Gy3RvPH/G2VizA/s5K/LlFDDAq3d9k+FnnC9jbbwBahG9AI2JX5L1mOU1McAIljcAdHK9XvH6vwEYz0wvQGfXM78AzGGmF2CQZ+FrFhigL9ELMNCjuPVueIC+LG+AAQQNr1j+ANCX6AUADnEDz8pELwAcYCYe1iZ6AV4QO+trNYZmOWFdohfgBettM5wZQy/r9+X4YgTRC1CAqOrLt+S10fMG0P5Pbz6yDOCA64t964uz4B3n9lvy3v17/HMstHpO7P+MInqhMyf0HD1muewfc3jOz+l5Ewi9WN4A8AYvkcNfxC6rMdML8KZPXyJ/9rNgRZ8udbg+dhwDjCJ6AT7kYg3vs6SHWUQvAPAxH+nHKkQvAHCKmVtW4I1sAADEE70AAMQTvQAAxBO9AADEE70AAMQTvQAAxBO90JmP8gGA+UQvAADxRC8AAPFELwAA8UQvAADxRC8AAPFELwAA8UQvAADxRC8AAPFELwAA8UQvAADxRC8AAPFELwAA8UQvAADxRC8AAPFELwAA8UQvAADxRC8AAPFELwAA8f4DstuWDjIZmlYAAAAASUVORK5CYII=" alt="" />
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
const int maxn=1e3+; struct node
{
int x,y;
}f[]; int shu[],w; void cal(ll n)
{
if (n==)
w=;
else
{
cal(n>>);
shu[++w]=n & ;
}
} int main()
{
ll n;
int g,i,j,k;
while (~scanf("%lld",&n))
{
w=;
cal(n); g=;
j=;
k=; for (i=;i<=w;i++)
{
///(k+1)->(k+2)
f[++g]={k+,k+};
if (shu[i])
{
f[++g]={j,k+};
j+=;
}
k+=;
}
f[++g]={k,};
f[++g]={j,};
f[++g]={j+,j+};
if (n==)
f[++g]={,}; printf("%d\n",g);
for (i=;i<=g;i++)
printf("%d %d\n",f[i].x,f[i].y);
}
return ;
}
/*
0
1
2
3
4 4294967296
4294967295
4294967294 */
#1878 : Palindromes
找规律。
Java TLE了，难受！
关于字符串的处理，以后别用Java写。。。
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1e6+; int shu[maxn],ori[maxn];
char str[maxn]; int main()
{
int t,len,i;
scanf("%d",&t);
while (t--)
{
scanf("%s",str);
len=strlen(str);
for (i=;i<=len;i++)
shu[i]=str[len-i]-;
if (str[]>'')
{
///odd
for (i=;i<=len-;i++)
ori[i]=;
ori[len]=; for (i=;i<=len;i++)
{
shu[i]-=ori[i];
if (shu[i]<)
{
shu[i]+=;
shu[i+]--;
}
} printf("%c",shu[len]++);
for (i=len-;i>=;i--)
printf("%c",shu[i]+);
if (len>)
{
for (i=;i<=len-;i++)
printf("%c",shu[i]+);
printf("%c",shu[len]++);
}
printf("\n");
}
else if (len==)
printf("0\n");
else if (str[]=='')
{
///odd
for (i=;i<=len-;i++)
ori[i]=;
ori[len-]=; for (i=;i<=len;i++)
{
shu[i]-=ori[i];
if (shu[i]<)
{
shu[i]+=;
shu[i+]--;
}
} printf("%c",shu[len-]++);
for (i=len-;i>=;i--)
printf("%c",shu[i]+);
if (len->)
{
for (i=;i<=len-;i++)
printf("%c",shu[i]+);
printf("%c",shu[len-]++);
}
printf("\n");
}
else
{
///even
for (i=;i<=len-;i++)
ori[i]=;
ori[len-]=;
ori[len]=; for (i=;i<=len;i++)
{
shu[i]-=ori[i];
if (shu[i]<)
{
shu[i]+=;
shu[i+]--;
}
} printf("%c",shu[len-]++);
for (i=len-;i>=;i--)
printf("%c",shu[i]+);
for (i=;i<=len-;i++)
printf("%c",shu[i]+);
printf("%c",shu[len-]++);
printf("\n");
}
}
return ;
}
#1877 : Approximate Matching
得到所有与串S相似(相等)的串，组成一颗树，AC自动机，预处理每个节点遇到'0','1'到达的节点。
统计每个点在某一个位置出现的次数，每次每个点遇到'0','1'，到达新的节点。
当到达叶子节点(某一个串的终止位置)时，总结果加上 该点的出现次数*2^k(k为还没确定的位置数目)，同时，该节点的出现次数设置为0(以后再不出现)。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define ll long long
4 #define minv 1e-6
5 #define inf 1e9
6 #define pi 3.1415926536
7 #define nl 2.7182818284
8 const ll mod=1e9+7;//998244353
9 const int maxn=1e5+10;
10
11 ///at most 40 strings, each string contain 40 characters
12
13 struct node
14 {
15 int c,en;
16 ll v[2];
17 node *pre;
18 node *next[2];
19 node *fail;
20 node *num[2];
21 };
22
23 ll er[50];
24 char str[50];
25 queue<node*> q;
26
27 int main()
28 {
29 node *tr,*pos,*be,*p,*d;
30 int n,m,x,y,t,i,j,k,c;
31 ll result;
32 er[0]=1;
33 for (i=1;i<=40;i++)
34 er[i]=er[i-1]<<1;
35
36 scanf("%d",&t);
37 while (t--)
38 {
39 scanf("%d%d",&n,&m);
40 scanf("%s",str);
41 if (n>m)
42 {
43 printf("0\n");
44 continue;
45 }
46 tr=(node*) malloc (sizeof(node));
47 for (i=0;i<2;i++)
48 tr->next[i]=NULL;
49 tr->en=0,tr->v[0]=0,tr->v[1]=0;
50
51 for (i=0;i<=n;i++)
52 {
53 if (i!=n)
54 str[i]=(str[i]=='0')?'1':'0';
55
56 pos=tr;
57 for (j=0;j<n;j++)
58 {
59 c=str[j]-48;
60 if (pos->next[c])
61 pos=pos->next[c];
62 else
63 {
64 p=(node*) malloc (sizeof(node));
65 for (k=0;k<2;k++)
66 p->next[k]=NULL;
67 p->en=0,p->v[0]=0,p->v[1]=0;
68 p->c=c;
69
70 pos->next[c]=p;
71 p->pre=pos;
72 pos=p;
73 }
74 }
75 pos->en=1;
76
77 if (i!=n)
78 str[i]=(str[i]=='0')?'1':'0';
79 }
80
81 be=(node*) malloc (sizeof(node));
82 for (i=0;i<2;i++)
83 be->next[i]=tr;
84 tr->pre=be;
85 tr->num[0]=tr,tr->num[1]=tr;///???
86
87 ///长度相等，不用不停fail判断是否存在拥有结尾标志的点
88 q.push(tr);
89 while (!q.empty())
90 {
91 d=q.front();
92 q.pop();
93 if (d==tr)
94 d->fail=be;
95 else
96 {
97 pos=d->pre->fail;
98 c=d->c;
99 while (pos->next[c]==NULL)
100 pos=pos->fail;
101 d->fail=pos->next[c];
102
103 for (j=0;j<2;j++)
104 if (d->fail->next[j])
105 d->num[j]=d->fail->next[j];
106 else
107 d->num[j]=d->fail->num[j];
108 }
109 for (j=0;j<2;j++)
110 if (d->next[j])
111 q.push(d->next[j]);
112 }
113
114 result=0;
115 x=0,y=1;
116 tr->v[0]=1;
117 for (i=1;i<=m;i++)
118 {
119 q.push(tr);
120 while (!q.empty())
121 {
122 d=q.front();
123 for (j=0;j<2;j++)
124 if (d->next[j])
125 d->next[j]->v[y]+=d->v[x];
126 else
127 d->num[j]->v[y]+=d->v[x];
128 q.pop();
129 for (j=0;j<2;j++)
130 if (d->next[j])
131 q.push(d->next[j]);
132 }
133
134 q.push(tr);
135 while (!q.empty())
136 {
137 d=q.front();
138 // printf("%d ",d->v[y]);
139 d->v[x]=0;
140 if (d->en==1)
141 {
142 result+=d->v[y]*er[m-i];
143 d->v[y]=0;
144 }
145 q.pop();
146 for (j=0;j<2;j++)
147 if (d->next[j])
148 q.push(d->next[j]);
149 }
150 // printf("\n");
151
152 x=x^1,y=y^1;
153 }
154 printf("%lld\n",result);
155 }
156 return 0;
157 }