December 2015 – Page 2

UVa 10795 A Different Task

December 06, 20152015-12-06hahaschoolLeave a comment

题意

可以参考LRJ大礼包白书第一章例题11

和汉诺塔游戏一样的规则，区别是这个问题会给出多达60个圆盘每一个最开始在哪根柱子上，要你求出从这个局势开始到终盘(00n)最少要移动多少次。

思路

大概是个。。。构造题？

思路比较复杂，而且还涉及传统汉诺塔问题的结论（把一根有k个盘子的堆移到一个空柱子上，需要((2^k)-1)步）。

具体的思路可以参考白书P27.

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXN = 105;

int init[MAXN];
int end[MAXN];
int n;

int interchange(int a,int b){
    return 6-a-b;
}

long long func(int *P,int i,int fin){
    if(i == 0){
        return 0;
    }
    if(P[i] == fin){
        return func(P,i-1,fin);
    }
    return func(P,i-1,interchange(P[i],fin)) + (1LL << (i-1));
}

long long solve(){
    int k = n;
    for(; k >= 1; k--){
        if(init[k] != end[k]){
            break;
        }
    }
    if(!k) return k;
    return func(init,k-1,interchange(init[k],end[k])) + func(end,k-1,interchange(init[k],end[k])) + 1;
}

int main(){
    int caseCnt = 0;
    while(scanf(" %d",&n) != EOF && n){
        caseCnt++;
        for(int i = 1; i<= n;i++){
            scanf(" %d",&init[i]);
        }
        for(int i = 1; i<= n; i++){
            scanf(" %d",&end[i]);
        }
        printf("Case %d: %lld\n",caseCnt,solve());
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXN = 105;

int init[MAXN];

int end[MAXN];

int n;

int interchange(int a,int b){

return 6-a-b;

}

long long func(int *P,int i,int fin){

if(i == 0){

return 0;

}

if(P[i] == fin){

return func(P,i-1,fin);

}

return func(P,i-1,interchange(P[i],fin)) + (1LL << (i-1));

}

long long solve(){

int k = n;

for(; k >= 1; k--){

if(init[k] != end[k]){

break;

}

if(!k) return k;

return func(init,k-1,interchange(init[k],end[k])) + func(end,k-1,interchange(init[k],end[k])) + 1;

}

int main(){

int caseCnt = 0;

while(scanf(" %d",&n) != EOF && n){

caseCnt++;

for(int i = 1; i<= n;i++){

scanf(" %d",&init[i]);

}

for(int i = 1; i<= n; i++){

scanf(" %d",&end[i]);

}

printf("Case %d: %lld\n",caseCnt,solve());

}

return 0;

}

POJ 2114 Boatherds

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出一棵树，树边带有边权，问你能不能找出一条路径使得路径边权之和正好等于给出的k值。

思路

和这个题非常像，只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 100005;
const int MAXE = 200005;
const int INF = 0x3f3f3f3f;

int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV];
int n;

void init(){
    gtot = 2;
    for(int i = 1; i<=n; i++){
        head[i] = 0;
    }
}
void addEdge(int from,int to,int _cost){
    end[gtot] = to;
    cost[gtot] = _cost;
    nxt[gtot] = head[from];
    head[from] = gtot++;
}

int siz[MAXV],midpn,bal;
void getbal(int cur,int par,int totsiz){
    siz[cur] = 1;
    int dpn = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != par && !vis[now]){
            getbal(now,cur,totsiz);
            siz[cur] += siz[now];
            dpn = max(dpn,siz[now]);
        }
    }
    dpn = max(dpn,totsiz-siz[cur]);
    if(dpn < midpn){
        midpn = dpn;
        bal = cur;
    }
}

int dis[MAXV],distot;
void dfs_dis(int cur,int par,int hav = 0){
    dis[distot++] = hav;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != par && !vis[now]){
            dfs_dis(now,cur,hav+cost[j]);
            siz[cur] += siz[now];
        }
    }
}

