第一题？最小生成树啊

　　今天的第一题就让我不懂了，题意描述的太不清楚了(当然不是因为我蒟蒻!)，反正就是，怎么看都是走地道的话怎么都最多只能携带一块派么！好吧，先看看题目。 　　听完了老师的讲解之后(实际上也不过是那个样子而已)，决定还是要写一个题解的。(不过这学校的电脑是在是太鬼畜了，强行练习我们的盲打技巧，而且还贼卡，xp系统，怪不得大家都自带电脑)

　　反正主要就是Kruskal算法 1: 　　1. 记Graph中有v个顶点，e个边 　　2. 新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边 　　3. 将原图Graph中所有e个边按权值从小到大排序 　　4. 循环： 从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中 if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中 添加这条边到图Graphnew中 先上常大佬的代码(有人说过自己的题解不能粘别人的代码吗?并没有人)，虽然T了三个点，但是依旧极具参考价值(毕竟大佬)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

const int MAXM=1e5+10;
const int MAXN=1e4+10;

struct UnionFindSet{
 int fa[MAXN];
 void init(int n){
  for(int i=1;i<=n;i++) fa[i]=i;
 }
 int getfather(int x){
  return fa[x]==x?x:fa[x]=getfather(fa[x]);
 }
 bool merge(int x,int y){
  int fax=getfather(x),fay=getfather(y);
  if(fax==fay) return false;
  fa[fax]=fay;
  return true;
 }
}UFS;

struct Edge{
 int from,to,dist;
 bool operator < (const Edge &e) const {
  return dist < e.dist;
 }
}edges[MAXM];
Edge e[MAXM];

int N,T;
int x,y,d;

void init(){
 scanf("%d%d",&N,&T);
 for(int i=0;i<T;i++) 
  scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].dist);
}

void Kruscal(){
 memcpy(e,edges,sizeof(edges));
 sort(e,e+T);
 UFS.init(N);
 long long ans=0;
 for(int i=0;i<T;i++) if(UFS.merge(e[i].from,e[i].to)) ans+=e[i].dist;
 printf("%lld\n",ans);
}

int Q;

void work(){
 Kruscal();
 scanf("%d",&Q);
 for(int i=0;i<Q;i++){
  int id,d;
  scanf("%d%d",&id,&d);
  id--;
  edges[id].dist=d;
  Kruscal();
 }
}

int main(){
 freopen("tubea.in","r",stdin);
 freopen("tubea.out","w",stdout);
 init();
 work();
 return 0;
}

