SGU 103 Traffic Lights

March 22, 20152015-03-22hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/103
翻译版，这里不重复劳动了

思路

这个题的可怕之处不是有多难想，而是虽然基本模型很简单就是图上最短路，但是这回有许多许多的限制条件。
正确地计算当前灯的状态是这个题最大的难点，我采用的方法是（其实我写跪了，李大神给我捞上来的）：首先把到这个路口已经消耗的时间减去题目给的初始时间，我叫他有效时间，接下来把这个有效时间模上两种颜色的灯持续时间之和，剩下的时间是对灯的状态真正有影响的时间，接下来分别脑内模拟一下站在这个路灯时如果是紫色最后会怎么变，如果是蓝色会怎么变，然后基本就可以写出这个时间和最终颜色的关系了，还可以得到最终这个颜色还能再持续多长时间，这两条非常重要，一定要搞对。
接下来的难点就是计算从当前点移动到下一个点之前等待两点灯的颜色同步的时间，算这个就要依赖于上面的两个值：当前颜色和当前颜色还剩多长时间，假设我们要从A点移动到B，已经走了tim时间，那么我们就要分别计算A点和B点在tim时的这两个数据，然后如果AB在tim时颜色正好相等，那么无需等待直接通行，所以等待时间为0，如果颜色不同呢？只要看A和B哪个剩余的时间短，这个就是等待时间了。要是剩余的时间又一样？那就要脑内模拟一下了，然后发现我们可以再比较A的下一颜色和B的下一颜色谁的持续时间短，等待时间就是剩余时间＋最短的持续时间。如果下一个颜色还一样，那就比较下下个颜色。要是还一样？对不起，hehe了，走别的吧～（所以说这个题很sxbk)
接下来是最段路部分，我们把权值设定为走到这个点要花多少时间，从当前点走到下一个点时，下一个点的可能值就是(当前点已用时间+等待两个点的灯同步的时间+路上消耗的时间)，以此为基准进行松弛操作。

接下来上代码

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

int str = 0,ter = 0;
int n = 0,m = 0;

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

struct vertexType{
    char color;
    int init;
    int blue;
    int purple;
    int pre;//for backtracking
    int dis;
    vector<edgeType> edge;
    vertexType(){
        color = 0;
        init = 0;
        blue = 0;
        purple = 0;
        pre = 0;
        dis = 0x3f3f3f3f;
        edge.clear();
    }
} vertex[305];

char getColor(int timepast,int a){
    vertexType &av = vertex[a];
    int atime = (timepast % (av.blue+av.purple)) - av.init;
    if (av.color == 'P') {
        if (atime < 0) {
            return 'P';
        }else if(atime < av.blue){
            return 'B';
        }else{
            return 'P';
        }
    }else{
        if (atime < 0) {
            return 'B';
        }else if(atime < av.purple){
            return 'P';
        }else{
            return 'B';
        }
    }
}
char getTime(int timepast,int a){
    vertexType &av = vertex[a];
    int atime = (timepast %(av.blue+av.purple)) - av.init;
    if (av.color == 'P') {
        if (atime < 0) {
            return -atime;
        }else if(atime < av.blue){
            return av.blue-atime;
        }else{
            return av.blue+av.purple-atime;
        }
    }else{
        if (atime < 0) {
            return -atime;
        }else if(atime < av.purple){
            return av.purple-atime;
        }else{
            return av.blue+av.purple-atime;
        }
    }
}

int waitTime(int a,int b){
    //from a to b
    vertexType &av = vertex[a];
    vertexType &bv = vertex[b];
    int atime = getTime(av.dis, a);
    int btime = getTime(av.dis, b);
    char acolor = getColor(av.dis,a);
    char bcolor = getColor(av.dis,b);
    if (acolor == bcolor) {
        return 0;
    }
    if (abs(atime - btime)) {
        return min(atime,btime);
    }else if(acolor == 'P'){
        if (abs(av.blue-bv.purple)) {
            return atime+min(av.blue,bv.purple);
        }else if(abs(av.purple-bv.blue)){
            return atime+av.blue+min(av.purple,bv.blue);
        }else{
            return -1;
        }
    }else if(acolor == 'B'){
        if (abs(av.purple-bv.blue)) {
            return atime+min(av.purple,bv.blue);
        }else if(abs(av.blue-bv.purple)){
            return atime+av.purple+min(av.blue,bv.purple);
        }else{
            return -1;
        }
    }else{
        return -1;
    }
}

struct cmp{
    bool operator () (int a,int b){
        return vertex[a].dis > vertex[b].dis;
    }
};

void dijkstra(){
    vertex[str].dis = 0;
    priority_queue<int,vector<int>,cmp> q;
    q.push(str);
    bool vis[305];
    memset(vis, 0, sizeof(vis));
    while (!q.empty()) {
        int nown = q.top();
        q.pop();
        vis[nown] = true;
        vertexType &nowv = vertex[nown];
        for (int i = 0; i < nowv.edge.size(); i++) {
            int nextn = nowv.edge[i].to;
            vertexType &nextv = vertex[nextn];
            if (vis[nextn]) {
                continue;
            }
            int wait = waitTime(nown,nextn);
            if (wait == -1) {
                continue;
            }
            if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) {
                //relax
                nextv.dis = wait + nowv.dis + nowv.edge[i].cost;
                nextv.pre = nown;
                q.push(nextn);
            }
        }
    }

}



int main(){
    scanf(" %d %d %d %d",&str,&ter,&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple);
    }
    for (int i = 1; i <= m; i++) {
        int a = 0,b = 0,c = 0;
        scanf(" %d %d %d",&a,&b,&c);
        vertex[a].edge.push_back(edgeType(b,c));
        vertex[b].edge.push_back(edgeType(a,c));
    }
    dijkstra();
    if (vertex[ter].dis == 0x3f3f3f3f) {
        printf("0\n");
        return 0;
    }
    printf("%d\n",vertex[ter].dis);
    stack<int> path;
    int curr = ter;
    while (curr) {
        path.push(curr);
        curr = vertex[curr].pre;
    }
    while (path.size()>1) {
        printf("%d ",path.top());
        path.pop();
    }
    printf("%d\n",path.top());
    path.pop();

    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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

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

int str = 0,ter = 0;

int n = 0,m = 0;

struct edgeType{

int to;

int cost;

edgeType(){

to = 0;

cost = 0;

}

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

char color;

int init;

int blue;

int purple;

int pre;//for backtracking

int dis;

vector<edgeType> edge;

vertexType(){

color = 0;

init = 0;

blue = 0;

purple = 0;

pre = 0;

dis = 0x3f3f3f3f;

edge.clear();

}

} vertex[305];

