【代码模板】不存在的NOIP2016-白红宇

【代码模板】不存在的NOIP2016

阅读量：5332 次

发布时间：2019-06-15

本文共 7399 字，大约阅读时间需要 24 分钟。

当年中二，零碎模板

0x01gmath

/** 占坑待填 20171004* Bigint高精度* 数据结构模板* 图论算法模板* 数学完善*///头文件模板#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;//预处理定义typedef long long LL;typedef long double LD;#define fst first#define sec second#define mp make_pairconst int N = 1e5, inf = 1e9; //代替define的写法 & e计数法的使用int readint(){ //readint好简单啊为什么。。。 int x=0, op=1; char ch = getchar(); //一定要赋初始值 while(ch < '0' || ch > '9'){ if(ch=='-')op=-1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x=x*10+ch-'0'; ch = getchar(); } return x*op;}//gmath数学库//用的时候记得加typedef long long LL;//int pri[N];//decom: vector
                    
                     ;//素数int pri[N];void get_prime(int n){ //诶氏筛法 pri[1] = 1; for(int i = 2; i*i <= n; i++)if(!pri[i]) for(int j = 2*i; j <= n; j+=i) pri[j] = 1;}//数论LL gcd(LL a, LL b){ return b==0 ? a : gcd(b,a%b); }LL lcm(LL a, LL b){ return a/gcd(a,b)*b; }LL exgcd(LL a, LL b, LL &x, LL &y){ if(!b){ x = 1, y = 0; return a; } LL r = exgcd(b, a%b, x, y); LL t = x; x = y; y = t-a/b*y; return r;}/*vector
                     
                       Decom(int n){ //haveBUG int i; vector
                      
                       res; res.push_back(1); for(int i = 2; i <= n; i++){ if(n == 1)break; while(n%i == 0){ res.push_back(i); n /= i; } } if(n)res.push_back(n); return res;}*///快速幂，快速乘LL mul(LL a, LL b, LL p){ LL x = 0; while(b){ if(b&1)x=(x+a)%p; a = (a<<1)%p; b >>= 1; } return x;}LL mul(LL a, LL b){ LL x = 0; while(b){ if(b&1)x += a; a <<= 1; b >>= 1; } return x;}LL pow(LL a, LL b, LL p){ LL x = 1; while(b){ if(b&1)x = mul(x,a,p)%p; a = mul(a,a,p)%p; b >>= 1; } return x%p;}LL pow(LL a, LL b){ LL x = 1; while(b){ if(b&1)x = mul(x,a); a = mul(a,a); b >>= 1; } return x;}//计算几何学struct Point{ double x, y; }; //点typedef Point Vector; //向量struct Segment{ Point p1, p2; }; //线段typedef Segment Line; //直线class Circle{ public: Point c; double r; Circle(Point c = Point(), double r = 0.0):c(c),r(r){}};//typedef vector
                       
                         Polygon; //多边形//排序算法模板int swap(int &a, int &b){ int t = a; a = b; b = t; }//冒泡排序//1.相邻的数据两两比较,小数放前面,大数放后面//2.这样每一次操作过后最小的数就被排在了最前面void BubbleSort(int a[], int n){ for(int i = 1; i < n; i++){ //循环有序数组,每次循环后保证到i位置的值是有序的。 for(int j = n; j > i; j--) //循环无序数组两两比较 if(a[j] < a[j-1])swap(a[j],a[j-1]); //如果是逆序对就交换(保证每次把最小的值往前交换) //Print(a,n); }}//插入排序//1.数据分为两部分,一开始有序部分包含1个元素//2.依次将无序部分的元素插入到有序部分当中void InsertSort(int a[], int n){ //直接插入排序 for(int i = 2; i <= n; i++){ //遍历无序部分,每次取出第一个元素 int j = i-1, k = a[i]; //j为当前下标, k为无序部分第一个元素 while(j>=1 && k
                        
                          r)return ; //递归出口,越界返回 int k = a[l];//k就是基准数(k的选取与内循环的找数顺序有关) int i = l, j = r;//区间 while(i < j){ //i==j时,两数相遇, //顺序有影响,先从右往左找,找到第一个比基准数小的位置 while(i
                         
                          =k)j--;//切记‘>=’(可以忽略掉与k相等的值,不然i永远不会大于j,则死循环) //然后从左往右找到第一个比基准数大的位置 while(i

G[N], rG[N]; vector

