比赛链接

AC 7题，Rank 9th

题意:

有一个完全有向图,给定许多条有向边(会重复),求一条最短路径要求每条边至少经过一次

题解:

很像欧拉通路,不同的是不同块之间不联通,且每个点度数可能不符合要求(出度等于入度)

考虑引入结点0,作为转换结点,用于连接联通块和平衡度数

    Q[0].clear();
    for (int i = 1; i <= N; i++) {
      if (indeg[i] == outdeg[i]) continue;
      int cnt = abs(outdeg[i] - indeg[i]);
      if (outdeg[i] > indeg[i])
        while (cnt--) Q[0].push_back(i);
      else
        while (cnt--) Q[i].push_back(0);
    }

接着从0点开始寻找欧拉通路即可(注意处理无关结点——没有边相连)

void dfs(int u) {
  vis[u] = true;
  while (!Q[u].empty()) {
    int v = Q[u].front();
    Q[u].pop_front();
    dfs(v);
  }
  S.push(u);
}

题意:

求解$(7+4\sqrt{3})^{n}$整数部分

题解:

$(7+4\sqrt{3})^{n}=x+y\sqrt{3},(7-4\sqrt{3})^{n}=x-y\sqrt{3}$

$0<(7-4\sqrt{3})<1,0<(7-4\sqrt{3})^{n}<1 \Rightarrow x,y\sqrt{3}整数部分相差不超过过1
又x \in N^{+},[y\sqrt{3}]=x-1,[(7+4\sqrt{3})^{n}]=2x-1$

$在Z(\sqrt{3})空间上快速幂即可$

by Hardict