A. Absenteeism
这题是想的越多写的代码越少。
首先根据题目中的约束，可以弄出一堆矩形，直接线段树加扫描线就行。其实不算难写。
开始推性质，找简洁的做法。
求的区间为 \([x,y]\)，给定的区间为 \([l_i,r_i]\)。
如果不存在第四种限制，那么直接不用来了。
否则可以把所有这种限制转为 \(x\le\min r_i,y\ge\max l_i\)。
只考虑 \(x-y<k\)。
对于所有限制，显然被包含的没有用。删除后剩下的区间互不包含。
首先满足第一个限制，那么最理想的情况是 \(x=l_i-1,y=r_{i-1}+1\)。
如果 \(x\ge m-k\) 并且有区间覆盖了 \(x\)，需要把 \(x\) 再往前调。
最后一定是到了 \(m-k\) 或某个 \(l_j-1\) 处。\(y\) 同理。
再简单预处理就是标算做法，不过还可以继续推。
根据刚才的结论，\(x\) 的取值一定是 \(l_i-1\) 或 \(m-k\)。
-
\(2k\le m\)，若 \(x>m-k\or y<k\) 一定会被第四种情况的区间发现，因此不需要考虑情况 2/3/4，只需要满足不被包含。
-
\(2k>m\)
若 \(x\le m-k\and y\ge k\) 且不被包含，则仍是合法的。
首先考虑 \(x>m-k\) 时的取值：
对于第四种区间，由于要有交，且 \(x\) 不能被区间包含，有 \(x<\min l_i\or x\le m-k\)。
令 \(L=\min l_i-1\)，若 \(L\le m-k\) 则 \(x\) 最大取到 \(m-k\)。
否则考虑剩下的区间，满足 \(r_i<m-k\or l_i>k\)。
前者 \(x<m-k\)，不会影响。后者 \(x>k\)，则 \(x>L\)，已经非法。
\(y\) 的取值同理。
综上，只需要保证 \([x,y]\) 不被包含且 \(x\le\max(L-1,m-k)\and y\ge\min(R+1,k)\)。
可能的 \(x\) 取值也只有 \(O(n)\) 个。只需要排序后扫描一遍，时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
vector<array<int,2>> a;
int L=m,R=0,X=0,Y=k;
for(int l,r;n--;){
scanf("%d%d",&l,&r);
a.push_back({l,r});
a.push_back({max(l-1,0),m+1});
if(l<=k&&r>=m-k) L=min(L,l),R=max(R,r);
}
a.push_back({m-k,m+1});
if(!R) return puts("-1 -1"),0;
sort(a.begin(),a.end());
L=max(L-1,m-k);R=min(R+1,k);
auto upd=[&](int x,int y){
if(y-x<Y-X) X=x,Y=y;
};
for(auto&x:a)
if(x[1]<=m) R=max(R,x[1]+1);
else if(x[0]<=L) upd(x[0],R);
printf("%d %d\n",X,Y);
return 0;
}
C. Cyclically Shifted Maze
枚举一维的循环移位，另一维处理前后缀并查集，维护连通块数量，简单合并即可。复杂度 \(O(n^3\alpha(n))\)。
#include <bits/stdc++.h>
using namespace std;
const int N=200;
int n,m,cnt,bl[N],br[N],fa[N*N],fl[N][N],fr[N][N];
vector<array<int,2>> ans;
string s[N];
int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
void merge(int x,int y){
if((x=getf(x))==(y=getf(y))) return;
cnt--;
if(x>y) swap(x,y);
fa[y]=x;
}
void init(int*bn,int(&fn)[N][N]){
iota(fa,fa+n*m,0);cnt=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) if(s[j][i]=='.'){
cnt++;
if(i&&s[j][i-1]=='.') merge(j+n*i-n,j+n*i);
if(j&&s[j-1][i]=='.') merge(j+n*i-1,j+n*i);
}
bn[i]=cnt;
for(int j=0;j<n;j++) fn[i][j]=getf(j);
}
for(int i=0;i<n;i++) reverse(s[i].begin(),s[i].end());
}
void solve(int r){
init(bl,fl);init(br,fr);
if(cnt<2) ans.push_back({r,0});
for(int i=1;i<m;i++){
cnt=bl[i-1]+br[m-i-1];
for(int j=0;j<n;j++) fa[j]=fl[i-1][j],fa[j+n]=fr[m-i-1][j]+n;
for(int j=0;j<n;j++) if(s[j][0]=='.'&&s[j][m-1]=='.') merge(j,j+n);
if(cnt<2) ans.push_back({r,i});
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++) solve(i),rotate(s,s+1,s+n);
printf("%d\n",ans.size());
for(auto&x:ans) printf("%d %d\n",x[0],x[1]);
return 0;
}
H. Video Reviews - 2
倒着考虑，若 \(a_i<m\) 则不需要操作，直接 m--。
否则当 \(i=m\) 时必须操作，花费一次操作后 m--。
可以证明被操作的序列字典序是最小的，且此时是最优解。
空间开不下，存个逆元。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a,k,ans,ed[N],c[N],y[N],z[N],iv[N];
int inv(int x,const int mod){
int res=1,t=mod-2;
for(;t;x=1ll*x*x%mod,t>>=1)
if(t&1) res=1ll*res*x%mod;
return res;
}
int main(){
scanf("%d%d%d%d",&n,&m,&a,&k);
ed[0]=a;
for(int i=1,x;i<=k;i++){
scanf("%d%d%d%d",&c[i],&x,&y[i],&z[i]);
iv[i]=inv(x,z[i]);
for(int t=c[i];t--;) a=(1ll*a*x+y[i])%z[i];
ed[i]=a;
}
for(int i=k;i;i--){
a=ed[i];
for(int t=c[i];m&&t--;n--){
if(a<m) m--;
else if(n==m) ans++,m--;
a=1ll*(a-y[i]+z[i])*iv[i]%z[i];
}
}
if(ed[0]>=m&&m==1) ans++;
printf("%d\n",ans);
return 0;
}
I. Chess Tournament
希望对于每场对局 \((x,y)\) 都找到一个特征值，每轮都进行相同特征值的对局。
之后找到了一个：环上到 \(x,y\) 距离相同的点（不用最短距离）。不过需要保证 \(n\) 为奇数。
其实是偶数也没影响，把 \((x,n)\) 当成特征值为 \(x\) 的。
当 \(k=\frac{n}{2}\) 时，这样构造已经合法了。
发现按照这个顺序加入对于任意 \(k\) 都合法，因为任意连续 \(k\) 对不会有相同的数。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k;
scanf("%d%d",&n,&k);
vector<array<int,2>> v;
int m=n-1+(n%2),s=n*(n-1)/2;
for(int i=0;i<m;i++){
if(n%2==0) v.push_back({i,n-1});
for(int j=1;j<=m/2;j++) v.push_back({(i-j+m)%m,(i+j)%m});
}
printf("%d\n",(s+k-1)/k);
for(int i=0;i<s;i+=k){
printf("%d\n",min(s-i,k));
for(int j=i;j<s&&j<i+k;j++) printf("%d %d\n",v[j][0]+1,v[j][1]+1);
}
return 0;
}
K. Bloodseeker
首先让 \(h=\min(h,m)\)。
对于 \(h>t\) 的，在考虑到不需要一直打一个怪到底后，容易发现可以当成一个 \(h-t\) 的血包（在还剩 \(t\) 滴血时打这个怪）。
对于 \(h\le t\)，由 exchange argument 算一下发现按 \(h\) 从大到小排最优。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
bool solve(){
int n,m;
scanf("%d%d",&n,&m);
ll s=m;
vector<array<int,2>> a;
for(int t,h;n--;){
scanf("%d%d",&t,&h);
if((h=min(h,m))>t) s+=h-t;
else a.push_back({-h,t});
}
sort(a.begin(),a.end());
for(auto&x:a)
if(s<x[1]) return 0;
else s-=x[0]+x[1];
return 1;
}
int main(){
int t;
scanf("%d",&t);
while(t--) puts(solve()?"YES":"NO");
return 0;
}