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;
}
原文地址：http://www.cnblogs.com/L3067545513/p/16849228.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
