牛客周赛 Round 41
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
ll a,b,c;
cin>>a>>b>>c;
if(a>=b&&c>=b)
{
cout<<min(a,c)-b;
}
else
{
cout<<0;
}
}
|
B
构造就直接往后移动一位进行构造其实就可以了，我想复杂了
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
int a[N];
int vis[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
if(k==1||k>n)
{
cout<<-1;
}
else
{
if(k%2==0)
{
for(int i=1;i<=k;i++)
{
cout<<a[k-i+1]<<' ';
}
for(int i=k+1;i<=n;i++)
{
cout<<a[i]<<' ';
}
}
else
{
cout<<a[k]<<' ';
for(int i=1;i<=k-1;i++)
{
cout<<a[i]<<" ";
}
for(int i=k+1;i<=n;i++)
{
cout<<a[i]<<' ';
}
}
}
}
|
C
一开始写了好多，发现直接复制扫一遍就行
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
string s;
cin>>s;
s+=s;
int n=s.length();
s=" "+s;
int sum=0;
for(int i=n/2-1;i<=n-1;i++)
{
if(((s[i]-'0')*10+s[i+1]-'0')%4==0)
{
cout<<sum;
return 0;
}
else
{
sum++;
}
}
cout<<-1;
}
|
D
一开始想用线段树查询，真是nt了，好好的前缀和不用
然后就是一顿操作
需要讨论%3的情况
如果可以整除
rreedd就一定是这种
如果取余是1，就是
reed,rred,redd
如果是2
就是rreed,reedd,rredd，分别用前缀和进行讨论
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long ;
const int N=1e6+100;
#define int long long
int sum1[N];
int sum2[N];
int sum3[N];
signed main()
{
int n,q;
cin>>n>>q;
string s;
cin>>s;
s=" "+s;
for(int i=1;i<=n;i++)
{
sum1[i]=sum1[i-1]+(s[i]=='r');
sum2[i]=sum2[i-1]+(s[i]=='e');
sum3[i]=sum3[i-1]+(s[i]=='d');
}
while(q--)
{
int l,r;
cin>>l>>r;
int x=r-l+1;
if(x<3)
{
cout<<0<<'\n';
continue;
}
if(x%3==0)
{
int y=x/3;
cout<<abs(sum1[l+y-1]-sum1[l-1]-y)+abs(sum2[l+2*y-1]-sum2[l+y-1]-y)+abs(sum3[l+3*y-1]-sum3[l+2*y-1]-y)<<'\n';
}
else if(x%3==1)
{
int y=x/3;
int ans=min(abs(sum1[l+y-1]-sum1[l-1]-y)+abs(sum2[l+2*y]-sum2[l+y-1]-y-1)+abs(sum3[r]-sum3[l+2*y]-y),abs(sum1[l+y]-sum1[l-1]-y-1)+abs(sum2[l+2*y]-sum2[l+y]-y)+abs(sum3[r]-sum3[l+2*y]-y));
ans=min(ans,abs(sum1[l+y-1]-sum1[l-1]-y)+abs(sum2[l+2*y-1]-sum2[l+y-1]-y)+abs(sum3[r]-sum3[l+2*y-1]-y-1));
cout<<ans<<'\n';
}
else
{
int y=x/3;
int ans=min(abs(sum1[l+y]-sum1[l-1]-y-1)+abs(sum2[l+2*y+1]-sum2[l+y]-y-1)+abs(sum3[r]-sum3[l+2*y+1]-y),abs(sum1[l+y-1]-sum1[l-1]-y)+abs(sum2[l+2*y]-sum2[l+y-1]-y-1)+abs(sum3[r]-sum3[l+2*y]-y-1));
ans=min(ans,abs(sum1[l+y]-sum1[l-1]-y-1)+abs(sum2[l+2*y]-sum2[l+y]-y)+abs(sum3[r]-sum3[l+2*y]-y-1));
cout<<ans<<'\n';
}
}
}
|
E
采取连通块来，由于每个红色的节点的子树必须是0，因此可以直接进行类似于连通块的操作
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const ll N = 2e5,T=0x3f3f3f3f, P = 1e9+7;
const double G= 1e-6;
int n ,m,ans,l,r;
vector<int>w[N] , s[N];
int fat[N],fa[N];
int d[N];
bool st[N];
void dfs(int u, int v)
{
fat[u] = v;
for(auto it : w[u])
{
if(fat[it]) continue;
dfs(it,u);
}
}
int find(int x)
{
if(fa[x]!=x) return fa[x] = find(fa[x]);
return fa[x];
}
void uni(int x)
{
int q = find( fat[x]) , p = find(x);
if(s[q].size()>=s[p].size())
{
fa[p] = q;
for(auto it : s[p])
{
s[q].push_back(it);
}
s[p].clear();
}
else{
fa[q] = p;
for(auto it : s[q])
{
s[p].push_back(it);
}
s[q].clear();
}
}
int main(){
cin>>n>>l>>r;
string str ; cin>>str;
str = " " + str;
for(int i=0;i<n-1;i++)
{
int a ,b ;cin>>a>>b;
w[a].push_back(b);
w[b].push_back(a);
}
dfs(1,1);
for(int i=1;i<=n;i++) fa[i] = i,s[i].push_back(i);
for(int i=1;i<=n;i++)
{
if(str[i]!='R')
{
uni(i);
}
}
for(int i=1;i<=n;i++)
{
if(str[i]=='R')
{
int root = find(fa[i]); int len = s[root].size();
for(int j=0;j<len/2;j++) d[s[root][j]] = -1;
for(int j=len/2;j<len/2*2;j++) d[s[root][j]] = 1;
if(len%2) st[s[root].back()] = true;
}
}
for(int i=1;i<=n;i++)
{
if(d[i] || st[i]) cout<<d[i]<<" ";
else cout<<1<<" ";
}
}
|
