解题报告 – Page 2

UVA 11462 Age Sort

December 06, 20152015-12-06hahaschoolLeave a comment

题意

排序，25MB大数据，都是整数，最大100最小0，内存极其紧张。

思路

面对这种数据范围很小，量很大的情况，考虑计数排序，原理非常简单就是开个数组统计一下不同值有多少个数字就搞定了，时间O(n)。

能做到O(n)的排序算法还有Sleep Sort，不过因为利用多线程睡眠差异太难控制所以也没啥实际意义。

被卡常数的时候，也可以考虑用计数排序进行没什么卵用的优化（结果可能就真卡过了）。

代码

#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 cnt[101];

int main(){
    int n;
    while(scanf(" %d",&n) != EOF && n){
        memset(cnt,0,sizeof(cnt));
        for(int i = 1; i <= n; i++){
            int a;
            scanf(" %d",&a);
            cnt[a]++;
        }
        for(int i = 1; i <= 100; i++){
            if(cnt[i])
            if(n == cnt[i]){
                for(int j = 1; j <= cnt[i]-1; j++){
                    printf("%d ",i);
                }
                printf("%d\n",i);
            }else{
                for(int j = 1; j <= cnt[i]; j++){
                    printf("%d ",i);
                }
            }
            n -= cnt[i];
        }
    }
    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 cnt[101];

int main(){

int n;

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

memset(cnt,0,sizeof(cnt));

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

int a;

scanf(" %d",&a);

cnt[a]++;

}

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

if(cnt[i])

if(n == cnt[i]){

for(int j = 1; j <= cnt[i]-1; j++){

printf("%d ",i);

}

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

}else{

for(int j = 1; j <= cnt[i]; j++){

printf("%d ",i);

}

n -= cnt[i];

}

return 0;

}

LA3177 Beijing Guards

December 06, 20152015-12-06hahaschoolLeave a comment

题意

可以参见LRJ白书第一章例题16.

有n个人，围个圈，每个人想要一定数量的礼物，注意每个人所持礼物不可以重样，两个相邻的人所持的礼物也不能重样，问你至少要准备多少种不同的礼物，才能符合要求？

思路

大概是个构造题综合二分答案。

首先要想到对n的分类讨论：

如果n是偶数，那么你只需要准备两套不同配置的礼物，按照ABABABABAB这样循环下去就可以满足要求了，因此答案是max{r_i+r_((i+1)%n)}
如果n是奇数，情况就比较复杂。我们可以先反向思考，如果给定有r种礼物，如何才能构造合适的礼物配置满足题设要求？白书里面给了这样一种方法：令编号为奇数的尽量选取靠前的种类，编号为偶数的尽量选取靠后的种类，即把r种礼物分成两半（即前、后两组），对于每一个人维护他按照上面策略进行选取的前组后组中元素数量，最后检查第一个人和最后一个人是否相容即可。这样我们就有了二分答案的检查方法了。

代码

#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;

int n;
int seq[MAXN];
int ls[MAXN],rs[MAXN];
int res;
bool check(int k) {
    int lb = seq[1],rb = k-lb;
    ls[1] = seq[1],rs[1] = 0;
    for(int i = 2; i<= n; i++){
        int lrm = lb - ls[i-1];
        int rrm = rb - rs[i-1];
        if(i % 2 == 0){
            if(seq[i] < lrm){
                ls[i] = seq[i];
                rs[i] = 0;
            }else{
                ls[i] = lrm;
                rs[i] = seq[i] - lrm;
            }
        }else{
            if(seq[i] < rrm){
                rs[i] = seq[i];
                ls[i] = 0;
            }else{
                rs[i] = rrm;
                ls[i] = seq[i] - rrm;
            }
        }
    }
    return ls[n] == 0;
}

