Skip to content

Latest commit

 

History

History
312 lines (256 loc) · 7.67 KB

6-杂项.md

File metadata and controls

312 lines (256 loc) · 7.67 KB

杂项

整数哈希

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//https://codeforces.com/blog/entry/62393

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;

GCC位运算

需要gcc编译器

  • int __builtin_ffs (unsigned int x) 返回x的最后一位1的是从后向前第几位,比如7368(1110011001000)返回4。

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

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

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

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

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

来源 https://blog.csdn.net/yuer158462008/article/details/46383635

对拍

for windows

#include<bits/stdc++.h>
using namespace std;

//输入文件  input.in
//正确的程序名   ac.cpp  ac.exe  ac.out
//待验证的程序名  wa.cpp  wa.exe  wa.out

void gen(){//生成INPUT内的数据
	FILE *op=fopen("input.in","w");
	//mt19937 RAND(time(nullptr));
	//uniform_int_distribution<int>(1,100)(RAND);//范围内均匀随机整数
	//fprintf(op,"%d\n",233);
	fclose(op);
}

bool check(){//比较 ac.out 和 wa.out 的内容  一致则返回0  否则返回非0
	return system("fc wa.out ac.out");
}

int main(){
	system("g++ wa.cpp -o wa.exe");
	system("g++ ac.cpp -o ac.exe");
	while(1){
		gen(); int st,ed;

		st=clock();
		system("ac.exe < input.in > ac.out");
		ed=clock();
		printf("ac cost %lld ms\n",(ed-st)*1000ll/CLOCKS_PER_SEC);
		
		st=clock();
		system("wa.exe < input.in > wa.out");
		ed=clock();
		printf("wa cost %lld ms\n",(ed-st)*1000ll/CLOCKS_PER_SEC);

		if(check()){
			puts("Wrong Answer");
			system("pause");
			return 0;
		}
	}
	return 0;
}

fread/fwrite实现的读写类

没用

#include <bits/stdc++.h>
using namespace std;

struct MY_IO { 
    #define MAXSIZE (1 << 20) //缓冲区大小 不小于 1 << 14
    inline bool isdigit(const char &x) {return x >= '0' && x <= '9';} //字符集 看情况改
    inline bool blank(const char &c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; }

    char buf[MAXSIZE + 1], *p1, *p2, pbuf[MAXSIZE + 1], *pp;
    MY_IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~MY_IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }

    char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? EOF : *p1++;
    }

    void pc(const char &c) {
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
    }

    template <typename T>
    bool read(T &x) {
        x = 0; char c = gc(); int f = 1;
        while (!isdigit(c) && (c != '-') && (c != EOF)) c = gc();
        if (c == EOF) return 0;
        if (c == '-') f = -1, c = gc();
        while (isdigit(c)) { x = x * 10 + (c & 15); c = gc();}
        x *= f; return 1;
    }

    template <typename T, typename... Args>
    bool read(T &x, Args &...args) {
        bool res = 1;
        res &= read(x);
        res &= read(args...);
        return res;
    }

    int gets(char *s) {
        char c = gc();
        while (blank(c) && c != EOF) c = gc();
        if (c == EOF) return 0;
        int len = 0;
        while (!blank(c) && c != EOF) *s++ = c, c = gc(), ++len;
        *s = 0; return len;
    }

    void getc(char &c) { for (c = gc(); blank(c) && c != EOF; c = gc());}

    template <typename T>
    void write(T x) {
        if (x < 0) x = -x, putchar('-');
        static char sta[55];
        int top = 0;
        do sta[top++] = x % 10 + '0', x /= 10; while (x);
        while (top) putchar(sta[--top]);
    }

    template <typename T>
    void write(T x, const char &Lastchar) {write(x); pc(Lastchar);}

    void puts(char *s) {while ((*s) != 0)pc(*s++);}

    int getline(char *s){
        char c = gc(); int len = 0;
        while (c != '\n' && c != EOF)*s++ = c, c = gc(), ++len;
        *s = 0; return len;
    }

    void putline(char *s){ while ((*s) != 0) pc(*s++); pc('\n');}
} IO;

#define read  IO.read    //读一个/多个整数
#define write IO.write   //写一个整数  
#define gc    IO.gc      //getchar() 
#define pc    IO.pc      //putchar() 
#define gets  IO.gets    //读一个指定字符集的C风格字符串 到s[0..len-1] 返回len 
#define getc  IO.getc    //读一个指定字符集的字符    
#define puts  IO.puts    //写一个C风格字符串   
#define getl  IO.getline //读一行   
#define putl  IO.putline //写一个C风格字符串并换行   

Python最短路

EPS=1e-6
M=1000000007
INF=0x3f3f3f3f
INFLL=0x3f3f3f3f3f3f3f3f
N=100010
def pause():input("\npress the enter key to exit")
import math
import sys

#二元组
class dat:
    def __init__(self,f=0,s=0):
        self.first=f
        self.second=s
    def __lt__(self,a):
        return self.second<a.second if self.first==a.first else self.first<a.first

#小根堆
class Priority_Queue:  #  数据类型必须支持<比较
    def __init__(self):
        self.q=[0]
        self.tot=0
    def up(self,x):
        while(x>1):
            if(self.q[x]<self.q[x>>1]):
                self.q[x],self.q[x>>1]=self.q[x>>1],self.q[x]
                x>>=1
            else:return
    def down(self,x):
        s=x<<1
        while(s<=self.tot):
            if(s<self.tot)and(self.q[s|1]<self.q[s]):s|=1
            if(self.q[s]<self.q[x]):
                self.q[x],self.q[s]=self.q[s],self.q[x]
                x=s
            else:return
            s<<=1
    def clear(self):
        q=[0]
        self.tot=0
    def size(self):return self.tot
    def push(self,thenew):
        self.q.append(thenew)
        self.tot+=1
        self.up(self.tot)
    def top(self):return self.q[1]
    def pop(self,k=1):
        if(self.tot==0):return
        self.q[self.tot],self.q[k]=self.q[k],self.q[self.tot]
        self.tot-=1
        self.q.pop()
        self.up(k)
        self.down(k)
#小根堆

#前向星存图
class qxx:
    def __init__(self):
        self.nex=0
        self.to=0
        self.v=0
e=[qxx() for i in range(N<<1)]
h=[0 for i in range(N)]
etot=0
def add(u,v,w):
    global e,h,etot
    etot+=1
    e[etot].nex=h[u]
    h[u]=etot
    e[etot].to=v
    e[etot].w=w
def alledge(u):  # 访问某点的所有出边
    i=h[u]
    while i:
        yield i
        i=e[i].nex
#前向星存图

dis=[INF for i in range(N)]
q=Priority_Queue()
def dij(s):
    dis[s]=1
    q.push(dat(1,s))
    while(q.size()):
        j=q.top()
        q.pop()
        if(dis[j.second]<j.first)and(dis[j.second]!=INF):continue
        for i in alledge(j.second):
            k=e[i].to
            w=e[i].w
            if(dis[k]>dis[j.second]*w)or(dis[k]==INF):
                dis[k]=dis[j.second]*w
                q.push(dat(dis[k],k))


def main():
    n,m=map(int,input().split())
    for line in sys.stdin:
        if(m==0):break
        u,v,w=map(int,line.split())
        add(u,v,w)
        m-=1
    dij(1)
    print(dis[n]%9987)
    return 0


main()
#pause()