只能把补了的题目放这儿了，先留个坑，怕忘记。
Problem G URAL 1806 Mobile Telegraphs
题意是:给定n个电话号码，每个号码是一个长度为10的仅含'0'~'9'的字符串，每两个电话号码a，b之间能通信，需要满足一下条件之一：
1.b能通过改变a中某一个数字的值获得；
2.b能通过交换a中两个数字获得。
n个电话号码不相同，且相互通信的费用由之间的最长公共前缀长度决定。
分析：
对于一个电话号码逐位判断改变某一位的值得到哪些号码，或者交换某两个数字的得到哪些号码，由此判断该号码能与哪些号码通信，通信费用也可以很快求出。
然后就是dijkstra 或者spfa了。注意map存储LL判断的时候，前导0 可能会被忽略。
另外在spfa或dij里面进行边的转移，而不事先把边求出来可以加速过程。
#include <bits/stdc++.h>
#define esp 1e-6
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define pb push_back
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(x) (x&(-x))
#define mp(a, b) make_pair((a), (b))
#define bit(k) (1<<(k))
#define iin freopen("pow.in", "r", stdin);
#define oout freopen("pow.out", "w", stdout);
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout);
#define bug puts("********))))))");
#define Inout iin oout
#define inout in out #define SET(a, v) memset(a, (v), sizeof(a))
#define SORT(a) sort((a).begin(), (a).end())
#define REV(a) reverse((a).begin(), (a).end())
#define READ(a, n) {REP(i, n) cin>>(a)[i];}
#define REP(i, n) for(int i = 0; i < (n); i++)
#define VREP(i, n, base) for(int i = (n); i >= (base); i--)
#define Rep(i, base, n) for(int i = (base); i < (n); i++)
#define REPS(s, i) for(int i = 0; (s)[i]; i++)
#define pf(x) ((x)*(x))
#define mod(n) ((n))
#define Log(a, b) (log((double)b)/log((double)a))
#define Srand() srand((int)time(0))
#define random(number) (rand()%number)
#define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<unsigned short> VI;
typedef pair<unsigned short,unsigned short> PII;
typedef vector<PII> VII;
typedef vector<PII, int> VIII;
typedef VI:: iterator IT;
typedef map<string, int> Mps;
typedef map<LL, int> Mpi;
typedef map<int, PII> Mpii;
typedef map<PII, int> Mpiii;
Mpi mps;
const int maxn = ;
const int maxm = + ; unsigned short co[maxn];
unsigned short pa[maxm];
LL a[]; LL s[maxm];
int n;
int d[maxm];
bool inq[maxm]; VII g[maxm];
struct HeapNode
{
int d;
unsigned short u;
HeapNode() {}
HeapNode(int d, unsigned short u):d(d), u(u) {}
bool operator < (const HeapNode &rhs)const
{
return d > rhs.d;
}
};
unsigned short cmp1(LL x, LL y)
{
char ss[][];
sprintf(ss[], "%010I64d", x);
sprintf(ss[] ,"%010I64d", y);
int i = ;
for(i = ; i <= ; i++)
{
if(ss[][i] != ss[][i])
break;
}
return co[i];
}
void bfs(int src)
{
priority_queue<HeapNode> q;
q.push(HeapNode(, src));
d[src] = ;
inq[src] = false;
while(!q.empty())
{
HeapNode u = q.top();
int x = u.u;
int dd = u.d;
q.pop();
if(inq[x])
continue;
inq[x] = true;
char ss[];
sprintf(ss+, "%010I64d", s[x]);
Rep(j, , )
{
int c = ss[-j]-'';
REP(k, )
{
if(k == c)
continue;
LL tmp = s[x] + (k-c)*a[j-];
if(mps.count(tmp))
{
int y = mps[tmp];
int l = cmp1(s[x], s[y]);
if(d[y] > dd + l)
{
pa[y] = x;
d[y] = dd + l;
q.push(HeapNode(d[y], y));
}
}
}
}
Rep(j, , ) for(int k = j+; k <= ; k++)
{
int c1 = ss[-j]-'';
int c2 = ss[-k]-'';
if(c1 == c2)
continue;
LL tmp = s[x] + (c2-c1)*a[j-] + (c1-c2)*a[k-];
if(mps.count(tmp))
{
int y = mps[tmp];
int l = cmp1(s[x], s[y]);
if(d[y] >dd + l)
{
pa[y] = x;
d[y] = dd + l;
q.push(HeapNode(d[y], y));
}
}
}
}
}
VI ans; void print(int s)
{
ans.pb(s);
while()
{
s = pa[s];
ans.pb(s);
if(s == )
break;
}
printf("%d\n", ans.size());
VREP(i, ans.size()-, )
{
printf("%hu%c", ans[i], i == ? '\n' : ' ');
}
}
int main()
{ a[] = ;
Rep(i, , )
a[i] = a[i-]*;
scanf("%d", &n);
REP(i, )
scanf("%hu", co+i);
Rep(i, , n+)
{
scanf("%I64d", s+i);
mps[s[i]] = i;
d[i] = inf;
inq[i] = false;
} bfs();
if(d[n] >= inf)
puts("-1");
else
{
printf("%d\n", d[n]);
print(n);
}
return ;
}
Problem D URAL 1803 The Czechs' Rifles
题意：实际上就是要你求出前n个斐波那契数的k进制表示下，各个位数之和，然后再排序输出。
分析：首先可以证明的是，fn <= 2*fn-1,所以fn <= 2^n,所以可以这样求每个斐波那契数的k进制表示下各数位之和，将其表示成cnt进制的数，cnt为不超过n的k的最大次幂，
然后预处理出来小于cnt的各个数的k进制下数位之和。接下来就是通过前两项酸算出当前的斐波那契数，然后并将其k进制下各位加起来。这个过程其实就是模拟的一个大数加法的过程。
#include <bits/stdc++.h>
#define in freopen("solve_in.txt", "r", stdin);
using namespace std;
const int maxn = + ;
struct Node
{
int id, su;
bool operator < (const Node &rhs)const
{
if(su == rhs.su)
return id < rhs.id;
return su < rhs.su;
}
} ans[maxn];
int sum[maxn];
int dp[][maxn]; int n, k;
int main()
{ scanf("%d%d", &k, &n);
int cnt = ;
while(cnt * k < maxn)
cnt *= k;
for(int i = ; i < maxn; i++)
{
int tmp = i;
while(tmp)
{
sum[i] += tmp%k;
tmp /= k;
}
}
dp[][] = dp[][] = ;
ans[].id = , ans[].id = ;
ans[].su = ans[].su = ;
int st = ;
for(int i = ; i <= n; i++)
{
int delta = ;
int now = i&;
int pre = now^;
ans[i].id = i;
for(int k = ; k < st; k++)
{
dp[now][k] += dp[pre][k] + delta;
if(dp[now][k] >= cnt)
{
delta = dp[now][k]/cnt;
dp[now][k] %= cnt;
}
else delta = ;
ans[i].su += sum[dp[now][k]];
}
if(delta)
dp[now][st++] = delta;
ans[i].su += sum[delta];
}
std::sort(ans+, ans++n);
for(int i = ; i <= n; i++)
printf("%d%c", ans[i].id, i == n ? '\n' : ' ');
return ;
}