POJ – Page 3 – hahaschool

POJ3352 Road Construction / POJ3177 Redundant Paths

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给你一个联通图，问你最少要添加多少条边才能把这个图变成一个双联通图。

思路

非常经典的边双联通分量缩点问题。找出图中所有的边双联通分量，把这些分量各自收缩为一个点，节点之间若有边，一定是割边，这样就得到了一棵由边联通分量缩成的点和割边组成的树，把一个树变成双联通图要添加的最少边数是(r+1)/2其中r是这棵树的节点数量，这是一个蛮重要的结论。

找边联通分量的方法有好多，可以找到所有割边之后，对于每个点启动一次dfs，搜索中屏蔽掉所有割边，这样就可以收割所有的边双联通分量，也可以对于每个点直接启动一次tarjan算法，在函数返回的过程中，收割掉所有low值一样的节点就可以得到边双联通分量。这份代码使用的是后一种方案。

代码

两个题一个数据中有重边，一个没有，这份代码考虑了这个问题，所以连边都能顺利过，双倍经验。

//
//  POJ3552.cpp
//  playground
//
//  Copyright © 2015 Adam Chang. All rights reserved.
//

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

using namespace std;

const int MAXN = 1005;

int n = 0, m = 0;
vector<int> to[MAXN];
vector<int> to2[MAXN];

void add_edge(int a, int b){
    to[a].push_back(b);
    to[b].push_back(a);
}

void add_edge2(int a, int b){
    to2[a].push_back(b);
    to2[b].push_back(a);
}


void remove_duplicate(vector<int> *to){
    for (int i = 1; i <= n; i++) {
        sort(to[i].begin(), to[i].end());
        to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end());
    }
}

int sdcc_belong[MAXN];
stack<int> sdcc_stk;
int sdcc_dfn[MAXN];
int sdcc_low[MAXN];
vector<vector<int> > sdcc;
int sdcc_cnt = 0;

void sdcc_tarjan(int cur, int par){
    sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++;
    sdcc_stk.push(cur);
    for (int i = 0; i < to[cur].size(); i++) {
        int nxt = to[cur][i];
        if (nxt == par) {
            continue;
        }
        if (!sdcc_dfn[nxt]) {
            //如果对面点还没有进入过，那就进去
            sdcc_tarjan(nxt, cur);
            sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]);
        }else {
            //如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值
            sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]);
        }
    }
    //我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割
    if (sdcc_low[cur] == sdcc_dfn[cur]) {
        //当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了
        //generate sdcc
        int last;
        sdcc.push_back(vector<int>());
        int sdccid = (int)sdcc.size();
        do{
            last = sdcc_stk.top();
            sdcc_stk.pop();
            sdcc[sdccid-1].push_back(last);
            sdcc_belong[last] = sdccid;
        }while (cur != last);
    }
}

void get_sdcc(){
    memset(sdcc_belong, 0, sizeof(sdcc_belong));
    while (!sdcc_stk.empty()) {
        sdcc_stk.pop();
    }
    memset(sdcc_dfn, 0, sizeof(sdcc_dfn));
    memset(sdcc_low, 0, sizeof(sdcc_low));
    sdcc.clear();
    sdcc_cnt = 0;

    for (int i = 1; i <= n; i++) {
        if (!sdcc_dfn[i]) {
            sdcc_tarjan(i,0);
        }
    }
}

int main(){
    scanf(" %d %d",&n, &m);
    for (int i = 1; i <= n; i++) {
        to[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        int a = 0, b = 0;
        scanf(" %d %d",&a, &b);
        add_edge(a, b);
    }
    get_sdcc();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < to[i].size(); j++) {
            if (sdcc_belong[to[i][j]] != sdcc_belong[i]) {
                add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]);
            }
        }
    }
    remove_duplicate(to2);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (to2[i].size() == 1) {
            res++;
        }
    }
    cout << (res+1)/2 << endl;
    return 0;
}

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

// POJ3552.cpp

// playground

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

const int MAXN = 1005;

int n = 0, m = 0;

vector<int> to[MAXN];