char getColor(int timepast,int a){

vertexType &av = vertex[a];

int atime = (timepast % (av.blue+av.purple)) - av.init;

if (av.color == 'P') {

if (atime < 0) {

return 'P';

}else if(atime < av.blue){

return 'B';

}else{

return 'P';

}

}else{

if (atime < 0) {

return 'B';

}else if(atime < av.purple){

return 'P';

}else{

return 'B';

}

char getTime(int timepast,int a){

vertexType &av = vertex[a];

int atime = (timepast %(av.blue+av.purple)) - av.init;

if (av.color == 'P') {

if (atime < 0) {

return -atime;

}else if(atime < av.blue){

return av.blue-atime;

}else{

return av.blue+av.purple-atime;

}

}else{

if (atime < 0) {

return -atime;

}else if(atime < av.purple){

return av.purple-atime;

}else{

return av.blue+av.purple-atime;

}

int waitTime(int a,int b){

//from a to b

vertexType &av = vertex[a];

vertexType &bv = vertex[b];

int atime = getTime(av.dis, a);

int btime = getTime(av.dis, b);

char acolor = getColor(av.dis,a);

char bcolor = getColor(av.dis,b);

if (acolor == bcolor) {

return 0;

}

if (abs(atime - btime)) {

return min(atime,btime);

}else if(acolor == 'P'){

if (abs(av.blue-bv.purple)) {

return atime+min(av.blue,bv.purple);

}else if(abs(av.purple-bv.blue)){

return atime+av.blue+min(av.purple,bv.blue);

}else{

return -1;

}

}else if(acolor == 'B'){

if (abs(av.purple-bv.blue)) {

return atime+min(av.purple,bv.blue);

}else if(abs(av.blue-bv.purple)){

return atime+av.purple+min(av.blue,bv.purple);

}else{

return -1;

}

}else{

return -1;

}

struct cmp{

bool operator () (int a,int b){

return vertex[a].dis > vertex[b].dis;

}

};

void dijkstra(){

vertex[str].dis = 0;

priority_queue<int,vector<int>,cmp> q;

q.push(str);

bool vis[305];

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

while (!q.empty()) {

int nown = q.top();

q.pop();

vis[nown] = true;

vertexType &nowv = vertex[nown];

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

int nextn = nowv.edge[i].to;

vertexType &nextv = vertex[nextn];

if (vis[nextn]) {

continue;

}

int wait = waitTime(nown,nextn);

if (wait == -1) {

continue;

}

if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) {

//relax

nextv.dis = wait + nowv.dis + nowv.edge[i].cost;

nextv.pre = nown;

q.push(nextn);

}

int main(){

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

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

scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple);

}

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

int a = 0,b = 0,c = 0;

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

vertex[a].edge.push_back(edgeType(b,c));

vertex[b].edge.push_back(edgeType(a,c));

}

dijkstra();

if (vertex[ter].dis == 0x3f3f3f3f) {

printf("0\n");

return 0;

}

printf("%d\n",vertex[ter].dis);

stack<int> path;

int curr = ter;

while (curr) {

path.push(curr);

curr = vertex[curr].pre;

}

while (path.size()>1) {

printf("%d ",path.top());

path.pop();

}

printf("%d\n",path.top());

path.pop();

return 0;

}

Codeforces 118D Caesar's Legions

March 22, 20152015-03-22hahaschoolLeave a comment

题意

给你两种士兵，n1个A和n2个B，同种士兵是一样的，不分先后，然后你最多能把k1个A排到一起k2个B排到一起，问你有多少种有效排法。

思路

动态规划，建一个三维dp数组，其实是一个二维的表，每个格子有两个值，dp[i][j]表示截至目前只使用i个A，j个B来进行排列，dp[i][j][0]表示以A结尾的排列序列个数,dp[i][j][1]表示以B结尾的排列序列个数，之后我们来转移状态，对于当前的以A结尾的排列，我们可以再其末尾加1～k2个B，构成新的以B结尾的排列，所以我们就可以把dp[i][j+k][1]更新了（k表示加几个B）。同样的，用B结尾排列个数的值更新之后的A结尾排列个数的值，把这个表这样逐步打好，最后输出dp[n1][n2][0]+dp[n1][n2][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;

int dp[120][120][2];

#define MODER 100000000

int main(){
    int n1 = 0,n2 = 0,k1 = 0,k2 = 0;
    memset(dp, 0, sizeof(dp));
    cin >> n1 >> n2 >> k1 >> k2;
    for (int i = 1; i <= k1; i++) {
        dp[i][0][0] = 1;
    }
    for (int j = 1; j <= k2; j++) {
        dp[0][j][1] = 1;
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            for (int k = 1; k <= k2; k++) {
                dp[i][j+k][1] += dp[i][j][0] % MODER;
                dp[i][j+k][1] %= MODER;
            }
        }
        for (int j = 1; j <= 100; j++) {
            for (int k = 1; k <= k1; k++) {
                dp[i+k][j][0] += dp[i][j][1] % MODER;
                dp[i+k][j][0] %= MODER;
            }
        }
    }
    cout << (dp[n1][n2][0]+dp[n1][n2][1]+MODER)%MODER << 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;

int dp[120][120][2];

#define MODER 100000000

int main(){

int n1 = 0,n2 = 0,k1 = 0,k2 = 0;

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

cin >> n1 >> n2 >> k1 >> k2;

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

dp[i][0][0] = 1;

}

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

dp[0][j][1] = 1;

}

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

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

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

dp[i][j+k][1] += dp[i][j][0] % MODER;

dp[i][j+k][1] %= MODER;

}

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

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

dp[i+k][j][0] += dp[i][j][1] % MODER;

dp[i+k][j][0] %= MODER;

}

cout << (dp[n1][n2][0]+dp[n1][n2][1]+MODER)%MODER << endl;

return 0;

}

CodeForces 347C Alice and Bob

March 22, 20152015-03-22hahaschoolLeave a comment

题意

两个人互相玩，他们先搞一个集合，里面几个不同的数，接下来随便挑俩作差，如果差的绝对值集合里没有，就给这个差的绝对值加进去，直到集合加不进去值为止，没招的那位就跪了。

思路

写几个数模拟一下就会发现，游戏结束时，集合里面是所有的初始几个值的最大公约数的倍数，举个例子init={2,6,8},gcd=2,final={2,4,6,8}，利用这个规律我们就可以知道最终集合有几个元素，最终元素个数减去初始元素个数就是这场比赛将在多少手之后结束，接下来判断奇偶就可以判断谁赢了。

接下来上代码

#include <iostream>
#include <vector>

using namespace std;

long long gcd(long long a,long long b){
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}
long long lcm(long long x,long long y){

    return x*y/gcd(x, y);
}

int main(){

    int n = 0;
    cin >> n;
    long long maxn = 0;
    long long g = 1;
    cin >> maxn;
    g = maxn;
    for (int i = 1; i <= n-1; i++) {
        long long tmp = 0;
        cin >> tmp;
        maxn = max(maxn,tmp);
        g = gcd(g,tmp);
    }

    if ((maxn/g - n)&1) {
        cout << "Alice" << endl;
    }else{
        cout << "Bob" << endl;
    }
    return 0;

}

#include <iostream>

#include <vector>

using namespace std;

long long gcd(long long a,long long b){

if (b == 0) {

return a;

}

return gcd(b, a%b);

}

long long lcm(long long x,long long y){

return x*y/gcd(x, y);

}

int main(){

int n = 0;

cin >> n;

long long maxn = 0;

long long g = 1;

cin >> maxn;

g = maxn;

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

long long tmp = 0;

cin >> tmp;

maxn = max(maxn,tmp);

g = gcd(g,tmp);

}

if ((maxn/g - n)&1) {

cout << "Alice" << endl;

}else{

cout << "Bob" << endl;

}

return 0;

}

从零开始,把Raspberry Pi打造成双栈11n无线路由器,支持教育网原生IPv6

March 22, 20152015-03-22hahaschool13 Comments

准备工作

