4
17
2016
1

C++模板学习

之前因为什么奇怪的原因抱回来一本C++ Primer,认真研读之后发现什么都没看懂

但是唯一明白的就是我之前一直不会写C++啊。

然后大致草草的明白了类和继承和OOP编程的基础开始学习模板

写了各线段树的模板…… 区间修改的借口还待调试

#ifndef SEGMENT_TREE
#define SEGMENT_TREE

//这是一个我想使用的标准线段书模板
//我们需要提供节点类型,每个节点类型都必须包含push_down,push_up,两种操作
//如果使用函数的modify string 命令接口那么必须包含modify(std::string &)接口
//如果不想要使用这个接口,可以使用#define NOSTRINGMODIFY 来避免这个借口带来的编译问题
//其中modify可以接受一个字符串作为目的的操作
//这里我们提供一种标准的 class StandardNode 可以从中继承使用
#include <string>
#include <cmath>
const int DEFUALTSEGMENTSIZE = 100000;
template <typename T>
class SegmentTree{
public:
	explicit SegmentTree(int Size);
	explicit SegmentTree(T *,int Size);
	~SegmentTree();
	void init(T *);
	void modify(int pos,const T &x);
#ifndef NOSTRINGMODIFY
	void modify(int l,int r,const std::string &cmd);
	void modify(int l,int r,const std::string &cmd,const T &x);
#endif
	T query(int l,int r);
private:
	int Size;
	void build(int i,int l,int r,T *);
	void build(int i,int l,int r);
	void modify(int i,int pos,const T &x);
#ifndef UNFINSHIED
	void modify(int i,int l,int r,const std::string &cmd);
	void modify(int i,int l,int r,const std::string &cmd,const T &x);
	inline void push_up(int i);
	inline void push_down(int i);
#endif
	T query(int i,int l,int r);
	int D;
	class segmentTreeNodeClass{
	public:
		T data;
		int l,r;
		int mid(){ return l+r>>1; }
	}*s;
};

template<typename T>
SegmentTree<T>::SegmentTree(int _Size):Size(_Size){
	D = (int)ceil(log(Size) / log(2)); 
	s = new segmentTreeNodeClass[1 << D+1];
	build(1,1,1 << D);
}

template<typename T>
SegmentTree<T>::SegmentTree(T *x,int Size):Size(Size){
	D = (int)ceil(log(Size) / log(2)); 
	s = new segmentTreeNodeClass[1 << D+1];
	build(1,1,1 << D,x);
}

template<typename T>
SegmentTree<T>::~SegmentTree(){
//currently do nothing at all
}	

template<typename T>
void SegmentTree<T>::init(T *x){
	build(1,1,1<<D,x);
}

template<typename T>
void SegmentTree<T>::modify(int pos,const T &x){
	modify(1,pos,x);
}
#ifndef NOSTRINGMODIFY
template<typename T>
void SegmentTree<T>::modify(int l,int r,const std::string &cmd){
	modify(1,l,r,cmd);
}

template<typename T>
void SegmentTree<T>::modify(int l,int r,const std::string &cmd,const T &x){
	modify(1,l,r,cmd,x);
}
#endif

template<typename T>
T SegmentTree<T>::query(int l,int r){
	return query(1,l,r);
}

template<typename T>
void SegmentTree<T>::build(int i,int l,int r){
	s[i].l = l;
	s[i].r = r;
	s[i].data.setRange(l,r);
	if (l==r) return;
	int m = l+r>>1;
	build(i<<1,l,m);
	build(i<<1|1,m+1,r);
}

template<typename T>
void SegmentTree<T>::build(int i,int l,int r,T *x){
	s[i].l = l;
	s[i].r = r;
	s[i].data.setRange(l,r);
	if (l==r){
		if (l <= Size) s[i].data = x[l];
		s[i].data.setRange(l,r);
		return;
	}
	int m = l+r>>1;
	build(i<<1,l,m,x);
	build(i<<1|1,m+1,r,x);
	push_up(i);
	return;
}