vector<int> to2[MAXN];

void add_edge(int a, int b){

to[a].push_back(b);

to[b].push_back(a);

}

void add_edge2(int a, int b){

to2[a].push_back(b);

to2[b].push_back(a);

}

void remove_duplicate(vector<int> *to){

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

sort(to[i].begin(), to[i].end());

to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end());

}

int sdcc_belong[MAXN];

stack<int> sdcc_stk;

int sdcc_dfn[MAXN];

int sdcc_low[MAXN];

vector<vector<int> > sdcc;

int sdcc_cnt = 0;

void sdcc_tarjan(int cur, int par){

sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++;

sdcc_stk.push(cur);

for (int i = 0; i < to[cur].size(); i++) {

int nxt = to[cur][i];

if (nxt == par) {

continue;

}

if (!sdcc_dfn[nxt]) {

//如果对面点还没有进入过，那就进去

sdcc_tarjan(nxt, cur);

sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]);

}else {

//如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值

sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]);

}

//我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割

if (sdcc_low[cur] == sdcc_dfn[cur]) {

//当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了

//generate sdcc

int last;

sdcc.push_back(vector<int>());

int sdccid = (int)sdcc.size();

do{

last = sdcc_stk.top();

sdcc_stk.pop();

sdcc[sdccid-1].push_back(last);

sdcc_belong[last] = sdccid;

}while (cur != last);

}

void get_sdcc(){

memset(sdcc_belong, 0, sizeof(sdcc_belong));

while (!sdcc_stk.empty()) {

sdcc_stk.pop();

}

memset(sdcc_dfn, 0, sizeof(sdcc_dfn));

memset(sdcc_low, 0, sizeof(sdcc_low));

sdcc.clear();

sdcc_cnt = 0;

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

if (!sdcc_dfn[i]) {

sdcc_tarjan(i,0);

}

int main(){

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

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

to[i].clear();

}

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

int a = 0, b = 0;

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

add_edge(a, b);

}

get_sdcc();

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

for (int j = 0; j < to[i].size(); j++) {

if (sdcc_belong[to[i][j]] != sdcc_belong[i]) {

add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]);

}

remove_duplicate(to2);

int res = 0;

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

if (to2[i].size() == 1) {

res++;

}

cout << (res+1)/2 << endl;

return 0;

}

POJ 2909 Goldbach's Conjecture

May 27, 20152015-05-27hahaschoolLeave a comment

題意

給你個數，讓你求出有多少種素數的組合使得兩個素數的和等於給你的這個數。數據範圍比較小，小於等於32768.

思路

沒啥好的數學辦法，但是數據範圍比較小，所以不妨嘗試打個素數表看看小於32768的素數有多少，打完了發現就3000多個，這樣的話即使是O(n^2)的時間複雜度也沒有問題。我們開個計數器數組，然後枚舉素數和，加到計數器上面，預處理好這些之後，直接受理查詢就可以了。

代碼

//
//  POJ2909.cpp
//  playground
//
//  Created by Adam Chang on 2015/05/27.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//

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

using namespace std;

#define MAXN 32800

bool prime[MAXN];
vector<int> primels;
int cnt[MAXN];

