A. Dalton the Teacher
询问把一个排列变成 pi=i 的最小操作次数。
直接记录 pi=i 的个数即可，然后除二向上取整。
B. Longest Divisors Interval
询问一个数最多能被多少个连续的数字整除
如果一个数能被 x 个连续的数字整除，那么根据鸽巢原理，一定可以被 1,2,3,4,...,x 整除。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100100;
int T,n;
signed main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
int ans=0,tans=0;
for(int i=1;i<=min(n,1000ll);i++)
{
if(n%i==0) {
tans++;
ans=max(ans,tans);
}
else tans=0;
}
cout<<ans<<'\n';
}
return 0;
}
|
C. Dual
给你一个序列，每次可以把 ai 操作为 ai=ai+aj，你需要把他弄成不下降序列，最多 31 步 ，输出方案。
假设我们构造出绝对值最大的负数需要 x1 步 ，然后把所有正数变成负数需要 x2 布，同理对正数定义 y1,y2 那么一定有不等式
x1+x2+y1+y2≤25 因为 x1+y1≤5,x2+y2≤20
换句话说 x1+x2,y1+y2 有一个必定小于等于 12
然后如果去全为非负或者非正，我们最多需要进行 n−1=19 次 ,总共操作次数 ≤31 次
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include<bits/stdc++.h>
using namespace std;
const int maxn=55;
int T,n,a[maxn],cnt,b[maxn];
int mmx,mmn;
struct que{
int x,y;
}q[maxn];
void sol1()
{
while(abs(b[mmx])<abs(b[mmn]))
{
q[++cnt].x=mmx;
q[cnt].y=mmx;
b[mmx]*=2;
}
for(int i=1;i<=n;i++)
{
if(b[i]<0)
{
q[++cnt].x=i;
q[cnt].y=mmx;
}
}
for(int i=1;i<n;i++)
{
q[++cnt].x=i+1;
q[cnt].y=i;
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
cout<<q[i].x<<" "<<q[i].y<<'\n';
}
}
void sol2()
{
while(abs(b[mmn])<abs(b[mmx]))
{
q[++cnt].x=mmn;
q[cnt].y=mmn;
b[mmn]*=2;
}
for(int i=1;i<=n;i++)
{
if(b[i]>0)
{
q[++cnt].x=i;
q[cnt].y=mmn;
}
}
for(int i=n-1;i;i--)
{
q[++cnt].x=i;
q[cnt].y=i+1;
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
cout<<q[i].x<<" "<<q[i].y<<'\n';
}
}
void solve()
{
mmx=1,mmn=1;
int cnt0=0,cnt1=0;
for(int i=1;i<=n;i++) b[i]=a[i];
for(int i=1;i<=n;i++)
{
if(b[mmx]<b[i]) mmx=i;
if(b[mmn]>b[i]) mmn=i;
if(b[i]>0) cnt1++;
if(b[i]<0) cnt0++;
}
if(b[mmx]<=0)
{
cout<<n-1<<'\n';
for(int i=n-1;i;i--)
{
cout<<i<<' '<<i+1<<'\n';
}
}
else if(b[mmn]>=0)
{
cout<<n-1<<'\n';
for(int i=1;i<n;i++)
{
cout<<i+1<<' '<<i<<'\n';
}
}
else
{
if(abs(b[mmx])>=abs(b[mmn]))
{
if(cnt0>12) sol2();
else sol1();
}
else
{
if(cnt1>12) sol1();
else sol2();
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cnt=0;
solve();
}
}
|
D. Earn or Unlock
显然可以转化为一个背包问题，因为到了 x 位置的花费和获得都是固定的，bitset 背包考虑能到哪些位置就可了。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200100;
bitset <maxn> b,t;
int n,a[maxn],ans=0;
int sum[maxn];
signed main()
{
ios::sync_with_stdio(false);
cin>>n;
t.set();
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=n+1;i<=n*2;i++) sum[i]=sum[i-1];
ans=a[1];
b[1]=1;
for(int i=1;i<=n*2;i++)
{
if(i<=n)b=b|((b&t)<<a[i]);
if(b[i])ans=max(ans,sum[i]-i+1);
t[i]=0;
}
cout<<ans<<"\n";
}
|