Raspberry Pi一块
- 要求已经刷写好了Raspbian系统，关于系统的刷写／无显示器配置这种事情，请参照这里，这里不想多说。
USB无线网卡一枚,一个合格的USB无线网卡最好是不用USB HUB就能稳定运作的，插上之后，在终端机中输入ifconfig输出内容中应该有出现wlan0字样。
- 无论你有没有现成的USB无线网卡，都请查看USB无线网卡对RPi兼容性列表来确定自己的USB无线网卡是不是支持RPi，如果是杂牌的话，要想办法看到自己的USB无线网卡的芯片型号，然后对照这个表里面有同样型号的无线网卡的兼容性说明。如果你现在无线网卡的芯片在这个表里面不是针对Raspbian out of box的，买买买，不要停～
- AP功能是一定要有的，如果有11n的话更好（后面会讲如何设置），目前来说直到RPi 2 Model B都没有实装USB 3.0所以没有必要买ac的无线网卡。
- 我用的是Tenda W311U+,这款有个天线，不过貌似也没啥太大的效果，用起来蛮稳定，速度一般（即使打开了11n机能）
外网，这篇教程针对的是没有认证的，原生支持IPv6的教育网，有固定IP。
- 如果你的网络需要认证客户端的话，可以找个借口（用mac什么的）把认证取消，取消不了的话。。。别折腾了～（当然如果你真想折腾，openwrt社区里面会有dalao提供linux的模拟验证客户端，但是这个不在本文讨论之列）
- 如果你是ADSL用户，本文没有拨号设定，IPv6也需要tunnel,这种情况，建议移步这里
- 如果你不想折腾IPv6有关机能，忽略本文的IPv6部分即可，同样的，不想开11n的话，也可以忽略本文的11n设定部分。
确定你的有线无线网卡代号，在终端机中输入ifconfig就可以看到当前连接的所有网络接口，有线网络一般是eth开头，RPi的自带网卡一般是eth0，你连接的无线网卡一般是wlan开头，只插一个的话就是wlan0，这个是给内网用的。下文中的eth0和wlan0就是这么来的，如果不一样的话请自行翻译～

开工！先来配置IPv4无线路由

配置网络接口

在终端机中输入sudo emacs /etc/network/interfaces打开网络接口配置文件，狂按Ctrl+k清除全部内容，然后写入一下内容，完成后按Control+x,Control+c,y保存退出（放弃更改的话Ctrl+x,Ctrl+c,n,yes<换行键>）。

auto lo
iface lo inet loopback

iface eth0 inet static #如果你的IP是自动分配的，把static改成dhcp，然后去掉下面三行就可以了
      address 125.216.249.000 #改成学校给你的固定IP
      netmask 255.255.255.0 #学校给你的子网掩码
      gateway 125.216.249.254 #学校给你的网关
iface eth0 inet6 manual #IPv6设定，不管他

iface wlan0 inet static
      address 10.0.0.1 #内网网关(可以理解成路由器)地址,也可以写成192.168.1.1什么的，那样的话本文后面的部分你也要做相应的改动了。
      netmask 255.255.255.0 #内网子网掩码，虽然是A段网络，但RPi显然没有NB到能拖那么多设备，所以三个255就够用。
iface wlan0 inet6 manual #IPv6设定，不管他

auto lo

iface lo inet loopback

iface eth0 inet static #如果你的IP是自动分配的，把static改成dhcp，然后去掉下面三行就可以了

address 125.216.249.000 #改成学校给你的固定IP

netmask 255.255.255.0 #学校给你的子网掩码

gateway 125.216.249.254 #学校给你的网关

iface eth0 inet6 manual #IPv6设定，不管他

iface wlan0 inet static

address 10.0.0.1 #内网网关(可以理解成路由器)地址,也可以写成192.168.1.1什么的，那样的话本文后面的部分你也要做相应的改动了。

netmask 255.255.255.0 #内网子网掩码，虽然是A段网络，但RPi显然没有NB到能拖那么多设备，所以三个255就够用。

iface wlan0 inet6 manual #IPv6设定，不管他

配置好之后，随便ping个网站看看能不能通外网，可以的话继续～

配置外网DNS

终端机中输入sudo emacs /etc/resolv.conf，在里面按下面的样子加上你需要的DNS地址

nameserver 222.201.130.30
nameserver 222.201.130.33
nameserver 8.8.8.8
nameserver 114.114.114.114

nameserver 222.201.130.30

nameserver 222.201.130.33

nameserver 8.8.8.8

nameserver 114.114.114.114

安装必要的软件包

这里假定你已经可以流畅的链接你的apt软件源了，如果官方源慢的要死就需要换源了，换源教程在这里。
按你的需要在终端机中（有选择性地）输入如下命令：

编译工具

sudo apt-get install subversion git build-essential autotools-dev autoconf libtool gettext gawk gperf cmake

1	sudo apt-get install subversion git build-essential autotools-dev autoconf libtool gettext gawk gperf cmake

即便装了一堆也有可能发生有软件包装不了的情况，不过本文提到的需要编译的软件基本都能过。

编辑器

sudo apt-get install vim emacs

1	sudo apt-get install vim emacs

这俩选一个，或者都不选用系统自带地nano，我用emacs，我不想挑起战争～

AP与IPv4机能

sudo apt-get install udhcpd hostapd iptables wireless-tools

1	sudo apt-get install udhcpd hostapd iptables wireless-tools

IPv6机能

软件包

sudo apt-get install radvd wide-dhcpv6-server

1	sudo apt-get install radvd wide-dhcpv6-server

本文使用NPD Proxy和DHCPV6实现IPv6机能。

编译安装npd6

cd ~
sudo git clone https://github.com/npd6/npd6 npd6
cd npd6
sudo make
sudo make install

cd ~

sudo git clone https://github.com/npd6/npd6 npd6

cd npd6

sudo make

sudo make install

配置hostapd以使用无线网卡软AP

在终端机中输入sudo emacs /etc/default/hostapd,打开之后找DAEMON_CONF="",把这行首的#去掉，然后把这句话改成DAEMON_CONF="/etc/hostapd/hostapd.conf"，保存退出。
在终端机输入sudo mkdir /etc/hostapd,然后sudo emacs /etc/hostapd/hostapd.conf,把文件内容（有的话清除，没有的话就从头写）改成（请仔细看注释有选择性地写～）：

#这里是无线网卡的代号
interface=wlan0
#这个一般不用改，除非你的无线网卡比较奇葩要单独指定驱动，大部分无线网卡驱动都是基于下面这个的
driver=nl80211
#无线网络名称
ssid=744 Experimental
#这个不用改
hw_mode=g
#这个如果不开11n的话，可以改一个不太拥挤的信道提高链接速度
channel=11
#这个不用改
auth_algs=3
#这个不用改
dtim_period=1
#下面这个去掉会增加速度但是降低稳定性
rts_threshold=2347
#下面这个去掉会增加速度但是降低稳定性
fragm_threshold=2346
#这个不用改
ignore_broadcast_ssid=0
#网络加密模式，0就是没有，1是WPA，2是WPA2，3是两个全开
wpa=3
#WIFI密码
wpa_passphrase=hahaschool
#这个不用改
wpa_key_mgmt=WPA-PSK
#wpa那个填1的话要去掉一个
wpa_pairwise=TKIP
rsn_pairwise=CCMP
#WMM机能，不知道是什么的话开着就行
wmm_enabled=1
#MAC地址黑白名单，本文不介绍这个机能
macaddr_acl=0 #for filtering make this 1 and decomment below and create two lists
#accept_mac_file=/etc/hostapd/hostapd.accept
#deny_mac_file=/etc/hostapd/hostapd.deny
#下面这两项是11n机能相关的，写不对会导致hostapd打不开，先不要写进去
ieee80211n=1
ht_capab=[HT40-][SHORT-GI-40][SHORT-GI-20][GF][SMPS-STATIC][RX-STBC1]

#这里是无线网卡的代号

interface=wlan0

#这个一般不用改，除非你的无线网卡比较奇葩要单独指定驱动，大部分无线网卡驱动都是基于下面这个的