template<typename T>
void SegmentTree<T>::modify(int i,int pos,const T &x){
	if (s[i].l==pos && s[i].r==pos){
		s[i].data = x;
		s[i].data.setRange(pos,pos);
		return;
	}
	push_down(i);
	if (pos <= s[i].mid()) modify(i<<1,pos,x);
	else modify(i<<1|1,pos,x);
	push_up(i);
}

#ifndef NOSTRINGMODIFY
template<typename T>
void SegmentTree<T>::modify(int i,int l,int r,const std::string &cmd){
	if (s[i].l==l && s[i].r==r){
		s[i].data.modify(cmd);
		return;
	}
	push_down(i);
	int m = s[i].mid();
	if (r<=m) modify(i<<1,l,r,cmd);
	else if (l>m) modify(i<<1|1,l,r,cmd);
	else modify(i<<1,l,m,cmd),modify(i<<1,m+1,r,cmd);
	push_up(i);
}


template<typename T>
void SegmentTree<T>::modify(int i,int l,int r,const std::string &cmd,const T &x){
	if (s[i].l==l && s[i].r==r){
		s[i].data.modify(cmd,x);
		return;
	}
	push_down(i);
	int m = s[i].mid();
	if (r<=m) modify(i<<1,l,r,cmd,x);
	else if (l>m) modify(i<<1|1,l,r,cmd,x);
	else modify(i<<1,l,m,cmd,x),modify(i<<1,m+1,r,cmd,x);
	push_up(i);
}
#endif

template<typename T>
T SegmentTree<T>::query(int i,int l,int r){
	if (s[i].l==l && s[i].r==r) return s[i].data;
	int m=s[i].mid();
	T ret;
	push_down(i);
	if (r<=m) ret = query(i<<1,l,r);
	else if (l>m) ret =query(i<<1|1,l,r);
	else ret.push_up(query(i<<1,l,m),query(i<<1|1,m+1,r));
	push_up(i);
	return ret;
}

template<typename T>
inline void SegmentTree<T>::push_up(int i){
	s[i].data.push_up(s[i<<1].data,s[i<<1|1].data);
}

template<typename T>
inline void SegmentTree<T>::push_down(int i){
	s[i].data.push_down(s[i<<1].data,s[i<<1|1].data);
}

class StandardNode{
public:
	virtual void push_up(const StandardNode &x,const StandardNode &y)  {}
	virtual void push_down(StandardNode &x,StandardNode &y)  {}
	virtual void modify(const std::string &cmd)  {}
	virtual void modify(const std::string &cmd,const StandardNode &x)  {}
	virtual void setRange(int l,int r){}	
	virtual ~StandardNode(){}
};
#endif
Category: 未分类 | Tags: C++ 模板 线段树
2
24
2016
0

图片爬虫+模拟登陆+定时爬去——知乎图片爬去

首先是模拟登陆,这个只要输错一次密码就可以得到POST的数据了非常的良心

这个没有headers验证。。

# coding = 'utf-8'
import requests
import bs4

dic = {"_xsrf":"c892d53f291611e18902b1101bae4a8f",
       "email":"495327165@qq.com",
       "password":"your_password",
       "remember_me":"false"}

headers = {"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/46.0.2486.0 Safari/537.36 Edge/13.10586"}
login_url = r"http://www.zhihu.com/login/email"
def login(s):
    a = s.post(login_url,dic,headers = headers)
    url_test = r"https://www.zhihu.com/people/wang-yuan-wei-38"
    responce = s.get(url_test,headers = headers)
    responce.encoding = 'utf-8'
    soup = bs4.BeautifulSoup(responce.text,'html.parser',from_encoding = 'utf-8')
    
    a = soup.find("a",href = "/people/edit")

    if a != None:
        print("successful login")
        return True
    else:
        print("unsuccessful login")
        return False

if __name__ == "__main__":
    s = requests.Session()
    print(login(s))

 

下载图片,首先我们需要把照片弄放到题目的文件夹下面就需要一个Name和Path

#coding = utf-8
import requests
import bs4
import urllib
import os
headers = {"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/46.0.2486.0 Safari/537.36 Edge/13.10586"}

