LRJ – hahaschool

LA2678 Subsequence

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出一个由n个整数组成的数列，要你求长度最短的连续序列，使得序列中所有元素的和大于等于S。

思路

单调性优化，或者说是尺取法。

暴力O(n^3)显然无法接受，套用前缀和优化再枚举O(n^2)，还是无法接受。

在套用前缀和的基础上，可以枚举终点，二分查找起点，这样是O(nlogn)，可以过了。

然而还有更好的办法，设两个指针，表示连续区间的左端点和右端点，一开始不断右移右端点，直到序列大于等于S，记录长度。然后右移左端点，再开始不断尝试右移右端点，直到条件再次满足，停下纪录，右移一下左端点。。。如此往复，直到右端点无法右移，且左端点无论怎么移动也无法满足条件。

这就是尺取法（名字来源于挑战程序设计竞赛），CF上面也叫Double Pointers，是一种基于单调性的优化手段。

代码

前缀和＋尺取

#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>
#include <cassert>

using namespace std;

const int MAXN = 100005;

int seq[MAXN];
int sum[MAXN];
int s,n;

int solve(){
    if(sum[n] < s) return 0;
    int ret = n;
    int ptr = 0;
    for(int i = 1; i<= n; i++){
        if(sum[i] >= s){
            while(sum[i] - sum[ptr] >= s){
                ret = min(ret,i-ptr);
                ptr++;
            }
        }
    }
    return ret;
}

