3
29
2016
0

长诗·

二进制文件读入:

输入重定向到一个FILE类型的指针

4bytes不可用LL,否则会全部WA掉

FILE *fin=fopen("Ryan.in","rb");
fread(&n,4,1,fin);
fread(a+1,4,n,fin);

在OJ上 采用以下方式

fread(&n,4,1,stdin);
fread(a+1,4,n,stdin);

priority_queue<int>:数值大的元素,优先级高

priority_queue<int,vector<int>,greater<int> >数值小的元素,优先级高

取堆顶元素:q.top();

queue<int>取堆顶元素:q.front();


结构体中重载运算符:

rhs指的是==运算符右边的操作元素
struct node{
    int val,pos;
    bool operator <(const node &rhs)const{
        return val<rhs.val;
    }
};

离散化:

方法一:num为元素"种数",

b从1开始:unique()-(b+1)

a从1开始lower_bound()-b

lower_bound()-(b+1)则是从0开始

方法二:

map<int,int> mp;
m=0;
for2(i,1,n){
	a[i]=read();b[i]=read();w[i]=read();
	f[2*i-1]=a[i];f[2*i]=b[i];//下标随意
}
sort(f+1,f+2*n+1);
for2(i,1,2*n) if(i==1||f[i]!=f[i-1]) mp[f[i]]=++m;//hash映射
for2(i,1,n) addedge(mp[a[i]],mp[b[i]],1,-w[i]);

 


分数的表示与输出:

一般情况:欧拉定理 概率递推:monster

模意义下:小Z的袜子(POPOQQQ)


pow(2,x) 直接(1<<x)即可 = _ =

二进制表示状态中常用


双向边(最短路)+单向边(网络流)连边:

inline void add_edge(int x,int y,ll z1,ll z2)
{
    e[++cnt]=(edge_type){y,head[x],z1};head[x]=cnt;
    e[++cnt]=(edge_type){x,head[y],z2};head[y]=cnt;
}
/*****main*******/
    F(i,1,m)
    {
        x[i]=read();y[i]=read();z[i]=read();
        add_edge(x[i],y[i],z[i],z[i]);
    }
    F(i,1,n) c[i]=read();
    c[1]=c[n]=inf;//S为1,T为n
    dijkstra();
    memset(head,0,sizeof(head));//清空head!
    cnt=1;s=1;t=2*n;
    F(i,1,n) add_edge(i,i+n,c[i],0);//点有权值
    F(i,1,m)
    {
        if (dis[y[i]]==dis[x[i]]+z[i]) add_edge(x[i]+n,y[i],inf,0);
        if (dis[x[i]]==dis[y[i]]+z[i]) add_edge(y[i]+n,x[i],inf,0);
    }
    dinic();

x是奇数 x&1

x是偶数 ~x&1


分数结构体

复数结构体


四种GCC内置位运算函数:来自richard-desktop

//返回x的最后一位1是从后向前第几位
//eg.7368(1110011001000)返回4
int __builtin_ffs(unsigned int x)

//返回前导的0的个数
int __builtin_clz(unsigned int x)

//返回后面的0个个数,和__builtin_clz相对。
int __builtin_ctz(unsigned int x)

//返回二进制表示中1的个数
int __builtin_popcount(unsigned int x)

//返回x的奇偶校验位,也就是x的1的个数模2的结果
int __builtin_parity(unsigned int x)
 

此外,这些函数都有相应的usigned long和usigned long long版本,只需要在函数名后面加上l或ll就可以了,比如int __builtin_clzll。


O(n)求逆元: 注意这里的MOD必须是素数。

inv[1]=1;
for(int i=2;i<M;i++)
 inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;

读入含空格的字符串:

F(i,0,len-1){ 
	s[i]=getchar();
       while(s[i]=='\n') s[i]=getchar();
}

数据结构的数据生成器:

数据生成器的话就模拟一个数组,
选过的就加入数组里,
然后随机选取选过的和没选过的连条边

prufer code,rand出一个数组然后哈哈。prufer编码可以O(nlogn)建出一棵n个结点的树

树还可以对1~n随机排序(就是比大小的函数写成随即返回的),然后随一个点,向他后面没有连过点的节点连边。
此外还有神马葵花型数据,莲花型数据,牵牛花型数据,串串红型数据(就是一个很长的链上挂着几个点),楼主自己试一下吧,也许就是这种极限情况的问题。

本沙茶只会先随便建一个无向图然后求MST……

图论的数据生成器

比如说有向无环图,random每条边的两个点,然后暴力判断加上去会不会出环,没我那么懒得话可以各种优化……反正只是出数据

有向无环图:编号小的连到大的(貌似没问题?)
无向图:生成一颗树然后随便再连一些边
树:1当作根,其余随机一个编号比它小的做father
如果想让树比较接近一条链可以按一定概率选father

树:for(int i=2;i<=n;++i) printf("%d %d\n",rand()%(i-1)+1,i);一定是树(不过这样不能卡暴力)
有向无环图:random_shuffle一个拓扑序,根据拓扑序连边
当然上面那个树也能生成一个序利用序连边

