B.RGB Coloring

綠色可以看作拿紅和藍都涂了，那么只需要滿足A*a + B*b = K && 0 ≤?a,b?≤ n，答案加上C(n,a)*C(n,b)

#include <bits/stdc++.h> typedef long long ll; const ll mod = 998244353; const int N = 300000 + 100; using namespace std; ll n,inv[N],fc[N],K,ans,A,B;; ll q_pow(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1LL;}return ans; } ll C(ll n,ll m) {return ((fc[n]*inv[n-m])%mod*inv[m])%mod; } int main() {scanf("%lld%lld%lld%lld",&n,&A,&B,&K);fc[0]=1;for(int i=1;i<=n;++i)fc[i]=(fc[i-1]*i)%mod;inv[n] = q_pow(fc[n],mod-2);for(ll i=n-1;i>=0;--i)inv[i]=(inv[i+1]*(i+1))%mod;for(ll a=0;a<=n;++a) {ll b = (K-A*a)/B;if(b<0||b>n)continue;if((K-A*a)%B)continue;ans += (C(n,a)*C(n,b))%mod;ans %= mod;}cout << ans <<'\n';return 0; }

C.Interval Game

貪心，盡量不斷走重復的路，左右來回每次盡量到最兩邊，先左后右，先右后左，取個最優解。

#include <bits/stdc++.h> typedef long long ll; using namespace std; struct nodel{int x,id;nodel(){}nodel(int a,int b){x=a;id=b;}bool operator < (const nodel a)const {return a.x > x;} }; struct noder{int x,id;noder(){}noder(int a,int b){x=a;id=b;}bool operator < (const noder a)const {return a.x < x;} }; priority_queue<nodel> ql,ql2; priority_queue<noder> qr,qr2; int n,out[100000+100]; ll ans1,ans2; int main() {scanf("%d",&n);for(int i=1;i<=n;++i) {int l,r;scanf("%d%d",&l,&r);ql.push(nodel(l,i));ql2.push(nodel(l,i));qr.push(noder(r,i));qr2.push(noder(r,i));}int now=0;for(int ti=1;ti<=n;++ti) {while(!ql.empty()&&out[ql.top().id])ql.pop();while(!qr.empty()&&out[qr.top().id])qr.pop();if(ti%2&&now < ql.top().x)ans1+=abs(now-ql.top().x),now=ql.top().x,out[ql.top().id]=1,ql.pop();else if(now > qr.top().x) ans1+=abs(now-qr.top().x),now=qr.top().x,out[qr.top().id]=1,qr.pop();}ans1 += abs(now);memset(out,0,sizeof(out));now=0;for(int ti=1;ti<=n;++ti) {while(!ql2.empty()&&out[ql2.top().id])ql2.pop();while(!qr2.empty()&&out[qr2.top().id])qr2.pop();if(ti%2==0&&now < ql2.top().x)ans2+=abs(now-ql2.top().x),now=ql2.top().x,out[ql2.top().id]=1,ql2.pop();else if(now > qr2.top().x) ans2+=abs(now-qr2.top().x),now=qr2.top().x,out[qr2.top().id]=1,qr2.pop();}ans2 += abs(now);cout << max(ans1,ans2) <<'\n';return 0; }

　　

轉載于:https://www.cnblogs.com/RRRR-wys/p/9131313.html

總結

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

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