本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-17 22:04:44
前言：
赛场上 C 题吃了 $23$ 个罚时，D题时间不够了（赛后 1 分钟想出正解）。
结果呢？
rating: $\color{brown} 500 \rightarrow 497 \color{black}(-3)$
rating 暴跌 3 
A - Shampoo
暴力即可。
AC 代码：
#include <bits\/stdc++.h>
using namespace std;
int main()
{
int v,a,b,c;
cin>>v>>a>>b>>c;
int cnt=2;
while(1)
{
cnt++;
cnt%=3;
if(cnt==0)
{
if(v<a)
{
printf("F");
return 0;
}
v-=a;
}
if(cnt==1)
{
if(v<b)
{
printf("M");
return 0;
}
v-=b;
}
if(cnt==2)
{
if(v<c)
{
printf("T");
return 0;
}
v-=c;
}
}
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
B - Hit and Blow
暴力即可。
AC 代码：
#include <bits\/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn],b[maxn];
int n;
int main()
{
cin>>n;
int ans1=0,ans2=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)if(a[i]==b[i])ans1++;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)continue;
if(a[i]==b[j])ans2++;
}
}
printf("%d\n%d",ans1,ans2);
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
C - Collision 2
题目大意：
给你 $n$ 个点的坐标 $(x_i,y_i)$。每个点都有一个运动方向（向左或向右），假如让每个点不断运动，是否会有两个点相遇？
保证初始时任意两个点坐标不同。
题目分析：
维护一个结构体 $node$，存储每个点的坐标和方向。然后根据横坐标对其从小到大进行排序。
定义一个 map 容器：
map<pair<int,char>,vector<int>> im;
代表纵坐标为 pair.first，方向为 pair.second 的所有点的横坐标有哪些（由 vector 存储）
然后遍历每一个点，假设其纵坐标为 $y$ ，横坐标为 $x$ 如果其方向为向左，那么看一下存储 (( 当前纵坐标上所有向右的点 ) 的横坐标) 的 vector 的第一个元素，如果第一个元素的值小于 $x$，那么输出 Yes，否则则说明当前 vector 没有元素符合小于等于 $x$，那么跳过。（因为已经从小到大排序了）
如果当前方向为右，应该能举一反三吧我就懒得说了
AC 代码：
#include <bits\/stdc++.h>
using namespace std;
map<pair<int,char>,vector<int>> im;
const int maxn=2e5+5;
struct Node
{
int x,y,s;
}node[maxn];
int n;
char s[maxn];
inline bool cmp(Node a,Node b)
{
return a.x<b.x;
}
int main()
{
int cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&node[i].x,&node[i].y);
}
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
node[i].s=s[i];
}
sort(node+1,node+n+1,cmp);
for(int i=1;i<=n;i++)
{
im[make_pair(node[i].y,node[i].s)].emplace_back(node[i].x);
}
for(int i=1;i<=n;i++)
{
if(node[i].s=='L')
{
for(int pos:im[make_pair(node[i].y,'R')])
{
if(pos<=node[i].x)
{
printf("Yes");
return 0;
}
else
{
break;
}
}
}
if(node[i].s=='R')
{
int po=im[make_pair(node[i].y,'L')].size()-1;
if(po<0)continue;
if(im[make_pair(node[i].y,'L')][po]>=node[i].x)
{
printf("Yes");
return 0;
}
}
}
printf("No");
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
D - Moves on Binary Tree
题目分析：
可以发现到达父节点就是 $x$ >>= $1$，
到达左子节点就是 $x$ <<= $1$，到达右子节点就是 $x$ = $x$ << $1$ | $1$。
把二进制弄成高精，string 存一下。最后 bitset 转换成 long long 就行了。
AC 代码：
#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char s[maxn];
typedef long long ll;
ll n,x;
string ans;
int main()
{
scanf("%lld%lld",&n,&x);
scanf("%s",s+1);
bitset<100> bit(x);
ans+=bit.to_string();
for(int i=1;i<=n;i++)
{
if(s[i]=='U')
{
ans.pop_back();
}
if(s[i]=='L')
{
ans.append("0");
}
if(s[i]=='R')
{
ans.append("1");
}
}
bitset<maxn> out(ans);
printf("%lld",out.to_ulong());
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
E - Edge Deletion
题目分析：
floyd 求出每两个点之间最短路，然后枚举每一条边判断是否可以被其他边替代，如果当前边可以被替代那么 $ans$++，最后输出 $ans$
AC 代码：
#include <bits\/stdc++.h>
using namespace std;
const int maxn=305;
const int maxm=45000;
int n,m;
int imap[maxn][maxn];
int a[maxm],b[maxm],c[maxm];
signed main()
{
memset(imap,0x3f3f3f3f,sizeof(imap));
scanf("%d%d",&n,&m);
int ai,bi,ci;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&ai,&bi,&ci);
a[i]=ai;
b[i]=bi;
c[i]=ci;
imap[ai][bi]=ci;
imap[bi][ai]=ci;
}
for(int mid=1;mid<=n;mid++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
imap[i][j]=min(imap[i][j],imap[i][mid]+imap[mid][j]);
}
}
}
int ans=0;
bool flag;
for(int i=1;i<=m;i++)
{
flag=0;
for(int j=1;j<=n;j++)
{
if(imap[a[i]][j]+imap[j][b[i]]<=c[i])
{
flag=1;
}
}
ans+=flag;
}
printf("%d",ans);
return 0;
}
F - Lottery
题目前置：
有理数取余，应该谁都会吧（清北灵堂清北学堂好像讲过）
题目分析：
设 $p_i = \frac{W_i}{\Sigma^N_{j=1}W_j}$
显然，第 $i$ 个物品抽到了 $c_i$ 个的概率为 ${p_i}^{c_i}$。所有的物品综合起来，概率即为 $\prod_{i=1}^{n} {p_i}^{c_i}$
此处引用 @sunjiangnan55 的图片：
根据这个定理，假设抽了 $k$ 次。把 $k$ 次抽奖机会分配给 $n$ 个物品，每个物品抽到了 $c_i$ 个，那么排列方式就有 $\frac{k!}{\prod_{i=1}^{n} {c_i!}}$ 个。
两个概率乘起来就是(抽奖抽了 $k$ 次之后，第 $i$ 号物品获得 $c_i$ 个)的概率：$\prod_{i=1}^{n} {p_i}^{c_i} \cdot \frac{k!}{\prod_{i=1}^{n} {c_i!}}$
来通过 dp 求解。
设 $f[i][j][k]$ 表示 $i$ 个物品，抽了 $k$ 次后得到了 $j$ 个不同奖品的方案数。
状态转移： $f[i][j][k] = (f[i-1][j][k] + \Sigma_{l=1}^{k} f[i-1][j-1][k-l] \cdot {p_i}^{l} \cdot {l!}^{998244351}) mod 998244353$
这里我解释一下，${l!}^{998244351}$ 代表 $l!$ 的逆元；$l$ 的意思就是新抽了多少次奖；从 $j-1$ 转移过来是代表增加了一个种类的奖品，因为只增加了一个种类 ，但是抽中了 $l$ 个奖品，所以这些新抽中的一定是同一种类的（这个新种类就是当前第 $i$ 个物品），这种情况发生的概率为 ${p_i}^{l}$，所以要乘上 ${p_i}^{l}$。
AC 代码：
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
const int mod=998244353;
int n,m,k;
int w[maxn];
ll p[maxn];\/\/每个点被选中的概率
ll sum;\/\/w总和
inline int ksm(ll a,ll b,ll mod)
{
ll ret=1;
while(b)
{
if(b&1)ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
inline int ny(ll a,ll mod)
{\/\/逆元
return ksm(a,mod-2,mod);
}
ll fact[maxn];
ll f[maxn][maxn][maxn];
\/\/i个物品，抽了k次之后得到了j个不同奖品
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum+=w[i];
}
for(int i=1;i<=n;i++)
{\/\/预处理被选概率
p[i]=((ll)w[i]*ny(sum,mod))%mod;
}
fact[0]=1;
for(int i=1;i<maxn;i++)
{
fact[i]=fact[i-1]*i%mod;
}
f[0][0][0]=1;
for(int i=1;i<=n;i++)
{
int tmp=min(i,m);
for(int j=0;j<=tmp;j++)
{
for(int kkksc03=0;kkksc03<=k;kkksc03++)
{
f[i][j][kkksc03]=f[i-1][j][kkksc03];
if(j>0)
{
for(int l=1;l<=kkksc03;l++)
{
f[i][j][kkksc03]+=(f[i-1][j-1][kkksc03-l]*ksm(p[i],l,mod)%mod*ny(fact[l],mod)%mod);
f[i][j][kkksc03]%=mod;
}
}
}
}
}
printf("%lld",f[n][m][k]*fact[k]%mod);
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
G - Sqrt
题目分析：
很容易得到一个 $O(\sqrt N)$ 的垃圾做法。显然，$f[x] = \Sigma_{i=1}^{\sqrt N} f[i]$，$f[1]=1$
尝试对此改进，可以通过只枚举 $1 \rightarrow N^{\frac{1}{4}}$，那么显然，对于 $i$，$f[i]$ 的 $i$ 可以由 从$\sqrt N$ 到 $i^2$的所有数一步步按题意操作得来。
所以答案就是 $\Sigma_{i=1}^{n^{\frac{1}{4}}} (f[i] \cdot(\sqrt N - i^2 + 1))$
AC代码：
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=6e6+5;
int t;
ll x;
ll great_sqrt(ll sum)
{
ll res=(ll)sqrt(sum-0.1);
while(res*res<=sum)res++;
return res-1;
}
ll dp[maxn];
int main()
{
dp[1]=1;
for(int i=2;i<=55000;i++)
{
int tmp=great_sqrt(i);
for(int j=1;j<=tmp;j++)
{
dp[i]+=dp[j];
}
}
scanf("%d",&t);
while(t--)
{
scanf("%lld",&x);
if(x<=55000)
{
printf("%lld\n",dp[x]);
continue;
}
ll x2=great_sqrt(x);
ll x3=great_sqrt(x2);
ll ans=0;
for(ll i=1;i<=x3;i++)
{
ans+=(x2-i*i+1)*dp[i];
}
printf("%lld\n",ans);
}
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
鲁ICP备2025150228号