专栏首页奇妙的算法世界IME++ Starters Try-outs 2019 题解

IME++ Starters Try-outs 2019 题解

目录

A

题意描述

思路

显然如果有多棵树,则一定会存在无法到达的点。否则直接暴力 b f s bfs bfs求每个点到其余点的距离, a n s ans ans取 m a x max max即可

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
struct DSU{
    vector<int> data;

    void init(int n){data.assign(n,-1);}

    bool unionSet(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y] < data[x]) swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x != y;
    }

    bool same(int x,int y) {return root(x)==root(y);}

    int root(int x) {return data[x] < 0 ? x : data[x]=root(data[x]);}

    int Size(int x) {return -data[root(x)];}
};
int n,m,dep[N];
bool st[N];
vector<int> g[N];
int bfs(int u){
	mst(dep,-1);
	mst(st,false);
	queue<int> q;
	dep[u]=0;
	q.push(u);
	while(q.size()){
		int t=q.front();
		st[t]=true;
		q.pop();
		rep(i,0,sz(g[t])){
			int v=g[t][i];
			if(st[v]) continue;
			if(dep[v]==-1){
				dep[v]=dep[t]+1;
				q.push(v);
			}
		}
	}
	int res=0;
	rep(i,1,n+1) res=max(res,dep[i]);
	return res;
}
void solve(){
	DSU d;
	cin>>n>>m;
	d.init(n+1);
	rep(i,0,m){
		int a,b;
		cin>>a>>b;
		g[a].PB(b);
		g[b].PB(a);
		d.unionSet(a,b);
	}
	if(d.Size(1)!=n) cout<<"=["<<endl;
	else{
		int ans=0;
		rep(i,1,n+1){
			ans=max(ans,bfs(i));
		}
		cout<<"=] "<<ans<<endl;
	}
}
int main(){
    IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

B

题意描述

思路

最长公共子序列裸题,套模板即可

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=2*1e3+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int f[N][N];
char a[N],b[N];
void solve(){
	cin>>a+1>>b+1;
	int len1=strlen(a+1),len2=strlen(b+1);
	rep(i,1,len1+1){
		rep(j,1,len2+1){
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
		}
	}
	cout<<f[len1][len2]<<endl;
}
int main(){
    //IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

C

题意描述

思路

将每个人的技能值排个序,从前到后 d f s dfs dfs即可。(这道题数据挺弱的,有的假算法都可以过)

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=30;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
ll a[N];
int n,x,d,ans;
void dfs(int now,ll mn,ll sum){
	if(sum>=x) ans++;
	rep(i,now+1,n){
		if(a[i]-mn<=d) dfs(i,mn,sum+a[i]);
	}
}
void solve(){
	cin>>n>>x>>d;
	rep(i,0,n) cin>>a[i];
	sort(a,a+n);
	rep(i,0,n){
		dfs(i,a[i],a[i]);
	}
	cout<<ans<<endl;
}
int main(){
    IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

D

题意描述

思路

排序后将第一个与最后一个结合,第二个与倒数第二个结合,以此类推。然后取最大值和最小值相减。

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int a[N];
void solve(){
	int n;
	cin>>n;
	rep(i,0,n*2) cin>>a[i];
	sort(a,a+n*2);
	vector<int> v;
	rep(i,0,n){
		v.PB(a[i]+a[n*2-i-1]);
	}
	sort(all(v));
	cout<<v[sz(v)-1]-v[0]<<endl;
}
int main(){
    //IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

E

题意描述

思路

思路很简单,就是使用 m a p map map统计每个字符串出现的次数,如果多次出现,则存进 a n s ans ans数组。做这道题时先是因为未知错误一直在第一个样例wa,后来一直超时,最后输出时使用puts才A掉。

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=8*1e6+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int n;
char s[N];
unordered_map<string,int> cnt;
string ans[N];
void solve(){
	cin>>n;
	int idx=0;
	rep(i,0,n){
		cin>>s;
		if(!cnt[s]) cnt[s]++;
		else{
			if(strlen(s)>=4){
				ans[idx++]=s;
			}
		}
	}
	if(n==1){
		cout<<"SAFO"<<endl;
		return;
	}
	if(!idx){
		cout<<"SAFO"<<endl;
		return;
	}	
	cout<<idx<<endl;
	rep(i,0,idx){
		puts(ans[i].c_str());
	}
}
int main(){
    IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
    	solve();
    return 0;
}

F

题意描述

思路

并查集裸题,套模板即可

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=30;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
struct DSU{
    vector<int> data;

    void init(int n){data.assign(n,-1);}

    bool unionSet(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y] < data[x]) swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x != y;
    }

    bool same(int x,int y) {return root(x)==root(y);}

    int root(int x) {return data[x] < 0 ? x : data[x]=root(data[x]);}

    int Size(int x) {return -data[root(x)];}
};
void solve(){
	DSU d;
	map<string,int> s;
	int n,m;
	cin>>n>>m;
	d.init(n+1);
	int idx=1;
	rep(i,0,n){
		string str;
		cin>>str;
		s[str]=idx++;
	}
	rep(i,0,m){
		int op;
		string s1,s2;
		cin>>op>>s1>>s2;
		int a=s[s1],b=s[s2];
		if(op==1) d.unionSet(a,b);
		else{
			if(d.same(a,b)) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
	}
}
int main(){
    //IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

G

题意描述

思路

线段树裸题,分别维护最大值最小值和 s u m sum sum即可

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int w[N];
struct Node{
    int l,r,mn,mx,sum;
}node[N * 4];
struct SegTree{

    void push_up(int ind){
		node[ind].mn=min(node[lson].mn,node[rson].mn);
		node[ind].mx=max(node[lson].mx,node[rson].mx);
		node[ind].sum=node[lson].sum+node[rson].sum;
    }

    void push_down(int ind){

    }

    void build(int l,int r,int ind){
        node[ind].l=l;
        node[ind].r=r;
        if(l==r){
			node[ind].mn=w[l];
			node[ind].mx=w[l];
			node[ind].sum=w[l];
        }else{
            int mid=l+r>>1;
            build(l,mid,lson);
            build(mid+1,r,rson);
            push_up(ind);
        }
    }

    void update(int l,int r,int ind,int val){
        if(l>node[ind].r || r<node[ind].l) return;
        if(l<=node[ind].l && r>=node[ind].r){
			node[ind].mn=val;
			node[ind].mx=val;
			node[ind].sum=val;
        }else{
            push_down(ind);
            update(l,r,lson,val);
            update(l,r,rson,val);
            push_up(ind);
        }
    }

    void query_sum(int l,int r,int ind,int &ans){
        if(l>node[ind].r || r<node[ind].l) return;
        if(l<=node[ind].l && node[ind].r<=r){
			ans+=node[ind].sum;
        }else{
            push_down(ind);
            query_sum(l,r,lson,ans);
            query_sum(l,r,rson,ans);
            push_up(ind);
        }
    }
    
    void query_max(int l,int r,int ind,int &ans){
        if(l>node[ind].r || r<node[ind].l) return;
        if(l<=node[ind].l && node[ind].r<=r){
			ans=max(ans,node[ind].mx);
        }else{
            push_down(ind);
            query_max(l,r,lson,ans);
            query_max(l,r,rson,ans);
            push_up(ind);
        }
    }
    
    void query_min(int l,int r,int ind,int &ans){
        if(l>node[ind].r || r<node[ind].l) return;
        if(l<=node[ind].l && node[ind].r<=r){
			ans=min(ans,node[ind].mn);
        }else{
            push_down(ind);
            query_min(l,r,lson,ans);
            query_min(l,r,rson,ans);
            push_up(ind);
        }
    }
};
void solve(){
	int n,q;
	cin>>n>>q;
	SegTree seg;
	rep(i,1,n+1) cin>>w[i];
	seg.build(1,n,1);
	while(q--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			int sum=0,mn=INF,mx=0;
			seg.query_sum(x,y,1,sum);
			seg.query_max(x,y,1,mx);
			seg.query_min(x,y,1,mn);
			cout<<sum-mn-mx<<endl;
		}else{
			seg.update(x,x,1,y);
		}
	}
}
int main(){
    //IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

H

题意描述

思路

要我们解一个同余方程,发现答案可以取 0 0 0,而任何数的 0 0 0次幂都是1,所以输出 0 0 0即可。(样例的这个 − 1 -1 −1没有看懂是什么意思)

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
void solve(){
	int n,m;
	scanf("%d%d",&n,&m);
	cout<<0<<endl;	
}
int main(){
    //IOS;
    //freopen("window.in", "r", stdin);
    //freopen("window.out", "w", stdout);
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforces 1324E(dp)

    dejavu1zz
  • codeforces 1384A(构造)

    The length of the longest common prefix of two strings s=s1s2…sn and t=t1t2…tm i...

    dejavu1zz
  • codeforces 1311D(暴力)

    dejavu1zz
  • codeforces 1384A(构造)

    The length of the longest common prefix of two strings s=s1s2…sn and t=t1t2…tm i...

    dejavu1zz
  • CCF考试——201409-2画图

      在一个定义了直角坐标系的纸上,画一个(x1,y1)到(x2,y2)的矩形指将横坐标范围从x1到x2,纵坐标范围从y1到y2之间的区域涂上颜色。   下...

    AI那点小事
  • 算法导论第六章堆排序(一)

    现在来看, 堆的含义大概有两种,一种是数据结构,一种是在一些语言中所定义的“垃圾回收机制”,如Java,在书本上的开篇强调了这两者,并强调若非特殊说明,皆把堆看...

    猿大白
  • codeforces 1405B(思维)

    You’re given an array a of n integers, such that a1+a2+⋯+an=0.

    dejavu1zz
  • 《从0开始学架构》读书笔记

    本质是通过冗余实现高可用(多台、多机房、多通道), 但是冗余带来了更大的复杂性. 比如任务分配器(例nginx)连接检测、管理、维护、中断处理.

    用户2825413
  • Java的标签

    以前笔者如何退出双重循环呢? 利用循环条件判断,加上break、continue、return可以改变流程

    晚上没宵夜
  • 数据结构之堆

    有没有更优的数据结构?使用堆,可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。

    崔笑颜

扫码关注云+社区

领取腾讯云代金券