真的难写。
$\checkmark$ A
给定序列 $a$，求该序列差最小的数对。
差最小的数对一定在排序后的相邻两项中产生。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| constexpr int N=2e5+5;
int a[N];
inline void work()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int mn=2e9+5,tot=0;
for(int i=2;i<=n;i++)
{
int x=a[i]-a[i-1];
if(mn>x) mn=x,tot=0;
if(mn==x) ++tot;
}
cout<<mn<<" "<<tot<<endl;
}
|
$\checkmark$ B
直接模拟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| constexpr int N=105;
vector<int>s;
int a[N];
inline void work()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) s.emplace_back(i);
for(int i=1;i<=k;i++) cin>>a[i];
int now=0;
for(int i=1;i<=k;i++)
{
int t=int(s.size());
a[i]=a[i]%t;
now=(now+a[i])%t;
cout<<s[now]<<" ";
s.erase(s.begin()+now);
now=now%(t-1);
}
}
|
$\checkmark$ C
给定一数字，求删去最少的位数使得其为 $3$ 的倍数且不含前导 $0$，不可能输出 $-1$。
将为 $3$ 的倍数转化为所有位上的数字之和是 $3$ 的倍数，可以通过贪心及分类讨论解决，但过于繁琐。此处选用 DP。设 $f_{i,j}$ 为前 $i$ 位，使得保留下来的数位之和 $\bmod 3=j$ 至少删去的数字。注意如果当前位为 $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
| constexpr int N=1e5+5;
int f[N][3],pre[N][3];
char s[N],ans[N];
inline void work()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>(s+1);int n=int(strlen(s+1));
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
{
int x=s[i]-'0';
for(int j=0;j<3;j++)
{
if(x==0)
{
if(f[i-1][j]==i-1) f[i][j]=i,pre[i][j]=1;
else f[i][j]=f[i-1][j],pre[i][j]=0;
}
else
{
if(f[i-1][j]+1<=f[i-1][(j+3-x%3)%3]) f[i][j]=f[i-1][j]+1,pre[i][j]=1;
else f[i][j]=f[i-1][(j+3-x%3)%3],pre[i][j]=0;
}
}
}
if(f[n][0]==n)
{
for(int i=1;i<=n;i++) if(s[i]=='0') return cout<<"0",void();
return cout<<"-1",void();
}
int tot=0,now=0;
for(int i=n;i>0;i--) if(!pre[i][now]) ans[++tot]=s[i],now=(now+3-(s[i]-'0')%3)%3;
reverse(ans+1,ans+tot+1);
cout<<(ans+1);
}
|
$\checkmark$ D
给一个完全二叉树，按中序遍历标号，要求支持对于某个点求父亲，左儿子，右儿子。
首先，每个子树的标号都是连续的，不妨即为 $l,r$，则子树根节点的标号 $u$ 为 $\frac{l+r}{2}$，且左子树的标号范围为 $[l,u)$，右子树为 $(u,r]$，每次询问预处理所求节点到根上所有节点的 $l,r$ 则可 $O(1)$ 完成操作。
其实可以直接从数字的性质入手，不需要预处理。
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
| using ll=long long;constexpr int N=105,M=1e5+5;
ll pl[N],pr[N],id[N];int top=0;
inline void gen(ll l,ll r,ll p)
{
++top;pl[top]=l,pr[top]=r;ll u=id[top]=(l+r)>>1;
if(p==u) return;
if(p<u) gen(l,u-1,p);
else gen(u+1,r,p);
}
inline void up()
{
if(top==1) return;
top--;
}
inline void ls()
{
if(pl[top]==pr[top]) return;
++top;
pl[top]=pl[top-1],pr[top]=id[top-1]-1;
id[top]=(pl[top]+pr[top])>>1;
}
inline void rs()
{
if(pl[top]==pr[top]) return;
++top;
pl[top]=id[top-1]+1,pr[top]=pr[top-1];
id[top]=(pl[top]+pr[top])>>1;
}
char s[M];
inline void work()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll n;int m;cin>>n>>m;
while(m--)
{
ll x;cin>>x;top=0;gen(1,n,x);
cin>>(s+1);int k=int(strlen(s+1));
for(int i=1;i<=k;i++)
{
if(s[i]=='U') up();
else if(s[i]=='L') ls();
else if(s[i]=='R') rs();
}
cout<<id[top]<<"\n";
}
}
|
$✗$ E
给定 $n$ 个数，将这 $n$ 个数中的每个数都拆分为若干个数的和，要求拆分完的数字极差不能超过 $1$。
如果你像我一样，往整除分块那里去想，那么你很可能得到一个 $O(n^2\sqrt{\max{a_i}})$ 的做法。记 $v=\min a_i$。记拆分完较小的数字为 $k$，则 $\forall i,\lfloor \frac{a_i}{k}\rfloor\ge a_i \bmod k$。考虑根号分治，显然对于 $\forall k \le \sqrt{v}$，该式恒成立。对于 $k>\sqrt{v}$ 枚举 $k$ 效率低下，可以改为枚举 $\lfloor \frac{a_i}{k}\rfloor$，则可得出此时的 $k$ 及 $v \bmod k$，然后对于所有的 $a_i$ 检查是否合法，注意当 $k \mid a_1$ 时要特判。此时时间复杂度 $O(n\sqrt{\min 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
24
25
26
27
28
29
30
31
32
33
| constexpr int N=505;using ll=long long;
int a[N],n,d=0;
inline bool check(int k,int r)
{
for(int i=1;i<=n;i++)
{
int x=a[i]/k,y=a[i]%k;
if(r&&y>x) return false;
if(!r)
{
if(y>x) --k,r=1,x=a[i]/k,y=a[i]%k;
if(y>x) return false;
}
}
d=k;
return true;
}
inline void work()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int B=int(floor(sqrt(a[1])))+1;
for(int i=1;i<=B;i++)
{
int k=a[1]/i,r=a[1]%i;
if(check(k,r)) break;
}
ll ans=0;
for(int i=1;i<=n;i++) ans=ans+(a[i]+d)/(d+1);
cout<<ans<<endl;
}
|
$✗$ F
计算几何，学不会。