首页 > 代码库 > HDOJ多校联合第五场
HDOJ多校联合第五场
1001 题意：求逆序对，然后交换k次相邻的两个数，使得剩下的逆序对最少。
分析：题目用到的结论是：数组中存在一对逆序对，那么可以通过交换相邻两个数使得逆序对减少1，交换k次，可以最多减少k个。
嘉定ai>aj,i < j,如果ai,aj相邻的，那么显然可以通过交换减少1；不相邻的情况，
考虑ak,k = j-1;
#11:ak > aj,那么ak,aj构成逆序对，交换后逆序对减少1；
#12:ak<=aj,那么ai,ak构成逆序对，问题转化为更小规模，可以通过同样的方法进一步分析，最终一定能够交换一次使得逆序对减少1个；
考虑ak,k = i+1;
#21:ak<ai,那么ai,ak构成逆序对，可以交换；
#22:ak>=ai那么ak,aj构成逆序对，问题规模缩小，和#12同样的处理方法。
所以最终答案就是max(0LL, ans-k)嘛，
代码：
分治法
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib>10 #include <string>11 #include <stack>12 #include <set>13 #include <map>14 #include <cmath>15 #include <vector>16 #include <queue>17 #include <algorithm>18 #define esp 1e-619 #define inf 0x3f3f3f3f20 #define pi acos(-1.0)21 #define pb push_back22 #define lson l, m, rt<<123 #define rson m+1, r, rt<<1|124 #define lowbit(x) (x&(-x))25 #define mp(a, b) make_pair((a), (b))26 #define bit(k) (1<<(k))27 #define iin freopen("pow.in", "r", stdin);28 #define oout freopen("pow.out", "w", stdout);29 #define in freopen("solve_in.txt", "r", stdin);30 #define out freopen("solve_out.txt", "w", stdout);31 #define bug puts("********))))))");32 #define Inout iin oout33 #define inout in out34 35 #define SET(a, v) memset(a, (v), sizeof(a))36 #define SORT(a) sort((a).begin(), (a).end())37 #define REV(a) reverse((a).begin(), (a).end())38 #define READ(a, n) {REP(i, n) cin>>(a)[i];}39 #define REP(i, n) for(int i = 0; i < (n); i++)40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--)41 #define Rep(i, base, n) for(int i = (base); i < (n); i++)42 #define REPS(s, i) for(int i = 0; (s)[i]; i++)43 #define pf(x) ((x)*(x))44 #define mod(n) ((n))45 #define Log(a, b) (log((double)b)/log((double)a))46 #define Srand() srand((int)time(0))47 #define random(number) (rand()%number)48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)49 50 using namespace std;51 typedef long long LL;52 typedef unsigned long long ULL;53 typedef vector<LL> VI;54 typedef pair<int,int> PII;55 typedef vector<PII> VII;56 typedef vector<PII, int> VIII;57 typedef VI:: iterator IT;58 typedef map<string, int> Mps;59 typedef map<int, int> Mpi;60 typedef map<int, PII> Mpii;61 typedef map<PII, int> Mpiii;62 const int maxn = 100000 + 100;63 int a[maxn];64 int n, k;65 LL ans;66 int T[maxn];67 68 void solve(int l, int r) {69 if(l == r || l > r)70 return;71 int m = l+(r-l)/2;72 solve(l, m);73 solve(m+1, r);74 int p = l, q = m+1;75 int cnt = 0;76 while(p <= m || q <= r) {77 if(p > m|| (q <= r && a[q] < a[p]))78 T[cnt++] = a[q++];79 else {80 ans = ans + (q-m-1);81 T[cnt++] = a[p++];82 }83 }84 REP(i, cnt)85 a[l+i] = T[i];86 }87 int main() {88 89 while(scanf("%d%d", &n, &k) == 2) {90 ans = 0;91 Rep(i, 1, n+1) scanf("%d", a+i);92 solve(1, n);93 cout<<max(0LL, ans-k)<<endl;94 }95 return 0;96 }
树状数组写法：
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib>10 #include <string>11 #include <stack>12 #include <set>13 #include <map>14 #include <cmath>15 #include <vector>16 #include <queue>17 #include <algorithm>18 #define esp 1e-619 #define inf 0x3f3f3f3f20 #define pi acos(-1.0)21 #define pb push_back22 #define lson l, m, rt<<123 #define rson m+1, r, rt<<1|124 #define lowbit(x) (x&(-x))25 #define mp(a, b) make_pair((a), (b))26 #define bit(k) (1<<(k))27 #define iin freopen("pow.in", "r", stdin);28 #define oout freopen("pow.out", "w", stdout);29 #define in freopen("solve_in.txt", "r", stdin);30 #define out freopen("solve_out.txt", "w", stdout);31 #define bug puts("********))))))");32 #define Inout iin oout33 #define inout in out34 35 #define SET(a, v) memset(a, (v), sizeof(a))36 #define SORT(a) sort((a).begin(), (a).end())37 #define REV(a) reverse((a).begin(), (a).end())38 #define READ(a, n) {REP(i, n) cin>>(a)[i];}39 #define REP(i, n) for(int i = 0; i < (n); i++)40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--)41 #define Rep(i, base, n) for(int i = (base); i < (n); i++)42 #define REPS(s, i) for(int i = 0; (s)[i]; i++)43 #define pf(x) ((x)*(x))44 #define mod(n) ((n))45 #define Log(a, b) (log((double)b)/log((double)a))46 #define Srand() srand((int)time(0))47 #define random(number) (rand()%number)48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)49 50 using namespace std;51 typedef long long LL;52 typedef unsigned long long ULL;53 typedef vector<LL> VI;54 typedef pair<int,int> PII;55 typedef vector<PII> VII;56 typedef vector<PII, int> VIII;57 typedef VI:: iterator IT;58 typedef map<string, int> Mps;59 typedef map<int, int> Mpi;60 typedef map<int, PII> Mpii;61 typedef map<PII, int> Mpiii;62 const int maxn = 100000 + 100;63 int a[maxn];64 int r[maxn], pos[maxn];65 int n, k;66 LL sum[maxn];67 bool cmp(int v1, int v2) {68 return a[v1] < a[v2] || (a[v1] == a[v2] && v1 < v2);69 }70 void update(int x) {71 while(x <= n) {72 sum[x] += 1;73 x += lowbit(x);74 }75 }76 LL getsum(int x) {77 LL ans = 0;78 while(x > 0) {79 ans += sum[x];80 x -= lowbit(x);81 }82 return ans;83 }84 int main() {85 86 while(scanf("%d%d", &n, &k) == 2) {87 Rep(i, 1, n+1) scanf("%d", a+i), r[i] = i, sum[i] = 0;88 sort(r+1, r+n+1, cmp);89 Rep(i, 1, n+1)90 pos[r[i]] = i;91 LL ans = 0;92 Rep(i, 1, n+1) {93 update(r[i]);94 ans += i-getsum(r[i]);95 }96 cout<<max(0LL, ans-k)<<endl;97 }98 return 0;99 }
1007：给定n个数(n<=40),以及m种关系即第ai个数必须小于第bi个数，求这样的排列有多少个？
分析：m种关系显然构成一个拓扑图，且各个连通图之间互相独立，因此单个考虑每个连通图的可能性，比如一个连通图中有k个点，
从n个数中任选k个数，然后求这个图中能有多少个安排方案满足拓扑关系。
研究标程，具体实现是，通过并查集找出连通关系，（话说一直没这么用过，还想着去dfs求，弱菜），然后重新编号，通过cover[i] 表示从点i出发的能到达的点，先用于i有直接变得点初始化，然后floyd求连通性。
具体dp时，转移时这样的，dp[st|1<<i] += dp[st], st 满足(st&1<<i) == 0 && (st&cover[i]) == cover[i].
代码：
1010:2个n*n的矩阵，输出相乘后每个元素对3取模后矩阵。
分析：输入时对每个元素取模，则剩下1*1,1*2,2*1，2*2这几种相乘情况，利用bitset，将相应的为1,2 的元素单独拿出来考虑，然后按照上面4种情况，分别求出相乘后的结果,最后加起来取模。
ADD：学习了一下bitset位集的使用。
代码：
1 #include <iostream> 2 #include <bitset> 3 #include <cstdio> 4 #define in freopen("solve_in.txt", "r", stdin); 5 6 using namespace std; 7 const int maxn =810; 8 bitset<maxn> b[2][2][maxn]; 9 int n;10 11 int main() {12 13 while(~scanf("%d", &n)) {14 for(int k = 0; k < 2; k++)15 for(int i = 0; i < n; i++)16 for(int j = 0; j < n; j++) {17 int t;18 scanf("%d", &t);19 t %= 3;20 if(k == 1) {21 b[k][0][j][i] = b[k][1][j][i] = 0;22 if(t == 1)23 b[k][0][j][i] = 1;24 else if(t == 2)25 b[k][1][j][i] = 1;26 } else {27 b[k][0][i][j] = b[k][1][i][j] = 0;28 if(t == 1)29 b[k][0][i][j] = 1;30 else if(t == 2)31 b[k][1][i][j] = 1;32 }33 }34 for(int i = 0; i < n; i++)35 for(int j = 0; j < n; j++) {36 int t1 = (b[0][0][i]&b[1][0][j]).count();37 int t2 = (b[0][0][i]&b[1][1][j]).count()*2;38 int t3 = (b[0][1][i]&b[1][0][j]).count()*2;39 int t4 = (b[0][1][i]&b[1][1][j]).count();40 int ans = (t1+t2+t3+t4)%3;41 printf("%d%c", ans, j == n-1 ? ‘\n‘ : ‘ ‘);42 }43 }44 return 0;45 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。