vs, cmp[N]; int vis[N], book[N], cnt; void dfs(int u){ if(vis[u])return ; vis[u] = 1; for(int i = 0; i < G[u].size(); i++)dfs(G[u][i]); vs.push_back(u); } void rdfs(int u){ if(book[u])return ; book[u] = cnt; cmp[cnt].push_back(u); for(int i = 0; i < rG[u].size(); i++)rdfs(rG[u][i]); }};struct Bigint{ vector

s; int is_minus; Bigint(long long num = 0, int ok = 1){ *this = num; is_minus = ok;}//构造函数,元素初始值为0 Bigint operator = (long long num){ s.clear(); do{ s.push_back(num%10); num /= 10; }while(num > 0); return *this; } Bigint operator = (const string& str){ s.clear(); for(int i = str.size()-1; i >= 0; i--) if(str[i] == '-')is_minus = -1; else s.push_back(str[i]-'0'); } Bigint operator + (const Bigint& b)const{ Bigint c; c.s.clear(); Bigint n = *this, m = b; if(n.is_minus==-1 && m.is_minus==1){ c = m-n; }else if(n.is_minus==1 && m.is_minus==-1){ c = n-m; }else { if(n.is_minus==-1 && m.is_minus==-1) c.is_minus = -1; int x = 0, len = max(n.s.size(),m.s.size());//x是进位 for(int i = 0; i < len; i++){ if(len >= n.s.size())n.s.push_back(0);//不够长的话补0 if(len >= m.s.size())m.s.push_back(0); c.s.push_back(n.s[i]+m.s[i]+x); x = c.s[i]/10; c.s[i] %= 10; } if(x)c.s.push_back(x);//最高进位 len = c.s.size()-1; while(c.s[len]==0 && len>0)len--; c.s.resize(len+1); } return c; } Bigint operator - (const Bigint& b)const{ Bigint n = *this, m = b; int ok = 1; //保证被减数大于减数 if(n.s.size()

0)len--;//删去多余的0 c.s.resize(len+1); //c.s.back() *= ok; c.is_minus = ok; return c; } Bigint operator * (const Bigint& b)const{ Bigint n = *this, m = b; n.s.insert(n.s.begin(),0); m.s.insert(m.s.begin(), 0); Bigint c; c.s.clear(); if(n.is_minus==-1 && m.is_minus==1)c.is_minus = -1; if(n.is_minus==1 && m.is_minus==-1)c.is_minus = -1; c.s.resize(n.s.size()+m.s.size()); for(int i = 1; i < n.s.size(); i++){ int x = 0; //进位 for(int j = 1; j < m.s.size(); j++){ c.s[i+j-1] += n.s[i]*m.s[j] + x;//原数+当前乘积+上次乘机进位 x = c.s[i+j-1]/10; c.s[i+j-1] %= 10; } c.s[i+m.s.size()-1] = x;//进位 } c.s.erase(c.s.begin()); int len = c.s.size(); while(c.s[len]==0 && len>0) len--; //删除多余的0 c.s.resize(len+1); return c; }};istream& operator >> (istream &in, Bigint& x){ string s; if(in>>s) x = s; return in;}ostream& operator << (ostream &out, const Bigint& x){ if(x.is_minus == -1)out<<-1*x.s[x.s.size()-1]; else out<

= 0; i--)out<

0x02STL

//提供了STL的范例//顺序容器：vector, deque, list//关联容器：set, map,//适配容器：stack, queue, priority_queue#include
    
     #include
     
        //基于红黑树#include
        //基于平衡二叉树#include
       
          //时间换空间(逃#include
        
          //各种黑科技#include
         
          using namespace std;//操作整理：声明，插入，删除，查找，遍历//用法整理：你自己想啊void setting(){ set
          
           myset; //声明int类型的集合(突然发现重名好像不会炸233333) //1. 基本操作 myset.insert(233); //往里面添加元素(重复插入无效) myset.erase(233); //删除里面的某个元素(如果不存在该元素则不操作)(这里也可以用迭代器删除区间) myset.count(233); //查询集合中是否存在某个元素 myset.clear(); //清空集合 //2. 迭代器 myset.insert(233); myset.insert(322); set
           
            ::iterator it; //如果重名声明迭代器的时候会炸掉 set
            
             ::reverse_iterator rit; //反向迭代器 for(it = myset.begin(); it != myset.end(); it++){ cout<<*it<<" "; } cout<<"\n"; for(rit = myset.rbegin(); rit != myset.rend(); rit++){ cout<<*rit<<" "; } cout<<"\n"; //3. 熟练搞事 cout<< (myset.find(233)==myset.begin()) <<" \n"; //查找键值的位置并返回迭代器 cout<< *myset.lower_bound(234)<<"\n"; //返回第一个>=key的元素的迭代器 cout<< *myset.upper_bound(233)<<"\n"; //返回第一个>key的元素的迭代器}void maping(){ map
             
              mymap; //左键右值 //1. 基本操作，，同为关联容器,基本和set差不多吧 mymap[5] = 7; //添加元素(注意 "mymap[0];" 同样往map中添加了元素，只是没有赋值而已) //2. 迭代器 map
              
               ::iterator it = mymap.begin(); cout<<(it->first)<<" "<<(it->second)<<"\n"; //map遍历时访问的是pair类型 //3. }void bitsetting(){}void stringing(){ string str = "123456789"; char ch[110]="233"; //构造函数 str = string(ch); //用c语言字符串s初始化 str = string(5,'c'); //用5个字符c初始化 string s1 = str; //赋值操作 //基本特性 str.size(); //返回大小 //各种操作 str.substr(0, 2); //返回子串,返回0开始的由两个字符组成的字符串}int main(){ stringing(); cout<<"Hello World"<

0x03框架什么的

//头文件模板#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    //命名空间using namespace std;//声明与宏定义typedef long long LL;typedef long double LD;#define fst first#define sec second#define mp make_pair//常量定义const int N = 1e5, inf = 1e9; //代替define的写法 & e计数法的使用//输入输出优化int readint(){ //readint好简单啊为什么。。。 int x=0, op=1; char ch = getchar(); //一定要赋初始值 while(ch < '0' || ch > '9'){ if(ch=='-')op=-1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x=x*10+ch-'0'; ch = getchar(); } return x*op;}int main(){ cout<<"Hello World"<

转载于:https://www.cnblogs.com/gwj1314/p/9444889.html

你可能感兴趣的文章