bool isPrime(int n){
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void genPrime(){
    memset(prime, true, sizeof(prime));
    for (int i = 2; i < MAXN; i++) {
        if (prime[i]) {
            if (isPrime(i)) {
                for (int k = 2; k * i < MAXN; k++) {
                    prime[k*i] = false;
                }
            }else{
                prime[i] = false;
                continue;
            }
        }else{
            continue;
        }
    }
}

int main(){
    genPrime();
    for (int i = 2; i <= MAXN; i++) {
        if (prime[i]) {
            primels.push_back(i);
        }
    }
    for (int i = 0; i < primels.size(); i++) {
        for (int j = i; j < primels.size(); j++) {
            if (primels[i] + primels[j] < MAXN) {
                cnt[primels[i] + primels[j]]++;
            }
        }
    }
    int q = 0;
    while (cin >> q && q) {
        cout << cnt[q] << endl;
    }

    return 0;
}

// POJ2909.cpp

// playground

// Created by Adam Chang on 2015/05/27.

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

using namespace std;

#define MAXN 32800

bool prime[MAXN];

vector<int> primels;

int cnt[MAXN];

bool isPrime(int n){

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

if (n % i == 0) {

return false;

}

return true;

}

void genPrime(){

memset(prime, true, sizeof(prime));

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

if (prime[i]) {

if (isPrime(i)) {

for (int k = 2; k * i < MAXN; k++) {

prime[k*i] = false;

}

}else{

prime[i] = false;

continue;

}

}else{

continue;

}

int main(){

genPrime();

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

if (prime[i]) {

primels.push_back(i);

}

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

for (int j = i; j < primels.size(); j++) {

if (primels[i] + primels[j] < MAXN) {

cnt[primels[i] + primels[j]]++;

}

int q = 0;

while (cin >> q && q) {

cout << cnt[q] << endl;

}

return 0;

}

POJ 3744 Scout YYF I

April 08, 20152015-04-08hahaschoolOne Comment

题意

某人在直线上走，直线上有若干格子，起点是1号格，每次这个人都有p概率走1格，1-p概率走二格，有一些格子有地雷，走上去就被爆了，所以要你求你能安全走到终点（可以看成是站在n+1号格）上概率。

思路

每一个格子的概率都可以通过它前两个的格子的概率推出来，这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么？快速幂。
所以这个题我们用快速幂来做。

dp方程其实都不叫dp，叫递推，大概长这个样子：

$\begin{bmatrix}p&1-p\\1&0 \end{bmatrix}\begin{bmatrix}p_{n} \\ p_{n-1}\end{bmatrix}=\begin{bmatrix} p_{n+1}\\p_{n}\end{bmatrix}$

直接矩阵乘法模版＋快速幂就行。

处理地雷的话，你就先走到地雷那里，停一下，把地雷格的dp值抹成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>

using namespace std;

const int N = 2;
int n;

struct Mat {
    double mat[N][N];
};
Mat operator * (Mat a, Mat b) {
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    int i, j, k;
    for(k = 0; k < N; ++k) {
        for(i = 0; i < N; ++i) {
            for(j = 0; j < N; ++j) {
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
        }
    }
    return c;
}
Mat operator ^ (Mat a, int k) {
    Mat c;
    int i, j;
    for(i = 0; i < N; ++i)
        for(j = 0; j < N; ++j)
            c.mat[i][j] = (i == j);    //初始化为单位矩阵

    for(; k; k >>= 1) {
        if(k&1) c = c*a;

        a = a*a;
    }
    return c;
}


int main(){
    while(cin >> n){
        double p = 0;
        cin >> p;
        vector<double> mine;
        mine.push_back(0);
        for(int i = 1;i <= n;i++){
            int tmp = 0;
            cin >> tmp;
            mine.push_back(tmp);
        }
        sort(mine.begin(),mine.end());
        Mat a,b;
        double dn = 1;
        for(int i = 1;i < mine.size();i++){
            a.mat[0][0] = p;
            a.mat[0][1] = 1-p;
            a.mat[1][0] = 1;
            a.mat[1][1] = 0;
            Mat c = a^(mine[i]-mine[i-1]);
            b.mat[0][0] = 0;
            b.mat[0][1] = 0;
            b.mat[1][0] = dn;
            b.mat[1][1] = 0;
            Mat d = c * b;
            dn = d.mat[1][0];
        }
        printf("%.7f\n",dn);
    }


    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>

using namespace std;

const int N = 2;

int n;

struct Mat {

double mat[N][N];

};

Mat operator * (Mat a, Mat b) {

Mat c;

memset(c.mat, 0, sizeof(c.mat));

int i, j, k;

for(k = 0; k < N; ++k) {

for(i = 0; i < N; ++i) {

for(j = 0; j < N; ++j) {

c.mat[i][j] += a.mat[i][k] * b.mat[k][j];

}

return c;

}

Mat operator ^ (Mat a, int k) {

Mat c;

int i, j;

for(i = 0; i < N; ++i)

for(j = 0; j < N; ++j)

c.mat[i][j] = (i == j); //初始化为单位矩阵

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

if(k&1) c = c*a;

a = a*a;

}

return c;

}

int main(){

while(cin >> n){

double p = 0;

cin >> p;

vector<double> mine;

mine.push_back(0);

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

int tmp = 0;

cin >> tmp;

mine.push_back(tmp);

}

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

Mat a,b;

double dn = 1;

for(int i = 1;i < mine.size();i++){

a.mat[0][0] = p;

a.mat[0][1] = 1-p;

a.mat[1][0] = 1;

a.mat[1][1] = 0;

Mat c = a^(mine[i]-mine[i-1]);

b.mat[0][0] = 0;

b.mat[0][1] = 0;

b.mat[1][0] = dn;

b.mat[1][1] = 0;

Mat d = c * b;

dn = d.mat[1][0];

}

printf("%.7f\n",dn);

}

return 0;

}

POJ 2096 Collecting Bugs

April 07, 20152015-04-07hahaschoolLeave a comment

题意

给软件挑bug，每天挑出来一个，每个bug都有两个属性：分类和子系统，这两个属性都是完全随机的，已知一共有n个分类，s个子系统，问你挑出的bug完全覆盖全部分类和子系统需要多长时间（求期望）。

思路

优惠券问题的变种，相当于升高到了二维，因此dp数组也要开成二维。

我们设定dp[i][j]表示距离完成任务还有i个分类j个子系统没有覆盖，状态的转移用如下几种：
1.挑出的bug属于全新的分类和子系统
2.挑出的bug仅仅属于全新的分类
3.挑出的bug仅仅属于全新的子系统
4.挑出的bug没有任何新意
这样，我们可以得出状态转移方程： $dp[i][j]=\frac{i}{n}\frac{j}{s}dp[i-1][j-1]+\frac{n-i}{n}\frac{j}{s}dp[i][j-1]+\frac{i}{n}\frac{n-j}{s}dp[i-1][j]+\frac{n-i}{n}\frac{n-j}{s}dp[i][j]+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>

using namespace std;

double dp[1010][1010];

int main(){
    int in = 0,im = 0;
    while (cin >> in >> im) {
        double n = in,m = im;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        for (int ii = 1; ii <= in; ii++) {
            double i = ii;
            dp[ii][0] = dp[ii-1][0] + n/i;
        }
        for (int ii = 1; ii <= im; ii++) {
            double i = ii;
            dp[0][ii] = dp[0][ii-1] + m/i;
        }
        for (int ii = 1; ii <= in; ii++) {
            for (int ij = 1; ij <= im; ij++) {
                double i = ii,j = ij;
                dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n;
                dp[ii][ij] /= m*n-(n-i)*(m-j);
            }
        }
        printf("%.4lf\n",dp[in][im]);
    }
    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>

using namespace std;

double dp[1010][1010];

int main(){

int in = 0,im = 0;

while (cin >> in >> im) {

double n = in,m = im;

memset(dp, 0, sizeof(dp));

dp[0][0] = 0;

for (int ii = 1; ii <= in; ii++) {

double i = ii;

dp[ii][0] = dp[ii-1][0] + n/i;

}

for (int ii = 1; ii <= im; ii++) {

double i = ii;

dp[0][ii] = dp[0][ii-1] + m/i;

}

for (int ii = 1; ii <= in; ii++) {

for (int ij = 1; ij <= im; ij++) {

double i = ii,j = ij;

dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n;

dp[ii][ij] /= m*n-(n-i)*(m-j);

}

printf("%.4lf\n",dp[in][im]);

}

return 0;

}

POJ 3488 Arne Saknussemm

April 07, 20152015-04-07hahaschoolLeave a comment

题意

这个题的目的是练习读题，所以请努力理解这个题的题意，这里故意不翻译，it’s good for you~。

思路

操作时需要注意，string对象的结束位置并不是像char数组那样用’\0‘标记的，除非string对象被重做，否则这个对象的size值不会改变，即使你把一个string对象的每个字符全都弄成’\0’，你输出的也不是空串，而是一堆不可见的’\0’。

如果这个题很神秘的WA到死，请检查一下是不是跪在了不可见字符上。

代码

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

using namespace std;

char grid[2001][2001];

int main(){
    int fragCnt = 0;
    while (scanf(" %d",&fragCnt) != EOF){
        memset(grid,0,sizeof(grid));
        for (int i = 1; i <= fragCnt; i++) {
            scanf(" %s",grid[i]);
        }
        int len = (int)strlen(grid[1]);
        string target;
        for (int i = len-1; i >= 0; i--) {
            for (int j = fragCnt; j >= 1; j--) {
                    target += grid[j][i];
            }
        }
        for (int i = (int)target.size()-1; i >= 0; i--) {
            if (target[i] == '_') {
                target[i] = 0;
            }else{
                break;
            }
        }
        for (int i = 0; i < target.size(); i++) {
            if (target[i] == 0) {
                break;
            }//结尾的char＝0也会被输出，string的size在修改末尾字符为0时不会更新
            if (target[i] == '\\') {
                putchar('\n');
            }else if(target[i] == '_'){
                putchar(' ');
            }else{
                putchar(target[i]);
            }
        }
        printf("\n\n");
    }
    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>

using namespace std;

char grid[2001][2001];

int main(){

int fragCnt = 0;

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

memset(grid,0,sizeof(grid));

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

scanf(" %s",grid[i]);

}

int len = (int)strlen(grid[1]);

string target;

for (int i = len-1; i >= 0; i--) {

for (int j = fragCnt; j >= 1; j--) {

target += grid[j][i];

}

for (int i = (int)target.size()-1; i >= 0; i--) {

if (target[i] == '_') {

target[i] = 0;

}else{

break;

}

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

if (target[i] == 0) {

break;

}//结尾的char＝0也会被输出，string的size在修改末尾字符为0时不会更新

if (target[i] == '\\') {

putchar('\n');

}else if(target[i] == '_'){

putchar(' ');

}else{

putchar(target[i]);

}

printf("\n\n");

}

return 0;

}

POJ 1019 Number Sequence

April 07, 20152015-04-07hahaschoolLeave a comment

题意

11212312341234512345612345671234567812345678912345678910123456789101112345678910…
让你求这么一个丧心病狂的数列第i位是啥。

思路

找规律，我们可以把数列切割为1/12/123/1234/…这样我们可以想办法求出每一段的控制范围，然后对于给出的i，先快速确定这个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>

using namespace std;

long long dp[100000];

int main(){
    for (int i = 1; i<= 100000; i++) {
        long long tmp = 0;
        long long base = 0;
        while (i-base > 0) {
            tmp += i-base;
            base = base*10 + 9;
        }
        dp[i] = dp[i-1] + tmp;
    }

    int caseCnt = 0;
    cin >> caseCnt;
    while (caseCnt--) {
        long long n = 0;
        cin >> n;
        long long pos = lower_bound(dp+1, dp+100000, n) - dp;
        pos--;
        n -= dp[pos];

        long long judge = 10;
        long long fact = 1;
        while (n / fact >= judge) {
            fact++;
            n += judge - 1;
            judge *= 10;
        }
        char num[1000];
        memset(num, 0, sizeof(num));
        sprintf(num, "%lld%lld",(n/fact)%10,(n/fact+1));
        cout << num[n%fact] << endl;
    }
    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>

using namespace std;

long long dp[100000];

int main(){

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

long long tmp = 0;

long long base = 0;

while (i-base > 0) {

tmp += i-base;

base = base*10 + 9;

}

dp[i] = dp[i-1] + tmp;

}

int caseCnt = 0;

cin >> caseCnt;

while (caseCnt--) {

long long n = 0;

cin >> n;

long long pos = lower_bound(dp+1, dp+100000, n) - dp;

pos--;

n -= dp[pos];

long long judge = 10;

long long fact = 1;

while (n / fact >= judge) {

fact++;

n += judge - 1;

judge *= 10;

}

char num[1000];

memset(num, 0, sizeof(num));

sprintf(num, "%lld%lld",(n/fact)%10,(n/fact+1));

cout << num[n%fact] << endl;

}

return 0;

}

POJ 3685 Matrix

April 07, 20152015-04-07hahaschoolLeave a comment

题意

好像是《挑战程序设计竞赛》上面的原题。题意是给你一个矩阵上每一项的位置与值对应的公式，让你求第k小的项。

思路

我们仔细看公式会发现对于每一个固定的j，公式结果随i单调递增，这样我们可以二分答案，对于mid值，我们在每一列再二分一次，求出比这个数小的数的个数，然后每一列的个数相加，就是这个数的排名。然后这个排名可以作为二分中判定的基准。这里还有一种替代思路，就是对于每一列不二分，而是解一个二次方程直接求出每一列的分排名。

代码

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

using namespace std;

inline long long f(long long i,long long j){
    return i*i+j*j+100000*i+i*j-100000*j;
}
bool ok(long long MID,long long n,long long m){
    long long cnt = 0;
    for (int j = 1; j <= n; j++) {
        long long high = n+1,low = 1,mid = (n+2)/2;
        while (high > low) {

            if (f(mid,j) >= MID) {
                high = mid;
            }else{
                low = mid+1;
            }
            mid = (high+low)>>1;
        }
        cnt += mid-1;
    }
    return cnt >= m;
}


int main(){
    int caseCnt = 0;
    scanf(" %d",&caseCnt);
    for (int xi = 1;xi <= caseCnt; xi++) {
        long long n = 0,m = 0;
        scanf(" %lld %lld",&n,&m);
        long long high = 1e12,low = -1e12,mid = 0;

        while (high > low) {
            if (ok(mid,n,m)) {
                high = mid;
            }else{
                low = mid+1;
            }
            mid = (high+low)>>1;
        }
        printf("%lld\n",mid-1);
    }
    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>

using namespace std;

inline long long f(long long i,long long j){

return i*i+j*j+100000*i+i*j-100000*j;

}

bool ok(long long MID,long long n,long long m){

long long cnt = 0;

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

long long high = n+1,low = 1,mid = (n+2)/2;

while (high > low) {

if (f(mid,j) >= MID) {

high = mid;

}else{

low = mid+1;

}

mid = (high+low)>>1;

}

cnt += mid-1;

}

return cnt >= m;

}

int main(){

int caseCnt = 0;

scanf(" %d",&caseCnt);

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

long long n = 0,m = 0;

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

long long high = 1e12,low = -1e12,mid = 0;

while (high > low) {

if (ok(mid,n,m)) {

high = mid;

}else{

low = mid+1;

}

mid = (high+low)>>1;

}

printf("%lld\n",mid-1);

}

return 0;

}

POJ 3740 Easy Finding

February 20, 20152015-02-20hahaschoolLeave 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>

using namespace std;

int board[17][301];

int now[301];

bool check(int n){
    for (int i = 1; i <= n; i++) {
        if (now[i] != 1) {
            return false;
        }
    }
    return true;
}

bool legal(int n){
    for (int i = 1; i <= n; i++) {
        if (now[i] > 1) {
            return false;
        }
    }
    return true;
}


bool dfs(int m,int n,int cur){
    if (check(n)) {
        return true;
    }
    if (cur > m) {
        return false;
    }
    for (int i = 1;i <= n; i++) {
        now[i] += board[cur][i];
    }
    if (legal(n)) {
        if (dfs(m, n, cur+1)) {
            return true;
        }
    }
    for (int i = 1; i <= n; i++) {
        now[i] -= board[cur][i];
    }
    return dfs(m, n, cur+1);
}


int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&m,&n) != EOF) {
        memset(board, 0, sizeof(board));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                scanf(" %d",&board[i][j]);
            }
        }
        memset(now, 0, sizeof(now));
        if (dfs(m, n, 1)) {
            printf("Yes, I found itn");
        }else{
            printf("It is impossiblen");
        }
    }


    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>

using namespace std;

int board[17][301];

int now[301];

bool check(int n){

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

if (now[i] != 1) {

return false;

}

return true;

}

bool legal(int n){

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

if (now[i] > 1) {

return false;

}

return true;

}

bool dfs(int m,int n,int cur){

if (check(n)) {

return true;

}

if (cur > m) {

return false;

}

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

now[i] += board[cur][i];

}

if (legal(n)) {

if (dfs(m, n, cur+1)) {

return true;

}

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

now[i] -= board[cur][i];

}

return dfs(m, n, cur+1);

}

int main(){

int n = 0,m = 0;

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

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

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

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

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

}

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

if (dfs(m, n, 1)) {

printf("Yes, I found itn");

}else{

printf("It is impossiblen");

}

return 0;

}

搜索题，但是BFS不可以，DFS的话优化还特别寸，写了几个版本都过不了，挺邪乎的。

PS：好长时间没做题，想必是遭了报应了。

POJ 3624 Charm Bracelet 顺便讲一下01背包

January 26, 20152015-01-26hahaschoolLeave a comment

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

using namespace std;

struct nodeType{
    int w,d;
    nodeType(int iw,int id){
        w = iw;
        d = id;
    }
};

int dp[2][13000];

int main(){
    int n = 0, m = 0;
    while (cin >> n >> m) {
        vector<nodeType> node;
        for (int i = 1; i <= n; i++) {
            int iw = 0,id = 0;
            cin >> iw >> id;
            node.push_back(nodeType(iw,id));
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j-node[i-1].w >= 0) {
                    dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]);
                }else{
                    dp[i%2][j] = dp[(i-1)%2][j];
                }
            }
        }
        cout << dp[node.size()%2][m] << endl;
    }

    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

