题解

排队

20% 1≤n≤20,1≤x,hi≤201\le n\le 20, 1\le x,h_i\le 201≤n≤20,1≤x,hi≤20 随便暴力

50% 1≤n≤2000,1≤x,hi≤1e91\le n \le 2000, 1\le x,h_i\le 1e91≤n≤2000,1≤x,hi≤1e9 枚举把哪个定成中位数

100% 1≤n≤2e5,1≤x,hi≤1e91\le n\le 2e5,1\le x,h_i\le 1e91≤n≤2e5,1≤x,hi≤1e9

先把高度排序。贪心地修改。最好的方法是把最中间的人变成xxx。那么就把左边比他高的或者右边比他矮的都改成xxx就好啦。

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int MAXN = 200005;

int n, x, h[MAXN];

LL Ans;

int main()

{

    scanf("%d%d", &n, &x);

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

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

    sort(h + 1, h + n + 1);

    int l = n>>1, r = (n>>1)+2;

    Ans = abs(h[(n>>1)+1]-x), h[(n>>1)+1] = x;

    while(l >= 1 && r <= n)

    {

        Ans += max(h[l]-h[l+1], 0), h[l] = min(h[l], h[l+1]); l--;

        Ans += max(h[r-1]-h[r], 0), h[r] = max(h[r], h[r-1]); r++;

    }

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

}

翘课

10% 2≤n,m≤500,k=12\le n,m\le 500,k=12≤n,m≤500,k=1

20% 2≤n,m≤200000,k=12\le n,m\le 200000,k=12≤n,m≤200000,k=1 暴力

40% 2≤n,m≤2000,k=22\le n,m\le 2000,k=22≤n,m≤2000,k=2 找环

70% 2≤n,m≤2000,k<n2\le n,m\le 2000,k<n2≤n,m≤2000,k<n 每次跑点判断

100% 2≤n,m≤200000,1≤k<n2\le n,m\le 200000,1\le k <n2≤n,m≤200000,1≤k<n 倒着删

考虑先把所有边加进去，再倒过来删边。

对于每个点，我们考虑要不要删掉它，删掉它表示它连接着选中的点的度小于 K 了。删完它之后我们把它邻居的度都–，然后再看它的邻居要不要被删掉。这样预处理把每个点判一次要不要删。

之后删一条边也是删完就判断连接的两个点需不需要被删掉。因为每个点只会被删一次，所以整体还是O(n)的。

题目做法可能多样，但思路应该都是倒过来。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

const int MAXM = 200005;

inline void read(int &num)

{

    char ch; int flag=1;

    while(!isdigit(ch=getchar()))if(ch=='-')flag=-flag;

    for(num=ch-'0';isdigit(ch=getchar());num=num*10+ch-'0');

    num*=flag;

}

int n, m, k, d[MAXN], Ans;

int fir[MAXN], to[MAXM<<1], nxt[MAXM<<1], cnt = 1;

inline void Add(int u, int v)

{

    to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;

    to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt;

}

bool flg[MAXN], used[MAXM<<1];

inline void del(int u)

{

    if(!flg[u]) return;

    flg[u] = 0; Ans--;

    for(int i = fir[u]; i; i = nxt[i])

		if(used[i^1] && (used[i^1] = 0, --d[to[i]] == k-1)) del(to[i]);

}

bool vis[MAXN];

inline bool dfs1(int u)

{

	if(vis[u]) return flg[u];

	vis[u] = 1;

	flg[u] = 1; Ans++;

    for(int i = fir[u]; i; i = nxt[i])

		if(dfs1(to[i]))

			++d[u], used[i] = 1;

    if(d[u] >= k) return 1;

	del(u);

	return 0;

}

int U[MAXM], V[MAXM], ans[MAXM];

int main ()

{

    read(n), read(m), read(k);

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

        read(U[i]), read(V[i]), Add(U[i], V[i]);

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

		if(!vis[i]) dfs1(i);

    for(int i = m; i >= 1; i--)

    {

        ans[i] = Ans;

        if(used[i<<1] && (used[i<<1] = 0, --d[U[i]] == k-1)) del(U[i]);

        if(used[i<<1|1] && (used[i<<1|1] = 0, --d[V[i]] == k-1)) del(V[i]);

    }

	for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);

}

运气大战

20% n≤10,q≤10n\le 10,q\le 10n≤10,q≤10 暴力

