A - Number of Multiples

按照題目意思走就行

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #include<iostream> #include<algorithm> using namespace std; int l,r,d; int main() {IO;cin>>l>>r>>d;if(r<l) swap(l,r);int res=r/d-l/d;if(l%d==0) res++;cout<<res<<endl;return 0; }

B - An Odd Problem

這題比A還純模擬，按題目意思走

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #include<iostream> #include<algorithm> using namespace std; const int N=110; int a[N],n; int main() {IO;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int res=0;for(int i=1;i<=n;i++)if((i&1)&&(a[i]&1)) res++;cout<<res<<endl;return 0; }

C - XYZ Triplets

這題剛開始看錯數據范圍，結果RE了，然后又算錯時間復雜度又TLE了，我也太菜了吧

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int N=10010; const double eps=1e-6; int n,f[N]; double calc1(int x,int y,int n) {double delta=(x+y)*(x+y)-4*(x*x+y*y+x*y-n);if((x+y)*(x+y)<=4*(x*x+y*y+x*y-n)) return -1;return (sqrt(delta)-(x+y))/2.0; } int calc2(int x,int y,int n) {int delta=(x+y)*(x+y)-4*(x*x+y*y+x*y-n);if(delta<=0) return -2;return (sqrt(delta)-(x+y))/2; } int main() {IO;cin>>n;for(int k=1;k<=n;k++)for(int i=1;i<=k/i;i++)for(int j=1;j<=k/j;j++){double x=calc1(i,j,k);int y=calc2(i,j,k);if(x<eps) continue;if(abs(x-y)<eps) f[k]++;}for(int i=1;i<=n;i++) cout<<f[i]<<endl;return 0; }

又是只做了三題，真就是簽到戰士？

D - Anything Goes to Zero

這題考試時想要高精度，我發現要寫好幾個高精度就懶得看了。第二天一看發現快速冪取模可以避免高精度，然后在網上搜了搜題解，搞了一上午終于AC了。
對于原二進制串中1的個數可能又三種情況①大于1②等于1③等于0我們可以發現只要模第一次，那么這個數就會回到$int$范圍內，不妨設原二進制串中$1$的個數為$s$，那么，第一次的需要模的數只有兩種情況$s?1,s+1$，于是我們可以用快速冪預處理出原串模$s?1,s+1$的值，每當反轉一位就相當于加上或減去2的整次冪，然后就可以很容易知道答案。
對于①存在$s?1,s+1$，而對于②只存在模$s+1$的情況：如果模$0$那么說明該串全是0，那么答案自然直接是$0$，如果模$s+1$，那么肯定模的是$2$，如果最后一位不是$1$該串是偶數，操作一次就可以了，如果最后一位是$1$，那么該串是奇數，稍微那么該操作需要兩次。對于③也是只存在模$s+1$的情況，而且肯定是模$1$，分析可知只用操作一次就可。

#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=200010; int a[N],n; ll qmi(ll a,ll b,ll p) {ll res=1%p;a%=p;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res; } int calc(ll x)//計算二進制中1的個數 {int res=0;while(x){x-=x&-x;res++;}return res; } ll md(ll x,ll y)//取模函數，保證取模后是正數 {return (x%y+y)%y; } int main() {cin>>n;int s=0;for(int i=1;i<=n;i++){scanf("%1d",&a[i]);s+=a[i];}if(s>1){ll x=0,y=0;for(int i=1;i<=n;i++){if(a[i]==0) continue;x=md(x+qmi(2,n-i,s-1),s-1);//預處理原串模s-1和s+1的值y=md(y+qmi(2,n-i,s+1),s+1);}for(int i=1;i<=n;i++){ll ans=0;int cnt=1;if(a[i]==0) ans=md(y+qmi(2,n-i,s+1),s+1);else ans=md(x-qmi(2,n-i,s-1),s-1);while(ans){ans%=calc(ans);cnt++;}cout<<cnt<<endl;}}else if(s==0) for(int i=1;i<=n;i++) cout<<1<<endl;else{for(int i=1;i<=n;i++){if(a[i]==1) cout<<0<<endl;//該串唯一的一個1被反轉，串值變成0else{if(a[n]==1||i==n) cout<<2<<endl;//最后一位是1else cout<<1<<endl;}}}return 0; }

E - Camel Train

①貪心+小根堆

題中有兩種駱駝一種$l>=r$，那么該駱駝需要盡可能往前放，另一種駱駝$l<r$盡可能往后放，并且它們的最優解互不影響。因此我們可以分別考慮兩種駱駝，不管哪種駱駝我們先把答案加上小的數，然后就變成之前做過的一個題lyd老師的<<算法競賽進階指南>>中的超市那道題。
貪心：按照位置貪心

#include<iostream> #include<algorithm> #include<queue> #include<cstring> #define k first #define w second using namespace std; typedef pair<int,int> pii; typedef long long ll; const int N=200010; pii a[N],b[N]; int main() {int T;cin>>T;while(T--){int n,cnta=0,cntb=0;cin>>n;ll res=0;for(int i=0;i<n;i++){int k,l,r;cin>>k>>l>>r;if((k==0&&l>=r)||(k==n&&r>l)) {res+=min(l,r);continue;}if(l>=r) res+=r,a[cnta++]={k,l-r};else res+=l,b[cntb++]={n-k,r-l};}sort(a,a+cnta),sort(b,b+cntb);priority_queue<int,vector<int>,greater<int> >heap;for(int i=0;i<cnta;i++){heap.push(a[i].w);while(heap.size()>a[i].k) heap.pop();}while(heap.size()){res+=heap.top();heap.pop();}for(int i=0;i<cntb;i++){heap.push(b[i].w);while(heap.size()>b[i].k) heap.pop();}while(heap.size()){res+=heap.top();heap.pop();}cout<<res<<endl;}return 0; }

②貪心+并查集

貪心：按照權值從大到小排序，對于每個牛，排到恰好的位置上，如果恰好的位置上有牛，就往前找看看前面有沒有空位置。并查集維護1~pos離pos最近并且位置為空的序號

#include<iostream> #include<algorithm> #include<queue> #include<cstring> #define w first #define k second using namespace std; typedef pair<int,int> pii; typedef long long ll; const int N=200010; pii a[N],b[N]; int p[N]; int find(int x) {if(p[x]!=x) p[x]=find(p[x]);return p[x]; } int main() {int T;cin>>T;while(T--){int n,cnta=0,cntb=0;cin>>n;ll res=0;for(int i=1;i<=n;i++) p[i]=i;for(int i=0;i<n;i++){int k,l,r;cin>>k>>l>>r;if((k==0&&l>=r)||(k==n&&r>l)) {res+=min(l,r);continue;}if(l>=r) res+=r,a[cnta++]={l-r,k};else res+=l,b[cntb++]={r-l,n-k};}sort(a,a+cnta),sort(b,b+cntb);reverse(a,a+cnta),reverse(b,b+cntb);for(int i=0;i<cnta;i++){int pos=find(a[i].k);if(pos) p[pos]=pos-1,res+=a[i].w;}for(int i=1;i<=n;i++) p[i]=i;for(int i=0;i<cntb;i++){int pos=find(b[i].k);if(pos) p[pos]=pos-1,res+=b[i].w;}cout<<res<<endl;}return 0; }

總結

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

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