CEOI 2021

\(pts\)：64 + 0 + 4

\(T1 : 64pts\)

首先我们肯定知道对于相同的数，一定是放在一起才是最优的，随意我们对于每段查询的区间要保证有序，然后我们发现，每个数出现的位置不同，他对答案的贡献也就不同，我们的想法是让答案最小，那么我们对于每个位置对答案的贡献一定要均摊，所以我们考虑错位排开，其实也可以打表找规律（到 \(6\) 就行了）。然后对于所有 \(q = 1\) 的就可以做出来了

点击查看代码

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int M = 3e5 + 7;

int a[M] , vis[M] , b[M] , t , size;

struct Query{int l , r , id;} Q[M];

bool cmp(Query a , Query b) {

	return belong[a.l] == belong[b.l] ? a.r < b.r : belong[a.l] < belong[b.l];

}

signed main () {

//	freopen("data.in","r",stdin);

//	freopen("data.ans","w",stdout);

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n , q; cin >> n >> q;

	for(int i = 1; i <= n; ++ i) cin >> a[i];

	if(q == 1) {

		int l , r; cin >> l >> r;

		sort(a + l , a + r + 1);

		int ans = 0 , cnt = 0 , sum = 0;

		for(int i = l; i <= r; ++ i) {if(!vis[a[i]]) cnt ++ ;vis[a[i]] ++; sum += cnt;}

		sort(vis + 1 , vis + 300000 + 1 , greater<int>());

		int  L = l , R = r , tot = 0;

		for(int i = cnt; i >= 1; -- i) {

			tot ++;

			if(tot & 1)while(vis[i]) a[L] = i , vis[i] -- , L ++;

			else while(vis[i]) a[R] = i , vis[i] -- , R --;

		}

		memset(vis , 0 , sizeof vis);

		cnt = 0 , sum = 0;

		for(int i = l; i <= r; ++ i) {if(!vis[a[i]]) cnt ++ ;vis[a[i]] ++; sum += cnt;}

		for(int i = l; i <= r; ++ i) {

			ans += sum;

			vis[a[i]] --;

			if(! vis[a[i]]) sum -= r - i + 1;

			else sum --;

		}

		return cout << ans << '\n' , 0;

	}

}

\(T2 : 0pts\)

\(T2\) 直接爆零了，一点思路都没有

\(T3\) ： \(4pts\)

我们首先对于链的情况进行分析，我们可以知道在一条链上的话，一定是有解的，那么考虑如何让答案最优，我们发现如果我们遍历两边这条链的话，那么一定是能找到 \(Branko\) 的，但是这样是最优的嘛，我们发现，链两端的对答案没有影响，所以可以直接排除掉，故为链的答案为 \((n - 2) * 2\)。那么在考虑一般情况，那么也就是在链上多几条支链，和环。我们先来考虑环的情况，如果说这个图中有环的话，那么是一定不能找到 \(Branko\) 的。那么最后再来考虑支链的情况，因为我们知道一个长度为 \(2\) 的链是一定能找到的，那么对于长度为 \(3\) 及以上的呢。那么我们发现如果说一条支链大于 \(2\) 了，那么 \(Ankica\) 就没办法继续往下猜了，因为这样\(Branko\) 可能就会跑到别的支链，就造成了无解，所以只要找到树的直径，再找支链即可。

点击查看代码

#include<bits/stdc++.h>

#define int long long

#define pb push_back

using namespace std;

const int M = 1e3 + 7;

int f[M] , id[M] , vis[M] , dep[M] , Max , pos;

vector<int> e[M] , a[M];

void dfs(int x , int fa , int sum) {

	if(Max < sum) Max = sum , pos = x;

	f[x] = fa;

	for(auto i : e[x]) {

		if(i == fa) continue;

		dfs(i , x , sum + 1);

	}

}

void dfs_1(int x , int fa) {

	dep[x] = 1;

	for(auto i : e[x]) {

		if(i == fa) continue;

		dfs_1(i , x);

		dep[x] = dep[i] + 1;

	}

}

signed main () {

	ios::sync_with_stdio(0),cin.tie(0);

	int n , m; cin >> n >> m;

	if(n == 1) return cout << "YES" << '\n' << 1 << '\n' << 1 << '\n' , 0;

	if(n == 2) return cout << "YES" << '\n' << 2 << '\n' << "1 1" << '\n' , 0;

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

		int u ,v; cin >> u >> v;

		e[u].pb(v) , e[v].pb(u);

	}	

	if(m >= n) return cout << "NO" << '\n' , 0;

	int pos1;

	dfs(1 , 0 , 0) , memset(f , 0 , sizeof f) , Max = 0 , pos1 = pos, dfs(pos , 0 , 0);

	int cnt = 0;

	for(int i = pos; i ; i = f[i]) {

		id[++ cnt] = i; vis[i] = 1;

	}

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

		if(! vis[i] && vis[f[i]]) {

			dfs_1(i , f[i]);

			if(dep[i] >= 3) return cout << "NO" << '\n' , 0;

			if(dep[i] > 1) a[f[i]].pb(i);

		}

	}

	cout << "YES" << '\n';

	vector<int> ans;

	for(int i = 2; i < cnt; ++ i) {

		ans.pb(id[i]);

		for(auto j : a[id[i]]) {

			ans.pb(j); ans.pb(id[i]);

		}

	}

	for(int i = cnt - 1; i > 1; -- i) {

		ans.pb(id[i]);

		for(auto j : a[id[i]]) {

			ans.pb(j);ans.pb(id[i]);

		}

	}

	cout << ans.size() << '\n';

	for(auto i : ans) cout << i << ' ';

	return 0;

}

巴特西

CEOI 2021

CEOI 2021

\(pts\)：64 + 0 + 4

\(T1 : 64pts\)

\(T2 : 0pts\)

\(T2\) 直接爆零了，一点思路都没有

\(T3\) ： \(4pts\)

最新文章

热门文章