int calc(int rt,int k){
    int ret = 0;
    distot = 0;
    dfs_dis(rt,0);
    sort(dis,dis+distot);
    for(int i = 0; i < distot; i++){
        pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]);
        ret += bin.second - bin.first;
    }
    return ret;
}

bool dfs_main(int cur,int k){
    int cnt = 0;
    cnt += calc(cur,k);
    vis[cur] = true;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(!vis[now]){
            cnt -= calc(now,k-2*cost[j]);
        }
    }
    if(cnt > 0){
        return true;
    }else{
        for(int j = head[cur]; j; j = nxt[j]){
            int now = end[j];
            if(!vis[now]){
                midpn = INF;
                getbal(now,cur,siz[now]);
                if(dfs_main(bal,k)){
                    return true;
                }
            }
        }
    }
    return false;
}

bool solve(int k){
    for(int i = 1; i<= n; i++){
        vis[i] = false;
    }
    midpn = INF;
    getbal(1,0,n);
    return dfs_main(bal,k);
}


int main(){
    while(scanf(" %d",&n) != EOF && n){
        init();
        for(int i = 1; i <= n; i++){
            int a,b;
            while(scanf(" %d",&a) != EOF && a){
                scanf(" %d",&b);
                addEdge(i,a,b);
                addEdge(a,i,b);
            }
        }
        int q;
        while(scanf(" %d",&q) != EOF && q){
            if(solve(q)){
                puts("AYE");
            }else{
                puts("NAY");
            }
        }
        puts(".");
    }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 100005;

const int MAXE = 200005;

const int INF = 0x3f3f3f3f;

int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV];

int n;