　　大意就是使用最小生成树，对于玲的每一次原力释放，再次使用最小生成树(至于类封装。。这的确是个好东西!) 　　当然，正解为何~~~ 　　题目给定一个无向图，最多有10 000个顶点，100 000条边。首先题目要求输出这个图的最小生成树的大小。接着题目要求最多有10 000个操作，每个操作是缩短图上的某条边，要求每次操作之后输出这个图的最小生成树的大小。 　　由于点数比较多，可以用邻接表存储给出的无向图。对于题目的第一个问题，可以用Kruskal算法求出原图的最小生成树的大小。 　　对于第二类问题，可以利用当前求得的最小生成树进行高效求解： 　　　1. 对于每条被缩短的边，如果它在当前的最小生成树上，那么把这条边缩短之后的无向图的最小生成树就可以通过把原来的最小生成树对应的边缩短得到。 　　　2. 如果被缩短的边不在原来的最小生成树上，先求出在最小生成树上加入这条边之后形成的环，如果这条边缩短之后仍然比环上的其他边长，则不影响生成树，否则在这个环里面选出最长的边，用被缩短的边把它替换掉。 　　在本题中应用Kruskal算法求出原图的最小生成树，该算法的过程如下： 　　按权值由小到大的顺序尝试将每一条边加入到生成树中，判断加入这条边之后是否会出现环，如果有，表明当前的边不能加入生成树中，否则可以加入。判断加入一条边之后树上是否出现环可以用并查集实现。重复这个操作直到所有的边都尝试完毕，得到的生成树就是最小生成树。总的复杂度为排序复杂度O(ElogE)，其中E是无向图边的数目。 　　在求出最小生成树的过程中可以用一个数组标记某条边在不在这个最小生成树上，那么给出一个缩边操作的时候，就可以快速判断要缩短的边在不在当前的最小生成树上。 　　对于当前的生成树，可以指定某个点为根节点，然后通过一次遍历求出树上各个节点的深度和它们的父节点、到父节点的边这些信息。要找出加入一条边之后所形成的环，可以通过如下算法得到，假设要加入的为u到v的边： 　　　1. 如果u和v的深度不相等，使深度大的往上爬。 　　　2. 如果u和v的深度相等，判断u和v是否同一个节点，如果不是，则同时往上爬； 　　如果是，则这个找环的过程就结束。 　　在找这个环的过程中可以利用之前遍历得到的信息来记录环上的权值最大的边和其权值，如果这条边是新加进来的边，那么缩短这条边之后的最小生成树没有变化，否则就需要把这条边加进来，同时删除环上权值最大的边。 　　每次在之前的最小生成树中删除和添加边的操作会破坏原来树的拓扑结构，所以需要重新遍历一遍来更新之前得到的节点的深度等信息。 　　对于每个操作，最坏情况下需要遍历整棵树，时间复杂度为O(N),因此以上算法的总的复杂度为O(NQ)，其中Q为询问个数；同时由于使用邻接表作为图的存储结构，空间复杂度为O(E)，可以满足题目时间限制和空间限制的要求。

神奇的数学思想(?)

　　不过对于第二题，老师倒是讲述了一个十分有趣的解决方法，就是利用五进制来进行解决。 　　这是一道常规搜索题。给出一个初始状态、一个目标状态和两种变换规则，求从初始状态到目标状态的最小变换次数，如果无解输出-1。 　　题中给定的每个状态有8个位置，每个位置上有5种情况，因此所有可能的状态数为58，即390625个。可以先对状态进行编码，然后广搜即可。 　　状态值=0×5^0+1×5^1+3×5^2+4×5^3+…+3×5^7=251830 　　已知状态值，求该状态所对应的布局时，只需将状态值不断地模5取余即可。 　　而对于状态转换，莫非就是两种: 　　(1) 旋转 　　　b=a%57×5+a/57 　　(2) 重生 　　　　1. 对于一个数i，克它的数字为(i+4)%5 　　　　2. 对于一个数i，如果被克，它将变成的数字为i=(i+3)%5 　　　b=a-4×54+(4+3)%5×54 　　　呃，a是进行状态转换前的状态值，b是进行状态转换之后的状态值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <cstdio>
#include <queue>
using namespace std;
/*
GOLD = 0
WOOD = 1
GROUND = 2
WATER = 3
FIRE = 4
*/
int BK[5] = {4, 0, 1, 2, 3};
int BN[5] = {3, 4, 0, 1, 2};
int C5[9] = {1, 5, 25, 125, 625, 3125, 15625, 78125, 390625};
int S, T;
int ud[400000];
int gtp(char *C) {
 if (C[0] == 'G')
  if (C[1] == 'O')
   return 0;
  else
   return 2;
  else
 if (C[0] == 'W')
  if (C[1] == 'O')
   return 1;
  else
   return 3;
  else
   return 4;
}
void init() {
 char C[8][10];
 int tls[8] = {0, 1, 2, 7, 3, 6, 5, 4};
 for (int i = 0; i < 8; i++)
  scanf("%s", C[tls[i]]);
 for (int i = 0; i < 8; i++)
  S = S*5 + gtp(C[i]);
 for (int i = 0; i < 8; i++)
  scanf("%s", C[tls[i]]);
 for (int i = 0; i < 8; i++)
  T = T*5 + gtp(C[i]);
}
void work() {
 if (S == T) {
  printf("0\n");
   return;
 }
 queue<int> ls;
 ls.push(S);
 ud[S] = 1;
 int u, t;
 int x;
 while (!ls.empty()) {
  u = ls.front();
  ls.pop();
  t = u/5 + u%5*C5[7];
  if (!ud[t]) {
   ud[t] = ud[u] + 1;
   ls.push(t);
   if (t == T)
    break;
  }
  bool hv[5] = {false};
  t = u;
  for (int i = 0; i < 8; i++) {
   hv[t%5] = true;
   t /= 5;
  }
  t = 0;
  for (int i = 0; i < 8; i++) {
   x = u / C5[i] % 5;
   if (hv[BK[x]])
   x = BN[x];
   t = u/C5[i+1]*C5[i+1] + x*C5[i] + u%C5[i];
   if (!ud[t]) {
    ud[t] = ud[u] + 1;
    ls.push(t);
    if (t == T)
     break;
   }
  }
 }
 printf("%d\n", ud[T] - 1);
}
int main() {
 freopen("fengshui.in", "r", stdin);
 freopen("fengshui.out", "w", stdout);
 init();
 work();
 return 0;
}

