A. Parallel Projection
题意：有一个 \(w\times d\times h\) 的长方体，顶面和底面有两个点，只能走直线且不能穿过长方体，求最短距离。
显然曼哈顿距离必须要走。多出来绕弯的距离一定是选一个点，到边缘的最短距离 \(\times 2\)。
By cxm1024
#include<bits/stdc++.h>
using namespace std;
signed main() {
int t;
cin>>t;
while(t-->0) {
int x,y,z,a,b,c,d;
cin>>x>>y>>z>>a>>b>>c>>d;
cout<<z+abs(a-c)+abs(b-d)+min({a,b,c,d,x-a,x-c,y-b,y-d})*2<<endl;
}
return 0;
}
B. Going to the Cinema
题意：有 \(n\) 个人，每人有一个要求 \(a_i\)，表示他愿意去电影院当且仅当其他人中有至少 \(a_i\) 个去。问全部满足要求的方案数。
首先对 \(a\) 从小到大排序，枚举总共去几个人。假设去 \(x\) 个人，则一定是 \(a_i\) 最小的 \(x\) 个人去。考虑第 \(x\) 个人是否愿意去，以及第 \(x+1\) 个人是否愿意不去即可。
By IceYukino
int T,n,a[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int ans=1;
if(a[1]!=0) ans++;
for(int i=1;i<n;i++){
if(a[i]>i-1||a[i+1]<=i) continue;
ans++;
}
cout<<ans<<endl;
}
return 0;
}
C. Equal Frequencies
给你一个小写字母字符串，求更改字母的方案，使得让所有出现过的字母的出现次数都相同，且次数尽可能少。
可以枚举需要总共出现几个字母，进而得到每个字母的出现次数 \(x\)。对于每个次数超过 \(x\) 的字母需要砍掉多余的改成其他字母；对于次数不超过 \(x\) 的字母，需要将一些填成 \(x\)，一些砍掉。显然让出现尽可能多的字母填成 \(x\) 最优。
By cxm1024
#include<bits/stdc++.h>
using namespace std;
struct node{
int val,num;
} tt[26];
int cnt[26];
signed main() {
int t;
cin>>t;
while(t--) {
memset(tt,0,sizeof(tt));
memset(cnt,0,sizeof(cnt));
int n;
string s;
cin>>n>>s;
for(int i=0;i<n;i++)
tt[s[i]-'a'].val++;
for(int i=0;i<26;i++)
tt[i].num=i;
sort(tt,tt+26,[](node p,node q) {
return p.val<q.val;
});
int minx=1e9,mini;
for(int i=1;i<=26;i++) {
if(n%i!=0) continue;
int x=n/i,sum=0,ans=0;
for(int j=25;j>=0;j--) {
if(tt[j].val>x) sum+=tt[j].val-x,ans+=tt[j].val-x;
else if(26-j<=i) ans+=x-tt[j].val;
else ans+=tt[j].val;
}
if(ans<minx) minx=ans,mini=i;
}
int x=n/mini;
for(int j=25;j>=0;j--) {
if(tt[j].val>x) cnt[tt[j].num]=x-tt[j].val;
else if(26-j<=mini) cnt[tt[j].num]=x-tt[j].val;
else cnt[tt[j].num]=-tt[j].val;
}
vector<int> add;
for(int j=0;j<26;j++)
while(cnt[j]>0) add.push_back(j),cnt[j]--;
for(int i=0;i<n;i++)
if(cnt[s[i]-'a']<0)
cnt[s[i]-'a']++,s[i]=add.back()+'a',add.pop_back();
cout<<minx/2<<endl<<s<<endl;
}
return 0;
}
D. Many Perfect Squares
题意：有一个不重复的正整数数组 \(a\)，你需要找到一个 \(x\)，使得每个元素加上 \(x\) 后出现尽可能多的完全平方数。
显然答案至少为 \(1\)。如果答案超过 \(2\)，可以枚举钦定两个变成完全平方数的数 \(p,q(p<q)\)，则有 \(a^2=p+x,b^2=q+x\)，得出 \(b^2-a^2=q-p\)，即 \((b+a)(b-a)=q-p\)。对 \(q-p\) 枚举因数，求得 \(a,b\)，进而得到 \(x\)，即可算出此时的完全平方数个数。
By IceYukino
int T,n,a[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int mx=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
int del=a[j]-a[i];
for(int k=1;k<=sqrt(del);k++){
if(del%k!=0) continue;
int c=k,b=del/k;
if((c+b)%2==1) continue;
int tmp=(c+b)/2,y=(c-b)/2;
if(tmp*tmp>=a[j]&&y*y>=a[i]&&tmp*tmp-a[j]==y*y-a[i]){
int x=tmp*tmp-a[j],sum=0;
for(int l=1;l<=n;l++){
int u=a[l]+x;
int oo=sqrt(u);
if(oo*oo==u) sum++;
}
mx=max(mx,sum);
}
}
}
cout<<mx<<endl;
}
return 0;
}
有一个优化的技巧，当找到一个确定的 \(x\) 时，不立刻计算数量更新答案，而是存起来，到最后去重后再计算。由于同一个 \(x\) 可能会被多对不同的元素、因数找到，所以优化非常显著。
By noimi
int main() {
TEST {
INT(n);
VEC(ll, a, n);
vl cand;
rep(i, n) rep(j, i + 1, n) {
ll d = a[j] - a[i];
fore(l, divisor(d)) {
ll r = d / l;
if(l > r) continue;
if((l + r) & 1) continue;
ll x = (r - l) / 2, y = (r + l) / 2;
// dump(l, r, x, y, d);
cand.eb(x * x - a[i]);
}
}
ll ans = 1;
// rep(i, 0, 100) cand.eb(i);
fore(e, cand) {
if(e < 0) continue;
int now = 0;
fore(x, a) {
ll t = x + e;
ll s = sqrtl(t);
if(s * s == t) now++;
}
// if(now == 2) dump(e);
chmax(ans, now);
}
OUT(ans);
}
}
枚举因数的过程同样可以通过分解质因数，用 DFS 合并来实现。首先存下每个质因数以及次数，DFS 合并时依此搜索每个质因数，枚举该质因数选几次，进入下一个质因数搜索。由于一个质因数的次数不同，因数就不同，所以一定不重不漏。
By 18Michael
inline void init()
{
for(int i=2;i<=Mx;++i)
{
if(!u[i])p[++p_t]=i;
for(int j=1;j<=p_t && p[j]*i<=Mx;++j)
{
u[p[j]*i]=1;
if(!(i%p[j]))break;
}
}
//printf("%d\n",p_t);
}
inline void solve(int x)
{
//printf(" solve %d\n",x);
int w=Z/x;
if((x^w)&1)return ;
/*a+b=w
b-a=x*/
LL A=(w-x)/2,X=A*A-tmp,y,z;
if(X<0)return ;
res=0;
for(int i=1;i<=n;++i)
{
y=X+a[i];
z=sqrt(y);
res+=(z*z==y);
}
//printf(" X:%lld res:%d\n",X,res);
ans=max(ans,res);
}
inline void dfs(int x,int y)
{
//printf(" dfs %d %d\n",x,y);
if(y>Z/y)return ;
if(x>t)return solve(y);
for(int j=0;j<=num[x];++j)
{
dfs(x+1,y);
y*=val[x];
}
}
inline void calc(int x,int y)
{
//printf("calc %d %d\n",x,y);
Z=a[y]-a[x];
int z=Z;
tmp=a[x],t=0;
for(int i=1;i<=p_t && p[i]*p[i]<=z;++i)if(!(z%p[i]))
{
val[++t]=p[i],num[t]=0;
for(;!(z%p[i]);z/=p[i])++num[t];
}
//printf("t:%d\n",t);
if(z>1)val[++t]=z,num[t]=1;
//printf("t:%d\n",t);
//for(int i=1;i<=t;++i)printf("(%d,%d)",val[i],num[i]);
//puts("");
dfs(1,1);
}
int main()
{
init(),read(Test_num);
while(Test_num--)
{
read(n),ans=1;
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)calc(i,j);
printf("%d\n",ans);
}
return 0;
}
E. Rectangle Shrinking
题意：在一个 \(2\times 10^9\) 的网格中，放置了 \(n\) 个矩形。对于每个矩形，你可以删掉也可以用一个子矩形代替。要求最后不能有矩形重叠，且面积尽可能大。
做法一
一个简单的猜测为，最终面积即为面积并，考虑如何构造。我们采用在线添加的方式，每次添加一个新矩形时保持矩面积为矩形面积并且不重叠。矩形用三个 set 动态维护，分别表示跨两行、只第一行和只第二行。这样 set 内只需要存矩形的左右边界和标号。
考虑添加的矩形有哪些情况：如果有被新矩形覆盖的，直接删掉；如果新矩形被某个旧矩形覆盖，直接不考虑新矩形。否则，情况一定只有矩形交而不存在矩形覆盖。具体实现上，对新矩形的行数分类讨论：
假设新矩形为一行，先处理与一行矩形的冲突：新覆盖旧则删掉，旧覆盖新则跳过，出现相交则把新矩形缩短到不相交。结束后，如果新矩形被缩到没有了（\(l>r\)），同样直接跳过。接下来处理与两行矩形的冲突：旧覆盖新同样跳过，但新不能完全覆盖旧（行数不够）。如果新在区间上覆盖了旧（即覆盖了旧的其中一行），则将旧的被覆盖的一行删掉，两行矩形改为一行矩形。如果新和旧只相交不包含，则将新矩形缩短到不相交即可。
假设新矩形为两行，先处理与两行矩形的冲突，与1-1冲突相同。接着处理与一行矩形的冲突：新覆盖旧则删掉，旧覆盖新的一整行时，将新矩形改为一行矩形，转到一行矩形处理方式。如果只相交不包含，则将旧的一行矩形缩短到不相交。
By cxm1024
#include<bits/stdc++.h>
using namespace std;
struct node {
mutable int l,r,num;
bool operator<(const node &o) const {
return r<o.r;
}
};
struct vv {
int u,l,d,r;
} ans[200010];
signed main() {
int t;
cin>>t;
while(t--) {
set<node> s[3];
int n;
cin>>n;
for(int i=1;i<=n;i++)
ans[i]={0,0,0,0};
for(int i=1;i<=n;i++) {
int u,l,d,r;
cin>>u>>l>>d>>r;
if(u==d) {
auto tmp=s[u].lower_bound({l,l,0});
bool flag=1;
while(tmp!=s[u].end()) {
if(tmp->l<=l&&tmp->r>=r) {
flag=0;
break;
}
if(tmp->l>=l&&tmp->r<=r)
tmp=s[u].erase(tmp);
else if(tmp->l>r) break;
else if(tmp->l<l) l=tmp->r+1,tmp++;
else if(tmp->r>r) r=tmp->l-1,tmp++;
}
if(l>r||flag==0) continue;
auto tt=s[0].lower_bound({l,l,0});
while(tt!=s[0].end()) {
if(tt->l<=l&&tt->r>=r) {
flag=0;
break;
}
if(tt->l>=l&&tt->r<=r) {
s[3-u].insert({tt->l,tt->r,tt->num});
tt=s[0].erase(tt);
}
else if(tt->l>r) break;
else if(tt->l<l) l=tt->r+1,tt++;
else if(tt->r>r) r=tt->l-1,tt++;
}
if(l>r||flag==0) continue;
s[u].insert({l,r,i});
}
else {
auto tmp=s[0].lower_bound({l,l,0});
bool flag=1;
while(tmp!=s[0].end()) {
if(tmp->l<=l&&tmp->r>=r) {
flag=0;
break;
}
if(tmp->l>=l&&tmp->r<=r)
tmp=s[0].erase(tmp);
else if(tmp->l>r) break;
else if(tmp->l<l) l=tmp->r+1,tmp++;
else if(tmp->r>r) r=tmp->l-1,tmp++;
}
if(l>r||flag==0) continue;
for(int x=1;x<=2;x++) {
if(u==d) {
auto tt=s[u].lower_bound({l,l,0});
bool flg=1;
while(tt!=s[u].end()) {
if(tt->l<=l&&tt->r>=r) {
flg=0;
break;
}
if(tt->l>=l&&tt->r<=r)
tt=s[u].erase(tt);
else if(tt->l>r) break;
else if(tt->l<l) l=tt->r+1,tt++;
else if(tt->r>r) r=tt->l-1,tt++;
}
if(r<l||flg==0) flag=0;
continue;
}
auto tt=s[x].lower_bound({l,l,0});
while(tt!=s[x].end()) {
if(tt->l<=l&&tt->r>=r) {
u=d=3-x;
break;
}
if(tt->l>=l&&tt->r<=r)
tt=s[x].erase(tt);
else if(tt->l>r) break;
else if(tt->l<l) {
int ll=tt->l,rr=l-1,num=tt->num;
tt=s[x].erase(tt);
if(rr>=ll) {
s[x].insert({ll,rr,num});
tt=s[x].upper_bound({ll,rr,num});
}
}
else if(tt->r>r) {
tt->l=r+1;
if(tt->l>tt->r) tt=s[x].erase(tt);
else tt++;
}
}
}
if(l<=r&&flag) {
if(u==d) s[u].insert({l,r,i});
else s[0].insert({l,r,i});
}
}
}
int tot=0;
for(auto [l,r,num]:s[0])
ans[num]={1,l,2,r},tot+=(r-l+1)*2;
for(auto [l,r,num]:s[1])
ans[num]={1,l,1,r},tot+=r-l+1;
for(auto [l,r,num]:s[2])
ans[num]={2,l,2,r},tot+=r-l+1;
cout<<tot<<endl;
for(int i=1;i<=n;i++)
cout<<ans[i].u<<" "<<ans[i].l<<" "<<ans[i].d<<" "<<ans[i].r<<endl;
}
return 0;
}
做法二
将矩形离线下来，按左端点排序，依次添加每个矩形，同时维护两行分别能到达的最右端点。由于添加一个矩形时，之前的矩形左端点都不超过当前矩形的左端点，所以只要最右端点超过当前矩形的右端点，则一定被包含。如果当前矩形的某一整行都被包含，则删掉该行，删空则跳过本矩形；如果当前矩形的左端点比两行最优端点的较小值还要小，则改为较小值 \(+1\)，这样，新矩形和原来的图形最多有一行重叠，将重叠的那一行的旧矩形缩短即可。
By KrK
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> ii;
const int Maxn = 200005;
struct rec {
int u, l, d, r;
};
int T;
int n;
rec R[Maxn];
int seq[Maxn];
ii reach[2];
bool Less(const int &a, const int &b)
{
return R[a].l < R[b].l;
}
int main()
{
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d %d %d", &R[i].u, &R[i].l, &R[i].d, &R[i].r);
R[i].u--; R[i].d--;
seq[i] = i;
}
sort(seq, seq + n, Less);
reach[0] = reach[1] = ii(0, -1);
for (int z = 0; z < n; z++) {
int ind = seq[z];
int mn = min(reach[0].first, reach[1].first);
R[ind].l = max(R[ind].l, mn + 1);
if (R[ind].l > R[ind].r) continue;
if (reach[R[ind].u].first >= R[ind].r)
R[ind].u++;
if (R[ind].u > R[ind].d) continue;
if (reach[R[ind].d].first >= R[ind].r)
R[ind].d--;
if (R[ind].u > R[ind].d) continue;
for (int h = R[ind].u; h <= R[ind].d; h++) {
if (reach[h].first >= R[ind].l)
R[reach[h].second].r = R[ind].l - 1;
reach[h] = ii(R[ind].r, ind);
}
}
int res = 0;
for (int i = 0; i < n; i++)
if (R[i].u > R[i].d || R[i].l > R[i].r) {
R[i].u = R[i].d = -1;
R[i].l = R[i].r = 0;
} else res += (R[i].d - R[i].u + 1) * (R[i].r - R[i].l + 1);
printf("%d\n", res);
for (int z = 0; z < n; z++)
printf("%d %d %d %d\n", R[z].u + 1, R[z].l, R[z].d + 1, R[z].r);
}
return 0;
}
做法三
我们发现，一行和一行的冲突非常容易计算，两行和两行的冲突和很容易算，复杂的是一行和两行的部分，有较多分类讨论。于是考虑将第三种转化为第一种。
首先同样将所有矩形分成三类，每一类内部可以很方便地处理到不重叠。然后将两行的矩形拆成第一行的一个矩形和第二行的一个矩形，重新处理新的第一行和新的第二行。由于之前每类内部都处理完了，新第一行和第二行的冲突全部为一行矩形和“原两行矩形”的冲突。如果一个包含了另一个，则直接将被包含的删掉：如果删掉的为原两行矩形，则等价于把两行矩形缩成一行矩形。否则则为相交且不包含，由于原两行矩形不方便缩短（需要考虑另一行），所以我们要求让原一行矩形缩短即可。
这种做法虽然在代码实现上较做法二稍长，但分类讨论极少，不容易写错。
By orzdevinwang
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
using namespace std;
const int N = 1e6 + 7;
int n, u[N], d[N], l[N], r[N];
bool vis[N];
vector < int > S[3];
void solve(vi &a, int rp = -1) {
sort(a.begin(), a.end(), [&] (int x, int y) {
return r[x] == r[y] ? l[x] > l[y] : r[x] < r[y];
});
vi b;
for(auto x : a) {
while(sz(b) && l[b.back()] >= l[x]) {
if(rp == -1) vis[b.back()] = false;
else if(rp == 0) ++u[b.back()];
else assert(rp == 1), --d[b.back()];
b.pop_back();
}
if(sz(b) && r[b.back()] >= l[x]) {
int y = b.back();
int lenx = d[x] - u[x] + 1;
int leny = d[y] - u[y] + 1;
if(leny <= lenx) r[y] = l[x] - 1;
else l[x] = r[y] + 1;
}
b.emplace_back(x);
}
a = b;
}
void Main() {
cin >> n;
S[0].clear();
S[1].clear();
S[2].clear();
L(i, 1, n) {
cin >> u[i] >> l[i] >> d[i] >> r[i];
vis[i] = true;
int op = -1;
if(u[i] == 1 && d[i] == 1) op = 0;
if(u[i] == 2 && d[i] == 2) op = 1;
if(u[i] == 1 && d[i] == 2) op = 2;
assert(op != -1);
S[op].emplace_back(i);
}
L(i, 0, 2) solve(S[i]);
for(auto u : S[2]) L(i, 0, 1) S[i].emplace_back(u);
L(i, 0, 1) solve(S[i], i);
int sumsz = 0;
L(i, 1, n) if(vis[i]) {
int siz = (d[i] - u[i] + 1) * (r[i] - l[i] + 1);
if(siz < 0) {
cout << "jingya\n";
assert(false);
}
if(!siz) vis[i] = false;
sumsz += siz;
}
cout << sumsz << '\n';
L(i, 1, n)
if(vis[i]) cout << u[i] << ' ' << l[i] << ' ' << d[i] << ' ' << r[i] << '\n';
else cout << 0 << ' ' << 0 << ' ' << 0 << ' ' << 0 << '\n';
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--) Main();
return 0;
}
做法四
思路与做法三类似，但实现上更为巧妙。
考虑开两个 set 分别维护第一行的矩形和第二行的矩形。实现一个“插入矩形”函数，仅支持插入一个一行的矩形，且产生冲突时优先缩短新矩形而让旧矩形不变（包含则正常删除）。这可以用 set 很轻松地实现。
与做法三相同，在两行矩形与一行矩形产生冲突时，应优先更改一行矩形，对应在这里，则为先插入所有两行矩形再插入所有一行矩形。对于两行矩形，只需要将其拆成两个一行矩形插入，该插入函数自然会正确处理冲突。然后依次插入一行矩形即可。统计答案时要注意两行矩形如果有一行被包含、删除了，则改为一行矩形输出。
By yuto1115
template<class T>
class range_set {
using iterator = typename set<tuple<T, T, int>>::iterator;
set<tuple<T, T, int>> st;
// return the least range which intersects with [x, inf)
iterator least_intersecting_range(T x) {
auto it = st.lower_bound({x, x, -1});
if (it == st.begin() or ::get<1>(*prev(it)) <= x) return it;
return prev(it);
}
public:
range_set() {}
set<tuple<T, T, int>> get() { return st; }
void insert(T l, T r, int id) {
assert(l < r);
auto it = least_intersecting_range(l);
if (it != st.end() and ::get < 0 > (*it) < l) {
auto [nl, nr, _] = *it;
if (nr >= r) return;
l = nr;
++it;
}
while (it != st.end() and ::get < 1 > (*it) <= r) {
it = st.erase(it);
}
if (it != st.end() and ::get < 0 > (*it) < r) {
auto [nl, nr, _] = *it;
r = nl;
}
assert(l <= r);
if (l == r) return;
st.insert({l, r, id});
}
template<class U>
friend ostream &operator<<(ostream &, const range_set<U> &);
};
template<class T>
ostream &operator<<(ostream &os, const range_set<T> &st) { return os << st.st; }
void solve() {
INT(n);
vi u(n), l(n), d(n), r(n);
rep(i, n) scan(u[i], l[i], d[i], r[i]);
vector<range_set<int>> st(2);
rep(i, n) {
if (u[i] == 1 and d[i] == 2) {
st[0].insert(l[i], r[i] + 1, i);
}
}
st[1] = st[0];
rep(i, n) {
if (u[i] == 1 and d[i] == 1) {
st[0].insert(l[i], r[i] + 1, i);
}
}
rep(i, n) {
if (u[i] == 2 and d[i] == 2) {
st[1].insert(l[i], r[i] + 1, i);
}
}
vi nu(n, 3), nl(n), nd(n), nr(n);
int ans = 0;
for (auto [L, R, i]: st[0].get()) {
chmin(nu[i], 1);
chmax(nd[i], 1);
ans += R - L;
nl[i] = L;
nr[i] = R - 1;
}
for (auto [L, R, i]: st[1].get()) {
chmin(nu[i], 2);
chmax(nd[i], 2);
ans += R - L;
nl[i] = L;
nr[i] = R - 1;
}
print(ans);
rep(i, n) {
if (nu[i] == 3) nu[i] = 0;
print(nu[i], nl[i], nd[i], nr[i]);
}
}
int main() {
int t;
cin >> t;
rep(i, t) solve();
}