A
思路：
看到两两联通就容易想到最小生成树，然后要黑边多，白边少，那只需要最小生成树改一下排序条件就行了。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 2e7 + 10;
struct edge{
int u,v,w;
}e[maxn];
bool cmp(edge a,edge b){
return a.w < b.w;
}
int f[maxn];
int find(int x){
if(x != f[x]){
return f[x] = find(f[x]);
}
return f[x];
}
void solved(){
int n,m;cin>>n>>m;
for(int i = 1; i <= m; i++){
cin >> e[i].u >> e[i].v >> e[i].w;
}
for(int i = 1; i <= n; i++)f[i] = i;
sort(e + 1,e + 1 + m,cmp);
int ans = 0;
int res = 0;
for(int i = 1; i <= m; i++){
int fu = find(e[i].u);
int fv = find(e[i].v);
if(fu != fv){
ans++;
f[fu] = fv;
if(e[i].w == 1)res++;
if(ans == n - 1)break;
}
}
if(ans != n - 1)cout << "-1" << endl;
else cout << res << endl;
}
int main(){
solved();
return 0;
}C
思路：
要从1最快靠近n的方法，在满足题目约束下，最快的方法是3 + 1 + 3 + 1 + 。。。 + 3 + 1这样，3 + 1 = 4，那么答案就是(n / 4) * 2,然后把余数加进来n % 4,如果余数为3，的话直接跳三步，即操作次数为1.
那么答案就是2 * (x / 4) + ((x % 4 == 3 ? 1 : (x % 4)))
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
void solved(ll x){
cout << 2 * (x / 4) + ((x % 4 == 3 ? 1 : (x % 4))) << endl;
}
int main(){
ll x;cin>>x;
solved(x);
return 0;
}D
思路：
考虑每个数是否是是素数。
然后求一个素数前缀和。
容易发现答案就是f[n] + 1。
因为：最大的k，就是由k - 1个素数+一个合数组成。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int f[maxn];
bool check(int x){
for(int i = 2; i * i <= x; i++){
if(x % i == 0)return false;
}
return true;
}
int main(){
for(int i = 1; i <= 1e5; i++){
if(check(i)){
f[i] = f[i - 1] + 1;
}else{
f[i] = f[i - 1];
}
}
int n;cin>>n;
if(n <= 3){
cout <<"-1" << endl;
return 0;
}
cout << f[n] + 1 << endl;
return 0;
}E
思路：
这个没啥好多了，模拟就行了，注意去掉前导0，和结果为0的情况。
代码：
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
/*
void solved(){
int a,b;cin>>a>>b;
vector<int>ans;
while(a || b){
int x = a % 10;
int y = b % 10;
a /= 10;b /= 10;
ans.push_back((x + y) % 10);
}
reverse(ans.begin(),ans.end());
int i = 0;
while(i < ans.size() && ans[i] == 0)i++;
if(i == ans.size()){
cout << '0' << endl;return ;
}
for(; i < ans.size(); i++){
cout << ans[i];
}
}
*/
const int maxn = 2e5 + 10;
char a[maxn],b[maxn];
void solved(){
a[0] = '0';b[0] = '0';
scanf("%s",a + 1);
scanf("%s",b + 1);
int len1 = strlen(a + 1);
int len2 = strlen(b + 1);
vector<int>ans;
for(int i = len1,j = len2; true ;){
ans.push_back(((a[i] - '0') + (b[j] - '0')) % 10);
if(i == j && i == 0)break;
i--;j--;
i = max(0,i);j = max(0,j);
}
reverse(ans.begin(),ans.end());
int i = 0;
while(i < ans.size() && ans[i] == 0)i++;
if(i == ans.size()){
cout << '0' << endl;return ;
}
for(; i < ans.size(); i++){
cout << ans[i];
}
}
int main(){
solved();
return 0;
}H
思路：
容易发现第k小之后的元素没啥用了，我们只需要维护前k个元素即可。
比赛的时候我想的是map维护了，复杂度没问题，就是细节太多了不好写，写了一半还是放弃了。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;
void solved(){
int n,m,k;cin>>n>>m>>k;
map<int,int>mp;
for(int i = 1; i <= n; i++){
int x;cin>>x;
mp[x]++;
}
map<int,int>::iterator it = mp.begin();
for(k--;k - it->second >= 0 && it != mp.end(); it++){
k -= it->second;
}
int cnt = k;
while(m--){
int ins;cin>>ins;
if(ins == 2){
cout << it->first << endl;
}else{
int x;cin>>x;
mp[x]++;
if(x < it->first){
if(cnt == 0){
it--;cnt = it->second;
}else{
cnt--;
if(cnt == 0){it--;cnt = it->second;}
}
}
}
}
}
int main(){
solved();
return 0;
}用优先队列会比map更好维护，我们只需要搞一个大根堆，先让堆里面的元素个数为k，然后插一个比第k大还小的元素后，pop一个元素，如果比第k大更大的话不需要考虑。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
void solved(){
priority_queue<int,vector<int>,less<int> >st;
int n,m,k;cin>>n>>m>>k;
for(int i = 1; i <= n; i++){
int x;cin>>x;st.push(x);
}
while(st.size() > k)st.pop();
while(m--){
int ins;cin>>ins;
if(ins == 2){
if(st.size() < k)cout << "-1" << endl;
else cout << st.top() << endl;
}else{
int x;cin>>x;
if(x <= st.top() || st.size() < k){
st.push(x);
if(st.size() > k)
st.pop();
}
}
}
}
int main(){
solved();
return 0;
}待补
G
思路：
这题目很容易让人掉进一个坑，先排序a，然后枚举b，二分a中第一个大于b的数，但是这个数之后不能用了，所以这个二分不了。。。。。
然后我想了一个线段树做法：先离散化，然后枚举b，询问[h(bi)+1,2e5]是否有数，但是。。。。这个数要从权值线段树中删除。。。好像不好做。。。想了蛮久不知道咋处理，，，，最终重新审题。。。。
其实我们不关心b的顺序，应该我们要求的只是一个最优的匹配，即bi由在a中第一个大于bi的数匹配，求匹配的个数即可。
所以我们可以对a,b排序，然后双指针，这题就没了。。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn],b[maxn];
void solved(){
int n,m;cin>>n>>m;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= m; i++)cin>>b[i];
sort(a + 1,a + 1 + n);
sort(b + 1,b + 1 + m);
int ans = 0;
for(int i = 1,j = 1; j <= m;i++,j++){
while(i <= n && a[i] <= b[j])i++;
if(i == n + 1)break;
ans++;
}
cout << ans << endl;
}
int main(){
solved();
return 0;
}J
思路：
场下10分钟给切了，场上瞄了一眼没思路就滚了，害。。。还是切题太慢了。。。
这个题其实是一个很显然的dp。
对于每个数i我们有两种选择，拿或者不拿，如果当前这个数拿的话，那么前面i-1个数不能拿，也就是i-2这个数你可以选择拿或者不拿。
如果当前这个数不拿的话，前面这个数i - 1可以选择拿或者不拿。
那么总结下来就是：
if(mp[i]){
dp[i][0] = max(dp[i - 1][1],dp[i - 1][0]);
dp[i][1] = max(dp[i - 2][0],dp[i - 2][1]) + i * mp[i];
}else{
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1];
}mp[i]:表示当前这个数i出现的次数，只有这个数出现过我们还有选择拿的权力。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
int a[maxn];
ll dp[maxn][2];
void solved(){
int n;cin>>n;
map<ll,ll>mp;
for(int i = 1; i <= n; i++)cin>>a[i],mp[a[i]]++;
ll ans = 0;
for(int i = 0; i <= 2e5; i++){
if(mp[i]){
dp[i][0] = max(dp[i - 1][1],dp[i - 1][0]);
dp[i][1] = max(dp[i - 2][0],dp[i - 2][1]) + i * mp[i];
}else{
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1];
}
ans = max(ans,max(dp[i][0],dp[i][1]));
}
cout << ans << endl;
}
int main(){
solved();
return 0;
}B
I
思路：
注意到n很小，那么我们可以O(n^2)求出所有子区间异或和的值，和长度。
然后我们按照异或和的值排序。
那么对于每一个询问，我们二分lower_bound第一个大于等于x的值的位置。
那么[index,N]都是满足要求的，我们需要在这个区间找一个最小的长度那么就是区间最小值问题，线段树维护一下即可。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
const int maxn = 5e7 + 10;
typedef long long int ll;
int m[maxn << 2],c[maxn];
#define lson (rt * 2)
#define rson (rt * 2 + 1)
#define mid (l + r) / 2
ll b[maxn],a[maxn];
int tot;
void build(int l,int r,int rt){
if(l == r){
m[rt] = c[++tot];
return ;
}
build(l,mid,lson);
build(mid + 1,r,rson);
m[rt] = min(m[lson],m[rson]);
}
int query(int ql,int qr,int l,int r,int rt){
if(l >= ql && r <= qr)return m[rt];
int ans = 1e9;
if(ql <= mid)ans = min(ans,query(ql,qr,l,mid,lson));
if(qr > mid)ans = min(ans,query(ql,qr,mid + 1,r,rson));
return ans;
}
bool cmp(pair<ll,int>a,pair<ll,int>b){
return a.first < b.first;
}
void solved(){
int n,m;scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)scanf("%lld",&a[i]);
vector<pair<ll,int> >ve;
for(int i = 1; i <= n; i++){
ll x = a[i];
ve.push_back({x,1});
for(int j = i + 1; j <= n; j++){
x ^= a[j];
ve.push_back({x,j - i + 1});
}
}
int cnt = 0;
sort(ve.begin(),ve.end(),cmp);
int N = ve.size();
for(int i = 0; i < ve.size(); i++){
b[++cnt] = ve[i].first;
c[cnt] = ve[i].second;
}
build(1,N,1);
b[++cnt] = 1e9 + 7;
while(m--){
ll x;scanf("%lld",&x);
int index = lower_bound(b + 1,b + 1 + cnt,x) - b;
if(index == N + 1)puts("-1");
else printf("%d\n",query(index,N,1,N,1));
}
}
int main(){
solved();
return 0;
}
思路：线段树。
考虑维护[l,r]最大值的时候顺便维护一个计数cnt,容易得到一个简单的pushdown逻辑。
void pushdown(int rt){
if(m[lson] == m[rson]){
m[rt] = m[lson];
cnt[rt] = cnt[lson] + cnt[rson];
}else if(m[lson] > m[rson]){
m[rt] = m[lson];
cnt[rt] = cnt[lson];
}else{
m[rt] = m[rson];
cnt[rt] = cnt[rson];
}
}然后正常单点更新，区间查询就好了。
代码：
#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
#define lson (rt * 2)
#define rson (rt * 2 + 1)
#define mid (l + r) / 2
ll m[maxn << 2];
int cnt[maxn << 2];
void pushdown(int rt){
if(m[lson] == m[rson]){
m[rt] = m[lson];
cnt[rt] = cnt[lson] + cnt[rson];
}else if(m[lson] > m[rson]){
m[rt] = m[lson];
cnt[rt] = cnt[lson];
}else{
m[rt] = m[rson];
cnt[rt] = cnt[rson];
}
}
void build(int rt,int l,int r){
if(l == r){
scanf("%lld",&m[rt]);
cnt[rt] = 1;
return ;
}
build(lson,l,mid);
build(rson,mid + 1,r);
pushdown(rt);
}
void query(int rt,int ql,int qr,int l,int r,ll &x,int &y){
if(l >= ql && r <= qr) {
if(m[rt] > x){
x = m[rt];y = 0;
}
if(m[rt] == x)y += cnt[rt];
return ;
}
if(ql <= mid)query(lson,ql,qr,l,mid,x,y);
if(qr > mid)query(rson,ql,qr,mid + 1,r,x,y);
}
void update(int rt,int l,int r,int pos,int v){
if(l == r){
m[rt] = v;
return ;
}
if(pos <= mid)update(lson,l,mid,pos,v);
else update(rson,mid + 1,r,pos,v);
pushdown(rt);
}
void solved(){
int n,m;scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
string s;cin>>s;
if(s[0] == 'A'){
int l,r;cin>>l>>r;
ll x = -1;
int y = 0;
query(1,l,r,1,n,x,y);
printf("%lld %d\n",x,y);
}else{
int x,y;cin>>x>>y;
update(1,1,n,x,y);
}
}
}
int main(){
solved();
return 0;
}
京公网安备 11010502036488号