def download(url,path,name):
    print("downloading(%s,%s,%s)"%(url,path,name))
    cur_path = os.getcwd()
    new_path = os.path.join(cur_path,path)
    if name == None:
        name = url[-10:]
    else:
        if url[-4]=='.':
            name = name+url[-4:]
        if url[-5]=='.':
            name = name+url[-5:]
    if not os.path.isdir(new_path):
        print('创建',new_path)
        os.mkdir(new_path)
    else:
        pass
        #pos = name.find('.')
        #if int(name[:pos])==1:
        #    print("目标已经爬取!")
        #    return False
    responce = urllib.request.urlopen(url)
    file = ''
    
    if path == None:
        file = '/' + name
    else:
        file = path + '/' + name
    
    with open(file,'wb') as code:
        code.write(responce.read())
    return True
#<img width="950" class="origin_image zh-lightbox-thumb" src="https://pic4.zhimg.com/7489cce13a572ec50a6a9725d3bf36bb_b.jpg" data-original="https://pic4.zhimg.com/7489cce13a572ec50a6a9725d3bf36bb_r.jpg" data-rawheight="355" data-rawwidth="950">
sample_url = r"https://pic4.zhimg.com/a577e2473387b3cea5422135fbb8632b_r.jpg"
sample_name = "Pic_Try.jpg"
sample_path = r"为什么你告诉我到底是为什么!"
if __name__ == "__main__":
    download(sample_url,sample_path,sample_name)

 

get一种存贮图片的方式:

 

最最伟大的主程序……不过看起来没有任何意思

#coding:utf-8
import requests
import bs4
import picture
import re
import os
from login import login
from time import sleep
headers = {"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/46.0.2486.0 Safari/537.36 Edge/13.10586"}

url = r"https://www.zhihu.com/"
nextpage_url = r"https://www.zhihu.com/node/QuestionAnswerListV2"
nextpage_headers = {"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/46.0.2486.0 Safari/537.36 Edge/13.10586",
                    "X-Requested-With":"XMLHttpRequest",}
visit = set([]);
def progress():
    print(".")

def make_dir(path):
    path = path.replace('\n','')
    path = path.replace('?','?')
    path = path.replace('\\','')
    path = path.replace('/','')
    path = path.replace('<',' ')
    path = path.replace('>',' ')
    path = path.replace('|',' ')
    path = path.replace('*','#')
    path = path.replace(':',':')
    return path

def find_pic_with_soup(soup,path = None):
    lists = soup.find_all("img",class_ = "origin_image zh-lightbox-thumb lazy")
    path = make_dir(path)
    print("开始抓取问题:",path)
    now = 1
    cur_path = os.getcwd()
    cur_path = os.path.join(cur_path,path)
    number = 0
    if (cur_path[-1] != '\\'):
        cur_path = cur_path + '\\'

    for node in lists:
        now = now + 1
        if node["data-original"] in visit:
            print("已经爬去图片")
            continue
        number = number + 1
        picture.download(node["data-original"],path,str(now))
        
        visit.add(node["data-original"])
        file = open('visit.txt','a')
        file.write(node['data-original']+'\n')
        file.close()
    return number

def vis(path_url):
    count = 0
    number = 0
    progress()
    new_url = url + path_url
    print("爬去问题:",new_url)
    res = requests.get(new_url,headers = headers)
    progress()
    soup = bs4.BeautifulSoup(res.text,'html.parser',from_encoding = 'utf-8')

    res2 = requests.get(url + path_url)
    soup2 = bs4.BeautifulSoup(res2.text,'html.parser',from_encoding = 'utf-8')
    node = soup2.find("h2")
    path = node.get_text()
    count = find_pic_with_soup(soup,path)
    print("总共下载",count,"张图片")