int solve() {
    int l = res,r = 300005,mid;
    while(l + 1 < r){
        int mid = l + (r-l)/2;
        if(check(mid)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    if(check(l)){
        return l;
    }else {
        return r;
    }
}

int main() {
    while(scanf(" %d",&n) != EOF && n) {
        if(n == 1){
            scanf(" %d",&n);
            printf("%d\n",n);
            continue;
        }
        for(int i = 1; i <= n; i++) {
            scanf(" %d",&seq[i]);
        }
        res = 0;
        for(int i = 1; i <= n; i++) {
            if(i == n) {
                res = max(res,seq[1]+seq[n]);
            } else {
                res = max(res,seq[i]+seq[i+1]);
            }
        }
        if(n % 2) {
            printf("%d\n",solve());
        } else {
            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;

const int MAXN = 100005;

int n;

int seq[MAXN];

int ls[MAXN],rs[MAXN];

int res;

bool check(int k) {

int lb = seq[1],rb = k-lb;

ls[1] = seq[1],rs[1] = 0;

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

int lrm = lb - ls[i-1];

int rrm = rb - rs[i-1];

if(i % 2 == 0){

if(seq[i] < lrm){

ls[i] = seq[i];

rs[i] = 0;

}else{

ls[i] = lrm;

rs[i] = seq[i] - lrm;

}

}else{

if(seq[i] < rrm){

rs[i] = seq[i];

ls[i] = 0;

}else{

rs[i] = rrm;

ls[i] = seq[i] - rrm;

}

return ls[n] == 0;

}

int solve() {

int l = res,r = 300005,mid;

while(l + 1 < r){

int mid = l + (r-l)/2;

if(check(mid)){

r = mid;

}else{

l = mid+1;

}

if(check(l)){

return l;

}else {

return r;

}

int main() {

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

if(n == 1){

scanf(" %d",&n);

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

continue;

}

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

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

}

res = 0;

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

if(i == n) {

res = max(res,seq[1]+seq[n]);

} else {

res = max(res,seq[i]+seq[i+1]);

}

if(n % 2) {

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

} else {

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

}

return 0;

}

LA3902 Network

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出了一棵树，和一个初始的黑点（VOD服务器），所有边的边权均为1，你要求出最少还要染黑几个点，才能保证每一个白点到最近黑点之间的距离小于等于k。

思路

大概是贪心。

把给出的初始黑点当成树的根部，从根部dfs一次求出所有节点的深度，然后把深度最大的点（如果深度大于k）染黑，之后以这个点为中心dfs一次标记所有能覆盖的点。然后找第一个没有被覆盖的点，染黑，标记。。。直到所有点都被标记。

代码

#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 = 1005;
const int MAXE = 2005;
vector<int> leaf;
int par[MAXV],dep[MAXV];
bool vis[MAXV];
int tot,head[MAXV],nxt[MAXE],end[MAXE];
int n,s,k;
void init(){
    leaf.clear();
    tot = 2;
    for(int i = 1; i <= n; i++){
        head[i] = 0;
        vis[i] = false;
    }
}
void addEdge(int from,int to){
    end[tot] = to;
    nxt[tot] = head[from];
    head[from] = tot++;
}
void input(){
    scanf(" %d %d %d",&n,&s,&k);
    for(int i = 1; i< n; i++){
        int a,b;
        scanf(" %d %d",&a,&b);
        addEdge(a,b);
        addEdge(b,a);
    }
}
void dfs(int cur,int _par,int cdp){
    dep[cur] = cdp;
    par[cur] = _par;
    int cct = 0;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != _par){
            cct++;
            dfs(now,cur,cdp+1);
        }
    }
    if(!cct){
        leaf.push_back(cur);
    }
}
bool cmp(int a, int b){
    return dep[a] > dep[b];
}
void mkr(int cur,int _par,int cdp){
    if(cdp>=0){
    vis[cur] = true;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != _par){
            mkr(now,cur,cdp-1);
        }
    }
    }
}
int solve(){
    dfs(s,0,0);
    sort(leaf.begin(),leaf.end(),cmp);
    mkr(s,0,k);
    int ret = 0;
    for(int i = 0; i < leaf.size(); i++){
        if(!vis[leaf[i]]){
            ret++;
            int now = leaf[i];
            for(int i = 1; i <= k; i++){
                now = par[now];
            }
            mkr(now,0,k);
        }
    }
    return ret;
}

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        init();
        input();
        printf("%d\n",solve());
    }
    return 0;
}

100

101

102

103

104

105

#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 = 1005;

const int MAXE = 2005;

vector<int> leaf;

int par[MAXV],dep[MAXV];

bool vis[MAXV];

int tot,head[MAXV],nxt[MAXE],end[MAXE];

int n,s,k;

void init(){

leaf.clear();

tot = 2;

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

head[i] = 0;

vis[i] = false;

}

void addEdge(int from,int to){

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

void input(){

scanf(" %d %d %d",&n,&s,&k);

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

int a,b;

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

addEdge(a,b);

addEdge(b,a);

}

void dfs(int cur,int _par,int cdp){

dep[cur] = cdp;

par[cur] = _par;

int cct = 0;

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

int now = end[j];

if(now != _par){

cct++;

dfs(now,cur,cdp+1);

}

if(!cct){

leaf.push_back(cur);

}

bool cmp(int a, int b){

return dep[a] > dep[b];

}

void mkr(int cur,int _par,int cdp){

if(cdp>=0){

vis[cur] = true;

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

int now = end[j];

if(now != _par){

mkr(now,cur,cdp-1);

}

int solve(){

dfs(s,0,0);

sort(leaf.begin(),leaf.end(),cmp);

mkr(s,0,k);

int ret = 0;

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

if(!vis[leaf[i]]){

ret++;

int now = leaf[i];

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

now = par[now];

}

mkr(now,0,k);

}

return ret;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

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

init();

input();

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

}

return 0;

}

UVa 11520 Fill the Square

December 06, 20152015-12-06hahaschoolLeave a comment

题意

填充一个NxN网格，使得每个格子的字母与其相邻的字母均不相同。输出字典序最小的填充方案。

思路

注意到解的空间非常大，因此只要每一次从’a’~’z’枚举并检查当前格子就可以了。这样也可以保证字典序最小，因为每一次的填充是从最小的字母开始尝试的。

代码

#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;

char board[11][11];
int n;
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
void input(){
    memset(board,0,sizeof(board));
    scanf(" %d",&n);
    for(int i = 1; i<= n; i++){
        for(int j = 1; j <= n; j++){
            scanf(" %c",&board[i][j]);
        }
    }
}
void output(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            putchar(board[i][j]);
        }
        puts("");
    }
}

bool fillone(){
    int y = 1,x = 1;
    bool mkr[26];
    memset(mkr,0,sizeof(mkr));
    int ori = 1;
    while(x <= n){
        int stp = 1;
        while(stp <= n){
            if(board[y][x] != '.'){
                stp++;
                y += ori;
            }else{
                for(int i = 0; i< 4; i++){
                    char cur = board[y + dir[i][0]][x+dir[i][1]];
                    if(isalpha(cur)){
                        mkr[cur - 'A'] = true;
                    }
                }
                for(int i = 'A'; i <= 'Z'; i++){
                    if(!mkr[i-'A']){
                        board[y][x] = i;
                        return true;
                    }
                }
            }
        }
        y -= ori;
        ori *= -1;
        x++;
    }
    return false;
}

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        printf("Case %d:\n",d);
        input();
        while(fillone());
        output();
    }
    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;

