2018 Multi-University Training Contest 2 - （1004，1010，1007）

本文主要是介绍2018 Multi-University Training Contest 2 - （1004，1010，1007），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                                1004 Game

题意：两个人玩游戏，一开始有n个数1~n，两人轮流操作，每轮选择一个没有被拿走的数，然后拿走它和他所有约数。拿光所有数的人获胜，给定n问先手必胜还是后手必胜。

解析：图片来自多校交流群，侵删。

 

                               1010 Swaps and Inversions

题意：有长为n的序列，序列中每个逆序要交y元钱，但是可以通过花x元钱来交换两个相邻的元素。问最小花费。

解析：注意到逆序对数=交换相邻元素需要交换的次数，那么输出 min(x,y)*逆序对个数 即可。这里用树状数组+离散化来求逆序数。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100105],n,x,y;
long long ans;
struct AA
{int x,num,now;
}pos[100105];//若数组开为100005会RE，很迷。
bool cmp(AA aa,AA bb)
{return aa.x<bb.x;
}
bool cmpp(AA aa,AA bb)
{return aa.num<bb.num;
}
int lowbit(int i)
{return i&(-i);
}
void add(int i)
{while(i<=n){a[i]++;i+=lowbit(i);}
}
int sum(int i)
{int s=0;//cout<<i<<endl;while(i>0){s+=a[i];i-=lowbit(i);}return s;
}
int main()
{while(~scanf("%d%d%d",&n,&x,&y)){memset(a,0,sizeof(a));ans=0;for(int i=1;i<=n;i++){scanf("%d",&pos[i].num);pos[i].x=i;}sort(pos+1,pos+1+n,cmpp);int k=1;pos[1].now=1;for(int i=2;i<=n;i++){if(pos[i].num==pos[i-1].num) pos[i].now=k;else pos[i].now=++k;}sort(pos+1,pos+1+n,cmp);for(int i=1;i<=n;i++){add(pos[i].now);ans+=i-sum(pos[i].now);}cout<<ans*(long long)min(x,y)<<endl;}
}

 

                              1007 Naive Operations

题意：有a，b两个串，b数组给定初值后是固定的，a数组初值为0；现有q次操作，操作有两种①.add l r：对[al,ar]区间内元素全部加一；②.query l r：求∑ l...r (⌊ai/bi⌋)

解析：显然当ai的add次数大于等于bi次时，才会对结果有影响，那么q次操作不会带来太多次的答案影响。

①.用线段树维护i位置还差多少次add能对答案产生一次影响，即i位置初始为bi，每次add使其减一，减到0时i位置即对答案贡献1，此时使答案数组c的i位置加1，然后将此处再设置为bi。这里判断哪个位置减到0了就是用线段树维护区间最小值来查询位置。

②.答案数组c用树状数组维护，方便区间查询。

代码（ayf大佬的代码）：

#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <time.h>
#include <vector>
#include <string>
#include <math.h>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define mod 1000000007
#define PI acos(-1)
#define ll long long
#define inf 999999
#define ull unsigned long long
using namespace std;#define MAXN 100010
#define inf 0x3f3f3f3f
struct node{int l,r;//区间[l,r]int add;//区间的延时标记int mn; //区间最小值
}tree[MAXN<<2];//一定要开到4倍多的空间int b[MAXN<<2];int c[MAXN],n;
int lowbit(int i) {return i&(-i);}
void update(int i,int val)
{while(i<=n){c[i]+=val;i+=lowbit(i);}
}
int getsum(int i)
{int sum=0;while(i>0){sum+=c[i];i-=lowbit(i);}return sum;
}
void pushup(int index)
{tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(int index)
{if(tree[index].add){tree[index<<1].mn += tree[index].add;tree[index<<1|1].mn += tree[index].add;tree[index<<1].add += tree[index].add;tree[index<<1|1].add += tree[index].add;tree[index].add = 0;}
}
void build(int l,int r,int index)
{tree[index].l = l;tree[index].r = r;tree[index].add = 0;if(l == r){scanf("%d",&b[index]);tree[index].mn=b[index];return ;}int mid = (l+r)>>1;build(l,mid,index<<1);build(mid+1,r,index<<1|1);pushup(index);
}
void solve(int index)//找0位置
{if(tree[index].l==tree[index].r){if(tree[index].mn==0) tree[index].mn=b[index];update(tree[index].l,1);return ;}pushdown(index);int mid=(tree[index].l+tree[index].r)>>1;if(tree[index*2].mn==0) solve(index*2);if(tree[index*2+1].mn==0) solve(index*2+1);pushup(index);
}
void updata(int l,int r,int index,int val)
{if(l <= tree[index].l &&r>=tree[index].r){tree[index].mn += val;tree[index].add += val;if(tree[index].mn==0)//区间[tree[index].l,tree[index].r]中出现0，对结果产生影响，需要修改c数组的值{solve(index);}return ;}pushdown(index);int mid = (tree[index].l+tree[index].r)>>1;if(l <= mid) updata(l,r,index<<1,val);if(r > mid) updata(l,r,index<<1|1,val);pushup(index);
}
int main()
{int q,l,r;char s[20];while(scanf("%d%d",&n,&q)!=EOF){memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(tree,0,sizeof(tree));build(1,n,1);while(q--){scanf("%s%d%d",s,&l,&r);if(s[0]=='a'){updata(l,r,1,-1);}else{cout<<getsum(r)-getsum(l-1)<<endl;}}}
}

 

这篇关于2018 Multi-University Training Contest 2 - （1004，1010，1007）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---