if __name__ == "__main__":
    s = requests.Session()
    if login(s)==False:
        print("Login Failed! Terminated")
    else:
        file = open('visit.txt','r')
        while True:
            pic = file.readline()
            pic = pic.replace('\n','')
            if pic!='' and pic!=None:
                visit.add(pic)
            else:
                break
        while True:
            responce = s.get(url,headers = headers)
            responce.encoding = 'utf-8'
        
            soup = bs4.BeautifulSoup(responce.text,'html.parser',from_encoding = 'utf-8')
            nodes = soup.find_all("a",class_="question_link")
            
            for node in nodes:
                dis_url = node["href"]
                pos = dis_url.find('#')
                cur_url = dis_url[1:pos]
                vis(cur_url)
            print("Waiting for next Scrub")
            sleep(600)    

再加上一个__init__.py就完成了

 

Category: 未分类 | Tags: python 爬虫
2
18
2016
0

在Ubuntu14.04下为python2.7安装autopy

autopy是一个GUI接口,可以通过程序控制键盘和鼠标,是些外挂的不二选择。

这篇文章记录一下安装过程中遇到的问题,虽然大部分问题都在网上寻找到了解决问题,但是在这里记录一下

编译错误: Fatal Erorr :Python.h :没有那个文件或目录

解决方法:

 

sudo apt-get install python-dev

 

编译错误: Fatal Error: X11/Xlib.h : 没有那个文件或目录

解决方法:

 

sudo apt-get install libx11-dev

 

编译错误: Fatal Error:  X11/extensions/XTest.h :没有那个文件或目录

解决方方法:

 

sudo apt-get install xorg-dev

 

 

Category: 未分类 | Tags:
1
28
2016
9

使用python3 request模块模拟登录

首先我们使用request模块模拟登录是一件非常简单的事情,但是我花了一晚上的时间来弄明白他

s = request.Session()
data = {"Username":"xxxx","Password":"xxxx"}
headers = {"User-Agent":"........."}
url_login = r"http://xxxx.xxxxxxxxxxxxxx"
url = r"http://xxx.xxxxxxxx.xxxxx"
s.post(url_login,data,headers = header)
ret = s.get(url)

 

看起来非常简单,但是因为url_login并不是你的login界面,而是命令发出的一个界面……所以如何找到这个网址就成了我一个晚上都在研究的问题

 

方式1: 无数次实验登录并跟踪

失败原因: 跳转过程中post命令在审查元素里面没有了

 

方式2: 找firebug

失败原因: 好像下不来

 

终于来到伟大的方法三:

输入一个错误的密码看她的Query-string

 

然后就好了

感觉自己的智商被完草。。。

Category: 未分类 | Tags: python 爬虫
1
25
2016
0

我的第一个小爬虫

import urllib
import urllib.request
import bs4

def download(url):
    responce = urllib.request.urlopen(url);
    if responce.getcode() != 200:
        print('Wrong in Download')
        return None
    soup = bs4.BeautifulSoup(responce.read(),'html.parser',from_encoding = 'utf-8')
    return soup


zhedaodi shi shenme bug??????????​

import bs4
import urllib

def character(x):
    if 'a' <= x and x<='z':
        return False
    if 'A' <= x and x<='Z':
        return False
    if x=='.':
        return False
    return True

def analyze(soup):
    F = open('文本输出.txt','a',encoding = 'utf-8')

    L = soup.find('h1')
    string = L.get_text()
    string = string + '\n'
    F.write(string)
    A = soup.find('div',id = "content")
    string = A.get_text()
    string = string + '\n'
    F.write(string)
    F.close()
    flag = False
    Clist = soup.find_all('a')
    for C in Clist:
        if C.get_text()=="下一章":
            newurl = C['href']
            flag = True
            break
    if flag:
        return newurl
    else:
        return None

    

 

import downloader
import analyzer
import time
prefix = r'http://www.lingdiankanshu.com/html/0/175/'
url = r'75298.html'
n = 1
while True:
    now = time.time()
    soup = downloader.download(prefix + url)
    if soup == None:
        print('Finished or Error')
        break
    url = analyzer.analyze(soup)
    print('Chapter',n,'finished in',time.time()-now,'seconds')
    if url == None:
        print('No found next!')
        break
    n = n + 1
    

 

Category: 未分类 | Tags:
7
10
2015
0

bzoj 4173 数学

这道题进去看status发现代码好短,肯定有什么规律,就把后面那部分打个表一看发现就是n*m然后就交了一发Wa了……以为结论是错的后来去找题解发现是对的,就是有个地方忘记mod了