char board[11][11];

int n;

int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

void input(){

memset(board,0,sizeof(board));

scanf(" %d",&n);

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

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

scanf(" %c",&board[i][j]);

}

void output(){

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

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

putchar(board[i][j]);

}

puts("");

}

bool fillone(){

int y = 1,x = 1;

bool mkr[26];

memset(mkr,0,sizeof(mkr));

int ori = 1;

while(x <= n){

int stp = 1;

while(stp <= n){

if(board[y][x] != '.'){

stp++;

y += ori;

}else{

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

char cur = board[y + dir[i][0]][x+dir[i][1]];

if(isalpha(cur)){

mkr[cur - 'A'] = true;

}

for(int i = 'A'; i <= 'Z'; i++){

if(!mkr[i-'A']){

board[y][x] = i;

return true;

}

y -= ori;

ori *= -1;

x++;

}

return false;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

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

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

input();

while(fillone());

output();

}

return 0;

}

LA3635 Pie

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出若干个Pie，你要求出最大的大小k，使得每个人（包括自己）得到的Pie的大小都正好为k，注意在分Pie的时候，可以切碎，但是不可以给一个人不同种的Pie。

思路

二分答案。

类似于“最小值最大问题”，检查的时间可以接受，因此问题可以通过二分答案解决。

代码

#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,f;
double pie[10004];
const double PI = acos(-1);

void input(){
    scanf(" %d %d",&n,&f);
    for(int i = 1; i<= n; i++){
        scanf(" %lf",&pie[i]);
        pie[i]*=pie[i];
    }
}

bool check(double part){
    int cnt = 0;
    for(int i = 1; i<= n; i++){
        cnt += floor(pie[i]/part);
    }
    return cnt >= f+1;
}

double solve(){
    double l = 0.0,r = 110000000.0,mid;
    while(abs(l-r) > 1e-6){
        mid = (l+r)/2;
        if(check(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    return l;
}

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    while(caseCnt--){
        input();
        printf("%.4lf\n",PI*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;

int n,f;

double pie[10004];

const double PI = acos(-1);

void input(){

scanf(" %d %d",&n,&f);

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

scanf(" %lf",&pie[i]);

pie[i]*=pie[i];

}

bool check(double part){

int cnt = 0;

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

cnt += floor(pie[i]/part);

}

return cnt >= f+1;

}

double solve(){

double l = 0.0,r = 110000000.0,mid;

while(abs(l-r) > 1e-6){

mid = (l+r)/2;

if(check(mid)){

l = mid;

}else{

r = mid;

}

return l;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

while(caseCnt--){

input();

printf("%.4lf\n",PI*solve());

}

return 0;

}

LA3971 Assemble

December 06, 20152015-12-06hahaschoolLeave a comment

题意

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

思路

二分答案。

典型的“最小值最大问题”，考虑二分答案，检查一次二分的时间是可以接受的，因此本题得到解决。

代码

#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 Component{
    int q,p;
    bool operator < (const Component &b) const{
        if(q == b.q){
            return p < b.p;
        }
        return q < b.q;
    }
    Component(){
    }
    Component(int _p,int _q){
        p = _p;
        q = _q;
    }
};

typedef map<string,vector<Component> > Table;
Table tab;
int n,b;

void input(){
    tab.clear();
    scanf(" %d %d",&n,&b);
    for(int i = 1; i <= n; i++){
        string type;
        string name;
        int p,q;
        cin >> type >> name >> p >> q;
        tab[type].push_back(Component(p,q));
    }
    for(Table::iterator it = tab.begin(); it != tab.end(); it++){
        sort(it->second.begin(),it->second.end());
    }
}

bool check(int miq){
    int cst = 0;
    for(Table::iterator it = tab.begin(); it != tab.end(); it++){
        int sel = b+1;
        for(int i = 0; i < it->second.size(); i++){
            if(it->second[i].q >= miq){
                sel=min(sel,it->second[i].p);
            }
        }
        if(sel == b+1){
            return false;
        }else{
            cst += sel;
            if(cst > b){
                return false;
            }
        }
    }
    return true;
}

int solve(){
    int l = 0,r = 1000000000,mid;
    while(l < r){
        mid = l + (r-l+1)/2;
        if(check(mid)){
            l = mid;
        }else{
            r = mid-1;
        }
    }
    if(check(r)){
        return r;
    } else{
        return l;
    }
}

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    while(caseCnt--){
        input();
        cout << solve() << endl;
    }

    return 0;
}

100

101

102

#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 Component{

int q,p;

bool operator < (const Component &b) const{

if(q == b.q){

return p < b.p;

}

return q < b.q;

}

Component(){

}

Component(int _p,int _q){

p = _p;

q = _q;

}

};

typedef map<string,vector<Component> > Table;

Table tab;

int n,b;

void input(){

tab.clear();

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

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

string type;

string name;

int p,q;

cin >> type >> name >> p >> q;

tab[type].push_back(Component(p,q));

}

for(Table::iterator it = tab.begin(); it != tab.end(); it++){

sort(it->second.begin(),it->second.end());

}

bool check(int miq){

int cst = 0;

for(Table::iterator it = tab.begin(); it != tab.end(); it++){

int sel = b+1;

for(int i = 0; i < it->second.size(); i++){

if(it->second[i].q >= miq){

sel=min(sel,it->second[i].p);

}

if(sel == b+1){

return false;

}else{

cst += sel;

if(cst > b){

return false;

}

return true;

}

int solve(){

int l = 0,r = 1000000000,mid;

while(l < r){

mid = l + (r-l+1)/2;

if(check(mid)){

l = mid;

}else{

r = mid-1;

}

if(check(r)){

return r;

} else{

return l;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

while(caseCnt--){

input();

cout << solve() << endl;

}

return 0;

}

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;

}