driver=nl80211

#无线网络名称

ssid=744 Experimental

#这个不用改

hw_mode=g

#这个如果不开11n的话，可以改一个不太拥挤的信道提高链接速度

channel=11

#这个不用改

auth_algs=3

#这个不用改

dtim_period=1

#下面这个去掉会增加速度但是降低稳定性

rts_threshold=2347

#下面这个去掉会增加速度但是降低稳定性

fragm_threshold=2346

#这个不用改

ignore_broadcast_ssid=0

#网络加密模式，0就是没有，1是WPA，2是WPA2，3是两个全开

wpa=3

#WIFI密码

wpa_passphrase=hahaschool

#这个不用改

wpa_key_mgmt=WPA-PSK

#wpa那个填1的话要去掉一个

wpa_pairwise=TKIP

rsn_pairwise=CCMP

#WMM机能，不知道是什么的话开着就行

wmm_enabled=1

#MAC地址黑白名单，本文不介绍这个机能

macaddr_acl=0 #for filtering make this 1 and decomment below and create two lists

#accept_mac_file=/etc/hostapd/hostapd.accept

#deny_mac_file=/etc/hostapd/hostapd.deny

#下面这两项是11n机能相关的，写不对会导致hostapd打不开，先不要写进去

ieee80211n=1

ht_capab=[HT40-][SHORT-GI-40][SHORT-GI-20][GF][SMPS-STATIC][RX-STBC1]

打开系统的IPv4转发功能

在终端机中输入sudo emacs /etc/sysctl.conf,直接在文件头写入以下内容：

net.ipv4.conf.all.forwarding=1
net.ipv4.conf.default.rp_filter=1
net.ipv4.ip_forward=1

net.ipv4.conf.all.forwarding=1

net.ipv4.conf.default.rp_filter=1

net.ipv4.ip_forward=1

然后退出回到终端机输入sudo sysctl -q让修改立即生效。

配置DHCP服务器实现内网IPv4地址自动分配

终端机中输入sudo emacs /etc/udhcpd.conf,你需要去掉下面这些行首的#来解除注释，然后按照自己的配置方法修改，注意要和interfaces文件里面wlan0的地址设定一致：

# Sample udhcpd configuration file (/etc/udhcpd.conf)
# The start and end of the IP lease block
#在这里设定你内网IP的起点与终点
start           10.0.0.11       #default: 192.168.0.20
end             10.0.0.40       #default: 192.168.0.254
# The interface that udhcpd will use
#这里改成内网链接使用的网卡，我们这里要改成wlan0
interface       wlan0           #default: eth0
# The maximim number of leases (includes addressesd reserved
# by OFFER's, DECLINE's, and ARP conficts
#建议改小点，太大当心爆炸～
max_leases      30              #default: 254
# If remaining is true (default), udhcpd will store the time
# remaining for each lease in the udhcpd leases file. This is
# for embedded systems that cannot keep time between reboots.
# If you set remaining to no, the absolute time that the lease
# expires at will be stored in the dhcpd.leases file.
#这个随意，我没觉得有太大作用，可能是我从来不掉电的缘故，如果你的RPi老掉电就改成yes吧
remainings   no         #default: yes
###########################
#中间有一堆被注释掉的内容
###########################
#Examles
#DNS这里最多填两个
opt     dns     114.114.114.114 8.8.8.8
#子网掩码
option  subnet  255.255.255.0
#网关地址，就是你inerfaces里面给wlan0指定的IP地址
opt     router  10.0.0.1
#这个找一个内网地址段以外的地址填就好，也可以不配置
opt     wins    10.0.0.10
#神奇的功能，可以默认第三个DNS，如果你有这个需要可以再来一个（我是114+google+校园网内DNS,这样什么网站都可以正常解析)
option  dns     222.201.130.30  # appened to above DNS servers for a total of 3
#接下来的是作用域和租期时间，不懂就不要改了
option  domain  local
option  lease   864000          # 10 days of seconds

# Sample udhcpd configuration file (/etc/udhcpd.conf)

# The start and end of the IP lease block

#在这里设定你内网IP的起点与终点

start 10.0.0.11 #default: 192.168.0.20

end 10.0.0.40 #default: 192.168.0.254

# The interface that udhcpd will use

#这里改成内网链接使用的网卡，我们这里要改成wlan0

interface wlan0 #default: eth0

# The maximim number of leases (includes addressesd reserved

# by OFFER's, DECLINE's, and ARP conficts

#建议改小点，太大当心爆炸～

max_leases 30 #default: 254

# If remaining is true (default), udhcpd will store the time

# remaining for each lease in the udhcpd leases file. This is

# for embedded systems that cannot keep time between reboots.

# If you set remaining to no, the absolute time that the lease

# expires at will be stored in the dhcpd.leases file.

#这个随意，我没觉得有太大作用，可能是我从来不掉电的缘故，如果你的RPi老掉电就改成yes吧

remainings no #default: yes

###########################

#中间有一堆被注释掉的内容

###########################

#Examles

#DNS这里最多填两个

opt dns 114.114.114.114 8.8.8.8

#子网掩码

option subnet 255.255.255.0

#网关地址，就是你inerfaces里面给wlan0指定的IP地址

opt router 10.0.0.1

#这个找一个内网地址段以外的地址填就好，也可以不配置

opt wins 10.0.0.10

#神奇的功能，可以默认第三个DNS，如果你有这个需要可以再来一个（我是114+google+校园网内DNS,这样什么网站都可以正常解析)

option dns 222.201.130.30 # appened to above DNS servers for a total of 3

#接下来的是作用域和租期时间，不懂就不要改了

option domain local

option lease 864000 # 10 days of seconds

写一个bash脚本来一键打开无线路由机能，开机自动启动

在终端机输入emacs ~/router.sh,接下来写入：

sysctl -p
iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
iptables -A FORWARD -i eth0 -o wlan0 -m state --state RELATED,ESTABLISHED -j ACCEPT
iptables -A FORWARD -i wlan0 -o eth0 -j ACCEPT
service udhcpd restart

sysctl -p

iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

iptables -A FORWARD -i eth0 -o wlan0 -m state --state RELATED,ESTABLISHED -j ACCEPT

iptables -A FORWARD -i wlan0 -o eth0 -j ACCEPT

service udhcpd restart

保存，然后修改一下权限让他可以执行,输入sudo chmod 755 ~/router.sh就可以了。
接下来输入sudo emacs /etc/rc.local,在文件的末尾的exit 0这行上面，添加sudo /home/pi/router.sh保存退出。

重启测试

输入sudo reboot，不出意外的话重启之后你的设备可以正常连接你创建的无线网络上网了，802.11g，仅支持IPv4网络。
接下来会将IPv6和802.11n机能的开启,如果你有需要的话可以继续阅读。

配置IPv6实现无线双栈网络

查询外网IPv6地址和网关

Mac下可以插有线网络的话直接在设置里查看就可以了，Windows的话，命令行中输入ipconfig -all，如果你直接在RPi上看，终端机输入ifconfig就够了。纪录2001开头的IPv6地址和网关地址(我这里是fe80开头，有的情况下是2001开头，这个没关系，网关显示什么就记下来什么)，Windows下IPv6地址后面可能会显示/64这个是prefix长度，这个也要记下来。

修改sysctl.conf打开IPv6转发

终端机中输入sudo emacs /etc/sysctl.conf，然后添加：

net.ipv6.conf.all.proxy_ndp=1
net.ipv6.conf.all.forwarding=1

1 2	net.ipv6.conf.all.proxy_ndp=1 net.ipv6.conf.all.forwarding=1

