hihocoder编程练习赛56 A 描述
输入
输出
样例输入
样例输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
int n;
int a[maxn],b[maxn];
int num[maxn*10];
set <int>s;
int main
// freopen("input.txt" ,"r" ,stdin);
scanf("%d" ,&n);
memset(num,0,sizeof num);
for (int i=1;i<=n;i++) scanf("%d" ,&a[i]),num[a[i]]++;
for (int i=1;i<=n;i++) scanf("%d" ,&b[i]);
for (int i=1;i<=1000000;i++){
if (!num[i]) s.insert(i);
}
int ans=0;
for (int i=1;i<=n;i++){
num[a[i]]--;
num[b[i]]++;
s.erase(b[i]);
if (num[a[i]]==0) s.insert(a[i]);
ans=max(ans,*s.begin());
num[a[i]]++;
num[b[i]]--;
s.erase(a[i]);
if (num[b[i]]==0) s.insert(b[i]);
}
cout<<ans<<endl;
return 0;
}
思路 本题相当于要维护一个未出现数字集合的小根堆 并且要满足插入删除操作 联想到set
B 描述
是一个整数或小数。
没有多余的0。例如”03”，”0.10”, “00.2”, “1.0”都不合法。
小数点不能在首尾。例如”.2”, “2.”都不合法。
输入
输出
样例输入
样例输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
string s;
vector<pair<double,double> >a;
bool check(string s){
int len=s.length();
int flag=0;
for (int i=0;i<len;i++){
if (s[i]=='.' ){
flag=1;
break ;
}
}
if (len==1) return true ;
if (s[0]=='0' && s[1]!='.' ) return false ;
if (flag && s[len-1]=='0' ) return false ;
if (!flag) return true ;
return true ;
}
void fun(string s1,string s2){
int len1=s1.length();
int len2=s2.length();
for (int i=1;i<=len1;i++){
for (int j=1;j<=len2;j++){
if (i!=len1) s1.insert(i,"." );
if (j!=len2) s2.insert(j,"." );
// cout<<s1<<" " <<s2<<" " <<check(s1)<<" " <<check(s2)<<endl;
if (check(s1) && check(s2)){
double x,y;
if (len1==0 && s1[0]=='0' ) x=0;
else x=atof(s1.c_str());
if (len2==0 && s2[0]=='0' ) y=0;
else y=atof(s2.c_str());
a.push_back(make_pair(x,y));
}
if (i!=len1) s1.erase(i,1);
if (j!=len2) s2.erase(j,1);
}
}
}
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>s;
int len=s.length();
for (int i=1;i<len;i++){
string s1=" " ,s2=" " ;
s1=s.substr(0,i);
s2=s.substr(i,len-i);
fun(s1,s2);
}
sort(a.begin(),a.end());
for (int i=0;i<a.size();i++){
cout<<a[i].first<<
"," <<a[i].second<<endl;
}
return 0;
}
思路 暴力拆分 每个部分再暴力小数点位置 check后加入pair排序输出
C 描述
输入
输出
样例输入
样例输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
int n,m;
int p[maxn];
set <int>s[maxn];
int find(int x){
return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int a,int b){
int x=find(a);
int y=find(b);
if (x!=y){
// if (s[x].size()<s[y].size()) swap(x,y);
for (auto pp:s[y]) s[x].insert(find(pp));
p[y]=x;
}
}
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>n>>m;
for (int i=0;i<=n;i++) p[i]=i;
while (m--){
char op;
cin>>op;
if (op=='R' ){
int x,y,z;
scanf("%d%d%d" ,&x,&y,&z);
if (z==1) merge(x,y);
else {
x=find(x),y=find(y);
s[x].insert(y),s[y].insert(x);
}
}
else if (op=='Q' ){
int x,y;
scanf("%d%d" ,&x,&y);
x=find(x),y=find(y);
int ans=0;
if (x==y) ans=1;
else if (s[x].count(y) || s[y].count(x)) ans=2;
else ans=3;
cout<<ans<<endl;
}
}
return 0;
}
思路 并查集相关 基础上再加一个二维set判断不是集合的元素
