A - Not

簽到題

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=100010; int main() {IO;int T=1;//cin>>T;while(T--){int x;cin>>x;cout<<1-x<<endl;}return 0; }

B - Product Max

簽到題

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=100010; int main() {IO;int T=1;//cin>>T;while(T--){ll a,b,c,d;cin>>a>>b>>c>>d;cout<<max(max(a*c,a*d),max(b*c,b*d))<<endl;}return 0; }

C - Ubiquity

正難則反，容斥原理
先只考慮滿足第一個情況的方案數(shù)：$10^n$
那么其中肯定有不滿足第二個情況和第三個情況的方案，我們只要減去這種情況即可。
滿足第一個條件，不滿足第二個條件的方案數(shù)是$9^n$
滿足第一個條件，不滿足第三個條件的方案數(shù)是$9^n$
滿足第一個條件，同時不滿足第二個條件和第三個條件的方案數(shù)是$8^n$
根據(jù)容斥原理，滿足第一個條件但是不滿足第二個條件或者第三個條件的方案數(shù)是$9^n+9^n?8^n$
因此答案是$10^n?(9^n+9^n?8^n)$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=100010; const ll mod=1e9+7; ll qmi(ll a,ll b) {ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res; } int main() {IO;int T=1;//cin>>T;while(T--){ll n;cin>>n;cout<<((qmi(10ll,n)-2*qmi(9ll,n)+qmi(8ll,n))%mod+mod)%mod<<'\n';}return 0; }

D - Redistribution

考試的時候老想著完全背包。。
$f[i]$表示用$3\dots i$這些數(shù)湊成和是$i$的方案數(shù)
轉(zhuǎn)移：考慮最后一個數(shù)用的是誰？
$f[i]=f[i?3]+f[i?4]+?+f[i?i]$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=2010; const ll mod=1e9+7; ll f[N]; int main() {IO;int T=1;//cin>>T;while(T--){int s;cin>>s;f[0]=1;for(int i=3;i<=s;i++)for(int j=3;j<=i;j++)f[i]=(f[i]+f[i-j])%mod;cout<<f[s]<<'\n';}return 0; }

E - Dist Max

考慮兩個點$(x_1,y_1)$和$(x_2,y_2)$的曼哈頓距離$|x_1?x_2|+|y_1?y_2|$其實還可以進一步簡化成$$max(|(x_1+y_1)?(x_2+y_2)|,|(x_1?y_1)?(x_2?y_2)|)$$
由此將問題降維，然后就很容易解了。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=200010; int d1[N],d2[N],n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;d1[i]=x+y;d2[i]=x-y;}sort(d1+1,d1+1+n);sort(d2+1,d2+1+n);cout<<max(d1[n]-d1[1],d2[n]-d2[1])<<'\n';}return 0; }

無意中看到一個知識，此題轉(zhuǎn)化更專業(yè)的叫法曼哈頓距離與切比雪夫距離的轉(zhuǎn)換

F - Contrast

結(jié)論：將 B 按降序排序后，B 中最多只會有一段 $B[l～r]$ 與 $A[l～r]$ 是相同的，且 $A[l～r]$ 和 $B[l～r]$ 中所有值都等于同一個數(shù)$val$，仔細想想便可得到此結(jié)論。
把這些相等的位置記下來，然后與其他的位置交換，此位置序還需滿足$a_i=val$，每找到一個位置就可以交換一次，如果位置不夠則不可能滿足題意。
還有一個判斷不滿足題意的方法即統(tǒng)計a[]和b[]每個數(shù)出現(xiàn)的次數(shù)cnta[]和cntb[]，對于每一個$i$滿足$cnt{a}_i+cnt{b}_i\le n$才可能構(gòu)造出一組解，否則不可能滿足題意。
口胡證明：對于a[]中的i需要b[]至少存在有cnta[i]個不等于i的數(shù)與之配對，即cnta[i]<=n-cntb[i]，證畢。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=200010; int a[N],b[N],n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];reverse(b+1,b+1+n);vector<int> p,q;int val=0,cnt=0;for(int i=1;i<=n;i++){if(a[i]!=b[i]) continue;cnt++;p.push_back(i);val=b[i];}for(int i=1;i<=n;i++){if(!cnt) break;if(a[i]==b[i]) continue;if(a[i]!=val&&b[i]!=val){cnt--;q.push_back(i);}}if(cnt) return cout<<"No\n",0;for(int i=0;i<q.size();i++) swap(b[p[i]],b[q[i]]);cout<<"Yes\n";for(int i=1;i<=n;i++) cout<<b[i]<<' ';cout<<'\n';}return 0; }

ABC現(xiàn)在看來以及沒有想象中那么難，自己現(xiàn)在都可以接受。
正式上課了，要加油哦~

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。