KidGzz
Exclusive
Template
2.0
2019.10.23
目录
1. 交题必通
1.数据范围：数组大小 long long 精度 初始化
2.输入输出：多组输入输出 空格 空行 输出字符一致 样例 自己出样例。
3.交题：语言 对应的题目如果能够整除输出，不能整除+1，可以((sum+n-1)/n)
2. Decoders规划
时间规划：
1.第一个小时三个人分别工作，读题码代码，迅速切掉水题，和之前的流程一致。
2.二到四个小时三个人时刻保持两个人讨论一道题，一个人看另外一道题的状态，最大化保证题量和人员的分配，每半个小时换一下
3.最后一个小时三个人共同选择一道题并且共同A题，想数据，找破解点，共同打代码等。
交流规划：
讲题的时候先讲输入输出，然后配着样例讲题意，不要带自己的想法讲题，保证拥有两个思路。
交流思路的时候，通过将样例操作来理解思路，要交流整个思路，尽量写写伪代码，这样最终写的时候会快很多，也方便理解。
注意事项：
不允许三个人开三个题并都被卡，超过半小时仍然不换题。
能用1min处理的错误不要花费20min的代价。
3. 调错信息
1.看清楚变量类型，没说整数可能是小数类型
2.公式全都化简为用最初的变量计算，能不除尽量不除
3.调bug看双重for循环变量ij
4.if中的双等于
5.变量命名重复
4. Lower_bound 和upper_bound
5. STL重载
优先队列结构体(map,set通用)
struct node {
int x,y;
bool operator < (const node & a) const {
return x<a.x;
}
};
priority_queue <node> d;
优先队列普通抽大的
从小的往大的抽
priority_queue <int,vector<int>,greater<int> > q;
6. 进制转换
int i = 0;
while(n !=0 ) {
a[i] = n%3;
n/=3;
i++;
}
7. 关于string和数字转换
/*数字转string*/
template <class T> string _toStr(T tmp) {
stringstream ss;
ss << tmp;
return ss.str();
}
/*string转int*/
int _toInt(string tmp){
return atoi(tmp.c_str());
}
ll _toLL(string tmp){
return atoll(temp.c_str());
}
//s.substr(pos, n)截取s中从pos开始（包括0）的n个字符的子串，并返回
//s.substr(pos)截取s中从从pos开始（包括0）到末尾的所有字符的子串，并返回
/*string转char*/
string s="hello";
char a[6];
sscanf(s.c_str(), "%s", a);
java中：
数字转字符串
int i = 7;
String str = String.valueOf(i);//第一种
String str2 = i + "";//第二种
Integer it = i;
String str3 = it.toString();//第三种
字符串转数字
String str = "";
int i2 = Integer.parseInt(str);
8. 输出控制精度(long double)
cout.precision(4); //设置输出精度
cout << x << endl;
9. Int_128
#include <bits/stdc++.h>
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(ll x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int main()
{
ll a = read();
write(a);
return 0;
}
10. 遍历map
map<int, int>::iterator iter;
for(iter = _map.begin(); iter != _map.end(); iter++) {
cout << iter->first << " : " << iter->second << endl;
}
11. 判断double为整数
const double EPS 1e-6;
...
double a;
...
if(a - (double)((int)a) < EPS)
//则为整数
12. Java大数
Eclipse 有很强大的自动补全，但需要自己设置：
Window—>Preference—>Java—>Editor—>Content Assist中的Auto Activation Trigger for Java里面，添加上键盘的26个中英文字母(顺着键盘按，改成大写再按一次。)，把delay改成0
Scanner cin = new Scanner(System.in);
negate(); //取反数
abs(); //绝对
BigInteger x = new BigInteger(string);
String s = in.nextLine();
char[] chars = s.toArray();
char c = chars[0]; //c就是读入的单个字符
bitCount：
返回该数的二进制补码表示中不包扩符号位在内的位的个数。该方法在 BigIntegers 之上实现位向量风格的集合时很有用。
isProbablePrime：
如果该 BigInteger 可能是素数，则返回 true ；如果它很明确是一个合数，则返回 false 。 参数 certainty 是对调用者愿意忍受的不确定性的度量：如果该数是素数的概率超过了 1 - 1/2**certainty方法，则该方法返回 true 。执行时间正比于参数确定性的值。
6.int BigInteger互相转换
//int 转BigInteger
将int型的数赋值给BigInteger，BigInteger.valueOf(k);
//BigInteger 转int
BigInteger a = new BigInteger("123");
int b = a.intValue();
intValue，longValue，floatValue，doublue：把该数转换为该类型的数的值。
7.字符串处理
String str=z.stripTrailingZeros().toPlainString();
.stripTrailingZeros()去末尾0
.toPlainString();转字符串
8.进制处理
//进制转换
String s1 = "126656864e144ad88d7ff96badd2f68b"; // 16进制数
BigInteger b = new BigInteger(s1,16); // 16进制转成大数类型
String s2 = b.toString(8);//进制转成大数类型
13. 判断是否为平方数，+0.5防误差
int m = fljoor(sqrt(n)+0.5);
if(m*m == n)p(n)
14. 浮点数误差
15. 快读
//适用于正负整数
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF)
return 0; //EOF
while(c!='−'&&(c<'0'||c>'9'))
c=getchar();
sgn=(c=='−')?−1:1;
ret=(c=='−')?0:(c−'0');
while(c=getchar(),c>='0'&&c<='9')
ret=ret*10+(c−'0');
ret*=sgn;
return 1;
}
inline void out(int x) {
if(x>9)
out(x/10);
putchar(x%10+'0');
}
16. Vim说明
linux系统中用vim写acm代码的说明:
(注:在终端中使用以获得最佳效果)
1.打开终端 mkdir 新建文件夹 , touch 新建文件
2. vim xxx.cpp 然后写代码就可以了
3. 写好了以后直接按<F5>,会自动跳回终端编译并运行,Ctrl-C中断运行并跳回vim
4.
调试好了以后 <Ctrl-A> 复制代码到粘贴板,提交
17. 二分
查找数列里第一个大于等于val的值，返回下标
也就是c++里的lower_bound（）先判断中间的数，如果小于我们要找的key，那么就把左边的数列，包括中间的都抛弃掉first=middle+1，否则就保+留中间的数，抛弃掉右边数列len=half。
int my_lower_bound(int *arr,int size, int key){
int left = 0,right = size;
int mid;
while(left<right){
mid = (left+right)>>1;
if(arr[mid]<key)
left = mid +1;
else
right = mid;
}
return left;
}
int my_upper_bound(int *arr,int size, int key){
int left = 0,right = size;
int mid;
while(left<right){
mid = (left+right)>>1;
if(arr[mid]>key)
right = mid;
else
left = mid +1;
}、
return left;
}
18. 素数筛
//埃筛 筛map
//素数筛选（判断<MAXN 的数是否素数）
/*
* 素数筛选，判断小于MAXN 的数是不是素数。
* notprime 是一张表，为false 表示是素数，true 表示不是素数
*/
const int MAXN=1000010;
bool notprime[MAXN];//值为false 表示素数，值为true 表示非素数
void init() {
memset(notprime,false,sizeof(notprime));
notprime[0]=notprime[1]=true;
for(int i=2; i<MAXN; i++){
if(!notprime[i]) {
if(i>MAXN/i){
continue;//防止后面i*i 溢出(或者i,j 用longlong)
}
//直接从i*i 开始就可以，小于i 倍的已经筛选过了, 注意是j+=i
for(int j=i*i; j<MAXN; j+=i){
notprime[j]=true;
}
}
}
}
/*线筛 筛出一个只包含素数的数组
* ，存在小于等于MAXN 的素数
* prime[0] 存的是素数的个数
*/
const int MAXN=10000;
int prime[MAXN+1];
void getPrime() {
memset(prime,0,sizeof(prime));
for(int i=2; i<=MAXN; i++) {
if(!prime[i])
prime[++prime[0]]=i;
for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) {
prime[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
}
/*线筛 筛出一个只包含素数的数组
* ，存在小于等于MAXN 的素数
* prime[0] 存的是素数的个数
*/
const int MAXN=10000;
int prime[MAXN+1];
void getPrime() {
memset(prime,0,sizeof(prime));
for(int i=2; i<=MAXN; i++) {
if(!prime[i])
prime[++prime[0]]=i;
for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) {
prime[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
}
19. 快速幂和矩阵快速幂
//快速幂 (a^b)%mod
//如果求逆元，则b = mod-2;
ll pow_quick(ll a,ll b){
ll r = 1,base = a;
while(b){
if(b & 1){
r *= base;
r %= mod;
}
base *= base;
base %= mod;
b >>= 1;
}
return r;
}
//
ll pow_mul(ll a, ll b, ll p){//快速乘，计算a*b%p
ll ret = 0;
while(b){
if(b & 1) ret = (ret + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ret;
}
//矩阵快速幂定义全局变量
const ll maxn=1000+10;
const ll mod=1000000007;
const ll N = 2;
ll n = 0;
//定义一个矩阵
struct Matrix {
ll m[N][N];
};
//矩阵相乘
Matrix multi(Matrix a,Matrix b) {
Matrix c;
for(ll i=0; i<N; i++) {
for(ll j=0; j<N; j++) {
c.m[i][j]=0;
for(ll k=0; k<N; k++){
c.m[i][j] += a.m[i][k]*b.m[k][j]%mod;
}
c.m[i][j]%=mod;
}
}
return c;
}
//矩阵快速幂
Matrix power(Matrix A,ll k) {
Matrix ans,p=A;
re(ans.m,0);
for(ll i = 0; i < N; i ++){
ans.m[i][i] = 1;
}
while(k) {
if(k&1) {
ans=multi(ans,p);
k--;
}
k>>=1;
p=multi(p,p);
}
return ans;
}
int main() {
ll n;
while(~scanf("%lld",&n)) {
Matrix A = {
1,1,
1,0
};
Matrix ans =power(A,n-1);
printf("%lld\n",ans.m[0][0]);
}
return 0;
}
20. 错排
const ll mod = 1e9+7;
//取模得到一个错排值
ll D(ll n){
if(n == 1){
return 0;
}else if(n == 2){
return 1;
}
return (((n-1)%mod)*(D(n-1)+D(n-2))%mod)%mod;
}
//不取模得到一个错排值
ll D(ll n){
if(n == 1){
return 0;
}else if(n == 2){
return 1;
}
return (n-1)*(D(n-1)+D(n-2));
}
//取模打表
ll MAX = 20;
ll D[MAX];
void getD(ll n){
D[1] = 0;
D[2] = 1;
for(ll i = 3; i <= MAX; i ++){
D[i] = (((n-1)%mod)*(D[n-1]+D[n-2])%mod)%mod;
}
}
//不取模打表
ll MAX = 20;
ll D[MAX];
void getD(ll n){
D[1] = 0;
D[2] = 1;
for(ll i = 3; i <= MAX; i ++){
D[i] = (n-1)*(D[n-1]+D[n-2]);
}
}
21. 组合数
long long 范围 9223372036854775808 9e18
int 范围 2147483648 2e9
long long 能容纳的最大的组合数 33C65 3609714217008132870 3e18
int 范围能容纳的最大的组合数 17C34 2333606220 2e9
打表法一（打印当前组合数上方所有数，可以快速求出小于此值的所有组合数）
ll c[66][66];
void C(){
memset(c,0,sizeof(c));
for(ll i = 0; i <= n; i ++){
c[i][0] = 1;
for(ll j = 1;j <= i; j ++){
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
}
打表法二（打印当前组合数在杨辉三角中的一行，求同下标时的一行）
ll c[70];
void C(){
memset(c,0,sizeof(c));
c[0] = 1;
for(ll i = 1; i <= n; i ++){
c[i] = c[i-1]*(n-i+1)/i;
}
}
递归求某一个值(数值较小时，在33C65以下)
ll C(ll a,ll b){
if(b == 0 || a == b)return 1ll;
if(b == 1)return a;
return (C(a-1,b-1)+C(a-1,b));
}
取模情况：
ll n,m,mod;
//快速幂
ll pow_quick(ll a,ll b){
ll r = 1,base = a;
while(b){
if(b & 1){
r *= base;
r %= mod;
}
base *= base;
base %= mod;
b >>= 1;
}
return r;
}
//组合数
ll C(ll n, ll m){
if(m > n)
return 0;
ll ans = 1;
for(int i=1; i<=m; i++){
ll a = (n+i-m)%mod;
ll b = i%mod;
ans = (ans*(a*pow_quick(b,mod-2)%mod))%mod;
}
return ans;
}
//卢卡斯定理
ll Lucas(ll n, ll m){
if(m == 0)
return 1;
return C(n%mod, m%mod)*Lucas(n/mod,m/mod)%mod;
}
22. 欧拉函数
//求单个数的欧拉函数O(√n)
long long eular(long long n) {
long long ans = n;
for(int i = 2; i*i <= n; i++) {
if(n % i == 0) {
ans -= ans/i;
while(n % i == 0)
n /= i;
}
}
if(n > 1)
ans -= ans/n;
return ans;
}
//筛法欧拉函数
int euler[3000001];
void getEuler() {
memset(euler,0,sizeof(euler));
euler[1] = 1;
for(int i = 2; i <= 3000000; i++)
if(!euler[i])
for(int j = i; j <= 3000000; j += i) {
if(!euler[j])
euler[j] = j;
euler[j] = euler[j]/i*(i-1);
}
}
//分解质因素求欧拉函数
long long factor[100][2];
int fatCnt;
int getFactors(long long x) {
fatCnt=0;
long long tmp=x;
for(int i=1; prime[i]<=tmp/prime[i]; i++) {
factor[fatCnt][1]=0;
if(tmp%prime[i]==0) {
factor[fatCnt][0]=prime[i];
while(tmp%prime[i]==0) {
factor[fatCnt][1]++;
tmp/=prime[i];
}
fatCnt++;
}
}
if(tmp!=1) {
factor[fatCnt][0]=tmp;
factor[fatCnt++][1]=1;
}
return fatCnt;
}
getFactors(n);
int ret = n;
for(int i = 0;i < fatCnt;i++){
ret = ret/factor[i][0]*(factor[i][0]−1);
}
//线性筛（同时得到欧拉函数和素数表）
const int MAXN = 10000000;
bool check[MAXN+10];
int phi[MAXN+10];
int prime[MAXN+10];
int tot;//素数的个数
void phi_and_prime_table(int N) {
memset(check,false,sizeof(check));
phi[1] = 1;
tot = 0;
for(int i = 2; i <= N; i++) {
if( !check[i] ) {
prime[tot++] = i;
phi[i] = i-1;
}
for(int j = 0; j < tot; j++) {
if(i * prime[j] > N)
break;
check[i * prime[j]] = true;
if( i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
}
23. 欧拉降幂
24. 高斯消元
//高斯消元（浮点数）
#define eps 1e−9
const int MAXN=220;
double a[MAXN][MAXN],x[MAXN];//方程的左边的矩阵和等式右边的值, 求解之后x存的就是结果
int equ,var;//方程数和未知数个数
/*
* 返回0 表示无解,1 表示有解
*/
int Gauss() {
int i,j,k,col,max_r;
for(k=0,col=0; k<equ&&col<var; k++,col++) {
max_r=k;
for(i=k+1; i<equ; i++)
if(fabs(a[i][col])>fabs(a[max_r][col]))
max_r=i;
if(fabs(a[max_r][col])<eps)
return 0;
if(k!=max_r) {
for(j=col; j<var; j++)
swap(a[k][j],a[max_r][j]);
swap(x[k],x[max_r]);
}
x[k]/=a[k][col];
for(j=col+1; j<var; j++)
a[k][j]/=a[k][col];
a[k][col]=1;
for(i=0; i<equ; i++)
if(i!=k) {
x[i]−=x[k]*a[i][col];
for(j=col+1; j<var; j++)
a[i][j]−=a[k][j]*a[i][col];
a[i][col]=0;
}
}
return 1;
}
25. 数论重要定理
1.威尔逊定理
(p-1)!≡-1(mod p)
(p-1)!≡p-1(mod p)
若p为质数，则p能被(p-1)!+1整除
2.欧拉定理
若n,a互质，则a^φ(n)≡ 1 (mod n)
3.孙子定理(中国剩余定理)
有解
4.费马小定理
假如p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），若p能整除a，则a^(p-1) ≡0（mod p）。
京公网安备 11010502036488号