1. n个犯人，m个省份， 如果相邻的2个犯人来自同一省份，则是不安全的，求不安全的个数。
正难则反，用全部的个数减去非法的个数，就是最后的答案。 m^n - m * (m - 1) ^ (n - 1). 这里的m,n很大，所以就是快速幂乘法。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 const int mod = 100003; 8 ll n, m; 9 ll pow(ll x, ll y) { 10 if(y == 0) return 1; 11 ll r = 1; 12 ll b = x; 13 while(y) { 14 if(y & 1) { 15 r = r * b % mod; 16 } 17 y >>= 1; 18 b = b * b % mod; 19 } 20 return r; 21 } 22 void solve() { 23 cin >> m >> n; 24 //cout << m<< " " << n <<endl; 25 //cout << pow(m, n) << endl; 26 //cout << pow(m, n - 1) << endl; 27 ll res = ((pow(m, n) - pow(m - 1, n - 1) * m) % mod + mod)%mod; 28 cout << res << endl; 29 } 30 31 int main() { 32 freopen("test.in", "r", stdin); 33 //freopen("test.out", "w", stdout); 34 ios::sync_with_stdio(0); 35 cin.tie(0); cout.tie(0); 36 solve(); 37 return 0; 38 }
2. 从n个数，选取一些数，使得能被m整除。
这种题，就是一般的套路， 搞一下余数， 然后就是0,1背包。注意一维数组优化，滚动数组， 取余。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e6 + 10; 7 int n, m; 8 int a[maxn]; 9 void yes() { 10 cout << "Yes" << endl; 11 } 12 void no() { 13 cout << "No" << endl; 14 } 15 int dp[2][maxn]; 16 void solve() { 17 scanf("%d%d", &n, &m); 18 int x, y; 19 for (int i = 0; i < n; i++) { 20 scanf("%d", &x); 21 x = x % m; 22 a[x]++; 23 } 24 if(a[0] > 0) { 25 yes(); return; 26 } 27 28 dp[0][0] = 1; 29 vector<int> av; 30 for (int i = 1; i <= m - 1; i++) { 31 for (int j = 0; j < a[i]; j++) 32 av.push_back(i); 33 //cout << i << endl; 34 } 35 //cout << "asd" << endl; 36 int cur = 0, nxt = 1; 37 for (int tx : av) { 38 for (int i = m - 1; i >= 0; i--) { 39 if(dp[cur][i] > 0) { 40 dp[nxt][i] = 1; 41 int t = (i + tx) % m; 42 if(t == 0) t = m; 43 dp[nxt][t] = 1; 44 //cout << t << endl; 45 } 46 } 47 swap(cur, nxt); 48 for (int i = 0; i < m; i++) 49 dp[nxt][i] = 0; 50 //cout << tx << endl; 51 } 52 53 if(dp[cur][m]) yes(); 54 else no(); 55 } 56 57 int main() { 58 freopen("test.in", "r", stdin); 59 //freopen("test.out", "w", stdout); 60 solve(); 61 return 0; 62 }
3. 有一些操作，插入和查询，插入是往末尾进行插入，查找的是末尾长度为l的里面的最大值。
由于每次动态更新，区间不停的变换，我只想到线段树的做法，就写了线段树的。logn单点更新， logn区间查询。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 2e5 + 10; 7 ll f[maxn * 4]; 8 int n; 9 int x, y; 10 ll v; 11 void bt(int o, int left, int right) { 12 } 13 void add(int o, int left, int right) { 14 if(left > right) return; 15 if(left == right && left == x) { 16 f[o] = v; 17 } else { 18 int mid = (left + right) / 2; 19 if(x <= mid) add(o * 2, left, mid); 20 else add(o * 2 + 1, mid + 1, right); 21 f[o] = max(f[o * 2], f[o * 2 + 1]); 22 } 23 } 24 ll ask(int o, int left, int right) { 25 if(right < x || y < left) return 0; 26 if(x <= left && right <= y) return f[o]; 27 int mid = (left + right) / 2; 28 ll ml, mr;ml = mr = 0; 29 if(x <= mid) ml = ask(o * 2, left, mid); 30 if(y >= mid + 1) mr = ask(o * 2 + 1, mid + 1, right); 31 return max(ml, mr); 32 } 33 int m; 34 ll mod; 35 char ch[5]; 36 void solve() { 37 scanf("%d%lld", &m, &mod); 38 int p = 0; 39 ll lst = 0, t; 40 for (int i = 0; i < m; i++) { 41 //cout << i << endl; 42 scanf("%s%lld", ch, &t); 43 if(ch[0] == 'I') { 44 t = (t + lst) % mod; 45 x = ++p; v = t; 46 add(1, 1, m); 47 } else { 48 if(t == 0) { 49 printf("0 "); 50 continue; 51 } 52 x = p - t + 1; 53 y = p; 54 lst = ask(1, 1, m); 55 printf("%lld ", lst); 56 } 57 } 58 } 59 60 int main() { 61 freopen("test.in", "r", stdin); 62 //freopen("test.out", "w", stdout); 63 solve(); 64 return 0; 65 }
4. 逆序对，现在有1-n，一共n个数， 求逆序对的个数为m的排列的个数。1 <= n,m <= 1000.
枚举，数个数，贪心的方式是不行的，那就是dp了。
枚举最大的一个数，看如何进行转移。dp[i][j] 代表长度为i, 逆序对的个数为j的个数。考虑从dp[i-1]转移过来，增加的逆序对的个数，就很容易写出来转移方程。
写出来之后，发现时间复杂度是n^3的，不满足要求， 然后用前缀和维护一下，使得0（1）的求取区间的和。使得复杂度降为n^2.
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 const int mod = 10000; 8 int n, k; 9 int dp[maxn][maxn]; 10 int s[maxn][maxn]; 11 void solve() { 12 cin >> n >> k; 13 14 for (int i = 1; i <= n; i++) { 15 dp[i][0] = 1; 16 s[i][0] = 1; 17 for (int j = 1; j <= k; j++) { 18 dp[i][j] = s[i - 1][j]; 19 if(j - i >= 0) 20 dp[i][j] = (dp[i][j] - s[i - 1][j - i] + mod) % mod; 21 s[i][j] = (s[i][j - 1] + dp[i][j]) % mod; 22 //cout << i << " " << j << " " << dp[i][j] << endl; 23 } 24 25 } 26 cout << dp[n][k] << endl; 27 28 } 29 30 int main() { 31 freopen("test.in", "r", stdin); 32 //freopen("test.out", "w", stdout); 33 ios::sync_with_stdio(0); 34 cin.tie(0); cout.tie(0); 35 36 solve(); 37 return 0; 38 }