E:
大意： 一个 01序列 ， 一种操作是改变其中一个数 ，求最多操作一次序列的最大的逆序对个数
01序列的逆序对就是统计每个 0 前面 1 的个数
当我们把 0 -> 1 的时候 ， 贡献变化就是 后边 0 的个数 - 前面 1 的个数
当我们把 1 -> 0 的时候 ， 贡献变化就是 前边 1 的个数 - 后边 0 的个数
线性的维护一下就好
本题的坑点在于有可能原序列的逆序对个数最大 ， 即不做改变 ， 比较一下即可
F
n 个事件 ， 每个事件贡献是 aia_iai , k 是间隔天数 ， 表示两个相同的事件间隔多少天完成 ， c , d 表示需要 d 天 获得 c 的贡献 ， 求最大的 k
考虑二分答案 ， 为了使间隔天数尽可能大 ， 我们优先放贡献大的事件
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N = 2e5+10;
const int p = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1e9 + 10;
const double eps = 1e-9;int t , a[N] , n , c , d , maxx;
bool cmp(int a,int b){ return a > b; }signed main(){IOScin >> t; while(t--){cin >> n >> c >> d;for(int i=0;i<n;i++){cin >> a[i] ;}sort(a,a+n,cmp);int l = 0 , r = d; while(l <= r){int mid = (l + r) / 2 , sum = 0;for(int i=0;i<d;i++){int id = i % (mid + 1);if(id < n) sum += a[id];//这里一定注意间隔区间和数组区间的关系 }if(sum >= c) l = mid + 1;else r = mid - 1;}int id = l - 1;if(id == d){cout << "Infinity\n";}else if(id == -1){cout << "Impossible\n";}else{cout << id << "\n" ;}}return 0;
}
注意二分的边界就是另外两种情况 ， 不再去特判；
G：
一个无向图 ， 路径都是带权路径 ， 一个人要从 A -> B
在 A 点的初始值为 0 ， 每到达一个新的点都要把值亦或上路径的权值 ， 想要进入B ， 需要在进入B后初始值重新归0 ， 这个人可以传送一次 ， 传送到任何一个点(除B外)
思路：首先我们不知道从A走到哪里 ， 其次我们不知道传送到哪里然后走到B ， 但是我们知道这两条路径的异或和相等
思路就是从 A 开始枚举所有能走的点 ， 记录路径异或值 ， 然后再从B开始枚举所有能走的点 ， 找有没有跟之前一样的即可
坑点：有可能从A不走直接传送 ， 所以初始的 0 也算一条路径 ， 也应该记录下来
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N = 2e5+10;
const int p = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1e9 + 10;
const double eps = 1e-9;int n , a , b , t;
vector<PII>ve[N];
bool vis[N];
map<int,int>mp;
bool f = 0;void dfs1(int st ,int pre ,int now){for(auto [x,y] : ve[st]){if(x == pre || x == b) continue;mp[now ^ y] = 1;dfs1(x , st , now ^ y);}
}void dfs2(int st , int pre , int now){if(f) return ;for(auto [x,y] : ve[st]){if(x == pre) continue;if(mp[now ^ y]){f = 1;return ;} dfs2(x , st , now ^ y);}}signed main(){IOScin >> t;while(t--){cin >> n >> a >> b;for(int i=1;i<=n;i++) ve[i].clear(); mp.clear(); f = 0;mp[0] = 1;for(int i=1;i<=n-1;i++){int u , v , w;cin >> u >> v >> w;ve[u].emplace_back(v,w);ve[v].emplace_back(u,w);}dfs1(a,a,0);dfs2(b,b,0);if(f) cout << "Yes\n";else cout << "No\n";}return 0;
}
本文链接：https://my.lmcjl.com/post/2782.html
展开阅读全文
4 评论