Contest Hunter Round #70 - 连续两大交易事件杯省选模拟赛

orz lydrainbowcat

[Problem A]「艦これ市」70万幕后交易事件

排序机器=-=。重要的是相同的处理。

我们可以从小到大添加数字，然后维护一个位置的序列。每一种相等的数字都在一块。如果我们要添加一个新的数字，要把位置>它的数字全部弹出，而且要把小于它的数字(在队头)全部弹出，这样才能保证正确性和最优性。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

#define maxn 1000010

int n, m, ans;

int a[maxn];

vector<int> b[maxn];

int q[maxn];

int main(){

	scanf("%d", &n);

	for(int i = 1; i <= n; i ++){

		scanf("%d", &a[i]);

		b[a[i]].push_back(i);

		m = max(m, a[i]);

	}

	int l = 1, r = 0;

	for(int i = 1; i <= m; i ++){

		int N = b[i].size();

		for(int j = N - 1; j >= 0; j --){

			int k = b[i][j];

			while(l <= r && q[r] > k){

			    while(l <= r && a[q[l]] < a[q[r]])

					l ++;

				r --;

   			}

			ans = max(ans, r - l + 1 + N - j);

		}

		for(int j = 0; j < b[i].size(); j ++)

		    q[++ r] = b[i][j];

	}

	printf("%d\n", n - ans);

	return 0;

}

[Problem B]「NOIP市」神秘PY交易事件（前篇）　　

题目意思好长。。

而且两个人同能力要相等的工资？？

暴力都写炸了。。QAQ。。

bruteforce:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define maxn 100010

using namespace std;

struct Edge{

	int to, next, dis;

	Edge(int v = 0, int nxt = 0, int d = 0){

		to = v, next = nxt, dis = d;

	}

}edge[maxn << 2];

int h[maxn], cnt, n;

void add(int u, int v, int d){

	edge[++ cnt] = Edge(v, h[u], d); h[u] = cnt;

}

int dis[maxn];

queue<int>Q;

bool vis[maxn];

void Spfa(){

	int ans = 0;

	for(int i = 1; i <= n; i ++)

	    add(0, i, 1);

	Q.push(0);

	memset(dis, 0x80, sizeof dis);

	dis[0] = 0;

	while(!Q.empty()){

		int u = Q.front(); Q.pop();

		for(int i = h[u]; i; i = edge[i].next){

			int v = edge[i].to;

			if(dis[v] < dis[u] + edge[i].dis){

				dis[v] = dis[u] + edge[i].dis;

				if(vis[v] == false)

				    vis[v] = true, Q.push(v);

			}

		}vis[u] = false;

	}

	for(int i = 1; i <= n; i ++)

		ans += dis[i];

	printf("%d\n", ans);

}

int c[maxn];

Edge G[maxn << 2];

int H[maxn], CNT;

void Ins(int u, int v){

	CNT ++;

	G[CNT].to = v;

	G[CNT].next = H[u];

	H[u] = CNT;

}

int main(){

	scanf("%d", &n);

	for(int i = 1; i <= n; i ++)

	    scanf("%d", &c[i]);

	int u, v, m;

	scanf("%d", &m);

	for(int i = 1; i <= m; i ++){

		scanf("%d%d", &u, &v);

		Ins(u, v); Ins(v, u);

	}

	for(int i = 1; i <= n; i ++){

		for(int j = H[i]; j; j = G[j].next){

			int v = G[j].to;

			if(c[i] < c[v])

			    add(i, v, 1);

			if(c[i] == c[v])

				add(i, v, 0), add(v, i, 0);

			for(int k = H[i]; k; k = G[k].next){

				int u = G[k].to;

				if(c[v] < c[u])

				    add(v, u, 1);

				if(c[v] == c[u])

				    add(v, u, 0), add(u, v, 0);

			}

		}

	}

	Spfa();

	return 0;

}

然而正解是这样的。。对于相邻的人，如果能力值相同那么工资一定相同。这样工资相同的人可能会组成一些强连通分量，我们如果把这些scc缩掉就会形成一个DAG。(这个可以用并查集实现)。跑差分约束(最长路)或者拓扑排序都可。然后对于每一个点相邻的sort一遍，由于相邻的人的的能力值都不同，所以可以在相邻点之间连边即可(建边优化)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

#include <stack>

#define maxn 100010

using namespace std;

vector<int> G[maxn];

int c[maxn];

bool cmp(int i, int j){return c[i] < c[j];}

struct Edge{

	int to, next;

	Edge(int v = 0, int nxt = 0){

		to = v, next = nxt;

	}

}edge[maxn << 4];

int h[maxn], cnt, n, In[maxn];

void add(int u, int v){

	edge[++ cnt] = Edge(v, h[u]);

	h[u] = cnt;  ++ In[v];

}

int fa[maxn];

int getfa(int x){return x == fa[x] ? x : fa[x] = getfa(fa[x]);}

inline void Union(int x, int y){

	x = getfa(x), y = getfa(y);

	fa[x] = y;

}

stack<int> S;

int ans[maxn], ct[maxn];

int main(){

	scanf("%d", &n);

	for(int i = 1; i <= n; i ++)

	    scanf("%d", &c[i]), fa[i] = i;

	int u, v, m;

	scanf("%d", &m);

	for(int i = 1; i <= m; i ++){

		scanf("%d%d", &u, &v);

		G[u].push_back(v);

		G[v].push_back(u);

		if(c[u] == c[v])

		    Union(u, v);

	}

	for(int i = 1; i <= n; i ++){

		sort(G[i].begin(), G[i].end(), cmp);

		for(int j = 1; j < G[i].size(); j ++)

			if(c[G[i][j]] == c[G[i][j-1]])

			    Union(G[i][j], G[i][j-1]);

	}

	for(int i = 1; i <= n; i ++){

		for(int j = 0; j < G[i].size(); j ++)

		    if(c[i] < c[G[i][j]])

		        add(getfa(i), getfa(G[i][j]));

		for(int j = 1; j < G[i].size(); j ++)

		    if(getfa(G[i][j-1]) != getfa(G[i][j]))

		        add(getfa(G[i][j-1]), getfa(G[i][j]));

	}

	for(int i = 1; i <= n; i ++)

	    if(In[i] == 0 && getfa(i) == i)

			S.push(i);

	for(int i = 1; i <= n; i ++)

	    ct[getfa(i)] ++, ans[i] = 1;

	long long ret = 0;

	while(!S.empty()){

		int u = S.top(); S.pop();

		ret += 1ll * ct[u] * ans[u];

		for(int i = h[u]; i; i = edge[i].next){

			int v = edge[i].to;

			In[v] --;

			ans[v] = max(ans[v], ans[u] + 1);

			if(In[v] == 0) S.push(v);

		}

	}

	printf("%lld\n", ret);

	return 0;

}