A. Blackslex and Password
让位置 \(1,1+x,1+2x...,1+(k-1)x\) 用完前 \(k\) 个字母，则位置 \(1+kx\) 的字母必定要和前面那几个位置重复，所以答案就是 \(k*x+1\)
B. Blackslex and Showering
可以先计算出删数之前的答案 \(sum\)
然后可以 \(for\) 循环枚举删除第 \(i\) 个数
此时，删除这个数对答案造成的贡献是：\(-abs(a[i]-a[i-1])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1])\)
所以此时，\(ans_i=sum-abs(a[i]-a[i-1])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1])\)
对 \(ans\) 取最小值即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,ans=0;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];if(i!=1) ans+=abs(a[i]-a[i-1]);}int x=-inf;for(int i=1;i<=n;i++){int val=0;if(i==n) val=abs(a[i]-a[i-1]);else if(i==1) val=abs(a[i]-a[i+1]);else{val=abs(a[i]-a[i-1])+abs(a[i]-a[i+1])-abs(a[i-1]-a[i+1]);}x=max(x,val);}// sum-abs(a[i]-a[i-1])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1])cout<<ans-x<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;cin>>t; while(t--){solve(); }}
C. Blackslex and Number Theory
先考虑对 \(a\) 数组排序，此时 \(a[1]\) 为最小值，\(a[2]\) 为次小值
考虑让 \(k=a[1]\) 是否成立？显然成立，因为此时 \(a[1]~mod~k=0\)，而对于其他的数，也可以选择 \(x=a[i]\)，使得 \(a[i]~mod~x=0\)
考虑让 \(k=a[2]\) 是否成立？
不成立，因为此时，\(a[1]~mod~a[2]=a[1]\)，但 \(a[2]~mod~k=0\)，\(a[2]~mod~x(x>k)=a[2]\)
显然不相等，所以不成立
再考虑 \(k\) 在 \([a[1]+1,a[2]-1]\) 范围内，此时 \(a[1]~mod~k=a[1]\)
要使得 \(a[2]~mod~k=a[1]\)，则 \(k\) 最大可以取 \(a[2]-a[1]\)
如果\(a[2]-a[1]>a[1]\) 则 \(k\) 可以取到 \(a[2]-a[1]\)，此时其他数，也可以找到一个 \(x=a[i]-a[i]>k\)，使得 \(a[i]~mod~x=a[1]\)
否则 \(k\) 最大只能取 \(a[1]\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}sort(a.begin()+1,a.end());int ans=a[1];if(a[2]-a[1]>a[1]) ans=a[2]-a[1];cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;cin>>t; while(t--){solve(); }}