改写router.sh，加入IPv6配置信息

在终端机输入emacs ~/router.sh,接下来写入：

ip -6 addr del 2001:250:3000:3cc6:ba27:ebff:fee6:ce6c/64 dev eth0
ip -6 addr add 2001:250:3000:3cc6:ba27:ebff:fee6:ce6c/126 dev eth0
ip -6 addr add 2001:250:3000:3cc6:1::/80 dev wlan0
ip -6 route add default via fe80::204:96ff:fe20:add6 dev eth0 metric 256
ip -6 route add 2001:250:3000:3cc6:1::/80 dev wlan0

service radvd restart
service npd6 restart

ip -6 addr del 2001:250:3000:3cc6:ba27:ebff:fee6:ce6c/64 dev eth0

ip -6 addr add 2001:250:3000:3cc6:ba27:ebff:fee6:ce6c/126 dev eth0

ip -6 addr add 2001:250:3000:3cc6:1::/80 dev wlan0

ip -6 route add default via fe80::204:96ff:fe20:add6 dev eth0 metric 256

ip -6 route add 2001:250:3000:3cc6:1::/80 dev wlan0

service radvd restart

service npd6 restart

注意，上面这些东西加在service这行前面，上面这5行中，2001:250:3000:3cc6:ba27:ebff:fee6:ce6c是我查到的公网IPv6地址，这个要原样打进去,/64和/126也不能变（除非你的网络非常特殊，64可能要改成你查到的perfix长度，126是不能动的，防止错乱）,接下来2001:250:3000:3cc6:1:：/80这个是你内网用的IPv6地址，前面四段要和你查到的公网地址保持一致，后面的那一段是你的内网网段，填1就可以了（当然你换什么填什么），接下来那个fe80开头的地址换成你查到的网关地址，这样就搞定了。

配置radvd

radvd的作用是使内网客户端能自动获取IPv6地址。终端机中输入sudo emacs /etc/radvd.conf然后写入：

interface wlan0
{
AdvSendAdvert on;
AdvManagedFlag on;
AdvOtherConfigFlag on;
prefix 2001:250:3000:3cc6:1::/80 {
AdvRouterAddr off;
AdvOnLink on;
AdvAutonomous on;
};
};

interface wlan0