至于证明吗看PoPoQQQ大神的题解吧: http://blog.csdn.net/PoPoQQQ/article/details/46820313

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#include <iostream>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
};
const int  mod = 998244353;
inline LL phi(LL x){
	LL i,ret=x;
	for (i=2;i*i<=x;i++){
		if (x%i==0){
			ret=ret/i*(i-1);
			while (x%i==0) x/=i;
		}
	}
	if (x!=1) ret=ret/x*(x-1);
	return ret;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	LL n,m;
	cin>>n>>m;
	LL a=phi(n)%mod,b=phi(m)%mod;
	n%=mod; m%=mod;
	a=a*b%mod;
	a=a*n%mod;
	a=a*m%mod;
	cout<<a<<endl;
	return 0;
}

 

Category: 未分类 | Tags: bzoj 结论题
7
6
2015
1

bzoj 3120: Line

首先很容易想到DP,其次很容易想到是矩阵乘法,正常的玩法矩阵是 $$ q^n*P $$ 的,这个肯定玩不过去

然后就是想办法压抑下状态,首先我们知道我们关心的只是连续男生有A个的未知数两,所以可以改成n^q然后发现知道1和2的就可以知道3的所以可以存n^(q-1)然后发现不是所有的都可以比如说1个的有n个两个的有n个那肯定不可能出现所以状态就被压下去了

但是这道题这样依然很难在bzoj上通过,所以有一个矩阵乘法的小优化(虽然这个优化对一些矩阵会很慢,但是对于这样的转移矩阵来说就会快很多)

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <algorithm>
#include <cerrno>
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int mod = 1000000007;
const int Size = 200;
struct Matrix{
	int n;
	int x[Size][Size];
	Matrix(){ memset(x,0,sizeof(x)); }
	int *operator[](int A){ return x[A]; } 
}C,ret,A,B;
inline void mul(Matrix &A,Matrix &B,Matrix &ans){
	ans.n=A.n;
	memset(C.x,0,sizeof(C.x));
	for (int k=0;k<A.n;k++)
		for (int i=0;i<A.n;i++)
			if (A[i][k])
				for (int j=0;j<A.n;j++)
					if (B[k][j]) C[i][j]=(C[i][j]+(LL)A[i][k]*B[k][j])%mod;
	for (int i=0;i<A.n;i++)
		for (int j=0;j<A.n;j++) ans[i][j]=C[i][j];
}
inline void power(Matrix &A,LL B){
	memset(ret.x,0,sizeof(ret.x)); ret.n=A.n;
	for (int i=1;i<A.n;i++)
		ret[i][i]=1;
	while (B){
		if (B&1) mul(ret,A,ret);
		mul(A,A,A);
		B>>=1;
	}
}
pair<int,int>List[100];
int tot;
int n,q,p,c[11][11];
LL m;
inline void addtrans(Matrix &A,int j1,int a1,int a2,int j2,int b1,int b2,int num){
	if (j2>q) return;
//	printf("addtrans(%d,%d,%d,%d,%d,%d) %d\n",j1,a1,a2,j2,b1,b2,num);
	int pos1=lower_bound(List+1,List+tot+1,make_pair(a1,a2))-List;
	int pos2=lower_bound(List+1,List+tot+1,make_pair(b1,b2))-List;
	A[pos1*(q+1)+j1][pos2*(q+1)+j2]+=num;
}
inline void addtrans(Matrix &A,int j1,int a,int j2,int b,int num){
	if (j2>q) return;
	A[a*(q+1)+j1][b*(q+1)+j2]+=num;
}
inline void work2(){
	for (int i=0;i<=n;i++)
		for (int j=0;j+i<=n;j++)
			List[++tot]=make_pair(i,j);
	A.n=B.n=tot*(q+1)+q+1;
	for (int j=0;j<=q;j++)
		for (int a1=0;a1<=n;a1++)
			for (int a2=0;a1+a2<=n;a2++)
				for (int k1=0;k1<=a1;k1++)
					for (int k2=0;k2<=a2;k2++)
						addtrans(A,j,a1,a2,j+(k1+k2==n),n-k1-k2,k1,c[a1][k1]*c[a2][k2]);
	power(A,m);
	int p=lower_bound(List+1,List+tot+1,make_pair(n,0))-List;
	B[0][p*(q+1)]=1;
	mul(B,ret,B);
	int ans=0;
	for (int i=0;i<B.n;i++) ans=(ans+B[0][i])%mod;
	printf("%d\n",ans);
}
	
