D - Beautiful Sequence (贪心)
直接莽真的好晕啊,,还是应该想清楚再莽(误)。
要使每一个数字临近相差等于1,0只能和1相邻,3只能和2相邻
也就是一连串010101或者101010,一连串232323或者323232,
这两种串要能连在一起就只有01和23 可以,两边最多接一个1,一个2.
int main() { fast; int a,b,c,d; cin >> a >> b >> c >> d; if(a>b) { if(a==b+1 && c==0 && d==0) { cout << "YES" << endl; for(int i=0;i<b;i++) cout << "0 1 "; cout << 0 << endl; } else cout << "NO" << endl; return 0; } if(d>c) { if(d==c+1 && a==0 && b==0) { cout << "YES" << endl; for(int i=0;i<c;i++) cout << "3 2 "; cout << 3 << endl; } else cout << "NO" << endl; return 0; } b-=a; c-=d; if(abs(b-c)>1) cout << "NO" << endl; else { cout << "YES" << endl; if(b==c+1) cout << "1 "; for(int i=0;i<a;i++) cout << "0 1 "; for (int i=0;i<b && i<c;i++) cout << "2 1 "; for(int i=0;i<d;i++) cout << "2 3 "; if(c==b+1) cout << "2 "; cout << endl; } return 0; }
E. Beautiful Mirrors(概率DP+除法驱魔--费马小定理与快速幂)
概率DP+一个神奇的费马小定理,转换完🌶
//DP[i]=pi*(DP[i-1]+1)+(1-pi)*(DP[i-1]+DP[i]+1) //化简DP[i]=(DP[i-1]+1)/pi const int MOD = 998244353; ll arr[MAXN],dp[MAXN]; ll q_pow(ll x,ll y) { ll res=1; while(y) { if(y&1) res=res*x%MOD; x=x*x%MOD; y>>=1; } return res; } int main() { fast; int n;cin >> n; dp[0]=1; for(int i=1;i<=n;i++) { cin >> arr[i]; dp[i]=((dp[i-1]*100)%MOD*q_pow(arr[i],MOD-2))%MOD+1; } cout << dp[n]-1 << endl; return 0; }