{

AdvSendAdvert on;

AdvManagedFlag on;

AdvOtherConfigFlag on;

prefix 2001:250:3000:3cc6:1::/80 {

AdvRouterAddr off;

AdvOnLink on;

AdvAutonomous on;

};

注意上面的2001开头地址要换成你刚才设定好的内网地址。

配置npd6

npd6是邻居发现代理，是让内网客户端可以自动获取IPv6地址的。终端机中输入sudo emacs /etc/npd6.conf然后写入：

prefix=2001:250:3000:3cc6:1:
interface = eth0
ralogging = off
listtype = none
listlogging = off
collectTargets = 100
linkOption = false
ignoreLocal = true
routerNA = true
maxHops = 255
pollErrorLimit = 20

prefix=2001:250:3000:3cc6:1:

interface = eth0

ralogging = off

listtype = none

listlogging = off

collectTargets = 100

linkOption = false

ignoreLocal = true

routerNA = true

maxHops = 255

pollErrorLimit = 20

原文件中可能会用好多注释，不过没关系你只要对照上面把有效部分修改好就行了，注意2001开头那个地址要填你自己的

配置DHCPv6

DHCP是啥不用我多说了吧。终端机中输入sudo emacs /etc/wide-dhcpv6/dhcp6s.conf然后写入：

interface wlan0{
address-pool pool1 86400;
};
pool pool1 {
range 2001:250:3000:3cc6:1::200 to 2001:250:3000:3cc6:1::300;
};

interface wlan0{

address-pool pool1 86400;

};

pool pool1 {

range 2001:250:3000:3cc6:1::200 to 2001:250:3000:3cc6:1::300;

};

重启测试

sudo reboot，IPv6配置至此结束，没有异常的话在这里应该可以看到下图了吧。

配置802.11n机能

检查无线网卡支持哪些802.11n机能

在终端机中输入iw list | less之后你应该会看到一堆，我们只关注开头Capabilities的这部分，一般长得像这样：

Wiphy phy0
        Band 1:
                Capabilities: 0x172
                        HT20/HT40
                        Static SM Power Save
                        RX Greenfield
                        RX HT20 SGI
                        RX HT40 SGI
                        RX STBC 1-stream
                        Max AMSDU length: 3839 bytes
                        No DSSS/CCK HT40
                Maximum RX AMPDU length 65535 bytes (exponent: 0x003)
                Minimum RX AMPDU time spacing: 2 usec (0x04)
                HT RX MCS rate indexes supported: 0-7, 32
                TX unequal modulation not supported
                HT TX Max spatial streams: 1
                HT TX MCS rate indexes supported may differ

Wiphy phy0

Band 1:

Capabilities: 0x172

HT20/HT40

Static SM Power Save

RX Greenfield

RX HT20 SGI

RX HT40 SGI

RX STBC 1-stream

Max AMSDU length: 3839 bytes

No DSSS/CCK HT40

Maximum RX AMPDU length 65535 bytes (exponent: 0x003)

Minimum RX AMPDU time spacing: 2 usec (0x04)

HT RX MCS rate indexes supported: 0-7, 32

TX unequal modulation not supported

HT TX Max spatial streams: 1

HT TX MCS rate indexes supported may differ

你要把这一段记下来,之后按q键结束。

修改hostapd配置文件增加802.11n机能支持

sudo emacs /etc/hostapd/hostapd.conf然后修改两行：

ieee80211n=1
ht_capab=[HT40-][SHORT-GI-40][SHORT-GI-20][GF][SMPS-STATIC][RX-STBC1]

1 2	ieee80211n=1 ht_capab=[HT40-][SHORT-GI-40][SHORT-GI-20][GF][SMPS-STATIC][RX-STBC1]

你去要重点关照的就是ht_capab这一行，这一行输入的越全面，你得到的速度就越快。
我在下面引用了官方文档的配置802.11n的部分，你可以对照这个和记好的iw list数据决定填什么，填好之后保存。sudo service hostapd reboot如果提示成功，说明配置没有问题，这个时候应该可以享受到高速度了，如果FAIL了，请仔细检查ht_capab是不是填写错了，如果实在不行，就删掉不确定的项，牺牲一些速度吧。
hostapd详细的配置方法可以参照官方文档，其实hostapd可以支持802.11ac的，但是问题在于USB2.0的传输速率使得在RPi上用ac没有意义。

##### IEEE 802.11n related configuration ######################################

# ieee80211n: Whether IEEE 802.11n (HT) is enabled
# 0 = disabled (default)
# 1 = enabled
# Note: You will also need to enable WMM for full HT functionality.
#ieee80211n=1

# ht_capab: HT capabilities (list of flags)
# LDPC coding capability: [LDPC] = supported
# Supported channel width set: [HT40-] = both 20 MHz and 40 MHz with secondary
#	channel below the primary channel; [HT40+] = both 20 MHz and 40 MHz
#	with secondary channel above the primary channel
#	(20 MHz only if neither is set)
#	Note: There are limits on which channels can be used with HT40- and
#	HT40+. Following table shows the channels that may be available for
#	HT40- and HT40+ use per IEEE 802.11n Annex J:
#	freq		HT40-		HT40+
#	2.4 GHz		5-13		1-7 (1-9 in Europe/Japan)
#	5 GHz		40,48,56,64	36,44,52,60
#	(depending on the location, not all of these channels may be available
#	for use)
#	Please note that 40 MHz channels may switch their primary and secondary
#	channels if needed or creation of 40 MHz channel maybe rejected based
#	on overlapping BSSes. These changes are done automatically when hostapd
#	is setting up the 40 MHz channel.
# Spatial Multiplexing (SM) Power Save: [SMPS-STATIC] or [SMPS-DYNAMIC]
#	(SMPS disabled if neither is set)
# HT-greenfield: [GF] (disabled if not set)
# Short GI for 20 MHz: [SHORT-GI-20] (disabled if not set)
# Short GI for 40 MHz: [SHORT-GI-40] (disabled if not set)
# Tx STBC: [TX-STBC] (disabled if not set)
# Rx STBC: [RX-STBC1] (one spatial stream), [RX-STBC12] (one or two spatial
#	streams), or [RX-STBC123] (one, two, or three spatial streams); Rx STBC
#	disabled if none of these set
# HT-delayed Block Ack: [DELAYED-BA] (disabled if not set)
# Maximum A-MSDU length: [MAX-AMSDU-7935] for 7935 octets (3839 octets if not
#	set)
# DSSS/CCK Mode in 40 MHz: [DSSS_CCK-40] = allowed (not allowed if not set)
# 40 MHz intolerant [40-INTOLERANT] (not advertised if not set)
# L-SIG TXOP protection support: [LSIG-TXOP-PROT] (disabled if not set)
#ht_capab=[HT40-][SHORT-GI-20][SHORT-GI-40]

# Require stations to support HT PHY (reject association if they do not)
#require_ht=1

# If set non-zero, require stations to perform scans of overlapping
# channels to test for stations which would be affected by 40 MHz traffic.
# This parameter sets the interval in seconds between these scans. Setting this
# to non-zero allows 2.4 GHz band AP to move dynamically to a 40 MHz channel if
# no co-existence issues with neighboring devices are found.
#obss_interval=0

##### IEEE 802.11n related configuration ######################################

# ieee80211n: Whether IEEE 802.11n (HT) is enabled

# 0 = disabled (default)

# 1 = enabled

# Note: You will also need to enable WMM for full HT functionality.

#ieee80211n=1

# ht_capab: HT capabilities (list of flags)

# LDPC coding capability: [LDPC] = supported

# Supported channel width set: [HT40-] = both 20 MHz and 40 MHz with secondary

# channel below the primary channel; [HT40+] = both 20 MHz and 40 MHz

# with secondary channel above the primary channel

# (20 MHz only if neither is set)

# Note: There are limits on which channels can be used with HT40- and

# HT40+. Following table shows the channels that may be available for

# HT40- and HT40+ use per IEEE 802.11n Annex J:

# freq HT40- HT40+

# 2.4 GHz 5-13 1-7 (1-9 in Europe/Japan)

# 5 GHz 40,48,56,64 36,44,52,60

# (depending on the location, not all of these channels may be available

# for use)

# Please note that 40 MHz channels may switch their primary and secondary

# channels if needed or creation of 40 MHz channel maybe rejected based

# on overlapping BSSes. These changes are done automatically when hostapd

# is setting up the 40 MHz channel.

# Spatial Multiplexing (SM) Power Save: [SMPS-STATIC] or [SMPS-DYNAMIC]

# (SMPS disabled if neither is set)

# HT-greenfield: [GF] (disabled if not set)

# Short GI for 20 MHz: [SHORT-GI-20] (disabled if not set)

# Short GI for 40 MHz: [SHORT-GI-40] (disabled if not set)

# Tx STBC: [TX-STBC] (disabled if not set)

# Rx STBC: [RX-STBC1] (one spatial stream), [RX-STBC12] (one or two spatial

# streams), or [RX-STBC123] (one, two, or three spatial streams); Rx STBC

# disabled if none of these set

# HT-delayed Block Ack: [DELAYED-BA] (disabled if not set)

# Maximum A-MSDU length: [MAX-AMSDU-7935] for 7935 octets (3839 octets if not

# set)

# DSSS/CCK Mode in 40 MHz: [DSSS_CCK-40] = allowed (not allowed if not set)

# 40 MHz intolerant [40-INTOLERANT] (not advertised if not set)

# L-SIG TXOP protection support: [LSIG-TXOP-PROT] (disabled if not set)

#ht_capab=[HT40-][SHORT-GI-20][SHORT-GI-40]

# Require stations to support HT PHY (reject association if they do not)

#require_ht=1

# If set non-zero, require stations to perform scans of overlapping

# channels to test for stations which would be affected by 40 MHz traffic.

# This parameter sets the interval in seconds between these scans. Setting this

# to non-zero allows 2.4 GHz band AP to move dynamically to a 40 MHz channel if

# no co-existence issues with neighboring devices are found.

#obss_interval=0

收工

至此本文的目的已经达到，have fun！

本文系hahaschool原创，转载必须注明出处。

CodeForces 484B Maximum Value

March 12, 20152015-03-12hahaschoolLeave 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>

using namespace std;

int seq[200005];
int main(){
    int n = 0;
    scanf(" %d",&n);
    memset(seq, 0, sizeof(seq));
    for (int i = 1; i <= n; i++) {
        scanf(" %d",&seq[i]);
    }
    n = unique(seq+1,seq+1+n) - seq - 1;
    sort(seq+1, seq+1+n);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        //opt
        if (seq[i] == 1) {
            continue;
        }
        if (res >= seq[i]-1) {
            continue;
        }
        int k = 0;
        while (k * seq[i] <= seq[n]) {
            k++;
            int pos = lower_bound(seq+1,seq+1+n, k*seq[i]) - seq;
            pos--;
            if(pos >= i)
            res = max(res,seq[pos]%seq[i]);
            //quit
            if (res >= seq[i]-1) {
                break;
            }
        }
    }
    printf("%dn",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>

using namespace std;

int seq[200005];

int main(){

int n = 0;

scanf(" %d",&n);

memset(seq, 0, sizeof(seq));

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

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

}

n = unique(seq+1,seq+1+n) - seq - 1;

sort(seq+1, seq+1+n);

int res = 0;

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

//opt

if (seq[i] == 1) {

continue;

}

if (res >= seq[i]-1) {

continue;

}

int k = 0;

while (k * seq[i] <= seq[n]) {

k++;

int pos = lower_bound(seq+1,seq+1+n, k*seq[i]) - seq;

pos--;

if(pos >= i)

res = max(res,seq[pos]%seq[i]);

//quit

if (res >= seq[i]-1) {

break;

}

printf("%dn",res);

return 0;

}

在lower_bound之后如果加入了多余的判断（判断pos的位置等等），就会T，如果没有用unique来压缩输入，就会T。

总觉得很寸，应该是数据做的有漏洞。

解法的思路就是先从小到大排序，然后从第一项开始，借用素数筛法的思路，对于每个数检查以这个数的倍数为终点的各个区间，然后找出每个区间之内离终点最近的数，更新答案。找终点的过程使用了二分搜索，STL自带的lower_bound和upper_bound就能很好地工作，使用upper_bound的话还有一个小窍门就是把搜索目标设成目标－1，这样的话搜索完落在的点就和lower_bound是一样的了。

CodeForces 463C Gargari and Bishops

March 11, 20152015-03-11hahaschoolLeave 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>

using namespace std;

long long board[2005][2005];
long long sum[2005][2005];
long long dl[4005],dr[4005];

int main(){
    int n = 0;
    scanf(" %d",&n);
    memset(sum, 0, sizeof(sum));
    memset(board, 0, sizeof(board));
    memset(dl, 0, sizeof(dl));
    memset(dr, 0, sizeof(dr));
    for (int i = 1; i <= n; i++) {
        for (int j = 1;j <= n; j++) {
            scanf(" %lld",&board[i][j]);
            dl[i+j] += board[i][j];
            dr[i-j+n] += board[i][j];
        }
    }
    //update sum
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sum[i][j] = dl[i+j] + dr[i-j+n] - board[i][j];
        }
    }