inline void work1()
{
	A.n=B.n=n*(q+1)+(q+1);
	for (int j=0;j<=q;j++)
		for (int i=0;i<=n;i++)
			for (int k=0;k<=i;k++)
				addtrans(A,j,i,j+(k==n),n-k,c[i][k]);
	power(A,m);
	B[0][n*(q+1)]=1;
	mul(B,ret,B);
	int ans=0;
	for (int i=0;i<B.n;i++) ans=(ans+B[0][i])%mod; 
	printf("%d\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("line.in","r",stdin);
	freopen("line.out","w",stdout);
#endif
	n=read(); scanf("%lld",&m),p=read(),q=read();
	c[0][0]=1;
	for (int i=1;i<=n;i++){
		c[i][0]=1;
		for (int j=1;j<=i;j++)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	if (p==0){ printf("0\n"); return 0; }
	if (p==1){ printf("1\n"); return 0; }
	if (p==2){ work1(); return 0; }
	work2(); return 0;
}

 

Category: 未分类 | Tags:
7
4
2015
0

今日跪卢爷之 bzoj 4160: [Neerc2009]Exclusive Access 2

首先这样一道题我这样的蒟蒻肯定是不会的了

只有卢爷很快就能秒掉这种题目拉

下面是我们的对话:

 “卢爷,4160怎么做?”

“4160,什么题阿?”于是打开bzoj开始翻"哦,这道题阿,我也不会做"

"那您是怎么A掉的?" "就是随便猜了个性质,就是求出独立集覆盖就可以了"

“为什么?” “你感受以下就是可以的”

于是我感受了一下

然后就没了

 
//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#include <iostream>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 15;
int a[N][N];
int list[200];
int f[1<<N],ok[1<<N];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int m=read(),n=0;
	char s1[3],s2[3];
	memset(list,-1,sizeof(list));
	for (int i=1;i<=m;i++){
		scanf("%s%s",s1,s2);
		if (list[s1[0]]==-1) list[s1[0]]=n++;
		if (list[s2[0]]==-1) list[s2[0]]=n++;
		int x=list[s1[0]],y=list[s2[0]];
		a[x][y]=a[y][x]=1;
	}
	for (int s=1;s<(1<<n);s++){
		ok[s]=1;
		for (int j=0;j<n;j++)
			if (s>>j&1)
				for (int k=0;k<n;k++)
					if (s>>k&1)
						if (a[j][k] || a[k][j])
							ok[s]=0;	
	}
	for (int s=1;s<(1<<n);s++){
		f[s]=100000;
		if (ok[s]){
			f[s]=1; continue;
		}
		for (int s0=(s-1)&s;s0;s0=(s0-1)&s){
			if (ok[s0] && f[s^s0]<f[s]) f[s]=f[s^s0]+1;
		}
	}
	printf("%d\n",f[(1<<n)-1]-2);
	return 0; 
}

 

 

6
29
2015
2

【bzoj2229】[Zjoi2011]最小割

首先学习一下fhq的最小割树理论

应该是比较好理解的,然后只需要求n此最小割就可以得到任意两点之间的最小割了,因为大错一个字母然后拜样例所赐一直在疯狂的wa然后……然后&然后就没有了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <climits>
#include <queue>
#include <deque>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 155,M=3010;
struct edge{
	int to,flow;
	edge(int to=0,int flow=0):to(to),flow(flow){}
}e[M*2];
vector<int>g[N];
int vis[N],q[N],d[N],cnt;
inline void connect(int x,int y,int f){
	e[cnt]=edge(y,f); g[x].push_back(cnt++);
	e[cnt]=edge(x,f); g[y].push_back(cnt++);
}
int s,t,n,m;
int bfs(){
	int head=0,tail=1,u,v;
	memset(d,0,sizeof(d));
	q[1]=s; d[s]=1;
	while (head<tail){
		u=q[++head];
		for (vector<int>::iterator it=g[u].begin();it!=g[u].end();it++){
			if (e[*it].flow && d[e[*it].to]==0){
				d[e[*it].to]=d[u]+1;
				q[++tail]=e[*it].to;
			}
		}
	}
	return d[t];
}
int dfs(int x,int flow){
	if (x==t || flow==0) return flow;
	int f,totflow=0;
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (e[*it].flow && d[e[*it].to]==d[x]+1){
			f=dfs(e[*it].to,min(flow,e[*it].flow));
			totflow+=f; flow-=f;
			e[*it].flow-=f; e[(*it)^1].flow+=f;
			if (flow==0) return totflow;
		}
	}
	if (flow)d[x]=0;
	return totflow;
}
inline int dinic()
{
	int ret=0;
	while (bfs()) ret+=dfs(s,INT_MAX);
	return ret;
}
			