struct nodeType{

int w,d;

nodeType(int iw,int id){

w = iw;

d = id;

}

};

int dp[2][13000];

int main(){

int n = 0, m = 0;

while (cin >> n >> m) {

vector<nodeType> node;

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

int iw = 0,id = 0;

cin >> iw >> id;

node.push_back(nodeType(iw,id));

}

memset(dp, 0, sizeof(dp));

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

for (int j = 0; j <= m; j++) {

if (j-node[i-1].w >= 0) {

dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]);

}else{

dp[i%2][j] = dp[(i-1)%2][j];

}

cout << dp[node.size()%2][m] << endl;

}

return 0;

}

裸的01背包问题，是DP的基础题型了，没有太多好说的。

简要说一下01背包问题的状态转移特点：按两个基准纪录数据，第一个基准是我们从0～a号物品中选，第二个基准是选择的物品已经有了多少重量b，这样组成了dp数组dp[a][b]，这个数组存储的是当前状态的价值是多少。接下来我们开始dp，对于每一个当前状态（最多选择到第n个物品，已经占用了w重量），我们是从两种先前状态中导出的：1.最多选择到n－1个物品（就是当前物品还没有考虑呢），占用重量w－x（x是第n个物品重量），在这个状态上，我们添加上第n个物品。2.最多选择到n－1个物品，占用重量w，在这个状态上，我们什么也不做，直接把他当成当前状态。