十分有趣的字符串问题(dp)

　　而最后一道题,嗯:

算法分析

最优解来自于下面两种可能： 　　1. 先把原区间全部修改成与目标串同区间的第一个字母，再在此基础上继续寻找最优解； 　　2. 把原区间分成两部分分别求得的最优解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
#define XTT 66666666
using namespace std;
char s1[106],s2[106];
int f[106][106]={0};//i到j的刷法
int ans[106],i,j,k,len,len2;
int main()
{
    freopen("painter.in","r",stdin);
    freopen("painter.out","w",stdout);
    while(scanf("%s%s",s1,s2)!=EOF){
     len=strlen(s1);
     len2=strlen(s2);
     for(j=0;j<len;j++){
  for(i=j;i>=0;i--) { //从尾到头
       f[i][j]=f[i+1][j]+1;
       for(k=i+1;k<=j;k++){
        if(s2[i]==s2[k]) f[i][j]=min(f[i][j],(f[i+1][k]+f[k+1][j]));//ifi==k
       }
      }
     }
     for(i=0;i<len;i++)
      ans[i]=f[0][i];//初
     for(i=0;i<len;i++){
      if(s1[i]==s2[i])
       ans[i]=ans[i-1];//判存
      else{
       for(j=0;j<i;j++)
        ans[i]=min(ans[i],ans[j]+f[j+1][i]);
      }
     }
     cout<<ans[len-1]<<endl;
    }
    return 0;
}

　　懒得写了，代码一lou就搁这了，反正快要退役了(t.t)

题面

危险游戏

题目描述

玲和Janice打小就是好朋友，尽管友谊深厚，她们还是热衷于在各方面比拼，从学习到运动，从说大话到做白日梦。有一段时间，她们爱上了同一个男孩，于是她们各自组建了一个队伍又投入到新一轮的比拼中。 在过去的几轮比赛中，玲的队伍以3：1暂时领先，今晚她们要开到一块墓地再比一轮，她们要比赛给鬼魂派发馅饼。Janice很清楚这一次她必须赢，否则就会彻底被玲击败了。这块墓地共有N个坟墓，编号为1～N，双方队伍都在1号坟墓，有一些地道连接着一对对的坟墓，地道允许一个人从一端爬到另一端，两个队伍都必须将馅饼派发到每一个坟墓去才行。 在地道爬行是很惊险的，因此Janice希望所要爬的地道总长度尽可能的小，不幸的是，玲练过气功，她拥有不可思议的本领：能瞬间把一条地道缩短！这令Janice很困惑，于是她求助于你，做为她的团队成员，你需要告诉她每次地道发生改变后新的最小总长度。

输入格式

