前言
- 比赛链接。
真是一次比一次唐了。
被莫反害惨了属于是(其实完全是自己唐吧),T1 狂推莫反不止,一直想着怎么处理 \(999\) 的限制,最后推出来了复杂度是 \(999\sqrt n\) 的,过不去,继续唐我的高级分块套分块做法,比赛快结束了才发现正因为那个限制所以我直接枚举就行了,丫的最后少了个取模还挂了4pts,所以又被签到题爆刷了?!?!?!
好像打得唐的这几次都是因为 T1 死的,今天喵喵进来讲了学长们考 NOI 的经历告诉我们 T1 不能影响比赛以及心态的问题,每次都说下次不能这么挂了结果下次接着挂。
结果就是打完 T1 去调 T4 平衡树没调出来打暴力了,T2 没看(其实也是个签到题),T3 直接输出 \(0\)。
T1 黑客
签到题,直接枚举 \(i+j\),这个最多到 \(999\),对于每个 \(i+j\) 枚举每一对 \(\gcd(i,j)=1\),其贡献为 \((i+j)\times \min(\lfloor\dfrac{n}{i}\rfloor,\lfloor\dfrac{m}{j}\rfloor)\)。
最后分 \(4\) 块容斥即可,\(ans=calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
ll a,b,c,d;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll solve(ll n,ll m)
{
ll ans=0;
for(ll i=1;i<=min(999ll,n+m);i++)
{
for(ll x=max(1ll,i-m);x<=min(n,i-1);x++)
{
ll y=i-x;
if(gcd(x,y)!=1) continue;
(ans+=i*min(n/x,m/y)%P)%=P;
}
}
return ans;
}
signed main()
{
read(a),read(b),read(c),read(d);
write((solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1)+P+P)%P);
}
T2 密码技术
也是个签到题,发现两个结论:
- 行和列之间互不影响。
- 若 \(i,j\) 可换,\(j,k\) 可换,有 \(i,k\) 可换。
以上结论主要原因是题目保证元素不重复,都很显然。
所以直接并查集维护即可,每个块的贡献为 \(size!\),行和列答案乘起来即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=55,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
ll n,s,f[N],sz[N],ans=1,a[N][N],jc[N];
ll find(ll x) {return f[x]==x?x:f[x]=find(f[x]);}
void merge(ll x,ll y)
{
x=find(x),y=find(y);
if(x==y) return ;
f[y]=x;
sz[x]+=sz[y];
sz[y]=0;
}
signed main()
{
read(n),read(s);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
read(a[i][j]);
jc[0]=1;
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,jc[i]=jc[i-1]*i%P;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
bool flag=0;
for(int k=1;k<=n;k++)
if(a[i][k]+a[j][k]>s)
{
flag=1;
break;
}
if(!flag) merge(i,j);
}
for(int i=1;i<=n;i++)
if(sz[i]) (ans*=jc[sz[i]])%=P;
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
bool flag=0;
for(int k=1;k<=n;k++)
if(a[k][i]+a[k][j]>s)
{
flag=1;
break;
}
if(!flag) merge(i,j);
}
for(int i=1;i<=n;i++)
if(sz[i]) (ans*=jc[sz[i]])%=P;
write(ans);
}
T3 修水管
注:下面所说的修理指该处为最靠前的爆炸点,而轮数的定义也和题面不同,这里指修理了多少个点,也就是说最终论述可以不为 \(r\)。
对于修理点 \(i\),则点 \(1\sim i-1\) 均需满足以下条件之一:
- 被修理过。
- 没有爆炸且再也不会爆炸。
那么若去修理点 \(i\),对应有以下两种情况:
- 从本轮往后爆炸一次,对应被修理过。
- 后面轮中再也不会爆炸。
根据上面的定义只有此处修理了 \(i\) 论述才加一,设当前论述为 \(j\),后面最多还有 \(r-j\) 次修理的机会,在这些机会中若此时 \(i\) 爆炸了且没有修便会贡献一次 \(d_i\),故此时 \(i\) 必须修理;而在此之前的 \(j\) 轮中 \(i\) 不是最靠前的,他炸了也没有贡献且不计入轮数,由此上述结论是成立的。
故此设 \(f_{i,j}\) 表示前 \(i\) 个点进行了 \(j\) 轮的概率,有 DP 式子:
\[f_{i-1,j-1}\times (1-(1-p_i)^{r-j+1})+f_{i,j}=f_{i-1,j}\times (1-p_i)^{r-j} \]分别对标两种情况,定义 \(g_i\) 为修理 \(i\) 的概率,有:
\[g_{i}=\sum\limits_{j=1}^{r}f_{i-1,j-1}\times (1-(1-p_i)^{r-j+1}) \]直接对标情况一,最后统计期望:
\[ans=\sum\limits_{i=1}^ng_id_i \]点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=260,M=320;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
int T,n,r;
double p[N],d[N],f[N][N],g[N],ans;
double qpow(double a,int b)
{
double ans=1;
for(;b;b>>=1)
{
if(b&1) ans*=a;
a*=a;
}
return ans;
}
signed main()
{
read(T);
while(T--)
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
ans=0;
read(n),read(r);
for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i],&d[i]);
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=min(i,r);j++)
{
f[i][j]+=f[i-1][j]*qpow(1.0-p[i],r-j);
if(j!=0)
f[i][j]+=f[i-1][j-1]*(1.0-qpow(1.0-p[i],r-j+1));
}
for(int i=1;i<=n;i++)
for(int j=1;j<=min(i,r);j++)
g[i]+=f[i-1][j-1]*(1.0-qpow(1-p[i],r-j+1));
for(int i=1;i<=n;i++) ans+=g[i]*d[i];
printf("%.10lf\n",ans);
}
}
T4 货物搬运
有分块和平衡树套平衡树两种做法,赛时平衡树没调出来,目前大家都写得分块,又好写又好理解,赛后改分块了。
分块 + deque。 这个做法真的巨简单,但赛时打出来的虽然都写的分块但都没有用 deque,不过没有卡掉,思路是一致的,被大家爆切。
对于一个区间 \([l,r]\),即将 \(r\) 移到 \(l\) 的位置,其余均向后错一位,可以用分块很好的维护,两边的散块直接暴力重构,复杂度是 \(O(\sqrt n)\) 的,中间的整块即上一个块的末尾成为本块的开头,可以每个块开一个 deque 单次 \(O(1)\) 修改,复杂度也是 \(O(\sqrt n)\)。时空复杂度均为 \(O(n+m\sqrt n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=320;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,t,a[N],b[N],pos[N],cnt[M][N],last,sta[N],top;
deque<int>q[M];
int L(int x) {return (x-1)*t+1;}
int R(int x) {return x*t;}
void change(int l,int r)
{
int x=pos[l],y=pos[r],sy;
l-=L(x),r-=L(y);
if(x==y)
{
sta[++top]=q[x][r];
for(int i=l+1;i<=r;i++) sta[++top]=q[x][i-1];
for(int i=r;i>=l;i--) q[x][i]=sta[top--];
return ;
}
sy=q[y-1][q[y-1].size()-1];
for(int i=x+1;i<=y-1;i++)
{
int s=q[i-1].back();
q[i].push_front(s);
cnt[i][s]++;
}
for(int i=x+1;i<=y-1;i++)
{
int s=q[i].back();
q[i].pop_back();
cnt[i][s]--;
}
cnt[x][q[y][r]]++,cnt[y][q[y][r]]--;
cnt[x][q[x].back()]--,cnt[y][sy]++;
sta[++top]=q[y][r];
for(int i=l+1;i<=R(x)-L(x);i++) sta[++top]=q[x][i-1];
for(int i=R(x)-L(x);i>=l;i--) q[x][i]=sta[top--];
sta[++top]=sy;
for(int i=1;i<=r;i++) sta[++top]=q[y][i-1];
for(int i=r;i>=0;i--) q[y][i]=sta[top--];
}
int ask(int l,int r,int k)
{
int x=pos[l],y=pos[r],ans=0;
l-=L(x),r-=L(y);
if(x==y)
{
for(int i=l;i<=r;i++)
if(q[x][i]==k) ans++;
return ans;
}
for(int i=l;i<=R(x)-L(x);i++)
if(q[x][i]==k) ans++;
for(int i=x+1;i<=y-1;i++) ans+=cnt[i][k];
for(int i=0;i<=r;i++)
if(q[y][i]==k) ans++;
return ans;
}
signed main()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
read(m);
t=sqrt(n);
for(int i=1;i<=n;i++) pos[i]=(i-1)/t+1;
for(int i=1;i<=pos[n];i++)
for(int j=L(i);j<=R(i);j++)
{
q[i].push_back(a[j]);
cnt[i][a[j]]++;
}
for(int i=1,op,l,r,k;i<=m;i++)
{
read(op),read(l),read(r);
l=(l+last-1)%n+1,r=(r+last-1)%n+1;
if(l>r) swap(l,r);
if(op==1) change(l,r);
if(op==2)
{
read(k); k=(k+last-1)%n+1;
last=ask(l,r,k);
write(last),puts("");
}
}
}
总结
该思考以下怎么应对这个 “T1 综合症了”,首先若感觉 T1 很难先看看下面的题看是不是被 swap 了,如果是直接看下面题就好了,否则仔细想一想,尤其不要想复杂,时刻告诉自己 T1 不会太难,像今天狂推莫反的行为就应该给自己一个嘴巴子;其次若很长时间想不出来赶紧往下做,把这题忘掉,最起码把下面简单一点的题切掉或把部分分拿全,再回来想,通常这时候头脑稍微清醒一点会有新的思路,至少会跳出思维误区。最后尤其不要着急,T1 做不出来确实唐但不是致命的,因为 T1 不会耽误下面的题从而满盘皆输才是。
附录
这次 rk 前三没给发零食(不关我的事)
rk1 是外校六年级小孩哥直接 AK 了,膜拜。
标签:10,16,int,void,Tp,2024,inline,集训,define From: https://www.cnblogs.com/Charlieljk/p/18335419