AtCoder Beginner Contest 410 （A - F）

A - G1

点击查看代码

#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,k;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}cin>>k;int ans=0;for(int i=1;i<=n;i++){if(k<=a[i]) ans++;}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

B - Reverse Proxy

操作一直接翻进去，操作二每次暴力的找到最小的位置即可

点击查看代码

#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,q;cin>>n>>q;vector<int> a(n+1);vector<int> ans(q+1);for(int i=1;i<=q;i++){int x;cin>>x;if(x!=0){a[x]++;ans[i]=x;}else{int mn=inf,idx=-1;for(int j=1;j<=n;j++){if(a[j]<mn){mn=a[j];idx=j;}}a[idx]++;ans[i]=idx;}}for(int i=1;i<=q;i++){cout<<ans[i]<<" ";}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

C - Rotatable Array

可以每次 \(O(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,q;cin>>n>>q;vector<int> a(n);iota(a.begin(),a.end(),1);int now=0;while(q--){int op,p,x;cin>>op>>p;if(op==1){p--;cin>>x;a[(p+now)%n]=x;}else if(op==2){p--;cout<<a[(p+now)%n]<<endl;}else{now+=p;now%=n;}}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

D - XOR Shortest Walk

注意到 \(n\) 和值域都很小，所以可以直接 DP

设 \(f[i] [j]\) 表示走到点 \(i\) 且当前路径异或和为 \(j\) 的路径是否存在

状态转移可以直接枚举 \(i\) 的所有相邻节点

点击查看代码

#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,m;cin>>n>>m;vector<vector<pii>> g(n+1);vector<vector<int>> f(n+1,vector<int>(1025));while(m--){int a,b,w;cin>>a>>b>>w;g[a].push_back({b,w});}queue<pii> q;q.push({1,0});f[1][0]=1;while(q.size()){auto [u,now]=q.front();q.pop();for(auto [v,w]:g[u]){if(!f[v][w^now]){f[v][w^now]=1;q.push({v,w^now});}}}for(int i=0;i<1024;i++){if(f[n][i]){cout<<i;return;}}cout<<-1;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

E - Battles in a Row

设 \(f[i] [j]\) 表示花费 \(i\) 的生命值和 \(j\) 的魔法值最远可以走到哪

假设 \(f[i] [j]~=~k\)，则转移时可以尝试花费生命值或魔法值转移到 \(k+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,h,m;cin>>n>>h>>m;vector<pii> a(n+1);for(int i=1;i<=n;i++){int x,y;cin>>x>>y;a[i]={x,y};}vector<vector<int>> f(h+1,vector<int>(m+1,-inf));f[0][0]=0;int ans=0;for(int i=0;i<=h;i++){for(int j=0;j<=m;j++){if(f[i][j]<0 || f[i][j]==n) continue;int nxt=f[i][j]+1;auto [nxth,nxtm]=a[nxt];if(i+nxth<=h){f[i+nxth][j]=max(nxt,f[i+nxth][j]);ans=max(ans,f[i+nxth][j]);}if(j+nxtm<=m){f[i][j+nxtm]=max(nxt,f[i][j+nxtm]);ans=max(ans,f[i][j+nxtm]);}}}cout<<ans<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

F - Balanced Rectangles

第一步肯定是转换为 \(0,1\) 矩阵

暴力枚举复杂度显然是 \(O(H*W*H*W)\) 的

可以每次枚举矩形的上下界，固定上下界 \(up,down\) 后，问题就变成了，在这个一维的图形中，有多少 \(l,r\) 满足区间和为 \(0\)

而这一步可以用 \(map\) 或数组记录前缀和出现的次数，从而 \(O(W)\) 的计算 （\(map\) 复杂度过高；又因为会出现负数，所以数组维护需要加一个偏移量）

这样最后的复杂度是 \(O(H*H*W)\)，但可能存在 \(H=3e5,~W=1\) 的情况

所以当 \(H>W\) 时，将矩阵旋转 \(90\) 度，交换 \(H,W\) 即可。\(min(H,W)<=\sqrt{H*W}\)，所以复杂度是 \(O(H*W*\sqrt{H*W})\)

点击查看代码

#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;const int N=3e5;
int cnt[1000000];void solve(){int n,m;cin>>n>>m;//n*n*mvector<vector<int>> g(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char ch;cin>>ch;g[i][j]=(ch=='#'?1:-1);}}if(n>m){vector<vector<int>> t(m+1,vector<int>(n+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){t[m-j+1][i]=g[i][j];}}g=t;swap(n,m);}// for(int i=1;i<=n;i++){//     for(int j=1;j<=m;j++){//         cout<<g[i][j]<<" ";//     }//     cout<<endl;// }int ans=0;for(int u=1;u<=n;u++){vector<int> sum(m+1);for(int d=u;d<=n;d++){for(int i=1;i<=m;i++){sum[i]+=g[d][i];}cnt[N]=1;vector<int> pre(m+1);for(int i=1;i<=m;i++){pre[i]=sum[i]+pre[i-1];ans+=cnt[pre[i]+N];cnt[pre[i]+N]++;}for(int i=1;i<=m;i++){cnt[pre[i]+N]--;}}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}