    int x1 = 1,y1 = 1,x2 = 2,y2 = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i+j)%2) {
                //grp1
                if (sum[i][j] > sum[y2][x2]) {
                    y2 = i,x2 = j;
                }
            }else{
                //grp2
                if (sum[i][j] > sum[y1][x1]) {
                    y1 = i,x1 = j;
                }
            }
        }
    }

    printf("%lldn%d %d %d %dn",sum[y1][x1]+sum[y2][x2],y1,x1,y2,x2);
    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 board[2005][2005];

long long sum[2005][2005];

long long dl[4005],dr[4005];

int main(){

int n = 0;

scanf(" %d",&n);

memset(sum, 0, sizeof(sum));

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

memset(dl, 0, sizeof(dl));

memset(dr, 0, sizeof(dr));

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

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

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

dl[i+j] += board[i][j];

dr[i-j+n] += board[i][j];

}

//update sum

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

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

sum[i][j] = dl[i+j] + dr[i-j+n] - board[i][j];

}

int x1 = 1,y1 = 1,x2 = 2,y2 = 1;

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

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

if ((i+j)%2) {

//grp1

if (sum[i][j] > sum[y2][x2]) {

y2 = i,x2 = j;

}

}else{

//grp2

if (sum[i][j] > sum[y1][x1]) {

y1 = i,x1 = j;

}

printf("%lldn%d %d %d %dn",sum[y1][x1]+sum[y2][x2],y1,x1,y2,x2);

return 0;

}

最后还是没有了尊严，去看题解了。。。
http://blog.csdn.net/kenden23/article/details/38959141

这个题告诉我们了关于交叉坐标和对角线的性质，要想很好地做过需要很多优美的姿势-_-#。

CodeForces 475B Strongly Connected City

March 11, 20152015-03-11hahaschoolLeave 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>

using namespace std;

vector<int> ljb[404];
bool vis[10005];
bool instk[10005];
int dfn[10005];
int low[10005];
int tim = 0;
stack<int> stk;
vector<vector<int> > ccs;

void dfs(int currNode){
    vis[currNode] = true;
    dfn[currNode] = low[currNode] = tim++;
    stk.push(currNode);
    instk[currNode] = true;
    vector<int> now = ljb[currNode];
    for (int i = 0;i < now.size(); i++) {
        if (!vis[now[i]]) {
            dfs(now[i]);
            low[currNode] = min(low[currNode],low[now[i]]);
        }else if (instk[now[i]]) {
            low[currNode] = min(low[currNode],dfn[now[i]]);
        }
    }
    if (dfn[currNode] == low[currNode]) {
        int tmp = 0;
        vector<int> res;
        while (currNode != tmp) {
            tmp = stk.top();
            res.push_back(tmp);
            //cout << tmp << "~";
            stk.pop();
            instk[tmp] = false;
        }
        //sort(res.begin(),res.end());
        ccs.push_back(res);
        //cout << endl;
    }
}


