比赛链接
非常美丽地在1h内做完了前4题，结果第五题交互题，死活不对。。。
题解
A. Who Ate the Cake?
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int a,b;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>a>>b;
if(a!=b)
{
cout<<6-a-b<<"\n";
}
else
{
cout<<-1<<"\n";
}
return 0;
}
|
B. Piano 2
直接排序然后对比即可，就是要注意C数组的大小为n+m，因为这个博主整了2发罚时。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int c[205];
map<int,bool> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>c[i];
mp[c[i]]=1;
}
for(int i=0;i<m;i++)
{
cin>>c[i+n];
}
sort(c,c+m+n);
bool f=0;
for(int i=0;i<n+m;i++)
{
if(mp[c[i]])
{
if(f==1)
{
cout<<"Yes\n";
return 0;
}
else
{
f=1;
}
}
else
{
f=0;
}
}
cout<<"No\n";
return 0;
}
|
C. Bingo 2
纯模拟，但是注意卡常。一是要使用break；二是不用初始化，把每个点的值先填上
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,t;
int a[200005];
map<int,int> mp;
int g[2005][2005];
int ans,ans1=1e9;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>t;
for(int i=0;i<t;i++)
{
cin>>a[i];
mp[a[i]]=i+1;
}
for(int i=1;i<=n;i++)
{
bool f=1; ans=0;
for(int j=1;j<=n;j++)
{
if(!mp[n*(i-1)+j])
{
f=0;
break;
}
else
{
ans=max(mp[n*(i-1)+j],ans);
}
}
if(f==1)
{
ans1=min(ans1,ans);
}
f=1; ans=0;
for(int j=1;j<=n;j++)
{
if(!mp[n*(j-1)+i])
{
f=0;
break;
}
else
{
ans=max(mp[n*(j-1)+i],ans);
}
}
if(f==1)
{
ans1=min(ans1,ans);
}
}
bool f=1; ans=0;
for(int i=1;i<=n;i++)
{
if(!mp[n*(i-1)+i])
{
f=0;
break;
}
else
{
ans=max(mp[n*(i-1)+i],ans);
}
}
if(f==1)
{
ans1=min(ans1,ans);
}
f=1; ans=0;
for(int i=1;i<=n;i++)
{
if(!mp[n*(i-1)+n-i+1])
{
f=0;
break;
}
else
{
ans=max(mp[n*(i-1)+n-i+1],ans);
}
}
if(f==1)
{
ans1=min(ans1,ans);
}
cout<<(ans1==1e9?-1:ans1)<<"\n";;
return 0;
}
|
D. Intersecting Intervals
最水D题。
存一下所有开始时间和结束时间，然后按时间顺序排，注意由于区间左右皆开，所以开始要排在结束前面
然后如果遇到开始时间，ans+现有的未完区间，并且未完区间数+1，否则-1
请开long long
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
bool cmp(pair<ll,ll> x,pair<ll,ll> y)
{
if(x.first==y.first)
{
return x.second<y.second;
}
return x.first<y.first;
}
ll n,s,t;
vector<pair<ll,ll> > v;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(ll i=0;i<n;i++)
{
cin>>s>>t;
v.push_back({s,0});
v.push_back({t,1});
}
sort(v.begin(),v.end(),cmp);
ll k=0,ans=0;
for(ll i=0;i<v.size();i++)
{
if(v[i].second==0)
{
ans+=k;
k++;
}
else
{
k--;
}
}
cout<<ans<<"\n";
return 0;
}
|
E. Guess the Sum
为什么加了输入输出流解绑就会出现输入问题qwq，烦
参考jiangly大神的做法
(=_=) E又>F了
非常匪夷所思地使用了最短路
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,l,r;
int v;
int pre[300005];
queue<int> q;
int main()
{
cin>>n>>l>>r;
r++;
q.push(l);
memset(pre,-1,sizeof pre);
pre[l]=l;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=1;i<=(1<<n);i*=2)
{
for(auto y:{x-i,x+i})
{
if(y<0||y>(1<<n))
{
continue;
}
if(pre[y]==-1)
{
pre[y]=x;
q.push(y);
}
}
if(x&i)
{
break;
}
}
}
ll ans=0;
for(int i=r;i!=l;i=pre[i])
{
int b=i,a=pre[i];
int t=1;
if(a>b)
{
swap(a,b);
t=-t;
}
cout<<"? "<<__lg(b-a)<<" " <<a/(b-a)<<"\n";
int ret;
cin>>ret;
ans=(ans+t*ret+100)%100;
}
cout<<"! "<<ans<<"\n";
return 0;
}
|
F. MST Query
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
using namespace std;
ll n,m;
ll a[400005],b[400005],c[400005];
ll par[200005];
ll vis[400005];
ll dp[400005];
ll find(ll x)
{
return par[x]==x?x:par[x]=find(par[x]);
}
void merge(ll x,ll y)
{
x=find(x),y=find(y);
par[x]=y;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(ll i=1;i<n+m;i++)
{
cin>>a[i]>>b[i]>>c[i];
}
for(ll l=1;l<=10;l++)
{
for(ll i=1;i<=n;i++)
{
par[i]=i;
}
for(ll i=1;i<n+m;i++)
{
if(c[i]>l)
{
continue;
}
if(find(a[i])!=find(b[i]))
{
merge(a[i],b[i]);
if(!vis[i])
{
dp[i]+=l;
vis[i]=1;
}
}
else if(vis[i])
{
dp[i]-=l;
vis[i]=0;
}
}
}
ll ans=0;
for(ll i=1;i<n+m;i++)
{
ans+=dp[i];
if(i>=n)
{
cout<<ans<<"\n";
}
}
return 0;
}
|
G. Baseball