http://codeforces.com/contest/768/problem/C

這題的數值大小只有1000，那么可以聯想到，用數值做數組的下標，就是類似于計數排序那樣子。。

這樣就可以枚舉k次操作，然后for (int i = 0; i <= 1025; ++i)，也就是O(1000 * k)的復雜度而已。

0--1000中任選兩個數異或，最大值是1023

然后注意下只有奇數位異或，dp[now][val]計數轉移下去就好了

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e5 + 20; int a[maxn]; vector<int>vc[maxn]; map<pair<int, int>, int>pos; int dp[2][1025 + 20]; int f(int val) {return (val + 1) / 2; } void work() {int n, k, x;cin >> n >> k >> x;for (int i = 1; i <= n; ++i) {cin >> a[i];dp[0][a[i]]++;}int now = 0;for (int i = 1; i <= k; ++i) {now = !now;memset(dp[now], 0, sizeof dp[now]);int L = 1, R = 0;for (int j = 0; j <= 1025; ++j) {if (dp[!now][j]) {R = L + dp[!now][j] - 1;int has = f(R) - f(L - 1);dp[now][j ^ x] += has;dp[now][j] += dp[!now][j] - has;L = R + 1;}}assert(L == n + 1);}int mi = inf, mx = -inf;for (int i = 0; i <= 1025; ++i) {if (dp[now][i]) {mi = min(i, mi);mx = max(i, mx);}}cout << mx << " " << mi << endl; }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; } View Code

?

轉載于:https://www.cnblogs.com/liuweimingcprogram/p/6426291.html

總結

以上是生活随笔為你收集整理的C. Jon Snow and his Favourite Number DP + 注意数值大小的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。