XCPC 基础 对拍板子 介绍Windows环境下与Linux环境下的对拍
对拍去DEV
Windows环境 以DEV为例,首先建四个源代码到一个新建文件夹中,源代码分别命名为wa.cpp,data.cpp,violent.cpp,windows.cpp,除此之外什么也不需要添加
一份错误的/需要比对的代码,导入wa.cpp
一份暴力的/用来比对的代码,导入violent.cpp
一份用来造数据的代码
一份执行对拍程序的代码
wa.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <bits/stdc++.h> using namespace std;int main () { freopen ("in.txt" , "r" , stdin); freopen ("wa.txt" , "w" , stdout); return 0 ; }
violent.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <bits/stdc++.h> using namespace std;int main () { freopen ("in.txt" , "r" , stdin); freopen ("violent.txt" , "w" , stdout); return 0 ; }
data.cpp 1 2 3 4 5 6 7 8 9 #include <bits/stdc++.h> using namespace std;int main () { struct _timeb T; _ftime(&T); srand (T.millitm); int a = rand (); printf ("%d\n" , a); }
windows.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <bits/stdc++.h> using namespace std;int main () { while (1 ) { system ("data.exe" ); system ("violent.exe" ); system ("wa.exe" ); if (system ("fc wa.txt violent.txt" )) break ; } return 0 ; }
注意,以上所有程序均需要编译并运行
前缀和(Prefix Sum) 通过构建前缀和数组,从而能做到O(1)时间复杂度的区间查询(rangeQuery)
一维前缀和 构建前缀和数组 1 2 vector<int >pre (n+1 ,0 ); for (int i=1 ;i<=n;i++) pre[i]=pre[i-1 ]+a[i];
rangeQuery
二维前缀和 构建前缀和数组 1 2 3 4 5 6 7 vector<vector<int >>pre (n+1 ,vector <int >(m+1 )); for (int i=1 ;i<=n;i++){ for (int j=1 ;j<=m;j++){ pre[i][j]=pre[i-1 ][j]+pre[i][j-1 ]-pre[i-1 ][j-1 ]+a[i][j]; } }
rangeQuery 1 2 pre[x2][y2]-pre[x2][y1-1 ]-pre[x1-1 ][y2]+pre[x1-1 ][y1-1 ];
差分(Difference) 通过构建差分数组,从而能做到O(1)时间复杂度的区间修改(rangeModify)
一维差分
单点修改,单点询问
构建差分数组
1 2 vector<int >dif (n+5 ); for (int i=1 ;i<=n;i++) dif[i]=a[i]-a[i-1 ];
rangeModify
Query
1 for (int i=1 ;i<=n;i++) b[i]+=b[i-1 ];
单点修改,区间询问
具体就是构建两个差分数组,每次单点修改的左端加1,右端也加1,全部操作执行完求前缀和,区间询问[l,r]的时候相减即可
1 2 3 4 5 6 7 8 9 10 11 12 13 vector<int >L (n+10 ),R (n+10 ); for (int i=0 ;i<k;i++){ int u,v;cin>>u>>v; L[u]++;R[v]++; } for (int i=1 ;i<=n;i++) { L[i]+=L[i-1 ]; R[i]+=R[i-1 ]; } for (int i=1 ;i<=k;i++){ int l,r;cin>>l>>r; cout<<R[r]-L[l-1 ]<<"\n" ; }
二维差分 与一维差分不同的是,二维差分数组的构建与修改均可以通过差分函数来完成
1 2 3 4 5 6 7 vector<vector<int >>dif (n+5 ,vector <int >(m+5 )); auto modify=[&](int x1,int y1,int x2,int y2,int x){ dif[x1][y1]+=x; dif[x1][y2+1 ]-=x; dif[x2+1 ][y1]-=x; dif[x2+1 ][y2+1 ]+=x; };
构建差分数组 1 2 3 4 5 for (int i=1 ;i<=n;i++){ for (int j=1 ;j<=m;j++){ modify (i,j,i,j,a[i][j]); } }
rangeModify
Query 前缀和求
1 2 3 4 5 6 for (int i=1 ;i<=n;i++){ for (int j=1 ;j<=m;j++){ dif[i][j]+=dif[i-1 ][j]+dif[i][j-1 ]-dif[i-1 ][j-1 ]; } }
间隔差分 [l,r]中间隔k个数字修改,其中r=l + k * n, 相当于[l,l+k,l+2 * k,… l + n * k]这么多数修改
构建差分数组
求和
1 2 3 4 5 for (int i=1 ;i<=sum;i++)for (int i=k;i<=sum;i++){ pre[i]+=pre[i-k]; }
高精度 版本一 太全,不实用 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 const int MAXN = 5005 ;struct bign { int len, s[MAXN]; bign (){ memset (s, 0 , sizeof (s)); len = 1 ; } bign (int num) { *this = num; } bign (const char *num) { *this = num; } bign operator = (const int num){ char s[MAXN]; sprintf (s, "%d" , num); *this = s; return *this ; } bign operator = (const char *num){ for (int i = 0 ; num[i] == '0' ; num++) ; len = strlen (num); for (int i = 0 ; i < len; i++) s[i] = num[len-i-1 ] - '0' ; return *this ; } bign operator + (const bign &b) const { bign c; c.len = 0 ; for (int i = 0 , g = 0 ; g || i < max (len, b.len); i++){ int x = g; if (i < len) x += s[i]; if (i < b.len) x += b.s[i]; c.s[c.len++] = x % 10 ; g = x / 10 ; } return c; } bign operator += (const bign &b){ *this = *this + b; return *this ; } void clean () { while (len > 1 && !s[len-1 ]) len--; } bign operator * (const bign &b){ bign c; c.len = len + b.len; for (int i = 0 ; i < len; i++){ for (int j = 0 ; j < b.len; j++){ c.s[i+j] += s[i] * b.s[j]; } } for (int i = 0 ; i < c.len; i++){ c.s[i+1 ] += c.s[i]/10 ; c.s[i] %= 10 ; } c.clean (); return c; } bign operator *= (const bign &b){ *this = *this * b; return *this ; } bign operator - (const bign &b){ bign c; c.len = 0 ; for (int i = 0 , g = 0 ; i < len; i++){ int x = s[i] - g; if (i < b.len) x -= b.s[i]; if (x >= 0 ) g = 0 ; else { g = 1 ; x += 10 ; } c.s[c.len++] = x; } c.clean (); return c; } bign operator -= (const bign &b){ *this = *this - b; return *this ; } bign operator / (const bign &b) { bign c, f = 0 ; for (int i = len-1 ; i >= 0 ; i--){ f = f*10 ; f.s[0 ] = s[i]; while (f >= b){ f -= b; c.s[i]++; } } c.len = len; c.clean (); return c; } bign operator /= (const bign &b){ *this = *this / b; return *this ; } bign operator % (const bign &b){ bign r = *this / b; r = *this - r*b; r.clean (); return r; } bign operator %= (const bign &b){ *this = *this % b; return *this ; } bool operator < (const bign &b){ if (len != b.len) return len < b.len; for (int i = len-1 ; i != -1 ; i--){ if (s[i] != b.s[i]) return s[i] < b.s[i]; } return false ; } bool operator > (const bign &b){ if (len != b.len) return len > b.len; for (int i = len-1 ; i != -1 ; i--){ if (s[i] != b.s[i]) return s[i] > b.s[i]; } return false ; } bool operator == (const bign &b){ return !(*this > b) && !(*this < b); } bool operator != (const bign &b){ return !(*this == b); } bool operator <= (const bign &b){ return *this < b || *this == b; } bool operator >= (const bign &b){ return *this > b || *this == b; } string str () const { string res = "" ; for (int i = 0 ; i < len; i++) res = char (s[i]+'0' )+res; return res; } }; istream& operator >> (istream &in, bign &x){ string s; in >> s; x = s.c_str (); return in; } ostream& operator << (ostream &out, const bign &x){ out << x.str (); return out; }
声明方式 1 2 3 bign a; a="333333333333333333333333333" ; cout<<a*a<<endl;
版本二 STL int128库函数自定义 int128范围是$-2^{127}-2^{127-1}$
unsigned int128范围是$0-2^{128}$,约39位数
给int128 赋初值不能直接用一个很大的数字,比如1E100,这样赋出来是LONG_LONG_MAX
可以使用字符串,然后一直累乘
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 using i128 = __int128; ostream &operator <<(ostream &os, i128 n) { if (n == 0 ) { return os << 0 ; } string s; while (n > 0 ) { s += char ('0' + n % 10 ); n /= 10 ; } reverse (s.begin (), s.end ()); return os << s; } i128 toi128 (const string &s) { i128 n = 0 ; for (auto c : s) { n = n * 10 + (c - '0' ); } return n; } i128 sqrti128 (i128 n) { i128 lo = 0 , hi = 1E16 ; while (lo < hi) { i128 x = (lo + hi + 1 ) / 2 ; if (x * x <= n) { lo = x; } else { hi = x - 1 ; } } return lo; } i128 gcd (i128 a, i128 b) { while (b) { a %= b; std::swap (a, b); } return a; }
常用库函数重载 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 using i64 = long long; using i128 = __int128; /** 上取整下取整 **/ i64 ceilDiv(i64 n, i64 m) { if (n >= 0) { return (n + m - 1) / m; } else { return n / m; } } i64 floorDiv(i64 n, i64 m) { if (n >= 0) { return n / m; } else { return (n - m + 1) / m; } } /** 最大值赋值 **/ template<class T> void chmax(T &a, T b) { if (a < b) { a = b; } } /** 最大公约数 **/ i128 gcd(i128 a, i128 b) { return b ? gcd(b, a % b) : a; } /** 精确开平方 **/ i64 sqrt(i64 n) { i64 s = std::sqrt(n); while (s * s > n) { s--; } while ((s + 1) * (s + 1) <= n) { s++; } return s; } /** 精确开平方 **/ i64 get(i64 n) { i64 u = std::sqrt(2.0L * n); while (u * (u + 1) / 2 < n) { u++; } while (u * (u - 1) / 2 + 1 > n) { u--; } return u; } /** 求 Log **/ int logi(int a, int b) { int t = 0; i64 v = 1; while (v < b) { v *= a; t++; } return t; } int llog(int a, int b) { if (a <= b) { int l = logi(a, b); return (l == 0 ? 0 : std::__lg(2 * l - 1)); } int l = logi(b, a + 1) - 1; assert(l > 0); return -std::__lg(l); }
sqrt 对long long使用sqrt,类型转换为long double
pdbs 头文件及命名空间,注意编译器开g++
1 2 3 #include <bits/extc++.h> using namespace __gnu_cxx;using namespace __gnu_pbds;
平衡二叉树常见成员函数 1 2 3 4 5 6 7 8 empty () / size ()insert (x) erase (x) order_of_key (x) find_by_order (x) lower_bound (x) / upper_bound (x) join (Tree) split (x, Tree)
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/extc++.h> using namespace __gnu_pbds;bool Solve () { using PII = pair<int , int >; tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> ver; map<int , int > dic; int n; cin >> n; while (n--) { int op, x; cin >> op >> x; if (op == 1 ) { ver.insert ({x, ++dic[x]}); } else if (op == 2 ) { ver.erase ({x, dic[x]--}); } else if (op == 3 ) { cout << ver.order_of_key ({x, 1 }) + 1 << endl; } else if (op == 4 ) { x--; cout << ver.find_by_order (x)->first << endl; } else if (op == 5 ) { int idx = ver.order_of_key ({x, 1 }) - 1 ; cout << ver.find_by_order (idx)->first << endl; } else if (op == 6 ) { int idx = ver.order_of_key ( {x, dic[x]}); if (ver.find ({x, 1 }) != ver.end ()) idx++; cout << ver.find_by_order (idx)->first << endl; } } return 0 ; }
防卡unordered_map 1 2 3 unordered_map<int ,int >mp; mp.reserve (1024 ); mp.max_load_factor (0.25 );
卡时 1 2 3 4 5 auto start=clock ();auto time=clock ();clock在windows环境下单位为毫秒(*1000 得秒) 在Linux环境下为微秒(*1000000 得秒) if (time-start>=900 ) break ;
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 1.f ind(str,pos)2. count3. getline (cin,s)4. s.erase (pos,n)5. mt19937_64 rng (chrono::steady_clock::now().time_since_epoch().count()) ;6. __builtin_popcount( )7. map<int ,map<int ,int >>mp; 8.f or (auto t : {"DFS" , "dfs" }9. substr (起始位置,长度)10 s.replace (p0,n0,n,ch)11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. .iota(起始位,末位,初始值)25. 26. 27. 28. 29 30
进制转换 10进制转其他进制(n是数字,k是进制)
大于10的数字用字符表示
1 2 3 4 5 6 7 8 9 10 11 void solve () { int n;cin>>n; int k;cin>>k; string ans; while (n){ ans.push_back (n%k<10 ? n%k+'0' : n%k-10 +'A' ); n/=k; } reverse (ans.begin (),ans.end ()); cout<<ans<<'\n' ; }
其他进制转十进制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 unordered_map<char ,int >it; int r,ans;void init () { int s=10 ; for (char i='A' ;i<='Z' ;i++) { it[i]=s++; } } int main () { string n;cin>>r>>n; init (); for (int i=0 ;i<n.size ();i++){ ans*=r; if (isalpha (n[i])) ans+=it[n[i]]; else ans+=n[i]-'0' ; } cout<<ans<<endl;
字符串进制转化
1 2 stoi (s) auto s=to_string (x)
二分 左端点减1,右端点加1
基姆拉尔森计算公式 计算自1970年的某年某月某日是星期几
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 const int d[] = {31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };bool isLeap (int y) { return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0 ); } int daysInMonth (int y, int m) { return d[m - 1 ] + (isLeap (y) && m == 2 ); } int getDay (int y, int m, int d) { int ans = 0 ; for (int i = 1970 ; i < y; i++) { ans += 365 + isLeap (i); } for (int i = 1 ; i < m; i++) { ans += daysInMonth (y, i); } ans += d; return (ans + 2 ) % 7 + 1 ; }
三分模板 整数三分 每次都将区间变为[l,mid1],(mid1,mid2],(mid2,r]三个区间 根据条件判断将l,r指针移动至哪个区间,复杂度为log以3为底(区间大小)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void solve () { int l=2 ,r=999 ; while (l<r){ int mid1 = l + (r - l) / 3 ; int mid2 = r - (r - l) / 3 ; int s=query (mid1,mid2); if (s == mid1 * mid2){ l = mid2 + 1 ; }else if (s == mid1 * mid2 + mid1){ l = mid1 + 1 ; r = mid2; }else { r = mid1; } } cout << "! " << l << endl; }
实数三分 1 2 3 4 5 6 7 8 9 10 11 12 13 const double eps = 1e-9 ;while (r - l < eps) { double lmid = l + (r - l) / 3 ; double rmid = r - (r - l) / 3 ; lans = cal (lmid),rans = cal (rmid); if (lans <= rans) r = rmid; else l = lmid; if (lans >= rans) l = lmid; else r = rmid; } cout << l << endl;
Trick 比赛相关
认真读题至少2遍,必要时和队友确认题意
想思路前务必带入样例验证思路,否则请重复步骤1
初始化不要多次声明vector(特别是二分这种多次用到初始化的),用遍历的方式去赋初始值
切入点/典中典
子序列选择问题,暴力做法是枚举所有可能的子序列,当然这一定做不到,复杂度是$2^n$级别的
sol1 一般这类问题都可以通过dp解决,找到能够”拼接”起来的转移方程
sol2 通过组合数解决,注意应该直接计算保留的子序列方案数 not 删除的种类数
q个询问此类问题一般都是复杂度O(1)[提前预处理],O(logn)[预处理后在线询问]
区间[l,r]询问,转换成前缀和处理,即pre[r]-pre[l-1]
red求能组成多少个不同的red,只需要求每个’e’前面多少个r和后面多少个d,两者相乘即可
数论
将数x分开,每块最多t,分开的操作为拆成两个和为x的正整数,求次数
中位数就想二分
二进制乘以2,相当于整个数左移一位,末位补0,乘$2^{k}$就是左移k位
6x+8y+10z,取数不限可以遍历>=6的所有偶数
对于一个数组中的gcd,从左到右gcd如果递减,每次起码缩小一半(原因就是gcd一旦变化,一定会变成原有gcd的因数),所以gcd的变化是log级别的
递推数列具有模周期性,对于斐波那契数列,这个周期不会超过 60× 模数。
皮亚诺定理:模数为k的循环节长度不会超过6k
当题面给定数字范围可能超过long long的时候,首先应该想到按位贪心等算法,而不是高精度或i128
操作问题
数组中异或最终变成某个确定数的问题,可以使用前/后缀异或和的方法dp转移
循环移位 - 加长数组至2倍,然后直接找循环节出现的起始和结束位置
$操作a_{i}-=1;a_{i+1}+=1$,无操作限制求极差,将使得序列变成不递减序列,二分求极大极小做差
操作$a_i+=x$,次数不限,最终要求到某个数/求mex…,可以用dp,dp[a[i]+x]+=(dp[$a[i]$]-1),或者对x取模,用map存储,
图论
有其他增项的最短路
有无某种特性可以点数*2为无,点数 *2+1为有
DEBUG
当程序连输入的数据都输出不来,就是程序中某段卡死了