冰菓
牛客周赛 Round 44
这场题目不太难，最后一题没做出来（恶补基环树.....
A
直接除3
1
2
3
4
5
6
7
8
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
cout<<n/3;
}
|
B
开个map记录相同次数，最大数和最大公约数显然是相同时候
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int a[N];
int main()
{
int n;
cin>>n;
int maxn=0;
map<int,int>mp;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
int ans=0;
for(auto &[x,y]:mp)
{
ans=max(y,ans);
}
cout<<ans;
}
|
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
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
ll ans=0;
for(int i=s.length()-1;i>=1;i--)
{
if(s[i]=='0')
{
continue;
}
ans+=10-int(s[i]-'0');
s[i]='0';
while(i-1>=1&&s[i-1]=='9')
{
i--;
s[i]='0';
}
s[i-1]+=1;
}
cout<<ans<<'\n';
}
}
|
D
欧拉筛因子，然后再用前缀和。
1e5以内最大因子只有128个
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll=long long;
int a[N];
int prim[N], vis[N], d[N], sum[N], len;
int ans[N][140];
void eular_num(int n)
{
d[1] = 1;
for(int i = 2;i <= n;i ++)
{
if(! vis[i])
{
prim[len ++] = i;
sum[i] = 1;
d[i] = 2;
}
for(int j = 0; j < len && i * prim[j] <= n; j ++)
{
vis[i * prim[j]] = 1;
if(i % prim[j] == 0)
{
sum[i * prim[j]] = sum[i] + 1;
d[i * prim[j]] = d[i] / (sum[i] + 1) * (sum[i] + 2);
break;
}
sum[i * prim[j]] = 1;
d[i * prim[j]] = d[i] * 2;
}
}
}
int main()
{
int n;
cin>>n;
int q;
cin>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
eular_num(N);
for(int i=1;i<=n;i++)
{
for(int j=2;j<=128;j++)
{
ans[i][j]=ans[i-1][j];
}
ans[i][d[a[i]]]=ans[i-1][d[a[i]]]+1;
}
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
ll res=0;
for(int j=2;j<=128;j++)
{
res+=1ll*(ans[r][j]-ans[l-1][j])*(ans[r][j]-ans[l-1][j]-1)/2;
}
cout<<res<<'\n';
}
}
|
E
我的构造方法是偶数按照后一半先排，前一半后排，然后奇数对应-1.不过当n是奇数时候需要处理1和n
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;
using ll=long long;
const int N=1e6+100;
int a[N];
int main()
{
int n;
cin>>n;
int cnt=0;
int x=n;
int y=n-1;
if(n&1)
{
if(n==1||n==3||n==5||n==7)
{
cout<<-1;
return 0;
}
n--;
int c=n/2+1;
if(c&1)
{
c++;
}
for(int i=2;i<=n;i+=2)
{
if(c==n+2)
{
c=2;
}
a[i]=c;
c+=2;
}
for(int i=1;i<=n;i+=2)
{
a[i]=a[i+1]-1;
}
n++;
a[n]=n;
swap(a[1],a[n]);
}
else
{
if(n==2||n==4||n==6)
{
cout<<-1;
return 0;
}
if(n==8)
{
cout<<5<<' '<<6<<' '<<7<<" "<<8<<' '<<1<<" "<<2<<' '<<3<<' '<<4;
return 0;
}
int c=n/2+1;
if(c&1)
{
c++;
}
for(int i=2;i<=n;i+=2)
{
if(c==n+2)
{
c=2;
}
a[i]=c;
c+=2;
}
for(int i=1;i<=n-1;i+=2)
{
a[i]=a[i+1]-1;
}
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<' ';
}
}
|
也有优雅做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if (n < 8) {
cout << "-1\n";
return 0;
}
for (int i = 5; i <= n; i++) {
cout << i << ' ';
}
cout << (n % 2 ? "2 1 4 3" : "1 2 3 4") << '\n';
return 0;
}
|
F
注意到基环树上的环产生两个分支路线，因此 1到 𝑛 的路径最多只有 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
| #include<bits/stdc++.h>
using namespace std;
#define N 100050
int i,j,k,n,m,t,vis[N],f[N];
vector<pair<int,int> > v[N];
void dfs(int x,int dep){
if(x==n){
for(i=1;i<=n;i++)if(!vis[i])f[i]=min(f[i],dep);
return;
}
for(auto [y,id]:v[x])if(!vis[id]){
vis[id]=1; dfs(y,dep+1); vis[id]=0;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(i=1;i<=n;i++){
cin>>j>>k; f[i]=1e9;
v[j].push_back({k,i});
v[k].push_back({j,i});
}
dfs(1,0);
for(i=1;i<=n;i++){
cout<<(f[i]>1e6?-1:f[i])<<'\n';
}
}
|