第一行包含两个正整数，N（N<=10^4）和T(T<=10^5)，分别表示坟墓及地道的数目。 接下来有T行，每一行有三个数：ui,vi,li，表示在坟墓ui和vi之间有一条长度为li的地道（1<=ui,vi<=N,ui≠vi,li>0）。 接下来一行有一个正整数Q（Q<=10^4）。 然后跟着有Q行，每行有两个正数ai,wi（1<=ai<=T,wi>0），表示第ai条地道的长度将变为wi，这里的wi保证比该地道当前的长度要小。 输入数据保证从1号坟墓能到达所有的坟墓，没有两条地道连接着同样一对坟墓。所有地道的总长度可用无符号的32位二进制整数表示。

输出格式

第一行为到每个坟墓去所要走的最小总长度，接下来有Q行，即玲每使用一次气功，就更新一下这个总长度并输出一行。

样例输入

2 1 1 2 3 1 1 1

样例输出

3 1

风水

题目描述

风水是中国民间一种古老的学问，有人将之奉若神明，有人则认为这是迷信，谁知道呢！不管怎样，在当今社会，每一个人都应该尊重我们的老祖先传下来的宝贵文化。

风水主要关注地形，环境，以及相关的位置，其所有理论都来自一本古老的书，那就是《易经》，“易”意识着转变，世上所有事物都在变化，风水学希望能引导改变，从而使我们的生活变得更加美好。现在让我们看看风水的变化。

首先，我们必须了解风水学中构成万物的5大元素：金(GOLD)，木(WOOD),土(GROUND),水(WATER),火(FIRE)，世间万物皆由其中一种元素（仅有一种）所代表，比如：河流的代表元素是水，山的代表元素是土，在这里，我们着重考虑这些元素。在这个体系中，某种元素会“克”(Kill)另一种元素，而某种元素也会“生”(Born)另一种元素，这种相克相生的关系可以用下面两个环来描述：

每个位置有8个方向：东(east)、西(west)、南(south)、北(north)、东北(northeast)、西北(northwest)、东南(southeast)和西南(southwest)，每个方向也有一个代表元素。现在我们的问题是有关风水中的方向及其代表元素的。下面图a就是这样一个例子：

但是风水是会变的，可以通过下面两种方式改变：

  1. 旋转(TURN)：把整个方位沿顺时针方向旋转一下，下图b显示了图a经过一次旋转操作的结果。

  2. 重生(REBORN)：基于上面的相生相克关系，某个方向上的代表元素会被另一个任意位置的元素克，那么被克的元素会在原位置生出一种新的元素，当然了，所有的克与生均遵循上图所述的关系。下图b中位于东南的火会被位于东方的水相克，因此东南方位的元素会变成土，如下图c：

每一次改变，不管是旋转还是重生，代价均为1。现在，给你两个风水图，我们想知道其中第一个能否转变为第二个，如果能，最小代价是多少？

输入格式

输入数据共有6行组成，前3行表示第一个风水图，后3行表示第二个风水图。 风水图的8个方向如下所示，在两个相邻方向之间可能会有多个空格。

northwest north northeast

west east

southwest south southeast

输出格式

一行，输出其转变的最小代价，如果无法转变，输出-1。

样例输入

GOLD WOOD WATER WATER FIRE WOOD GOLD GROUND WATER GOLD WOOD WOOD WATER GOLD GROUND GROUND

样例输出

2

字符串印刷机

题目描述

有两个长度相等的字符串A和B，均由小写字母组成，现在给你一台功能强大的字符串印刷机，在它的帮助下，你可以将某个字符串中任意区间内的字母都变成你想要的其它字母，换句话说，在用完印刷机后，该区间内的所有字母都将变成同一个字母，现在你的任务是使用印刷机将A变成B，请问最少的操作次数是多少？

输入格式

输入有多个测试数据（不超过40组），每组测试数据占两行：

第一行表示字符串A，第二行表示字符串B，它们的长度均不超过100。

输出格式

对于每组测试数据，在一行输出一个结果，即最少操作次数。

样例输入

zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd

样例输出

6 7

  1. Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。 ↩︎