基础算法
快读
inline char nc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF
: *p1++;
}
template <typename T>
bool rn(T &v) {
static char ch;
while (ch != EOF && !isdigit(ch)) ch = nc();
if (ch == EOF) return false;
for (v = 0; isdigit(ch); ch = nc()) v = v * 10 + ch - '0';
return true;
}
template <typename T>
void o(T p) {
static int stk[70], tp;
if (p == 0) {
putchar('0');
return;
}
if (p < 0) {
p = -p;
putchar('-');
}
while (p) stk[++tp] = p % 10, p /= 10;
while (tp) putchar(stk[tp--] + '0');
}对拍
windows
@echo off //关掉输入显示，否则所有的命令也会显示出来
:loop
rand.exe > in.txt //生成随机输入
my.exe < in.txt > myout.txt
std.exe < in.txt > stdout.txt
fc myout.txt stdout.txt //比较文件
if not errorlevel 1 goto loop //不为1继续循环，fc在文件相同时返回0，不同时返回1
pause //不同时暂停，你可以看in.txt里的数据
goto loop //看完数据，按任意键结束暂停，继续循环linux
#!/bin/bash
while true; do
./r > input //生成随机事件
./a < input > output.a
./b < input > output.b
diff output.a output.b //文本比较
if [ $? -ne 0 ] ; then break;fi //判断返回值
donewys排 在四代i3上 0.8s过1e8
void sort(unsigned *a, int n) {
#define N 100000000
#define D 256
#define D1 255
#define cal(w, w2, tw, op)
p = w2 - 1;
for (i = 0; i < D; ++i) rs[i] = p, p += tw[i];
for (i = 0; i < N; i += 8) {
p = w + i;
*++rs[p[0] op] = p[0], *++rs[p[1] op] = p[1], *++rs[p[2] op] = p[2],
*++rs[p[3] op] = p[3], *++rs[p[4] op] = p[4],
*++rs[p[5] op] = p[5], *++rs[p[6] op] = p[6],
*++rs[p[7] op] = p[7];
}
unsigned b[N], *rs[D], t0[D], t1[D], t2[D], t3[D];
unsigned *p, i, x;
for (i = 0; i < N;) {
#define A
x = a[i], ++t0[x & D1], ++t1[x >> 8 & D1], ++t2[x >> 16 & D1],
++t3[x >> 24], ++i;
A A A A
#undef A
}
cal(a, b, t0, &D1);
cal(b, a, t1, >> 8 & D1);
cal(a, b, t2, >> 16 & D1);
cal(b, a, t3, >> 24);
}void sort(unsigned *a, int n) {
unsigned *b = new unsigned[n];
unsigned cnt1[256], cnt2[256], cnt3[256], cnt4[256];
memset(cnt1, 0, sizeof(cnt1));
memset(cnt2, 0, sizeof(cnt2));
memset(cnt3, 0, sizeof(cnt3));
memset(cnt4, 0, sizeof(cnt4));
for (int i = 0; i < n; i++) {
cnt1[a[i] & 255]++;
cnt2[(a[i] >> 8) & 255]++;
cnt3[(a[i] >> 16) & 255]++;
cnt4[a[i] >> 24]++;
}
for (int i = 1; i < 256; i++) {
cnt1[i] += cnt1[i - 1];
cnt2[i] += cnt2[i - 1];
cnt3[i] += cnt3[i - 1];
cnt4[i] += cnt4[i - 1];
}
for (int i = n - 1; i >= 0; i--) b[--cnt1[a[i] & 255]] = a[i];
for (int i = n - 1; i >= 0; i--) a[--cnt2[(b[i] >> 8) & 255]] = b[i];
for (int i = n - 1; i >= 0; i--) b[--cnt3[(a[i] >> 16) & 255]] = a[i];
for (int i = n - 1; i >= 0; i--) a[--cnt4[b[i] >> 24]] = b[i];
delete[] b;
}二分
二分找到符合题目要求中最大的答案
int l = minn, r = maxx;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
//答案为l - 1
//当[minn, maxx]内所有结果均不满足要求，答案为minn - 1二分找到符合题目要求中最小的答案
int l = minn, r = maxx;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
//答案为l
//当[minn, maxx]内所有结果均不满足要求，答案为maxxJAVA高精度
一、保留2位小数:
temp.setScale(2, BigDecimal.ROUND_HALF_UP);
二、当需要做除法时
temp.divide(BigDecimal.valueOf(除数), 保留位数, BigDecimal.ROUND_HALF_UP)
注意，保留位数为必填参数，否则会报错
参数说明:
ROUND_CEILING
如果BigDecimal是正的，则做ROUND_UP操作；如果为负，则做ROUND_DOWN操作
ROUND_DOWN
从不在舍弃(即截断)的小数之前增加数字
ROUND_FLOOR
如果BigDecimal为正，则作ROUND_UP；如果为负，则作ROUND_DOWN
ROUND_HALF_DOWN
若舍弃部分>.5，则作ROUND_UP；否则，作ROUND_DOWN
ROUND_HALF_EVEN
如果舍弃部分左边的数字为奇数，则作ROUND_HALF_UP；如果它为偶数，则作ROUND_HALF_DOWN
ROUND_HALF_UP
若舍弃部分>=.5，则作ROUND_UP；否则，作ROUND_DOWN
ROUND_UNNECESSARY
该“伪舍入模式”实际是指明所要求的操作必须是精确的，，因此不需要舍入操作
ROUND_UP
总是在非0舍弃小数(即截断)之前增加数字。
valueOf:赋初值
add:+
subtract:-
multiply:*
divide:/
remainder：this % val
divideAndRemainder：a[0]=this / val; a[1]=this % val
pow：a.pow(b)=a^b
gcd,abs:公约数，绝对值
negate：取负数
signum：符号函数
mod：a.mod(b)=a%b
shiftLeft:左移，this << n ，this*2^n
shiftRight:右移，this >> n，this/2^n
and:&
or:|
xor:^
not:!
bitLength：返回该数的最小二进制补码表示的位的个数，即 不包括 符号位 (ceil(log2(this <0 ? -this : this + 1)))。对正数来说，这等价于普通二进制表示的位的个数
bitCount：返回该数的二进制补码表示中不包扩符号位在内的位的个数。该方法在 BigIntegers 之上实现位向量风格的集合时很有用
isProbablePrime：如果该 BigInteger 可能是素数，则返回 true ；如果它很明确是一个合数，则返回 false 。 参数 certainty 是对调用者愿意忍受的不确定性的度量：如果该数是素数的概率超过了 1 - 1/2**certainty方法，则该方法返回 true 。执行时间正比于参数确定性的值
compareTo：根据该数值是小于、等于、或大于 val 返回 -1、0 或 1
equals：判断两数是否相等，也可以用compareTo来代替
min，max：取两个数的较小、大者
intValue，longValue，floatValue，doublue：把该数转换为该类型的数的值
Comments NOTHING