另30% n≤1000,q≤100n\le 1000,q\le 100n≤1000,q≤100 这个点我也不记得为什么放了，但看起来很多人只拿到了50所以可能还是有点意义的？

另20% n≤30000,q≤500n\le 30000,q\le 500n≤30000,q≤500 nq 的 dp

100% 2≤n≤30000,1≤q≤10000,1≤wi,ri≤1e6,1≤ai̸=bi≤n2\le n\le 30000,1\le q\le 10000,1\le w_i,r_i \le 1e6,1\le a_i\not=b_i \le n2≤n≤30000,1≤q≤10000,1≤wi,ri≤1e6,1≤ai̸=bi≤n

由于排序不等式，我们尽量想顺序放。两边都排序。

由于 n 个不能配的干扰，又不能完全顺序放。

有个结论，最后匹配出第 i 个人的运气值是第 j 个的话，∣i−j∣≤2|i-j|\le2∣i−j∣≤2。这个结论从最小化逆序对的个数来看，自己把附近几个线连起来画一画证明一下。

这样就可以用 dp[i]表示到 i 为止所有配好的最优答案。计算的时候需要用到前三轮的答案然后讨论一下。这个是 O(nq)的，可以过70%。

用线段树记录区间答案。区间记录这样的信息：把这个区间前0-2个和后0-2个元素去掉的答案，用3x3的矩阵维护。这样复杂度是O(qlogn)。

由于出题人良心发现将时限改为3s，常数小的nq算法也能过1.5s左右，下贴AC代码：

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int MAXN = 30005;

const LL INF = 1ll<<60;

inline void read(int &num)

{

    char ch; int flag=1;

    while(!isdigit(ch=getchar()))if(ch=='-')flag=-flag;

    for(num=ch-'0';isdigit(ch=getchar());num=num*10+ch-'0');

    num*=flag;

}

struct node

{

	int val, id;

}A[MAXN], B[MAXN];

LL dp[MAXN], cost[MAXN][2];

int n, q, posa[MAXN], posb[MAXN];

inline LL Calc(int i, int j)

{

	if(i < 1 || j < 1 || i > n || j > n || A[i].id == A[j].id) return -INF;

	return 1ll * A[i].val * B[j].val;

}

inline void Upd(int i)

{

	if(i < 1 || i > n) return;

	cost[i][0] = Calc(i, i+1) + Calc(i+1, i);

	cost[i][1] = max(Calc(i, i+1) + Calc(i+1, i+2) + Calc(i+2, i),

					Calc(i, i+2) + Calc(i+1, i) + Calc(i+2, i+1));

}

inline bool cmp(node x, node y) { return x.val < y.val; }

int main ()

{

	read(n), read(q);

	for(int i = 1; i <= n; i++) read(A[i].val), A[i].id = i;

	for(int i = 1; i <= n; i++) read(B[i].val), B[i].id = i;

	sort(A + 1, A + n + 1, cmp);

	sort(B + 1, B + n + 1, cmp);

	for(int i = 1; i <= n; i++) posa[A[i].id] = posb[B[i].id] = i, Upd(i);

	int x, y;

	while(q--)

	{

		read(x), read(y), swap(B[posb[x]].id, B[posb[y]].id), swap(posb[x], posb[y]);

		for(int i = -2; i <= 0; i++)

			Upd(posa[x+i]), Upd(posb[x+i]), Upd(posa[y+i]), Upd(posb[y+i]);

		dp[n+1] = 0;

		for(int i = n; i; i--)

		{

			dp[i] = max(dp[i+2] + cost[i][0], dp[i+3] + cost[i][1]);//i与i+1/2不能配对的情况一定会被另外更优的情况所取代，可能是此行的另一个max，可能是下一行的单独配对时取的max

			if(A[i].id != B[i].id) dp[i] = max(dp[i], dp[i+1] + 1ll * A[i].val * B[i].val);

		}

		printf("%lld\n", dp[1]);

	}

}

巴特西

NOI.ac 模拟赛20181103 排队翘课运气大战

题解

排队

翘课

运气大战

最新文章

热门文章

巴特西

NOI.ac 模拟赛20181103 排队 翘课 运气大战

题解

排队

翘课

运气大战

最新文章

热门文章

NOI.ac 模拟赛20181103 排队翘课运气大战