int main(){
    while(scanf(" %d %d",&n,&s) != EOF){
        for(int i = 1; i <= n; i++){
            scanf(" %d",&seq[i]);
            sum[i] = sum[i-1] + seq[i];
        }
        printf("%d\n",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>

#include <cassert>

using namespace std;

const int MAXN = 100005;

int seq[MAXN];

int sum[MAXN];

int s,n;

int solve(){

if(sum[n] < s) return 0;

int ret = n;

int ptr = 0;

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

if(sum[i] >= s){

while(sum[i] - sum[ptr] >= s){

ret = min(ret,i-ptr);

ptr++;

}

return ret;

}

int main(){

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

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

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

sum[i] = sum[i-1] + seq[i];

}

printf("%d\n",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>
#include <cassert>

using namespace std;

const int MAXN = 100005;

int seq[MAXN];
int sum[MAXN];
int s,n;

int binSearch(int l,int r,int rval){
    //right tilted
    while(l+1<r){
        int mid = l + (r-l)/2;
        if(rval - sum[mid] >= s){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    if(rval - sum[r] >= s){
        return r;
    }
    return l;
}

int solve(){
    if(sum[n] < s) return 0;
    int ret = n;
    for(int i = 1; i<= n; i++){
        if(sum[i] >= s){
            ret = min(i-binSearch(0,i-1,sum[i]),ret);
        }
    }
    return ret;
}

int main(){
    while(scanf(" %d %d",&n,&s) != EOF){
        for(int i = 1; i <= n; i++){
            scanf(" %d",&seq[i]);
            sum[i] = sum[i-1] + seq[i];
        }
        printf("%d\n",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>

#include <cassert>

using namespace std;

const int MAXN = 100005;

int seq[MAXN];

int sum[MAXN];

int s,n;

int binSearch(int l,int r,int rval){

//right tilted

while(l+1<r){

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

if(rval - sum[mid] >= s){

l = mid;

}else{

r = mid - 1;

}

if(rval - sum[r] >= s){

return r;

}

return l;

}

int solve(){

if(sum[n] < s) return 0;

int ret = n;

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

if(sum[i] >= s){

ret = min(i-binSearch(0,i-1,sum[i]),ret);

}

return ret;

}

int main(){

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

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

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

sum[i] = sum[i-1] + seq[i];

}

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

}

return 0;

}

LA3905 Meteor

December 06, 20152015-12-06hahaschoolLeave a comment

题意

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

思路

扫描线。

这个题分为两部分，首先是要求出每一颗流星划过取景框的时间区间，这一步反而是这个题最复杂的地方，因为要讨论许多种情况，具体的讨论策略可以参考下面的代码。

求出来所有的区间之后，问题转化为选出一条线，使得这条线穿过的区间最多，这里就是扫描线算法派上用场的时候了。其实实现很简单，就是对于每个区间的两个端点，分别创建一个表示起始的事件和一个表示结束的事件，然后把所有事件按照出现的时间排序，接下来从小往大检查，遇到开始事件的时候计数器+1，遇到结束事件的时候计数器-1.

这里有一个问题，如果开始事件和结束事件恰好位于同一时点，怎么办？注意到我们的区间都是开的，这样我们只要优先处理结束事件，就不会导致解偏大了（这里面的逻辑需要自己试着理解一下）。

代码

#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>
#include <cassert>

using namespace std;

int w,h;
int n;

struct Event {
    int t;
    int dir;
    bool operator < (const Event &b) const {
        if(t == b.t) {
            return dir < b.dir;
        }
        return t < b.t;
    }
};

vector<Event> event;

int main() {
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++) {
        scanf(" %d %d %d",&w,&h,&n);
        event.clear();
        for(int i = 1; i <= n; i++) {
            double x,y,a,b;
            scanf(" %lf %lf %lf %lf",&x,&y,&a,&b);
            bool fail = false;
            int l = 0,r = 0x3f3f3f3f;
            if(a != 0) {
                //Left Side
                int tls = -(x*2520/a);
                //Right Side
                int trs = (w-x)*2520/a;
                if(a > 0){
                    l = max(l,tls);
                    r = min(r,trs);
                }else{
                    l = max(l,trs);
                    r = min(r,tls);
                }
            }else{
                if(x <= 0 || x >= w){
                    fail = true;
                }
            }
            if(b != 0) {
                //Upper Side
                int tus = (h-y)*2520/b;
                //Down Side
                int tds = -(y*2520/b);
                if(b > 0){
                    l = max(l,tds);
                    r = min(r,tus);
                }else{
                    l = max(l,tus);
                    r = min(r,tds);
                }
            }else{
                if(y <= 0 || y >= h){
                    fail = true;
                }
            }
            Event tmp;
            if(!fail && l < r){
                tmp.t = l;
                tmp.dir = 1;
                event.push_back(tmp);
                tmp.t = r;
                tmp.dir = -1;
                event.push_back(tmp);
            }
        }
        sort(event.begin(),event.end());
        int cur = 0;
        int res = 0;
        for(int i = 0; i < event.size(); i++) {
            cur += event[i].dir;
            res = max(res,cur);
        }
        printf("%d\n",res);
    }

    return 0;
}

100

101

102

103

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

#include <cassert>

using namespace std;

int w,h;

int n;

struct Event {

int t;

int dir;

bool operator < (const Event &b) const {

if(t == b.t) {

return dir < b.dir;

}

return t < b.t;

}

};

vector<Event> event;

int main() {

int caseCnt;

scanf(" %d",&caseCnt);

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

scanf(" %d %d %d",&w,&h,&n);

event.clear();

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

double x,y,a,b;

scanf(" %lf %lf %lf %lf",&x,&y,&a,&b);

bool fail = false;

int l = 0,r = 0x3f3f3f3f;

if(a != 0) {

//Left Side

int tls = -(x*2520/a);

//Right Side

int trs = (w-x)*2520/a;

if(a > 0){

l = max(l,tls);

r = min(r,trs);

}else{

l = max(l,trs);

r = min(r,tls);

}

}else{

if(x <= 0 || x >= w){

fail = true;

}

if(b != 0) {

//Upper Side

int tus = (h-y)*2520/b;

//Down Side

int tds = -(y*2520/b);

if(b > 0){

l = max(l,tds);

r = min(r,tus);

}else{

l = max(l,tus);

r = min(r,tds);

}

}else{

if(y <= 0 || y >= h){

fail = true;

}

Event tmp;

if(!fail && l < r){

tmp.t = l;

tmp.dir = 1;

event.push_back(tmp);

tmp.t = r;

tmp.dir = -1;

event.push_back(tmp);

}

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

int cur = 0;

int res = 0;

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

cur += event[i].dir;

res = max(res,cur);

}

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

}

return 0;

}

UVA 11549 Calculator Conundrum

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出一个数，你要对他反复平方，平方完之后总是取运算结果的前n个十进制位（如果结果大于n位）作为答案，然后对这个答案继续进行刚才的操作。

这是一个循环的过程，你要找出在这个循环节中最大的数。

思路

首先是循环节这一点，意识到形成循环节并不难。从理论上来证明：我们可以设定一个运算＃表示相乘取前n位这一操作，初始值为a，a#1=a,1为单位元，N为所有k及k位以下整数组成的集合，两个数做运算得到的结果必然属于N，则<N,#>构成一个有限群，<a^x>必然构成循环群。

取前n位这一操作可以用字符串流，但是那样常数非常大，所以还是考虑利用数学运算来实现，这样会提高速度。

找出循环节的方法有两种，一种是开一个set，算一次insert一次，如果碰到算过的就停下。还有一种是Floyd判圈法，也就是同时维护两个数A和B，每一次令A=A^2,B=B^3,也就是B总是会比A多走一步，这样如果有环，A和B一定会相遇，在相遇时停下。

代码

Floyd判圈法，数学方法求前n位。

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

long long n;
long long k;

void nxt(long long &cur){
    cur = cur * cur;
            int cnt = 0;
            long long nxt = 0;
            long long fac = 1;
            for(int i = 1; i <= n && cur; i++){
                nxt += (cur%10)*fac;
                fac *= 10;
                cur /= 10;
            }
            fac /= 10;
            while(cur){
                nxt /= 10;
                nxt += (cur%10)*fac;
                cur /= 10;
            }
            cur = nxt;
}

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %lld %lld",&n,&k);
        long long res = k;
        long long cura = k,curb = k;
        do{
            nxt(cura);
            nxt(curb);
            res = max(res,curb);
            nxt(curb);
            res = max(res,curb);
        }while(cura != curb);
        printf("%lld\n",res);
    }
}

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

long long n;

long long k;

void nxt(long long &cur){

cur = cur * cur;

int cnt = 0;

long long nxt = 0;

long long fac = 1;

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

nxt += (cur%10)*fac;

fac *= 10;

cur /= 10;

}

fac /= 10;

while(cur){

nxt /= 10;

nxt += (cur%10)*fac;

cur /= 10;

}

cur = nxt;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

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

scanf(" %lld %lld",&n,&k);

long long res = k;

long long cura = k,curb = k;

do{

nxt(cura);

nxt(curb);

res = max(res,curb);

nxt(curb);

res = max(res,curb);

}while(cura != curb);

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

}

UVa 11078 Open Credit System

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出一个整数组成的序列，求两个整数A和B，其中A在数列的位置在B前面，令A-B最大，输出这个最大值。

思路

利用问题的单调性优化的典型例子。

暴力是O(n^2)的，显然无法通过。注意到A始终在B的前面，而且一定是A-B，也就是说对于每一个B，只要找到在它前面最大的A就可以了，不妨考虑随着B逐渐后移的同时，维护前面A的最大值，这样做的复杂度是O(n)的，很完美地解决了这个问题。

这种思想经常会被用在其他问题中作为一个需要优化的环节。

代码

#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,seq[MAXN];

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %d",&n);
        for(int i = 1; i <= n; i++){
            scanf(" %d",&seq[i]);
        }
        int res = 0x80000000;
        int mx = seq[1];
        for(int i = 2; i<= n; i++){
            res = max(res,mx-seq[i]);
            mx = max(mx,seq[i]);
        }
        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,seq[MAXN];

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

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

scanf(" %d",&n);

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

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

}

int res = 0x80000000;

int mx = seq[1];

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

res = max(res,mx-seq[i]);

mx = max(mx,seq[i]);

}

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

}

return 0;

}

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;

}