文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >专栏 >IME++ Starters Try-outs 2019 题解

IME++ Starters Try-outs 2019 题解

作者头像
dejavu1zz
发布于 2020-12-02 15:04:31
发布于 2020-12-02 15:04:31
68300
举报
文章被收录于专栏：奇妙的算法世界奇妙的算法世界
运行总次数：0

目录

A

题意描述
思路

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

AC代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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代码
代码语言：javascript
代码运行次数：0
运行
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/11/30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
node.js

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

node.js
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 目录
  • A
    • 题意描述
    • 思路
    • AC代码
  • B
    • 题意描述
    • 思路
    • AC代码
  • C
    • 题意描述
    • 思路
    • AC代码
  • D
    • 题意描述
    • 思路
    • AC代码
  • E
    • 题意描述
    • 思路
    • AC代码
  • F
    • 题意描述
    • 思路
    • AC代码
  • G
    • 题意描述
    • 思路
    • AC代码
  • H
    • 题意描述
    • 思路
    • AC代码
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论