AtCoder Beginner Contest 289 解题报告
\(\text{By DaiRuiChen007}\)
A. flip
逐位枚举反转即可
时间复杂度 \(\Theta(|s|)\)
#include<bits/stdc++.h>
using namespace std;
signed main() {
string s;
cin>>s;
int n=s.length();
for(int i=0;i<n;++i) s[i]='0'+((s[i]-'0')^1);
cout<<s<<"\n";
return 0;
}
B. V
枚举处理出每个分段再反转即可
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
int nxt[MAXN];
vector <int> ver[MAXN];
signed main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) nxt[i]=i;
for(int i=1;i<=m;++i) {
int u;
scanf("%d",&u);
nxt[u]=u+1;
}
for(int i=n;i>=1;--i) nxt[i]=nxt[nxt[i]],ver[nxt[i]].push_back(i);
for(int i=1;i<=n;++i) {
for(int j:ver[i]) printf("%d ",j);
}
puts("");
return 0;
}
C. Coverage
对 \(1\sim n\) 的元素状压然后 dp 解决
时间复杂度 \(\Theta(m2^n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=12;
int dp[MAXN][1<<MAXN],a[MAXN];
inline int bit(int x) { return 1<<x; }
signed main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int c;
scanf("%d",&c);
while(c--) {
int x;
scanf("%d",&x);
a[i]|=bit(x-1);
}
}
dp[0][0]=1;
for(int i=0;i<m;++i) {
for(int j=0;j<bit(n);++j) {
dp[i+1][j]+=dp[i][j];
dp[i+1][j|a[i+1]]+=dp[i][j];
}
}
printf("%d\n",dp[m][bit(n)-1]);
return 0;
}
D. Step Up Robot
dp 转移维护每个位置是否可达即可
时间复杂度 \(\Theta(nX)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
bool mark[MAXN],dp[MAXN];
int a[MAXN];
signed main() {
int n,m,x;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i) {
int u;
scanf("%d",&u);
mark[u]=true;
}
scanf("%d",&x);
dp[0]=true;
for(int i=0;i<x;++i) {
for(int j=1;j<=n;++j) {
if(i+a[j]>x||mark[i+a[j]]) continue;
dp[i+a[j]]|=dp[i];
}
}
puts(dp[x]?"Yes":"No");
return 0;
}
E. Swap Places
把两个人所在的位置 \((u,v)\) 看成一个状态整体做一遍 BFS 即可
时间复杂度 \(\Theta(n^2+mn)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001,INF=1e9;
int col[MAXN],dis[MAXN][MAXN];
vector <int> G[MAXN];
inline void solve() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
G[i].clear();
for(int j=1;j<=n;++j) dis[i][j]=INF;
}
for(int i=1;i<=n;++i) scanf("%d",&col[i]);
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
queue <pair<int,int> > q;
q.push(make_pair(1,n));
dis[1][n]=0;
while(!q.empty()) {
int u=q.front().first,v=q.front().second;
q.pop();
for(int x:G[u]) {
for(int y:G[v]) {
if(col[x]^col[y]&&(dis[x][y]>dis[u][v]+1)) {
dis[x][y]=dis[u][v]+1;
q.push(make_pair(x,y));
}
}
}
}
if(dis[n][1]==INF) dis[n][1]=-1;
printf("%d\n",dis[n][1]);
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
F. Teleporter Takahashi
一个显然的观察是 \((x,y)\) 关于 \((a,b)\) 对称后得到 \((x',y')=(2a-x,2b-y)\) 的操作不改变 \(x,y\) 的奇偶性，因此 \(s_x\equiv t_x\pmod2,s_y\equiv t_y\pmod 2\) 必然成立
注意到关于两个 \(x\) 相同的点对称不改变操作点的 \(x\) 值，因此可以对 \(x,y\) 分开考虑，由于 \(s_x-t_x,s_y-t_y\) 都是 \(2\) 的倍数，因此我们只需要构造单次移动步长为 \(2\) 的移动方法
注意到分别关于 \((a,c),(a+1,c)\) 对称即可向右移动 \(2\)，同理向上下左方向移动 \(2\) 步的操作也是显然的
注意特判 \(a=b\) 和 \(c=d\) 的情况
操作次数大约是 \(\frac 12(|s_x-t_x|+|s_y-t_y|)\) 的，可以通过本题
时间复杂度 \(\Theta(X+Y)\)，其中 \(X,Y\) 为横纵坐标值域
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sx,sy,tx,ty;
int a,b,c,d;
vector <int> X,Y;
int len=0;
inline void oper(int x,int y) {
X.push_back(x),Y.push_back(y);
++len;
sx=2*x-sx,sy=2*y-sy;
}
inline void Print() {
puts("Yes");
for(int i=0;i<len;++i) {
printf("%lld %lld\n",X[i],Y[i]);
}
exit(0);
}
inline void Quit() {
puts("No");
exit(0);
}
signed main() {
scanf("%lld%lld%lld%lld",&sx,&sy,&tx,&ty);
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(a==b&&c==d) {
if(sx==tx&&sy==ty) Print();
if(sx+tx==2*a&&sy+ty==2*c) {
oper(a,c);
Print();
}
Quit();
}
if(sx%2!=tx%2) {
puts("No");
return 0;
}
if(sy%2!=ty%2) {
puts("No");
return 0;
}
if(a==b&&sx!=tx&&sx+tx!=2*a) Quit();
if(c==d&&sy!=ty&&sy+ty!=2*c) Quit();
if(a==b&&sx!=tx) oper(a,c);
if(c==d&&sy!=ty) oper(a,c);
int gx=abs(sx-tx)/2,gy=abs(sy-ty)/2;
if(sx<tx) for(int i=1;i<=gx;++i) oper(a,c),oper(a+1,c);
else for(int i=1;i<=gx;++i) oper(a+1,c),oper(a,c);
if(sy<ty) for(int i=1;i<=gy;++i) oper(a,c),oper(a,c+1);
else for(int i=1;i<=gy;++i) oper(a,c+1),oper(a,c);
Print();
return 0;
}
G. Shopping in AtCoder store
先将所有顾客按 \(b\) 降序排序，显然能满足的顾客一定是一段连续的前缀，假设满足的顾客是 \(1\sim i\)，那么 \(p_j\le b_i+c_j\)，根据贪心显然令 \(p_j=b_i+c_j\)，因此我们的问题转化为对于所有 \(j\) 求 \(\max_{i=1}^n\{i\times (b_i+c_j)\}\)
注意到 \(i\times (b_i+c_j)=i\times c_j+i\times b_i\)，可以看成关于 \(c_j\) 的一次函数 \(y=i\times x+i\times b_i\)，那么我们只需要对所有 \(c_j\) 求 \(x=c_j\) 时的最大 \(y\) 值，直接用李超线段树维护即可
由于 \(c_j\) 值域较大，可以先对 \(c_1\sim c_n\) 排序，然后把函数改写为 \(f(x)=i\times c_x+i\times b_i\)，由于 \(c_1\sim c_n\) 有序，因此李超线段树需要的单调性依然满足，可以通过本题
时间复杂度 \(\Theta(m\log m+n\log n+m\log n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,MAXV=2e5+1;
int n,m,b[MAXN],c[MAXN];
struct line {
int k,b;
inline int f(int v) {
return k*c[v]+b;
}
line(int _k=0,int _b=0) { k=_k,b=_b; }
} a[MAXN];
class LCtree {
private:
int tree[MAXV<<2];
inline int left(int x) { return x<<1; }
inline int right(int x) { return x<<1|1; }
public:
inline void Modify(int id,int l=1,int r=m,int pos=1) {
int mid=(l+r)>>1;
if(a[id].f(mid)>a[tree[pos]].f(mid)) swap(tree[pos],id);
if(l==r) return ;
if(a[id].f(l)>a[tree[pos]].f(l)) Modify(id,l,mid,left(pos));
if(a[id].f(r)>a[tree[pos]].f(r)) Modify(id,mid+1,r,right(pos));
return ;
}
inline int Query(int x,int l=1,int r=m,int pos=1) {
int t=a[tree[pos]].f(x);
if(l==r) return t;
int mid=(l+r)>>1;
if(x<=mid) return max(t,Query(x,l,mid,left(pos)));
if(mid<x) return max(t,Query(x,mid+1,r,right(pos)));
}
} S;
int id[MAXN],ans[MAXN];
signed main() {
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&b[i]);
for(int i=1;i<=m;++i) scanf("%lld",&c[i]);
for(int i=1;i<=m;++i) id[i]=i;
sort(id+1,id+m+1,[&](int x,int y){ return c[x]<c[y]; });
sort(c+1,c+m+1);
sort(b+1,b+n+1,[&](int x,int y){ return x>y; });
for(int i=1;i<=n;++i) {
a[i]=line(i,i*b[i]);
S.Modify(i);
}
for(int i=1;i<=m;++i) {
ans[id[i]]=S.Query(i);
}
for(int i=1;i<=m;++i) printf("%lld ",ans[i]);
puts("");
return 0;
}
