暑假集训CSP提高模拟1
\(T1\) T2687. Start
- 原题： luogu P7506 「Wdsr-2.5」琪露诺的算数游戏
- 大模拟。
\(T2\) T807. mine
-
设 \(f_{i,0/1/2/3/4}\) 分别表示处理到第 \(i\) 位时，第 \(i\) 位为雷/第 \(i\) 位不为雷，第 \(i-1,i+1\) 位不为雷/第 \(i\) 位不为雷，第 \(i-1\) 位不为雷，第 \(i+1\) 位为雷/第 \(i\) 位不为雷，第 \(i-1\) 位为雷，第 \(i+1\) 位不为雷/第 \(i\) 位不为雷，第 \(i-1,i+1\) 位为雷的方案数，状态转移方程（如果存在这个状态的话）为 \(\begin{cases} f_{i,0}=f_{i-1,0}+f_{i-1,2}+f_{i-1,4} \\ f_{i,1}=f_{i-1,1}+f_{i-1,3} \\ f_{i,2}=f_{i-1,1}+f_{i-1,3} \\ f_{i,3}=f_{i-1,0} \\ f_{i,4}=f_{i-1,0} \end{cases}\) ，边界为 \(f_{0,1}=f_{0,2}=1\) 。
-
最终，有 \(f_{|s|,0}+f_{|s|,1}+f_{|s|,3}\) 即为所求。
点击查看代码
const ll p=1000000007; ll f[1000010][5]; char s[1000010]; int main() { ll n,i; cin>>(s+1); n=strlen(s+1); f[0][1]=f[0][2]=1; for(i=1;i<=n;i++) { if(s[i]=='?') { f[i][0]=(f[i-1][0]+f[i-1][2]+f[i-1][4])%p; f[i][1]=(f[i-1][1]+f[i-1][3])%p; f[i][2]=(f[i-1][1]+f[i-1][3])%p; f[i][3]=f[i-1][0]; f[i][4]=f[i-1][0]; } if(s[i]=='*') { f[i][0]=(f[i-1][0]+f[i-1][2]+f[i-1][4])%p; } if(s[i]=='0') { f[i][1]=(f[i-1][1]+f[i-1][3])%p; } if(s[i]=='1') { f[i][2]=(f[i-1][1]+f[i-1][3])%p; f[i][3]=f[i-1][0]; } if(s[i]=='2') { f[i][4]=f[i-1][0]; } } cout<<(f[n][0]+f[n][1]+f[n][3])%p<<endl; return 0; } -
貌似还有列出方程组后，手动解带状矩阵，求自由元数量的高级做法，但我不会，暂时咕了。
\(T3\) T2790. 小凯的疑惑
-
最终能组成的数一定能表示成 \(k \times \gcd(x,y)(k \in \mathbb{N})\) 的形式，即最终能组成的数 \(\bmod \gcd(x,y)=0\) 。
-
当 \(d \ne 1\) 时存在无数个正整数不能被如此表示。
-
当 \(d=1\) 时
- 由弱化版 luogu P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目 的结论，有不能被 \(x,y\) 表示的最大整数为 \(xy-x-y\) 。
- 又因为剩余系的性质，有当 \(a\) 跑遍模 \(y\) 的完全剩余系时 \(ax\) 也跑遍模 \(y\) 的完全剩余系。
- 考虑从完全剩余系入手，枚举 \(a \in [0,y)\) 即可不重不漏地算完。
- 设 \(c=ax+by(b \le 0 \le a)\) ，移项有 \(ax-c=-by\) 。当 \(ax\) 确定时，因为 \(c \ge 1\) 有 \(-b \in [1, \left\lfloor \dfrac{ax}{y} \right\rfloor]\) 。
- 最终，有 \(\begin{aligned} \sum\limits_{i=0}^{y-1} \left\lfloor \frac{ix}{y} \right\rfloor &=\frac{\sum\limits_{i=0}^{y-1} (ix)-\sum\limits_{i=0}^{y-1} (ix \bmod y)}{y} \\ &=\frac{x \times \sum\limits_{i=0}^{y-1}i-\sum\limits_{i=0}^{y-1}i}{y} \\ &=\frac{\frac{xy(y-1)}{2}-\frac{y(y-1)}{2}}{y} \\ &=\frac{(x-1)(y-1)}{2} \end{aligned}\) 即为所求。
点击查看代码
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } int main() { ll x,y; cin>>x>>y; cout<<(gcd(x,y)==1?(x-1)*(y-1)/2:-1)<<endl; return 0; }
\(T4\) T2810. 春节十二响
-
对于以 \(x\) 为根的子树内的节点分段时一定是和以 \(fa_{x}\) 为根的子树内除以 \(x\) 为根的子树外的其他子树的节点在同一个段。
-
从贪心的角度分析，大的数和大的数在一起一定是最优的，优先队列或可并堆维护。
-
启发式合并维护即可。
点击查看代码
struct node { ll nxt,to; }e[200010]; ll head[200010],a[200010],cnt=0; priority_queue<ll>q[200010],ls; void add(ll u,ll v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dsu_merge(ll x,ll y) { if(q[x].size()<q[y].size()) { swap(q[x],q[y]); } while(q[y].empty()==0) { ls.push(max(q[x].top(),q[y].top())); q[x].pop(); q[y].pop(); } while(ls.empty()==0) { q[x].push(ls.top()); ls.pop(); } } void dfs(ll x) { for(ll i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); dsu_merge(x,e[i].to); } q[x].push(a[x]); } int main() { ll n,u,v,ans=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=2;i<=n;i++) { cin>>u; v=i; add(u,v); } dfs(1); while(q[1].empty()==0) { ans+=q[1].top(); q[1].pop(); } cout<<ans<<endl; return 0; }