【LGR-179-Div.2】复旦勰码 3 月月赛 II & ZHYOI Round 4
\(T1\) luogu P10251 农场 \(100pts\)
-
注意到未注明给的是哪两个对角顶点。
- 赛时没注意到这一点，并因此吃了发罚时。
点击查看代码
int main() { ll n,x1,y1,x2,y2,xmax=-0x7f7f7f7f,xmin=0x7f7f7f7f,ymax=-0x7f7f7f7f,ymin=0x7f7f7f7f,i; cin>>n; for(i=1;i<=n;i++) { cin>>x1>>y1>>x2>>y2; xmax=max(xmax,max(x1,x2)); ymax=max(ymax,max(y1,y2)); xmin=min(xmin,min(x1,x2)); ymin=min(ymin,min(y1,y2)); } cout<<(xmax-xmin)*(ymax-ymin)<<endl; return 0; }
\(T2\) luogu P10252 线性变换 \(100pts\)
-
觉得比较像 luogu P3306 [SDOI2013] 随机数生成器 。
-
递推式为 \(x_{n}=ax_{n-1}-b\) 。
-
当 \(a=0\) 时，递推式转化为 \(x_{n}=-b\) ，则经过操作能得到的 \(x\) 的最小值为 \(\min(x_{1},-b)=-b\) 。
-
当 \(a \ne 0\) 时，
- 当 \(b=0\) 时，有 \(ax_{1} \ge a\) ，则经过操作能得到的 \(x\) 的最小值为 \(x_{1}\) 。
- 当 \(b \ne 0\) 时，
- 当 \(a=1\) 时，递推式转化为 \(\begin{aligned} x_{n} &=x_{n-1}-b \\ &=x_{n-2}-2b \\ &=x_{n-3}-3b \\ &= \dots \\ &=x_{1}-(n-1)b \end{aligned}\) 。则经过操作能得到的 \(x\) 的最小值为 \(x_{1} \bmod b-b\) 。
- 当 \(a \ne 1\) 时，有 \(\begin{aligned} x_{n+1}-x_{n}=ax_{n}-b-x_{n}=(a-1)x_{n}-b \end{aligned}\) ，其中 \((a-1)x_{n}-b\) 是呈指数级变化的，对于增长的直接特判即可，对于减少的直接暴力枚举即可。
点击查看代码
ll val(ll a,ll b,ll x) { return a*x-b; } int main() { ll t,x,a,b,i; cin>>t; for(i=1;i<=t;i++) { cin>>x>>a>>b; if(a==0) { cout<<-b<<endl; } else { if(b==0) { cout<<x<<endl; } else { if(a==1) { cout<<x%b-b<<endl; } else { while(x>=0&&val(a,b,x)<x) { x=val(a,b,x); } cout<<x<<endl; } } } } return 0; }
\(T3\) luogu P10253 说唱 \(25pts\)
- 部分分
-
\(25pts\) ：观察到 \(f(x)=\sum\limits_{i=0}^{\left\lfloor \log_{10}{x} \right\rfloor} \left\lfloor \dfrac{x}{10^i} \right\rfloor\) ，即若 \(f(x)=y\) ，则有 \(x \le y\) ，枚举即可。
点击查看代码
ll val(ll x) { ll n=log10(x)+1,sum=0,i; for(i=1;i<=n;i++) { sum+=x; x/=10; } return sum; } int main() { ll t,x,y,i,ans; cin>>t; for(i=1;i<=t;i++) { cin>>y; ans=-1; for(x=0;x<=y;x++) { if(val(x)==y) { if(ans==-1) { ans=x; } else { ans=-1; break; } } } cout<<ans<<endl; } return 0; }
-
- 正解
\(T4\) luogu P10254 口吃 \(10pts\)
- 部分分
-
\(10pts\) ：生成 \(1 \sim n\) 的全排列，计算其逆序对数求解。
点击查看代码
const ll p=998244353; ll a[1000],c[1000],d[1000]; struct node { ll dis,vis; }b[1000]; bool cmp(node x,node y) { return (x.dis==y.dis)?(x.vis<y.vis):(x.dis<y.dis); } ll lowbit(ll x) { return (x&(-x)); } ll getsum(ll x) { ll ans=0; for(ll i=x;i>=1;i-=lowbit(i)) { ans+=c[i]; } return ans; } void add(ll n,ll x,ll key) { for(ll i=x;i<=n;i+=lowbit(i)) { c[i]+=key; } } int main() { ll n,k,sum=0,ans=0,i; cin>>n>>k; for(i=1;i<=n;i++) { a[i]=i; } do { sum=0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { b[i].dis=a[i]; b[i].vis=i; } sort(b+1,b+1+n,cmp); for(i=1;i<=n;i++) { d[b[i].vis]=i; } for(i=1;i<=n;i++) { add(n,d[i],1); sum+=(i-getsum(d[i])); } if(sum==k) { for(i=1;i<=n;i++) { ans=(ans+i*a[i]%p)%p; } } }while(next_permutation(a+1,a+1+n)); cout<<ans<<endl; return 0; }
-
【LGR-179-Div.1】复旦勰码 3 月月赛 II & ZHYOI Round 4
\(T1\) luogu P10253 说唱 \(25pts\)
\(T2\) luogu P10254 口吃 \(10pts\)
\(T3\) luogu P10255 一首诗 \(0pts\)
\(T4\) luogu P10256 高仿的 Migos \(0pts\)
总结
- luogu P10253 说唱
- 赛时看见 \(y\) 极大，以为有纯数学解法，浪费了挺长时间。