void init(){

gtot = 2;

for(int i = 1; i<=n; i++){

head[i] = 0;

}

void addEdge(int from,int to,int _cost){

end[gtot] = to;

cost[gtot] = _cost;

nxt[gtot] = head[from];

head[from] = gtot++;

}

int siz[MAXV],midpn,bal;

void getbal(int cur,int par,int totsiz){

siz[cur] = 1;

int dpn = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(now != par && !vis[now]){

getbal(now,cur,totsiz);

siz[cur] += siz[now];

dpn = max(dpn,siz[now]);

}

dpn = max(dpn,totsiz-siz[cur]);

if(dpn < midpn){

midpn = dpn;

bal = cur;

}

int dis[MAXV],distot;

void dfs_dis(int cur,int par,int hav = 0){

dis[distot++] = hav;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(now != par && !vis[now]){

dfs_dis(now,cur,hav+cost[j]);

siz[cur] += siz[now];

}

int calc(int rt,int k){

int ret = 0;

distot = 0;

dfs_dis(rt,0);

sort(dis,dis+distot);

for(int i = 0; i < distot; i++){

pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]);

ret += bin.second - bin.first;

}

return ret;

}

bool dfs_main(int cur,int k){

int cnt = 0;

cnt += calc(cur,k);

vis[cur] = true;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(!vis[now]){

cnt -= calc(now,k-2*cost[j]);

}

if(cnt > 0){

return true;

}else{

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(!vis[now]){

midpn = INF;

getbal(now,cur,siz[now]);

if(dfs_main(bal,k)){

return true;

}

return false;

}

bool solve(int k){

for(int i = 1; i<= n; i++){

vis[i] = false;

}

midpn = INF;

getbal(1,0,n);

return dfs_main(bal,k);

}

int main(){

while(scanf(" %d",&n) != EOF && n){

init();

for(int i = 1; i <= n; i++){

int a,b;

while(scanf(" %d",&a) != EOF && a){

scanf(" %d",&b);

addEdge(i,a,b);

addEdge(a,i,b);

}

int q;

while(scanf(" %d",&q) != EOF && q){

if(solve(q)){

puts("AYE");

}else{

puts("NAY");

}

puts(".");

}

POJ 1987 Distance Statistics

December 06, 20152015-12-06hahaschoolOne Comment

题意

给出一棵树，和树上两点之间的边权大小，要你快速回答出树上有多少不同的点对使的这对点之间的距离至多为k。

思路

典型的点分治问题。

当考虑一棵有根树中有多少点对的距离小于等于k时，可以求出所有节点到根部的距离，然后使用二分，或者尺取的方法得到有多少对点之间的距离小于等于k。但是在上面的计算过程中我们想要求的是经过根部的符合要求的点对数量，但实际上多算入了一些并不符合要求的点，同时也漏掉了不经过根部的符合条件的点对。

所以我们可以这样看：一棵树的符合条件点对数=上面所述方法找出的点对数-各个子树中两点间距小于等于(k-2e)的点对数目(e是根部到孩子的树边的边权)+各个子树符合条件的点对数

上面的式子是递归的，这是一个树分治（点分治）策略。

在实现树分治的时候，一定要注意只有配合了重心的点分治才能达到O(nlogn)的复杂度，否则会面临特殊情况（比如链）退化到O(n^2).

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 40005;
const int MAXE = 80005;

int N,M,K;

int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot;
void gph_init(){
    gphtot = 2;
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
}
void gph_addEdge(int from,int _to,int cost){
    to[gphtot] = _to;
    nxt[gphtot] = head[from];
    len[gphtot] = cost;
    head[from] = gphtot++;
}
void input(){
    scanf(" %d %d",&N,&M);
    gph_init();
    for(int i = 1; i <= M; i++){
        int a,b,c;
        char d;
        scanf(" %d %d %d %c",&a,&b,&c,&d);
        gph_addEdge(a,b,c);
        gph_addEdge(b,a,c);
    }
    scanf(" %d",&K);
}

int siz[MAXV],mic,bal;
void getbal(int cur,int par,int totsiz){
    int mxc = 0;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = to[j];
        if(now != par && !vis[now]){
            getbal(now,cur,totsiz);
            siz[cur] += siz[now];
            mxc = max(mxc,siz[now]);
        }
    }
    mxc = max(mxc,totsiz - siz[cur]);
    if(mic > mxc){
        mic = mxc;
        bal = cur;
    }
}

int dis[MAXV],distot;
void dfs_dis(int cur,int par,int hav = 0){
    dis[distot++] = hav;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = to[j];
        if(now != par && !vis[now]){
            dfs_dis(now,cur,hav+len[j]);
            siz[cur] += siz[now];
        }
    }
}
int calc(int rt,int k){
    distot = 0;
    dfs_dis(rt,0,k);
    int ret = 0;
    sort(dis,dis+distot);
    int r = distot - 1;
    for(int l = 0; l < distot; l++){
        while(dis[r] + dis[l] > K){
            r--;
        }
        if(r <= l){
            break;
        }
        ret += r-l;
    }
    return ret;
}
int res;
void dfs_main(int cur){
    res += calc(cur,0);
    vis[cur] = true;
    for(int j = head[bal]; j; j = nxt[j]){
        int now = to[j];
        if(!vis[now]){
            res -= calc(now,len[j]);
            mic = 0x3f3f3f3f;
            getbal(now,cur,siz[now]);
            dfs_main(bal);
        }
    }
}
void solve(){
    res = 0;
    mic = 0x3f3f3f3f;
    getbal(1,0,N);
    dfs_main(bal);
    printf("%d\n",res);
}

int main(){
    input();
    solve();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 40005;

const int MAXE = 80005;

int N,M,K;

int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot;

void gph_init(){

gphtot = 2;

memset(head,0,sizeof(head));

memset(vis,0,sizeof(vis));

}

void gph_addEdge(int from,int _to,int cost){

to[gphtot] = _to;

nxt[gphtot] = head[from];

len[gphtot] = cost;

head[from] = gphtot++;

}

void input(){

scanf(" %d %d",&N,&M);

gph_init();

for(int i = 1; i <= M; i++){

int a,b,c;

char d;

scanf(" %d %d %d %c",&a,&b,&c,&d);

gph_addEdge(a,b,c);

gph_addEdge(b,a,c);

}

scanf(" %d",&K);

}

int siz[MAXV],mic,bal;

void getbal(int cur,int par,int totsiz){

int mxc = 0;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = to[j];

if(now != par && !vis[now]){

getbal(now,cur,totsiz);

siz[cur] += siz[now];

mxc = max(mxc,siz[now]);

}

mxc = max(mxc,totsiz - siz[cur]);

if(mic > mxc){

mic = mxc;

bal = cur;

}

int dis[MAXV],distot;

void dfs_dis(int cur,int par,int hav = 0){

dis[distot++] = hav;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = to[j];

if(now != par && !vis[now]){

dfs_dis(now,cur,hav+len[j]);

siz[cur] += siz[now];

}

int calc(int rt,int k){

distot = 0;

dfs_dis(rt,0,k);

int ret = 0;

sort(dis,dis+distot);

int r = distot - 1;

for(int l = 0; l < distot; l++){

while(dis[r] + dis[l] > K){

r--;

}

if(r <= l){

break;

}

ret += r-l;

}

return ret;

}

int res;

void dfs_main(int cur){

res += calc(cur,0);

vis[cur] = true;

for(int j = head[bal]; j; j = nxt[j]){

int now = to[j];

if(!vis[now]){

res -= calc(now,len[j]);

mic = 0x3f3f3f3f;

getbal(now,cur,siz[now]);

dfs_main(bal);

}

void solve(){

res = 0;

mic = 0x3f3f3f3f;

getbal(1,0,N);

dfs_main(bal);

printf("%d\n",res);

}

int main(){

input();

solve();

}

POJ 3107 Godfather

December 06, 20152015-12-06hahaschoolLeave a comment

题意

变相考察树的重心。

思路

请参考这个题和／或这个题

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 50005;
const int MAXE = 100005;

struct Graph {
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init() {
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to) {
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par) {
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]) {
        int now = gph.end[j];
        if(now != par) {
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}


vector<int> res;
int balance() {
    dfs(1,0);
    int ret = -1;
    for(int i = 1; i <= n; i++) {
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn <= n/2) {
            res.push_back(i);
            ret = 0;
        }
    }
    return ret;
}



int main() {
    scanf(" %d",&n);
    gph.init();
    for(int i = 1; i < n ; i++) {
        int a,b;
        scanf(" %d %d",&a,&b);
        gph.addEdge(a,b);
        gph.addEdge(b,a);
    }
    balance();
    for(int i = 0; i < res.size(); i++){
        printf("%d",res[i]);
        if(i == res.size()-1){
            puts("");
        }else{
            putchar(' ');
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 50005;

const int MAXE = 100005;

struct Graph {

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init() {

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to) {

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par) {

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]) {

int now = gph.end[j];

if(now != par) {

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

vector<int> res;

int balance() {

dfs(1,0);

int ret = -1;

for(int i = 1; i <= n; i++) {

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn <= n/2) {

res.push_back(i);

ret = 0;

}

return ret;

}

int main() {

scanf(" %d",&n);

gph.init();

for(int i = 1; i < n ; i++) {

int a,b;

scanf(" %d %d",&a,&b);

gph.addEdge(a,b);

gph.addEdge(b,a);

}

balance();

for(int i = 0; i < res.size(); i++){

printf("%d",res[i]);

if(i == res.size()-1){

puts("");

}else{

putchar(' ');

}

return 0;

}

POJ 2378 Tree Cutting

December 06, 20152015-12-06hahaschoolLeave a comment

题意

变相考察求树的重心。

思路

和这个题一致

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 20005;
const int MAXE = 40005;

struct Graph {
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init() {
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to) {
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par) {
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]) {
        int now = gph.end[j];
        if(now != par) {
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}

int balance() {
    dfs(1,0);
    int ret = -1;
    for(int i = 1; i <= n; i++) {
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn <= n/2) {
            printf("%d\n",i);
            ret = 0;
        }
    }
    return ret;
}



int main() {
    scanf(" %d",&n);
    gph.init();
    for(int i = 1; i < n ; i++) {
        int a,b;
        scanf(" %d %d",&a,&b);
        gph.addEdge(a,b);
        gph.addEdge(b,a);
    }
    int res = balance();
    if(res == -1) {
        puts("NONE");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 20005;

const int MAXE = 40005;

struct Graph {

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init() {

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to) {

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par) {

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]) {

int now = gph.end[j];

if(now != par) {

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

int balance() {

dfs(1,0);

int ret = -1;

for(int i = 1; i <= n; i++) {

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn <= n/2) {

printf("%d\n",i);

ret = 0;

}

return ret;

}

int main() {

scanf(" %d",&n);

gph.init();

for(int i = 1; i < n ; i++) {

int a,b;

scanf(" %d %d",&a,&b);

gph.addEdge(a,b);

gph.addEdge(b,a);

}

int res = balance();

if(res == -1) {

puts("NONE");

}

return 0;

}

POJ 1655 Balancing Act

December 06, 20152015-12-06hahaschool3 Comments

题意

求树的重心。

思路

树的重心的定义是：选树中某个点i当作树的根，所有子树中最大的那棵的大小是Si，整棵树中能令Si最小的那个点，就是树的重心。

求重心是作为树分治的一个环节出现的，只有保证了每一次点分治的位置都是重心才能保证树分治的复杂度为O(nlogn)。

求重心的想法是树dp，对于每个节点都要存储他所有孩子对应的子树中最大子树的大小，还要存储他的父亲是谁。求好了这些数据之后，按着定义，就可以知道谁是重心了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 20005;
const int MAXE = 40005;

struct Graph{
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init(){
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to){
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par){
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]){
        int now = gph.end[j];
        if(now != par){
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}

int balance(int &mib){
    dfs(1,0);
    int ret = 0;
    mib = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn < mib){
            mib = dpn;
            ret = i;
        }
    }
    return ret;
}



int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %d",&n);
        gph.init();
        for(int i = 1; i < n ; i++){
            int a,b;
            scanf(" %d %d",&a,&b);
            gph.addEdge(a,b);
            gph.addEdge(b,a);
        }
        int mib;
        int res = balance(mib);
        printf("%d %d\n",res,mib);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 20005;

const int MAXE = 40005;

struct Graph{

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init(){

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to){

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par){

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]){

int now = gph.end[j];

if(now != par){

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

int balance(int &mib){

dfs(1,0);

int ret = 0;

mib = 0x3f3f3f3f;

for(int i = 1; i <= n; i++){

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn < mib){

mib = dpn;

ret = i;

}

return ret;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

scanf(" %d",&n);

gph.init();

for(int i = 1; i < n ; i++){

int a,b;

scanf(" %d %d",&a,&b);

gph.addEdge(a,b);

gph.addEdge(b,a);

}

int mib;

int res = balance(mib);

printf("%d %d\n",res,mib);

}

return 0;

}

Codeforces 573C Bear and Drawing

December 06, 20152015-12-06hahaschoolLeave a comment

题意

你要在两条平行直线之间画一棵有n个节点的树，树必须是可平面的（意思就是不能有两条链发生相交的情况）。给出你若干个连边（他们已经组成一棵树），问你是否可能画出符合要求的树。

思路

通过小数据找规律，可以要想把一棵树的安排在两条平行直线上，这棵树需要满足以下几个条件：

首先我们在树上找到一条主链
凡是在主链上的点，它的度数没有限制
与主链直接相连的点，它的度数最大为3
剩下的点，度数最大为2

知道了这些，接下来就是实现的问题了。这里有一种很聪明的实现方法。

首先，统计所有节点的度数。
在每一个叶子节点都发动一次DFS，在DFS过程中若遇到的一切度数小于等于2的点，进入，并做删除标记，否则返回。这一步的目的是清除掉所有叶子节点所属的链（不能直接修改度数，否则会导致删掉整棵树）。
重新统计每个节点的度数，因为刚才只是做标记，没有改变度数。
接下来对于所有曾经为3度现在为1度的点打删除标记，这种点是与主链直接相连的点。
重新统计每个点的度数。
现在每个节点的度数都理应小于3了，因为我们刚才去掉了叶子节点所在的链，如果这棵树正确，一定会删到主链上。接下来又去掉了曾经3度删完1度的节点，这相当于完全去掉了支链。这个时候整棵树理应只剩一条链了，不可能再有度数大于2的节点了。

如果理解有困难，不妨尝试画图帮助理解。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXN = 100005;
const int MAXE = 200005;
int n;

struct Graph {
    int head[MAXN];
    int next[MAXE];
    int end[MAXE];
    int deg[MAXN];
    int ndeg[MAXN];
    bool del[MAXN];
    int tot;
    void init() {
        tot = 2;
        //memset(head,0,sizeof(head));
    }
    void addEdge(int from,int to) {
        end[tot] = to;
        next[tot] = head[from];
        head[from] = tot++;
        deg[from]++;
    }
} gph;

void dfs(int cur,int par = 0) {
    if(gph.deg[cur] <= 2){
        gph.del[cur] = true;
        for (int j = gph.head[cur]; j;j = gph.next[j]) {
            if(gph.end[j] != par){
                dfs(gph.end[j],cur);
            }
        }
    }
}

bool judge() {
    for(int i = 1; i <= n; i++){
        if(gph.deg[i] == 1){
            dfs(i);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(gph.deg[i] >= 3) {
            int ndeg = 0;
            for(int j = gph.head[i]; j; j = gph.next[j]) {
                if(!gph.del[gph.end[j]]) {
                    ndeg++;
                }
            }
            gph.ndeg[i] = ndeg;
        }
    }
    for(int i = 1; i<= n; i++) {
        if(gph.deg[i] == 3 && gph.ndeg[i] == 1) {
            gph.del[i] = true;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!gph.del[i]) {
            int fdeg = 0;
            for(int j = gph.head[i]; j; j = gph.next[j]) {
                if(!gph.del[gph.end[j]]) {
                    fdeg++;
                }
            }
            if(fdeg > 2) {
                return false;
            }
        }
    }
    return true;
}


int main() {
    gph.init();
    scanf(" %d",&n);
    for(int i = 1; i < n; i++) {
        int a,b;
        scanf(" %d %d",&a,&b);
        gph.addEdge(a,b);
        gph.addEdge(b,a);
    }
    if(judge()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXN = 100005;

const int MAXE = 200005;

int n;

struct Graph {

int head[MAXN];

int next[MAXE];

int end[MAXE];

int deg[MAXN];

int ndeg[MAXN];

bool del[MAXN];

int tot;

void init() {

tot = 2;

//memset(head,0,sizeof(head));

}

void addEdge(int from,int to) {

end[tot] = to;

next[tot] = head[from];

head[from] = tot++;

deg[from]++;

}

} gph;

void dfs(int cur,int par = 0) {

if(gph.deg[cur] <= 2){

gph.del[cur] = true;

for (int j = gph.head[cur]; j;j = gph.next[j]) {

if(gph.end[j] != par){

dfs(gph.end[j],cur);

}

bool judge() {

for(int i = 1; i <= n; i++){

if(gph.deg[i] == 1){

dfs(i);

}

for(int i = 1; i <= n; i++) {

if(gph.deg[i] >= 3) {

int ndeg = 0;

for(int j = gph.head[i]; j; j = gph.next[j]) {

if(!gph.del[gph.end[j]]) {

ndeg++;

}

gph.ndeg[i] = ndeg;

}

for(int i = 1; i<= n; i++) {

if(gph.deg[i] == 3 && gph.ndeg[i] == 1) {

gph.del[i] = true;

}

for(int i = 1; i <= n; i++) {

if(!gph.del[i]) {

int fdeg = 0;

for(int j = gph.head[i]; j; j = gph.next[j]) {

if(!gph.del[gph.end[j]]) {

fdeg++;

}

if(fdeg > 2) {

return false;

}

return true;

}

int main() {

gph.init();

scanf(" %d",&n);

for(int i = 1; i < n; i++) {

int a,b;

scanf(" %d %d",&a,&b);

gph.addEdge(a,b);

gph.addEdge(b,a);

}

if(judge()) {

cout << "Yes" << endl;

} else {

cout << "No" << endl;

}

return 0;

}

UVa 11384 Help is needed for Dexter

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题10

思路

试验小数据，找规律。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int main(){
    long long a;
    while(scanf(" %lld",&a) != EOF){
        int res = 0;
        long long fac = 1;
        while(fac <= a){
            fac *= 2;
            res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int main(){

long long a;

while(scanf(" %lld",&a) != EOF){

int res = 0;

long long fac = 1;

while(fac <= a){

fac *= 2;

res++;

}

printf("%d\n",res);

}

return 0;

}

UVa 11464 Even Parity

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题7.

思路

大概是个带有机智成分的枚举。

为什么这么说，因为这道题的关键思路点就是发现只要知道第一行，就可以构造出整个数表，这样我们只要枚举第一行就可以解决问题，复杂度直接降低了一次幂。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n;
int per[16];
int orig[16][16];
int now[16][16];

void genPermutation(int s){
    int cur = n;
    while(cur){
        if(s&1){
            per[cur] = 1;
        }else{
            per[cur] = 0;
        }
        cur--;
        s >>= 1;
    }
}

void genNow(){
    memset(now,0,sizeof(now));
    for(int i = 1; i <= n; i++){
        now[1][i] = per[i];
    }
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n; j++){
            int cnt = now[i-1][j] + now[i][j-1] + now[i][j+1];
            if(cnt % 2){
                now[i+1][j] = 1;
            }else{
                now[i+1][j] = 0;
            }
        }
    }
}

int compare(){
    int ret = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(now[i][j] == 0 && orig[i][j] == 1){
                return 0x3f3f3f3f;
            }
            if(now[i][j] != orig[i][j]){
                ret++;
            }
        }
    }
    return ret;
}



int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %d",&n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf(" %d",&orig[i][j]);
            }
        }
        int res = 0x3f3f3f3f;
        for(int i = 0; i < (1 << n); i++){
            genPermutation(i);
            genNow();
            res = min(res,compare());
        }
        if(res == 0x3f3f3f3f){
            res = -1;
        }
        printf("Case %d: %d\n",d,res);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n;

int per[16];

int orig[16][16];

int now[16][16];

void genPermutation(int s){

int cur = n;

while(cur){

if(s&1){

per[cur] = 1;

}else{

per[cur] = 0;

}

cur--;

s >>= 1;

}

void genNow(){

memset(now,0,sizeof(now));

for(int i = 1; i <= n; i++){

now[1][i] = per[i];

}

for(int i = 1; i < n; i++){

for(int j = 1; j <= n; j++){

int cnt = now[i-1][j] + now[i][j-1] + now[i][j+1];

if(cnt % 2){

now[i+1][j] = 1;

}else{

now[i+1][j] = 0;

}

int compare(){

int ret = 0;

for(int i = 1; i <= n; i++){

for(int j = 1; j <= n; j++){

if(now[i][j] == 0 && orig[i][j] == 1){

return 0x3f3f3f3f;

}

if(now[i][j] != orig[i][j]){

ret++;

}

return ret;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

scanf(" %d",&n);

for(int i = 1; i <= n; i++){

for(int j = 1; j <= n; j++){

scanf(" %d",&orig[i][j]);

}

int res = 0x3f3f3f3f;

for(int i = 0; i < (1 << n); i++){

genPermutation(i);

genNow();

res = min(res,compare());

}

if(res == 0x3f3f3f3f){

res = -1;

}

printf("Case %d: %d\n",d,res);

}

return 0;

}

UVA 10881 Piotr's Ants

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题5

思路

两个蚂蚁相遇会马上调换方向，从视觉上看其实相当于擦身而过（虽然两只蚂蚁的身份并没有交换）。就像在物理中，两个质量相等的小球发生完全弹性碰撞，交换速度。这里是本题第一个思路点。

无论在任何时候，第i只蚂蚁永远是第i只蚂蚁，因为上面也说了，只是视觉上的擦身，实际上蚂蚁又各自回去了。这是第二个思路点。在这个地方还有一个问题，那就是可能会以为仅仅是位置关系保持原来的顺序，其实方向关系也是保持原来的顺序的，这样就可以解决蚂蚁的最终状态的判定问题。

这样我们就有了解法：首先利用擦身而过的想法，求出最终所有蚂蚁的分布。然后利用标号守恒的想法，把终止状态和起始状态对应。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

struct Ant{
    int pos;
    int dir;//1:R -1:L 0:turing
    int id;
    bool operator < (const Ant &b) const{
        return pos < b.pos;
    }
};

bool cmp(const Ant &a, const Ant &b){
    return a.id < b.id;
}

vector<Ant> all;
int loc[10005];

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        int L,T,n;
        scanf(" %d %d %d",&L,&T,&n);
        Ant tmp;
        all.clear();
        all.resize(n);
        for(int i = 0; i < n; i++){
            tmp.id = i;
            scanf(" %d",&tmp.pos);
            char dir;
            scanf(" %c",&dir);
            if(dir == 'L'){
                tmp.dir = -1;
            }else{
                tmp.dir = 1;
            }
            all[i] = tmp;
        }
        sort(all.begin(),all.end());
        for(int i = 0; i < n; i++){
            loc[all[i].id] = i;
            all[i].pos += all[i].dir * T;
        }
        sort(all.begin(),all.end());
        for(int i = 0; i < all.size(); i++){
            if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){
                all[i].dir = 0;
            }
        }
        //sort(all.begin(),all.end(),cmp);
        printf("Case #%d:\n",d);
        for(int i = 0; i < all.size(); i++){
            if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){
                puts("Fell off");
            }else{
                printf("%d ",all[loc[i]].pos);
                if(all[loc[i]].dir == 1){
                    puts("R");
                }else if(all[loc[i]].dir == -1){
                    puts("L");
                }else{
                    puts("Turning");
                }
            }
        }
        puts("");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

struct Ant{

int pos;

int dir;//1:R -1:L 0:turing

int id;

bool operator < (const Ant &b) const{

return pos < b.pos;

}

};

bool cmp(const Ant &a, const Ant &b){

return a.id < b.id;

}

vector<Ant> all;

int loc[10005];

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

int L,T,n;

scanf(" %d %d %d",&L,&T,&n);

Ant tmp;

all.clear();

all.resize(n);

for(int i = 0; i < n; i++){

tmp.id = i;

scanf(" %d",&tmp.pos);

char dir;

scanf(" %c",&dir);

if(dir == 'L'){

tmp.dir = -1;

}else{

tmp.dir = 1;

}

all[i] = tmp;

}

sort(all.begin(),all.end());

for(int i = 0; i < n; i++){

loc[all[i].id] = i;

all[i].pos += all[i].dir * T;

}

sort(all.begin(),all.end());

for(int i = 0; i < all.size(); i++){

if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){

all[i].dir = 0;

}

//sort(all.begin(),all.end(),cmp);

printf("Case #%d:\n",d);

for(int i = 0; i < all.size(); i++){

if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){

puts("Fell off");

}else{

printf("%d ",all[loc[i]].pos);

if(all[loc[i]].dir == 1){

puts("R");

}else if(all[loc[i]].dir == -1){

puts("L");

}else{

puts("Turning");

}

puts("");

}

return 0;

}