int ans[N][N];
inline void rebuild(){
	for (int i=0;i<cnt;i+=2)
		e[i].flow=e[i+1].flow=(e[i].flow+e[i+1].flow)/2;	
}
int a[N],list[N];
void solve(int l,int r){
	if (l==r) return;
	rebuild();
	s=a[l],t=a[r];
	int Flow=dinic();
	for (int i=1;i<=n;i++)
		if (d[i])
			for (int j=1;j<=n;j++)
				if (d[j]==0)
					ans[i][j]=ans[j][i]=min(ans[i][j],Flow);
	int L=l,R=r;
	for (int i=l;i<=r;i++){
		if (d[a[i]])
			list[L++]=a[i];
		else list[R--]=a[i];
	}
	for (int i=l;i<=r;i++) a[i]=list[i];
	solve(l,L-1); solve(R+1,r);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int T=read();
	while (T--){
		cnt=0; for (int i=1;i<=n;i++) g[i].clear();
		memset(ans,127,sizeof(ans));
		n=read(); m=read();
		for (int i=1;i<=m;i++){
			int x=read(),y=read(),z=read();
			connect(x,y,z);
		}
		for (int i=1;i<=n;i++) a[i]=i;
		solve(1,n);
		int Q=read();
		while (Q--){
			int now=read(),ret=0;
			for (int i=1;i<=n;i++)
				for (int j=i+1;j<=n;j++)
					if (ans[i][j]<=now) ret++;
			printf("%d\n",ret);
		}
		puts("");
	}
	return 0;
}

 

Category: 未分类 | Tags: bzoj 最小割 最小割树
6
23
2015
0

bzoj 2566: xmastree

第一次写维护点分治的树

然后因为大错一个数字调了半个小时是在蛋疼,最近开的坑太多赶脚没有时间填了