树:随机一堆数,搞二叉排序树,然后你懂得


奇奇怪怪的快速输入输出类:

#include<bits/stdc++.h>
using namespace std; 
struct fastin{
	static const int buffer_size=10000000;
	char buf[buffer_size],*wbuf;
	fastin(): wbuf(0) { }

	void input(FILE *file=stdin){
		buf[fread(buf,1,buffer_size,file)]=0,wbuf=buf;
	}
	void input(const char *name){
		FILE *file=fopen(name,"r");
		buf[fread(buf,1,buffer_size,file)]=0,wbuf=buf;
		fclose(file);
	}
	inline bool eoln(){
		while(*wbuf!='\n' && !isgraph(*wbuf)) ++wbuf;
		return *wbuf=='\n';
	}
	inline bool eof(){
		while(*wbuf!=0 && !isgraph(*wbuf)) ++wbuf;
		return *wbuf==0;
	}
//快速读入整数(包含负数)
	template<typename int_type> 
	inline void getint(int_type &x){
		int sgn=+1; while(!isdigit(*wbuf)) ++wbuf;
		if(*(wbuf-1)=='-') sgn=-1; x=0;
		while(isdigit(*wbuf)) x=x*10+(*wbuf++)-'0';
		if(sgn==-1) x=-x;
	}
//快速读入实数(包含负数) 
	template<typename real_type>
	inline void getreal(real_type &x){
		int sgn=+1; while(!isdigit(*wbuf)) ++wbuf;
		if(*(wbuf-1)=='-') sgn=-1; x=0;
		while(isdigit(*wbuf)) x=x*10+(*wbuf++)-'0';
		if(*wbuf=='.'){
			++wbuf;
			for(real_type v=0.1;isdigit(*wbuf);v*=0.1,++wbuf)
				x+=v*(*wbuf-'0');
		}
		if(sgn==-1) x=-x;
	}
//快速读入字符串 
	inline void getstring(char *s){
		while(!isgraph(*wbuf)) ++wbuf;
		char *p=s; while(isgraph(*wbuf)) *p++=*wbuf++; *p=0;
	}
//快速读入整行字符串(含空格,不含回车) 
	inline void getline(char *s){
		char *p=s; while(*wbuf!='\n') *p++=*wbuf++; *p=0;
	}
//读入字符 
	inline void getchar(char &ch){ ch=*wbuf++; }
}fin;


struct fastout{
	static const int buffer_size=10000000;
	char buf[buffer_size],*wbuf; int prec;
	fastout(): wbuf(buf),prec(6) { }

	void clear(){ wbuf=buf; }
	void set_precision(int newprec){ prec=newprec; }
	void output(FILE *file=stdout){
		fwrite(buf,1,wbuf-buf,file);
	}
	void output(const char *name){
		FILE *file=fopen(name,"w");
		fwrite(buf,1,wbuf-buf,file);
		fclose(file);
	}
//快速输出整数(包含负数) 
	template<typename int_type>
	inline void putint(int_type x,char extra=0){
		if(!x) *wbuf++='0';
		if(x<0) *wbuf++='-',x=-x;
		static const int maxlen=40;
		static char s[maxlen]; int len=0;
		for(;x;x/=10) s[len++]=x%10+'0';
		for(--len;len>=0;--len) *wbuf++=s[len];
		if(extra) *wbuf++=extra;
	}
//快速输出实数 
	inline void putdouble(double x,char extra=0){
		wbuf+=sprintf(wbuf,"%.*f",prec,x);
		if(extra) *wbuf++=extra;
	}
//快速输出字符串 
	inline void putstring(const char *s){
		while(*s) *wbuf++=*s++;
	}
//输出字符 
	inline void putchar(char ch){ *wbuf++=ch; }
}fout;

调用:

int main(){
	fin.input();
	fin.getint(n),fin.getint(m);	
	solve();
 	for(int i=1;i<=m;++i) fout.putint(ans[i],'\n');
	fout.output();
	return 0;
}

稍微简单一点的快速读入(非负整数):

const int BUF_SIZE = (int) 1e4 + 10;
struct fastIO {
	char buf[BUF_SIZE];
	int cur;
	FILE *in;
	fastIO () {
		cur = BUF_SIZE;
		in = stdin;
	}
	inline char nextChar () {
		if (cur == BUF_SIZE) {
			fread (buf, BUF_SIZE, 1, in);
			cur = 0;
		}
		return buf[cur++];
	}
	inline int nextInt () {
		int x = 0;
		char c = nextChar ();
		while (!('0' <= c && c <= '9')) c = nextChar ();
		while ('0' <= c && c <= '9') {
			x = x * 10 + c - '0';
			c = nextChar ();
		}
		return x;
	}
} IO;

 

 
Category: 总结 | Tags: c++ STL 乱搞 黑科技 位运算 数论 数据生成 | Read Count: 739

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

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