本來懶得寫了，不過第一次AK還是記錄一下吧

A - ReLU

ABC的簽到題就是友好

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; int main() {IO;int T=1;//cin>>T;while(T--){int x;cin>>x;cout<<max(x,0)<<'\n';}return 0; }

B - Billiards

數學題

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; int main() {IO;int T=1;//cin>>T;while(T--){double x,y,a,b;cin>>x>>y>>a>>b;double res=x+(y/(y+b))*(a-x);printf("%.8lf\n",res);}return 0; }

C - Travel

由于n很小，直接暴力復雜度$(n?1)!$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=10;int a[N]; int d[N][N]; int main() {IO;int T=1;//cin>>T;while(T--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>d[i][j];for(int i=1;i<=n;i++) a[i]=i;ll res=0;do{if(a[1]!=1) break;//保證從1開始int now=0;for(int i=1;i<n;i++) now+=d[a[i]][a[i+1]];now+=d[a[n]][a[1]]; if(now==m) res++;}while(next_permutation(a+1,a+1+n));cout<<res<<'\n';}return 0; }

D - Water Heater

差分，注意時間為0也是一個時刻（wa了2發

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=200010; ll d[N]; int main() {IO;int T=1;//cin>>T;while(T--){int n,w;cin>>n>>w;for(int i=1;i<=n;i++){int a,b;ll c;cin>>a>>b>>c;d[a]+=c;d[b]-=c;}for(int i=1;i<=200000;i++) d[i]+=d[i-1];bool ok=1;for(int i=0;i<=200000;i++)if(d[i]>w) ok=0;if(ok) cout<<"Yes\n";else cout<<"No\n";}return 0; }

E - Queen on Grid

這題寫了很長時間（由于沒寫暴力
可以記錄一下三個方向的方案數和即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=2010; const ll mod=1e9+7; int n,m; char g[N][N]; ll f[N][N]; ll cnt[3][N][N]; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>g[i]+1;f[1][1]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(g[i][j]=='#') {for(int k=0;k<3;k++)cnt[k][i][j]=0;continue;}// for(int k=1;k<i;k++) // {// if(g[i-k][j]!='#') // f[i][j]=(f[i][j]+f[i-k][j])%mod;// else break;// }// for(int k=1;k<j;k++)// {// if(g[i][j-k]!='#') // f[i][j]=(f[i][j]+f[i][j-k])%mod; // else // break;// }// for(int k=1;k<min(i,j);k++)// {// if(g[i-k][j-k]!='#') // f[i][j]=(f[i][j]+f[i-k][j-k])%mod; // else // break;// }f[i][j]=(f[i][j]+cnt[0][i-1][j])%mod;f[i][j]=(f[i][j]+cnt[1][i][j-1])%mod;f[i][j]=(f[i][j]+cnt[2][i-1][j-1])%mod;cnt[0][i][j]=(cnt[0][i-1][j]+f[i][j])%mod;cnt[1][i][j]=(cnt[1][i][j-1]+f[i][j])%mod;cnt[2][i][j]=(cnt[2][i-1][j-1]+f[i][j])%mod;}cout<<f[n][m]<<' ';}return 0; }

還是寫一下暴力思路會清晰一些

F - Confluence

今天剛好復習了一下線段樹合并，結果這題就可以用線段樹合并搞（好幸運

每個人開一個動態開點值域線段樹，值域維護班級號，用并查集維護連通性，合并并查集的時候合并一下線段樹即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=200010; const ll mod=1e9+7; int p[N]; int n,q; int c[N]; int find(int x) {return x==p[x]?x:p[x]=find(p[x]); } struct node {int l,r;int sz; }tree[40*N]; int root[N],cnt; void insert(int &u,int l,int r,int x) {if(!u) u=++cnt;tree[u].sz++;if(l==r) return;int mid=l+r>>1;if(x<=mid) insert(tree[u].l,l,mid,x);else insert(tree[u].r,mid+1,r,x); } int merge(int x,int y) {if(!x||!y) return x+y;tree[x].sz+=tree[y].sz;tree[x].l=merge(tree[x].l,tree[y].l);tree[x].r=merge(tree[x].r,tree[y].r);return x;} int query(int u,int l,int r,int pos) {if(l==r) return tree[u].sz;int mid=l+r>>1;if(pos<=mid) return query(tree[u].l,l,mid,pos);else return query(tree[u].r,mid+1,r,pos); } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>q;for(int i=1;i<=n;i++) {cin>>c[i];insert(root[i],1,n,c[i]);}for(int i=1;i<=n;i++) p[i]=i;while(q--){int op,x,y;cin>>op>>x>>y;if(op==1){int px=find(x),py=find(y);if(px!=py){merge(root[px],root[py]);p[py]=px;}}else cout<<query(root[find(x)],1,n,y)<<'\n';} }return 0; }

暴力數據結構維護，第一次感受到學的數據結構有用！

要加油哦~

總結

以上是生活随笔為你收集整理的AtCoder Beginner Contest 183 总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。