在这两种先前状态中选择最好的那个（有时候因为某些原因，只能选择一个，那就选唯一的那个就好），保存下来决定为当前状态，再供以后使用。

这样我们只要读取dp[i][j]的值，就是“选择1～i中的物品，重量限定为j，最高价值是？”这个问题的答案。（没有用滚动数组的话）

POJ 1062 昂贵的聘礼

January 25, 20152015-01-25hahaschoolLeave a comment

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

 using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{
    int to;
    int cost;
    edgeType(int ito,int icost){
        to = ito;
        cost = icost;
    }
};

struct vertexType{
    vector<edgeType> edge;
    int cost;
    int level;
    vertexType(int icost,int ilevel){
        edge.clear();
        cost = icost;
        level = ilevel;
    }
};

int main(){
    int m = 0,n = 0;
    while (cin >> m >> n) {
        vector<vertexType> vertex;
        for (int i = 0; i < n; i++) {
            int vcost,vlevel,vsub;
            cin >> vcost >> vlevel >> vsub;
            vertexType now(vcost,vlevel);
            while (vsub--) {
                int to,cost;
                cin >> to >> cost;
                edgeType tmp(to-1,cost);
                now.edge.push_back(tmp);
            }
            vertex.push_back(now);
        }

        int maxlv = vertex[0].level,minlv = vertex[0].level;
        bool vis[105];
        int dis[105];
        memset(vis, 0, sizeof(vis));
        memset(dis, 0x3f3f, sizeof(dis));
        dis[0] = vertex[0].cost;
        while (true) {
            int cur = -1;
            int mindis = MAXN;
            for (int i = 0; i < vertex.size(); i++) {
                if (vis[i]) {
                    continue;
                }
                if (dis[i] < mindis) {
                    mindis = dis[i];
                    cur = i;
                }
            }
            if (cur == -1) break;

            vertexType nowvertex = vertex[cur];
            vis[cur] = true;
            maxlv = max(nowvertex.level,maxlv);
            minlv = min(nowvertex.level,minlv);
            //int nowlv = nowvertex.level;
            for (int i = 0; i < vertex[cur].edge.size(); i++) {
                edgeType nextedge = vertex[cur].edge[i];
                vertexType nextvertex = vertex[nextedge.to];
                if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) {
                    continue;
                }
                int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost;
                if (newcost < dis[nextedge.to]) {
                    dis[nextedge.to] = newcost;
                }
            }
        }
        int res = MAXN;
        for (int i = 0; i < n; i++) {
            res = min(dis[i], res);
        }
        cout << res << endl;
    }

    return 0;
}

