二进制文件读入：
输入重定向到一个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;
评论 (0)
