总结-小技巧

快速乘

inline long long Smul(long long a, long long b, long long mod) {
	long long l = a * (b >> 25ll) % mod * (1ll << 25) % mod;
	long long r = a * (b & ((1ll << 25) - 1)) % mod;
	return (l + r) % mod;
}

Hash常用质数

131
13331
122777
2999993
9999991
1e9+7/9
unsigned...

尺取法

尺取法可以(O(n))解决：对给定的一个序列，在序列中寻找包含全部需求的，长度最小的一段子序列一类问题

LuoguP1381 单词背诵

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("
-----------
")
#define D_e(x) std::cout << (#x) << " : " <<x << "
"
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#define Pause() system("pause")
#include <ctime>
#define TIME() fprintf(stderr, "
TIME :　%.3lfms
", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;
#define D_e(x) ;
#define FileOpen() ;
#define FilSave ;
#define Pause() ;
#define TIME() ;

#endif

struct ios {
	template<typename ATP> ios& operator >> (ATP &x) {
		x = 0; int f = 1; char c;
		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
		x *= f;
		return *this;
	}
}io;

using namespace std;

template<typename ATP> inline ATP Min(ATP a, ATP b) {
	return a < b ? a : b;
}
template<typename ATP> inline ATP Max(ATP a, ATP b) {
	return a > b ? a : b;
}

const int N = 100007;
const unsigned int MOD = 2999993;
const unsigned int base = 13331;

char str[N];
unsigned long long a[N], b[N];
int vis[MOD];
bool mark[MOD];
inline long long Hash(char *str) {
	int len = strlen(str + 1);
	unsigned long long val = 0;
	R(i,1,len){
		val = (val * base + (unsigned long long)(str[i] - 'a')) % MOD;
	}
	return (val + MOD) % MOD;
}
int main() {
	int n;
	io >> n;
	R(i,1,n){
		scanf("%s", str + 1);
		a[i] = Hash(str);
		mark[a[i]] = true;
	}
	int m;
	io >> m;
	int ans = 0, ans2 = 0x7fffffff;
	R(i,1,m){
		scanf("%s", str + 1);
		b[i] = Hash(str);
		if(mark[b[i]] && !vis[b[i]]){
			++ans;
			vis[b[i]] = 1;
		}
	}
	if(ans == 0){
		printf("0
0");
		return 0;
	}
	int l = 1, r = 1, tot = ans;
	Fill(vis, 0);
	while(1){
		if(!tot){
			while(!mark[b[l]]) ++l;
			if(l > m) break;
			ans2 = Min(ans2, r - l);
			if(vis[b[l]] == 1) ++tot;
			if(vis[b[l]] >= 1) --vis[b[l]], ++l;
		}
		else{
			if(r > m) break;
			if(mark[b[r]]){
				if(!vis[b[r]]) --tot;
				++vis[b[r]];
			}
			++r;
		}
	}
	printf("%d
%d", ans, ans2);
	return 0;
}

UOJ222【NOI2016】区间

线段树离散维护区间最值，尺取最优

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("
-----------
")
#define D_e(x) std::cout << (#x) << " : " <<x << "
"
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#define Pause() system("pause")
#include <ctime>
#define TIME() fprintf(stderr, "
TIME :　%.3lfms
", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;
#define D_e(x) ;
#define FileOpen() ;
#define FilSave ;
#define Pause() ;
#define TIME() ;

#endif

struct ios {
	template<typename ATP> ios& operator >> (ATP &x) {
		x = 0; int f = 1; char c;
		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
		x *= f;
		return *this;
	}
}io;

using namespace std;

template<typename ATP> inline ATP Min(ATP a, ATP b) {
	return a < b ? a : b;
}
template<typename ATP> inline ATP Max(ATP a, ATP b) {
	return a > b ? a : b;
}

const int N = 500007;

struct Tree {
	int mx, tag;
} t[N << 3];
#define ls rt << 1
#define rs rt << 1 | 1
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
inline void Pushup(int &rt) {
	t[rt].mx = Max(t[ls].mx, t[rs].mx);
}
inline void Pushdown(int &rt) {
	t[ls].tag += t[rt].tag;
	t[rs].tag += t[rt].tag;
	t[ls].mx += t[rt].tag;
	t[rs].mx += t[rt].tag;
	t[rt].tag = 0;
}
inline void Build(int rt, int l, int r) {
	if(l == r){
		t[rt].mx = 0;
		t[rt].tag = 0;
		return;
	}
	int mid = (l + r) >> 1;
	Build(lson), Build(rson);
}
inline void Updata(int rt, int l, int r, int L, int R, int w) {
	if(L <= l && r <= R){
		t[rt].mx += w;
		t[rt].tag += w;
		return;
	}
	if(t[rt].tag) Pushdown(rt);
	int mid = (l + r) >> 1;
	if(L <= mid) Updata(lson, L, R, w);
	if(R > mid) Updata(rson, L, R, w);
	Pushup(rt);
}
inline int Query(int rt, int l, int r, int L, int R) {
	if(L <= l && r <= R) return t[rt].mx;
	if(t[rt].tag) Pushdown(rt);
	int mid = (l + r) >> 1, maxx = 0;
	if(L <= mid) maxx = Max(maxx, Query(lson, L, R));
	if(R > mid) maxx = Max(maxx, Query(rson, L, R));
	return maxx;
}

struct nod {
	int l, r, len;
	bool operator < (const nod &com) const {
		return len > com.len;
	}
} a[N];
int b[N << 1];
int main() {
//FileOpen();
	int n, m;
	io >> n >> m;
	int tot = 0;
	R(i,1,n){
		io >> a[i].l >> a[i].r;
		a[i].len = a[i].r - a[i].l;
		b[++tot] = a[i].l;
		b[++tot] = a[i].r;
	}
	sort(a + 1, a + n + 1);
	sort(b + 1, b + tot + 1);
	tot = unique(b + 1, b + tot + 1) - b - 1;
	Build(1, 1, tot);
	int lst = 1, ans = 0x7fffffff;
	R(i,1,n){
		a[i].l = lower_bound(b + 1, b + tot + 1, a[i].l) - b;
		a[i].r = lower_bound(b + 1, b + tot + 1, a[i].r) - b;
		Updata(1, 1, tot, a[i].l, a[i].r, 1);
		while(t[1].mx >= m){
			ans = Min(ans, a[lst].len - a[i].len);
			Updata(1, 1, tot, a[lst].l, a[lst].r, -1);
			++lst;
		}
	}
	
	printf("%d", ans == 0x7fffffff ? -1 : ans);
	
	return 0;
}

二进制处理

#include "Head.cpp"
#include <bitset>
int main(){
	while(1){
		long long x;
		io >> x;
		cout << __builtin_popcount(x)  << endl;
		cout << bitset<32>(x) << endl;
	}
}