A：黑白边
一道并查集板子稍微做点修改，大体上来说就是先把黑色的边都合并，如果还存在不连通的情况就用白色的边合并，判断用白色的边合并了几次即可，如果还是不连通的情况，那么就输出-1。
#include<bits/stdc++.h>
using namespace std;
struct f{
int x,y;
}b[1555555];
int a[1555555],cnt,m;
inline int find(int x){
if(a[x]!=x)a[x]=find(a[x]);
return a[x];
}
int main(){
int n,s=0,flag=true;
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
if(z==0){
if(find(x)!=find(y)){
a[find(x)]=find(y);
}
}
else{
cnt++;
b[cnt].x=x;
b[cnt].y=y;
}
}
for(int i=1;i<=cnt;i++){
int x=b[i].x,y=b[i].y;
if(find(x)!=find(y)){
a[find(x)]=find(y);
s++;
}
}
for(int i=1;i<=n;i++){
if(a[i]==i&&flag)flag=false;
else if(a[i]==i)s=-1;
}
cout<<s<<endl;
return 0;
}
B:最好的宝石
区间最大和他的数量，区间最大很容易就想到线段树，但是还要求他的数量，数量的话我们在线段树的基础上魔改一下就行了。
用一个num数组来存这个区间内最大的数有多少相同的val数组表示区间内最大的数。
建树和修改的时候注意下
if(val[p<<1]==val[p<<1|1])num[p]=num[p<<1]+num[p<<1|1];
else if(val[p<<1]>val[p<<1|1])num[p]=num[p<<1];
else num[p]=num[p<<1|1];确保只记录了这个区间内最大的数的数量
数量查询的话我们判断找到的区间的最大的数是不是等于这个区间内整题的最大值，如果是这个最大值，那么加上这个数，否则jiu'bu'j
int MAXN;
inline int query(int p,int l,int r,int L,int R){
if(l>R||L>r)return 0;
if(l>=L&&r<=R){
if(val[p]==MAXN)return num[p];
else return 0;
}
int mid=(l+r)>>1;
return query(p<<1,l,mid,L,R)+query(p<<1|1,mid+1,r,L,R);
}#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
int a[N],val[N],num[N];
void build(int p,int l,int r){
if(l==r){
val[p]=a[l];num[p]=1;
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
val[p]=max(val[p<<1],val[p<<1|1]);
if(val[p<<1]==val[p<<1|1])num[p]=num[p<<1]+num[p<<1|1];
else if(val[p<<1]>val[p<<1|1])num[p]=num[p<<1];
else num[p]=num[p<<1|1];
}
inline void change(int p,int l,int r,int x,int k){
if(l>x||r<x)return ;
if(l==r){
val[p]=k;num[p]=1;
return ;
}
int mid=(l+r)>>1;
change(p<<1,l,mid,x,k);
change(p<<1|1,mid+1,r,x,k);
val[p]=max(val[p<<1],val[p<<1|1]);
if(val[p<<1]==val[p<<1|1])num[p]=num[p<<1]+num[p<<1|1];
else if(val[p<<1]>val[p<<1|1])num[p]=num[p<<1];
else num[p]=num[p<<1|1];
}
inline int querymaxn(int p,int l,int r,int L,int R){
if(l>R||L>r)return 0;
if(l>=L&&r<=R)return val[p];
int mid=(l+r)>>1;
return max(querymaxn(p<<1,l,mid,L,R),querymaxn(p<<1|1,mid+1,r,L,R));
}
int MAXN;
inline int query(int p,int l,int r,int L,int R){
if(l>R||L>r)return 0;
if(l>=L&&r<=R){
if(val[p]==MAXN)return num[p];
else return 0;
}
int mid=(l+r)>>1;
return query(p<<1,l,mid,L,R)+query(p<<1|1,mid+1,r,L,R);
}
int main(){
int n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
while(m--){
char s[10];scanf("%s",&s);
if(s[0]=='A'){
int l=read(),r=read();MAXN=querymaxn(1,1,n,l,r);
printf("%d %d\n",MAXN,query(1,1,n,l,r));
}
else{
int x=read(),k=read();
change(1,1,n,x,k);
}
}
return 0;
}C:滑板上楼梯
签到题：贪心。能一次爬3个台阶就绝对不爬一个台阶，注意开long long。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,ans;cin>>n;
if(n%4==0)ans=0;
else if(n%4==1)ans=1;
else if(n%4==2)ans=2;
else ans=1;
cout<<n/4*2+ans;
return 0;
}D：GCD
题目大意是问你给你一个集合，这个集合是1到n，你需要选一个数k，确保所有大小为k的子集都存在两个数属于子集k并且这两个数的最大公约数不为1.
我们假设最坏的情况就是这个为子集的数全部是素数再加上1，那么他们所有数之间的最大公约数一定都是1，这时候我们能保证在1到n中不论选哪个数都一定是区间内某一个素数的倍数即他们两最大公约数不为1.所以需要的k最小值就是1到n中素数的数量+1这个数再加上1.即素数的数量+2.
题目数据范围只有1e5，埃式筛和欧拉筛都可以。
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
bool vis[N];
int a[N];
int main() {
int n=read();
a[1]=2;
for(int i=2;i<=n;i++){
a[i]=a[i-1];
if(!vis[i]){
a[i]++;
}
else{
continue;
}
for(int j=i+i;j<=n;j+=i){
vis[j]=true;
}
}
if(a[n]>n)cout<<-1<<endl;
else cout<<a[n]<<endl;
return 0;
}E：牛牛的加法
这题啊，这题就是大数加法啊。把板子稍微该一丢丢就过了啊，甚至比大数加法还容易，因为不用考虑进位的原因。
#include<bits/stdc++.h>
using namespace std;
int main(){
string a,b;
cin>>a>>b;
if(a.size()<b.size())swap(a,b);
int n=a.size(),m=b.size();
string c=a;
for(int i=0,j=m-n;i<n;i++,j++){
if(j>=0){
c[i]=(a[i]-'0'+b[j]-'0')%10+'0';
}
}
bool flag=false;
for(int i=0;i<n;i++){
if(c[i]!='0'||flag){
cout<<c[i];
flag=true;
}
}
if(flag==0)cout<<0<<endl;
return 0;
}F:石子合并
签到题，贪心，每次合并都拿堆里面最大的那块和其他石头合并，一开始没看清还以为区间动态规划吓我一跳。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin.tie(0);
long long sum=0,maxn=0;
cin>>n;
for(int i=1;i<=n;i++){
long long x;cin>>x;
maxn=max(x,maxn);
sum+=x;
}
cout<<sum+maxn*(n-2)<<endl;
return 0;
}G：滑板比赛
还是贪心，把牛牛的和牛妹的华丽值排个序答案就出来了，牛妹的华丽值依次从小到大消耗牛牛的从小到大的即可。
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
int a[N],b[N],ans;
int main(){
int n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=m;i++)b[i]=read();
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int now=1;
for(int i=1;i<=m;i++){
while(a[now]<=b[i]&&now<=n)now++;
if(now>n)break;
ans++;now++;
}
cout<<ans<<endl;
return 0;
}H：第 k 小
这题看了下好多大佬写的平衡树啊，我也想歪了，因为这个是每次都求第K大（K是一个固定值）所以只需要维护一个堆，保证堆的大小是K即可。
我这个是维护一个容器，每次插入后保证他还是有序的，但是一开始插入的数实在是太多了，后面修改了下大于K的时候直接把后面的数都删了才过的。
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
int main() {
vector<int>q;
int n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
int x=read();q.push_back(x);
}
sort(q.begin(),q.end());
for(int i=1;i<=m;i++){
int opt=read();
if(opt==1){
int x=read();
int y=lower_bound(q.begin(),q.end(),x)-q.begin();n++;
q.insert(q.begin()+y,x);
while(n>k){
q.pop_back();
n--;
}
}
else if(n>=k){
printf("%d\n",q[k-1]);
}
else{
printf("-1\n");
}
}
return 0;
}优先队列的写法
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f*=-1;c=getchar();
}
while(isdigit(c)){
x=(x<<3)+(x<<1)+(c^48);c=getchar();
}
return x*f;
}
const int maxn=2e5+7;
priority_queue<int> que;
int main(){
int n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
int a=read();
if(que.size()<k){
que.push(a);
}
else{
if(a<que.top()){
que.pop();
que.push(a);
}
}
}
int op,x;
for(int i=1;i<=m;i++){
op=read();
if(op==1){
x=read();
if(que.size()<k){
que.push(x);
}
else{
if(x<que.top()){
que.pop();
que.push(x);
}
}
}
else{
if(que.size()<k){
printf("-1\n");
}
else{
printf("%d\n",que.top());
}
}
}
return 0;
}I：区间异或
n的大小只有3000很明显是告诉你要n^2枚举所有异或和。
每次查询很容易就想到二分查找，因此需要构造出一个从小到大按照异或和大小排序的序列，并且需要保证构造出来的异或和小的数一定要比异或和大的数所需要的区间小，否则这个数没有参考价值，不如直接选大的数并且还区间小。
构造方法
sort(q.begin(),q.end(),cmp);//排序
for(int i=0;i<q.size();i++){
while(w.size()&&w[w.size()-1].second>q[i].second)w.pop_back();//w.pop_back();是删掉容器的最后一个数
w.push_back(q[i]);
}二分查找
inline int check(vector<pair<int,int> >q,int x){//太菜了，lower_bound不会用，只能自己手写一个二分。
int l=0,r=q.size()-1,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(q[mid].first>=x){
r=mid-1;
ans=q[mid].second;
}
else l=mid+1;
}
return ans;
}AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
int a[N];
long long ans[N];
vector<pair<int,int> >q,w;
bool cmp(pair<int,int>a,pair<int,int>b){
return a.first<b.first;
}
inline int check(vector<pair<int,int> >q,int x){
int l=0,r=q.size()-1,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(q[mid].first>=x){
r=mid-1;
ans=q[mid].second;
}
else l=mid+1;
}
return ans;
}
int main(){
int n=read(),m=read(),maxn;
for(int i=1;i<=n;i++){
a[i]=read();maxn=max(maxn,a[i]);
}
for(int i=1;i<=n;i++){
int s=0;
for(int j=i;j<=n;j++){
s^=a[j];
if(s>maxn){
q.push_back({s,j-i+1});
}
}
}
q.push_back({maxn,1});
sort(q.begin(),q.end(),cmp);
for(int i=0;i<q.size();i++){
while(w.size()&&w[w.size()-1].second>q[i].second)w.pop_back();
w.push_back(q[i]);
}
while(m--){
int x=read();
cout<<check(w,x)<<endl;
}
return 0;
}J：小游戏
动态规划简单题，数据大小只有2e5，所以我们用桶来记录每个数。
当前这个数拿了的话前面一个数就不能拿了所以有两种情况
如果这个数我们拿了就是
ans[i]=ans[i-2]+(ll)a[i]*i
如果这个数我们没拿的话
ans[i]=ans[i-1]
那么动态转移方程就出来
ans[i]=max(ans[i-1],ans[i-2]+(ll)a[i]*i);
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
int a[N];
long long ans[N];
int main(){
int n=read();
for(int i=1;i<=n;i++){
int x=read();a[x]++;
}
ans[1]=a[1];
ans[2]=a[2]*2;
for(int i=3;i<=200000;i++){
ans[i]=max(ans[i-1],ans[i-2]+(ll)a[i]*i);
}
cout<<ans[200000]<<endl;
return 0;
}
京公网安备 11010502036488号