树状数组和逆序对
算法
树状数组求逆序对1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>#define lowbit(x) x&(-x)using namespace std;typedef long long ll;const int maxn=2e5+10;int sum[maxn],cnt=maxn-1;void add( int x ) { for(int i = x; i <= n; i += lowbit(i)) sum[i] += 1;}int query( int x ) { int ans = 0; for(int i = x; i; i -= lowbit(i)) ans += sum[i]; return ans;} int main(){ int n; cin>>n; ll ans=0; for( int i= ...
字母和棋盘问题
乘积最大字母
使用dfs时可以把答案放在dfs的参数中，也可以将dfs的返回值作为结果。
当dfs有返回值时，应该首先明白这个返回值代表的是什么意思。
1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<set>using namespace std;const int N = 25;int n, m;char g[N][N];set<char> s;int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};int dfs(int x, int y) { int res = 0; for(int i = 0; i < 4; i ++) { int a = x + dx[i], b = y + dy[i]; if(a < 0 || a >= n || b < ...
atcoder-c和虫食算
atcoder-C
(i + cnt) % m = x - 1,i表示一开始的下标，x表示要求的第几个元素，m表示字符串大小，所以我们只需要求出i值即可。然后因为i < m,cnt < m，所以i+cnt < 2m，所以i = (x + m - 1 - cnt) % m。
优雅 ~
12345678910111213141516171819202122232425262728#include<iostream>#include<cstring>#include<algorithm>using namespace std;int n, q;string s;int main() { cin >> n >> q; cin >> s; int cnt = 0; int m = s.size(); while(q --) { int k, x; scanf("%d%d", &k, & ...
dfs枚举类型和剪枝
算法放苹果123456789101112// u表示枚举到哪个盘子,sum表示剩余几个苹果，last表示枚举了多少个。int dfs(int u, int sum, int last) { if(u == n) { if(!sum) return 1; return 0; } int res = 0; for(int i = last; i <= sum; i ++) res += dfs(u + 1, sum - i, i); return res;}
指数型枚举
用一个数组来表示三个状态，代替这个序列是升序。
123456789101112131415161718192021int n;int state[N];void dfs(int u) { if(u > n) { for(int i = 1; i <= n; i ++) if(state[i] == 1 ...