int main(){
    int n = 0,m = 0;
    scanf(" %d %d",&n,&m);
    for (int i = 1; i <= n*m; i++) {
        ljb[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        char way = 0;
        scanf(" %c",&way);
        if (way == '>') {
            for (int j = 1; j < m; j++) {
                ljb[(i-1)*m+j].push_back((i-1)*m+j+1);
            }
        }else{
            for (int j = m; j > 1; j--) {
                ljb[(i-1)*m+j].push_back((i-1)*m+j-1);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        char way = 0;
        scanf(" %c",&way);
        if (way == '^') {
            for (int j = n; j > 1; j--) {
                ljb[(j-1)*m+i].push_back((j-2)*m+i);
            }
        }else{
            for (int j = 1;j < n; j++) {
                ljb[(j-1)*m+i].push_back((j)*m+i);
            }
        }
    }

    dfs(1);
    for (int i = 0; i < ccs.size(); i++) {
        if (ccs[i].size() == n*m) {
            printf("YESn");
            return 0;
        }
    }
    printf("NOn");
    return 0;

    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>

using namespace std;

vector<int> ljb[404];

bool vis[10005];

bool instk[10005];

int dfn[10005];

int low[10005];

int tim = 0;

stack<int> stk;

vector<vector<int> > ccs;

void dfs(int currNode){

vis[currNode] = true;

dfn[currNode] = low[currNode] = tim++;

stk.push(currNode);

instk[currNode] = true;

vector<int> now = ljb[currNode];

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

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

dfs(now[i]);

low[currNode] = min(low[currNode],low[now[i]]);

}else if (instk[now[i]]) {

low[currNode] = min(low[currNode],dfn[now[i]]);

}

if (dfn[currNode] == low[currNode]) {

int tmp = 0;

vector<int> res;

while (currNode != tmp) {

tmp = stk.top();

res.push_back(tmp);

//cout << tmp << "~";

stk.pop();

instk[tmp] = false;

}

//sort(res.begin(),res.end());

ccs.push_back(res);

//cout << endl;

}

int main(){

int n = 0,m = 0;

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

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

ljb[i].clear();

}

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

char way = 0;

scanf(" %c",&way);

if (way == '>') {

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

ljb[(i-1)*m+j].push_back((i-1)*m+j+1);

}

}else{

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

ljb[(i-1)*m+j].push_back((i-1)*m+j-1);

}

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

char way = 0;

scanf(" %c",&way);

if (way == '^') {

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

ljb[(j-1)*m+i].push_back((j-2)*m+i);

}

}else{

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

ljb[(j-1)*m+i].push_back((j)*m+i);

}

dfs(1);

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

if (ccs[i].size() == n*m) {

printf("YESn");

return 0;

}

printf("NOn");

return 0;

}

强联通分量的题，建图搞定了就搞定了。关于scc的算法可以翻我的图论标签找一下我写的一篇tarjan算法总结。

RTL8818EU Driver for Raspbian 3.18.7/8-v7+ (RPi 2B)

March 05, 20152015-03-05hahaschoolLeave a comment

For 3.18.8-v7+ #764
8188eu-v7-20150227.tar

For 3.18.7-v7+ #758 #759
8188eu-v7-20150223.tar

For 3.18.7-v7+ #755
8188eu-v7-20150212.tar

CDN使用済み、欢迎帮测疗效

March 03, 20152015-03-03hahaschoolLeave a comment

装了这么长时间的七牛插件都没有好好配置，这次搞好了，如果有异状请随时comment反映，谢谢啦！

ZOJ 3686 A Simple Tree Problem

March 02, 20152015-03-02hahaschoolOne 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>

using namespace std;

#define MAXN 262145

int tree[MAXN];
int lazy[MAXN];
int mark[MAXN];
int M = 1,H = 0;
void tree_init(unsigned int num){
    memset(tree, 0, sizeof(tree));
    memset(lazy, 0, sizeof(lazy));
    memset(mark, 0, sizeof(mark));
    M = 1;
    for (; M < num+2; M <<= 1) H++;
    M--;
    for (int i = 1; i <= num; i++) {
        mark[i+1+M] = 1;
    }
    for (int i = M; i >= 1; i--) {
        mark[i] = mark[(i << 1) + 1] + mark[i << 1];
    }
}




void lazy_down(int pos){
    if (lazy[pos]) {
        lazy[pos] = 0;
        lazy[pos*2] = lazy[pos*2]?0:1;
        tree[pos*2] = mark[pos*2] - tree[pos*2];
        lazy[pos*2+1] = lazy[pos*2+1]?0:1;
        tree[pos*2+1] = mark[pos*2+1] - tree[pos*2+1];
    }
}

void tree_negate(int from,int to,int l,int r,int pos){
    //default pos = 1 l = 1 r = n
    if (r < from || l > to){
        //out of range
        return;
    }else if (l >= from && r <= to) {
        //fully inclusive
        lazy[pos] = lazy[pos]?0:1;
        tree[pos] = mark[pos] - tree[pos];

    }else{
        //partially inclusive
        lazy_down(pos);
        tree_negate(from, to, l, l+mark[pos*2]-1, pos*2);
        tree_negate(from, to, l+mark[pos*2], r, pos*2+1);
        if (l < r) {
            tree[pos] = tree[pos*2] + tree[pos*2+1];
        }
    }

}

int res;
void tree_query(int from,int to,int l,int r,int pos){
    //default pos = 1 l = 1 r = n
    if (r < from || l > to){
        //out of range
        return;
    }else if (l >= from && r <= to) {
        //fully inclusive
        res += tree[pos];
    }else{
        //partially inclusive
        lazy_down(pos);
        tree_query(from, to, l, l+mark[pos*2]-1, pos*2);
        tree_query(from, to, l+mark[pos*2], r, pos*2+1);
    }

}



int n = 0,m = 0;
vector<int> child[MAXN];
vector<int> linear;
int str[MAXN],ter[MAXN];

bool vis[MAXN];
void dfs(int cur){
    linear.push_back(cur);
    str[cur] = (int)linear.size();
    vis[cur] = true;
    for (int i = 0; i < child[cur].size(); i++) {
        if (!vis[child[cur][i]]) {
            dfs(child[cur][i]);
        }
    }
    ter[cur] = (int)linear.size();
}

int main(){
    while (scanf(" %d %d",&n,&m) != EOF) {
        tree_init(n);
        for (int i = 1; i <= n; i++) {
            child[i].clear();
        }
        for (int i = 2; i <= n; i++) {
            int parent;
            scanf(" %d",&parent);
            child[parent].push_back(i);
        }
        memset(vis, false, sizeof(vis));
        linear.clear();
        dfs(1);
        for (int i = 1; i <= m; i++) {
            char arg1;
            int arg2;
            scanf(" %c %d",&arg1,&arg2);
            if (arg1 == 'o') {
                tree_negate(str[arg2], ter[arg2], 1, n, 1);
            }else{
                res = 0;
                tree_query(str[arg2], ter[arg2], 1, n, 1);
                printf("%d\n",res);
            }
        }
        printf("n");
    }

    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

134

135

136

137

138

139

140

141

142

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

#define MAXN 262145

int tree[MAXN];

int lazy[MAXN];

int mark[MAXN];

int M = 1,H = 0;

void tree_init(unsigned int num){

memset(tree, 0, sizeof(tree));

memset(lazy, 0, sizeof(lazy));

memset(mark, 0, sizeof(mark));

M = 1;

for (; M < num+2; M <<= 1) H++;

M--;

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

mark[i+1+M] = 1;

}

for (int i = M; i >= 1; i--) {

mark[i] = mark[(i << 1) + 1] + mark[i << 1];

}

void lazy_down(int pos){

if (lazy[pos]) {

lazy[pos] = 0;

lazy[pos*2] = lazy[pos*2]?0:1;

tree[pos*2] = mark[pos*2] - tree[pos*2];

lazy[pos*2+1] = lazy[pos*2+1]?0:1;

tree[pos*2+1] = mark[pos*2+1] - tree[pos*2+1];

}

void tree_negate(int from,int to,int l,int r,int pos){

//default pos = 1 l = 1 r = n

if (r < from || l > to){

//out of range

return;

}else if (l >= from && r <= to) {

//fully inclusive

lazy[pos] = lazy[pos]?0:1;

tree[pos] = mark[pos] - tree[pos];

}else{

//partially inclusive

lazy_down(pos);

tree_negate(from, to, l, l+mark[pos*2]-1, pos*2);

tree_negate(from, to, l+mark[pos*2], r, pos*2+1);

if (l < r) {

tree[pos] = tree[pos*2] + tree[pos*2+1];

}

int res;

void tree_query(int from,int to,int l,int r,int pos){

//default pos = 1 l = 1 r = n

if (r < from || l > to){

//out of range

return;

}else if (l >= from && r <= to) {

//fully inclusive

res += tree[pos];

}else{

//partially inclusive

lazy_down(pos);

tree_query(from, to, l, l+mark[pos*2]-1, pos*2);

tree_query(from, to, l+mark[pos*2], r, pos*2+1);

}

int n = 0,m = 0;

vector<int> child[MAXN];

vector<int> linear;

int str[MAXN],ter[MAXN];

bool vis[MAXN];

void dfs(int cur){

linear.push_back(cur);

str[cur] = (int)linear.size();

vis[cur] = true;

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

if (!vis[child[cur][i]]) {

dfs(child[cur][i]);

}

ter[cur] = (int)linear.size();

}

int main(){

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

tree_init(n);

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

child[i].clear();

}

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

int parent;

scanf(" %d",&parent);

child[parent].push_back(i);

}

memset(vis, false, sizeof(vis));

linear.clear();

dfs(1);

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

char arg1;

int arg2;

scanf(" %c %d",&arg1,&arg2);

if (arg1 == 'o') {

tree_negate(str[arg2], ter[arg2], 1, n, 1);

}else{

res = 0;

tree_query(str[arg2], ter[arg2], 1, n, 1);

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

}

printf("n");

}

return 0;

}

被这道题玩得相当惨。。。这道题是一个DFS＋线段树的题。

首先这个题是在一棵传统树上面进行大规模的区间读写操作，这是线段树的玩法，但是怎么玩呢？
这个时候DFS就派上用场了，我们通过DFS得到DLR遍历，把dfs时进入一个节点是时间记下来，出去一个节点的时间记下来，就可以得到这个节点的子树在DLR遍历中的区间的开始与结束标号，这样就相当于把2维的树降到一维了。
之后得到了一个一维的数组，就可以开线段树，这里涉及区间更新，还要加开懒惰标记。
这种把树压成线然后再搞是一种很常用很好的姿势！

其实这道题卡死我的就是懒惰标记这里。我原来一直在用zkw线段树，但是因为是自下向上操作没有递归，所以我就根本不知道怎么下手写懒惰标记了，鼓捣2天未果，orz各路大神的适配zkw线段树的懒惰标记是给rmq准备的，不适合这个题，没办法研究递归版本了。

递归版本的话，实现懒惰标记的思路就是：
1.更新时，如果发生了目标区间与当前区间相交的情况，首先把当前节点的懒惰标记下传给下一层，然后再去更新下一层，更新完下一层后，用更新好的下一层更新自身。如果目标区间完全包括当前区间，这个时候就不用往下走了，首先更新自己的值，然后更新自己位置的懒惰标记。
2.查询时，如果目标区间和当前区间相交，这时候需要下传当前节点的懒惰标记，然后进入下一层接着查询，如果目标区间完全包括当前区间，直接更新答案。
3.下传时，我们只操作当前节点的子节点，不可以操作当前节点（否则就重复操作啦），注意我们只下传了一层，所以不仅要操作下面一层的值，还要操作下面一层的懒惰标记，同时清空当前节点的懒惰标记。