100

101

102

103

104

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{

int to;

int cost;

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

vector<edgeType> edge;

int cost;

int level;

vertexType(int icost,int ilevel){

edge.clear();

cost = icost;

level = ilevel;

}

};

int main(){

int m = 0,n = 0;

while (cin >> m >> n) {

vector<vertexType> vertex;

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

int vcost,vlevel,vsub;

cin >> vcost >> vlevel >> vsub;

vertexType now(vcost,vlevel);

while (vsub--) {

int to,cost;

cin >> to >> cost;

edgeType tmp(to-1,cost);

now.edge.push_back(tmp);

}

vertex.push_back(now);

}

int maxlv = vertex[0].level,minlv = vertex[0].level;

bool vis[105];

int dis[105];

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

memset(dis, 0x3f3f, sizeof(dis));

dis[0] = vertex[0].cost;

while (true) {

int cur = -1;

int mindis = MAXN;

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

if (vis[i]) {

continue;

}

if (dis[i] < mindis) {

mindis = dis[i];

cur = i;

}

if (cur == -1) break;

vertexType nowvertex = vertex[cur];

vis[cur] = true;

maxlv = max(nowvertex.level,maxlv);

minlv = min(nowvertex.level,minlv);

//int nowlv = nowvertex.level;

for (int i = 0; i < vertex[cur].edge.size(); i++) {

edgeType nextedge = vertex[cur].edge[i];

vertexType nextvertex = vertex[nextedge.to];

if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) {

continue;

}

int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost;

if (newcost < dis[nextedge.to]) {

dis[nextedge.to] = newcost;

}

int res = MAXN;

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

res = min(dis[i], res);

}

cout << res << endl;

}

return 0;

}

这个题是一个比较基准有些多的最短路（和之前那个Dirt挺像）。

（这里的cost就是dijkstra算法里面的dis值）每一次更新下一节点时，下一节点的cost值为（当前cost值－当前点权＋下一边边权＋下一点点权）；每一次到达节点后，都根据当前抽出的节点的地位值，更新当前走过节点的地位的最大最小值，等接下来更新临接节点时，如果下一节点的地位与当前最大最小值中任意一个只差绝对值>m就要抛弃。以这两个为基准，进行正常的dijkstra，然后从头到尾的扫一遍cost数组，把最小值输出来就是答案。