算了一点点来吧

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#include <iostream>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 12010;
int start[N],to[N<<1],next[N<<1],len[N<<1],cnt,size[N],q[N],d[N];
int vis[N],use[N],fa[N],Pre[N],col[N],fl[N],inf=INT_MAX,p[N][20],pl[N][20];
int n,m,T;
multiset<pair<int,int> >S[N];
multiset<int>ans;
multiset<pair<int,int> >::iterator it,i1,i2;
inline void connect(int x,int y,int l){
	to[++cnt]=y; next[cnt]=start[x]; start[x]=cnt; len[cnt]=l;
}
inline int bfs(int x,int flag=0)
{
	vis[x]=1;
	int head=0,tail=1,u,v;
	q[1]=x; vis[x]=1;
	while (head<tail){
		u=q[++head];
		for (int p=start[u];p;p=next[p]){
			if (!vis[to[p]]&&!use[to[p]]){
				q[++tail]=to[p];
				fa[to[p]]=u;
				vis[to[p]]=1;
				if (flag==2){
					d[to[p]]=d[u]+1;
					fl[to[p]]=len[p];
				}
			}
		}
	}
	for (int i=1;i<=tail;i++) vis[q[i]]=0;
	if (flag==0||flag==2){
		return tail;
	}
	for (int i=1;i<=tail;i++){
		int x=q[i];
		size[x]=0;
	}
	int Max=tail+1,cur=0,y=-1;
	for (int i=tail;i;i--){
		int x=q[i];
		size[x]++; size[fa[x]]+=size[x];
		cur=0;
		for (int p=start[x];p;p=next[p])
			if (to[p]!=fa[x] && vis[to[p]]){
				cur=max(cur,size[to[p]]);
			}
			
		cur=max(cur,tail-size[x]);
		if (cur<Max){
			Max=cur;
			y=x;
		}
	}
	return y;
}
inline int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	int ans=0,j;
	while (d[x]>d[y]){
		for (j=1;d[p[x][j]]>=d[y];j++);
		ans+=pl[x][j-1]; x=p[x][j-1];
	}
	while (x!=y){
		for (j=1;p[x][j]!=p[y][j];j++);
		ans+=pl[x][j-1]+pl[y][j-1];
		x=p[x][j-1],y=p[y][j-1];
	}
	return ans;
}
void dfs(int x,int f){
	x=bfs(x,1);
	int n=bfs(x,0);
	use[x]=1; Pre[x]=f;
	for (int i=1;i<=n;i++)
		S[x].insert(make_pair(col[q[i]],lca(q[i],x)));
	int nowC=0,tot=0,flag=0;
	for (it=S[x].begin();it!=S[x].end();it++){
		if (it->X!=nowC){
			nowC=it->X;
			tot=0; flag=0;
		}
		if (it->X==nowC){
			tot++;
			if (tot<=2) flag+=it->Y;
			if (tot==2) ans.insert(flag);
		}
	}
	for (int p=start[x];p;p=next[p])
		if (!use[to[p]]) dfs(to[p],x);
}
inline int Make_Ans(multiset<pair<int,int> >& S,int c){
	i1=i2=S.upper_bound(make_pair(c,-1));
	if (i1==S.end() || i1->X!=c) return inf;
	i2++;
	if (i2==S.end() || i2->X!=c) return inf;
	int ret=i1->Y+i2->Y;
	return ret;
}
void modify(int x,int y,int c1,int c2){
	if (x==0) return;
	int d=lca(x,y);
	set<int>::iterator now=ans.find(Make_Ans(S[x],c1));
	if (now!=ans.end()) ans.erase(now);
	S[x].erase(S[x].find(make_pair(c1,d)));
	ans.insert(Make_Ans(S[x],c1));
	
	now=ans.find(Make_Ans(S[x],c2));
	if (now!=ans.end()) ans.erase(now);
	S[x].insert(make_pair(c2,d));
	ans.insert(Make_Ans(S[x],c2));
	
	modify(Pre[x],y,c1,c2);
}
int init()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	for (int i=1;i<=n;i++) col[i]=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		connect(x,y,z);
		connect(y,x,z);
	}
	bfs(1,2); d[0]=-1;
	for (int i=1;i<=10;i++) ans.insert(inf); 
	for (int i=1;i<=n;i++) p[i][0]=fa[i],pl[i][0]=fl[i];
	for (int j=1;j<20;j++)
		for (int i=1;i<=n;i++)
			p[i][j]=p[p[i][j-1]][j-1],
			pl[i][j]=pl[i][j-1]+pl[p[i][j-1]][j-1];
	dfs(1,0);
	return 0;
}
inline void show(){
	printf("show=====\n");
	for (multiset<int>::iterator it=ans.begin();it!=ans.end();it++)
		printf("%d ",*it);
	printf("\nover=====\n");
}
void work()
{
	T=read();
	printf("%d\n",*ans.begin());
//	show();
	while (T--){
		int x=read(),c=read();
		modify(x,x,col[x],c);
		col[x]=c;
		printf("%d\n",*ans.begin());
//		show();
	}
}
int main()
{
	init();
	work();
	return 0;
}

 

Category: 未分类 | Tags: bzoj 点分治 点分治树

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com