本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-22 14:48:23
前言：
被 D 题降智，E 题写了个 kruskal 结果被卡了，F 题是个普及组难度的原题但是我没去看，最后 rating：
$\color{brown}\text{706} \rightarrow \color{brown}\text{725}$，什么时候才能上 $\color{green}\text{6kyu}$
A
int ch=getchar();
cout<<char(ch);
两行代码结束。
复杂度：$O(1)$
B
这个东西直接模拟就行了。
复杂度：$O(n+k)$
#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
const int maxn=105;
int a[maxn],b[maxn];
int k,n;
int imax=0;
void main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
imax=max(imax,a[i]);
}
for(int i=1;i<=k;i++)
{
cin>>b[i];
if(a[b[i]]==imax)
{
printf("Yes");
return;
}
}
printf("No");
}
}
int main()
{
Main::main();
return 0;
}
C
可以枚举 $0 \rightarrow 9$ 代表最终每个都显示的数字，然后枚举每一秒，每一秒再枚举每个可以点击的按钮即可。
算一下就可以发现，最多 1000 秒就能使所有的卷轴显示相同的数字，因为极端情况下 $10$ 秒才能控制一个卷轴，最多有 $n$ 个卷轴，$n \le 100$，$10 \times 100 = 1000$。
总复杂度： $O(10 \times 1000 \times n) = O(10000n)$
#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
const int maxn=105;
char s[maxn][15];
int n;
bool vis[maxn];
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
}
int ans=0x3f3f3f3f;
for(int i=0;i<10;i++)\/\/zimu
{
int col=0;
for(int t=0;t<=1000;t++)\/\/miaoshu
{
bool flag=1;
for(int j=1;j<=n;j++)
{
if(!vis[j])
{
if(s[j][t%10]==(i+'0'))
{
vis[j]=1;
break;
}
}
}
for(int j=1;j<=n;j++)
{
if(!vis[j])
{
flag=0;
break;
}
}
if(flag)
{
col=t;
break;
}
}
ans=min(ans,col);
for(int j=1;j<=n;j++)
{
vis[j]=0;
}
}
printf("%d",ans);
}
}
int main()
{
Main::main();
return 0;
}
D
可以先计算所有情况，然后再减去不合法情况。
假设由有 $n$ 个元素，那么在其中任意选择 $3$ 个元素的情况有 $\dfrac{n \cdot (n-1) \cdot (n-2)}{6}$ 个，任意选择 $2$ 个元素的情况有 $\dfrac{n \cdot (n-1)}{2}$ 个。
那么先定义两个函数，方便后面使用：
long long sum_3(long long n)
{
return n*(n-1)*(n-2)\/6;
}
long long sum_2(long long n)
{
return n*(n-1)\/2;
}
设一个元素 $a_i$ 在数组中重复出现了 $x$ 次，数组有 $n$ 个元素。将会出现两种不合法情况，来分类一下。
- 第一种情况是三元组的组成元素全都是 $a_i$，这种情况有 $\dfrac{x \cdot (x-1) \cdot (x-2)}{6}$个，也就是
sum_3(x)。 - 第二种情况是三元组的两个元素是 $a_i$，直接在数组所有重复的 $a_i$ 中挑选有 $\dfrac{x \cdot (x-1)}{2}$ 个组合，显然，每个组合都会与其他 $n-2$ 个元素形成新的组合，有 $\dfrac{x \cdot (x-1)}{2} \cdot (n-2)$ 个情况。但是别忘了，其中有 $\dfrac{x \cdot (x-1)}{2} \cdot (x-2)$ 种情况会组合成三个元素都相等的三元组，而这些情况已经在第一条处理过，这里不需要再处理，所以实际上只用处理 $\dfrac{x \cdot (x-1)}{2} \cdot [n-2-(x-2)]=\dfrac{x \cdot (x-1)}{2} \cdot (n-x)$ 个情况
综上，设每个元素出现了 $x_i$，数组有 $n$ 个元素，那么答案就是：
$\dfrac{n \cdot (n-1) \cdot (n-2)}{6} - \sum_{i=1}^{n} (\dfrac{x_i \cdot (x_i-1) \cdot (x_i-2)}{6} + \dfrac{x_i \cdot (x_i-1)}{2} \cdot (n-x_i))$
复杂度 $O(n)$（unordered_map 是 $O(1)$的）
#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
typedef long long ll;
const int maxn=2e5+5;
unordered_map<int,int> im;
int a[maxn];
int n;
ll sum_3(ll n)
{
return n*(n-1)*(n-2)\/6ll;
}
ll sum_2(ll n)
{
return n*(n-1)\/2ll;
}
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
im[a[i]]++;
}
ll ans=sum_3(n);
for(int i=1;i<=n;i++)
{
if(im[a[i]])
{
ans-=sum_3(im[a[i]]);
ans-=sum_2(im[a[i]])*ll(n-im[a[i]]);
im[a[i]]=0;
}
}
printf("%lld",ans);
}
}
int main()
{
Main::main();
return 0;
}
E
不懂 prim 的请自行百度
这道题让构造一棵树使得 $1$ 到每个点的距离之和最短。最短路 + 生成树，那么肯定就是 prim（赛时我不会 prim，所以寄了）。
这道题算是把堆优化版 prim 板子改改就能过的那种，来说一下：
- 把更新最短路的地方改成
dijkstra的做法。 - 用
pair的第一个关键字来存储边权，第二个关键字存储边的编号。当要取出队首节点时，直接取出edge[que.top().second].to即可。 - 如果 $1$ 点存入小根堆种，取出队首节点时不会取出 $1$ 点，而是取出 $1$ 指向的节点，所以应该建立一个 $0$ 号节点并将其连向 $1$ 节点，初始时将 $0$ 号节点压入小根堆。
- 用一个
queue<int> ans来存储每个需要的边，每弹出队首，就将这条边加入其中，也就是：int id=que.top().second; ans.push((id+1)\/2);注：之所以 $id$ 要加 $1$ 然后除以 $2$ 是因为建图的时候建的双向边，编号为 $1,2$ 的是一条边，编号为 $3,4$ 的是一条边..........
这道题就结束了。
复杂度： $O((n+m)logm)$
#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
typedef long long ll;
const int maxn=2e5+5;
const int maxm=2e5+5;
int head[maxn<<1];
bool vis[maxn];
ll dis[maxn];
struct EDGE
{
int to,nxt,val;
}edge[maxm<<1];
int cnt;
inline void add(int u,int to,int val)
{
edge[++cnt].to=to;
edge[cnt].val=val;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
int n,m;
inline void prim()
{
queue<int> ans;
priority_queue<pair<ll,int>> que;
for(int i=0;i<=n;i++)
{
dis[i]=1e18;
}
dis[1]=0;
que.push(make_pair(0,m*2+1));
int tot=0;
while(tot<n&&!que.empty())
{
int id=que.top().second;
int u=edge[id].to;
que.pop();
if(vis[u])continue;
vis[u]=1;
ans.push(((id+1)>>1));
tot++;
for(int i=head[u];i;i=edge[i].nxt)
{
int to=edge[i].to;
if(dis[to]>dis[u]+ll(edge[i].val))
{
dis[to]=dis[u]+ll(edge[i].val);
que.push(make_pair(-dis[to],i));
}
}
}
ans.pop();
while(ans.size()!=0)
{
printf("%d ",ans.front());
ans.pop();
}
}
void main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int xi,yi,zi;
scanf("%d%d%d",&xi,&yi,&zi);
add(xi,yi,zi);
add(yi,xi,zi);
}
add(0,1,0);
prim();
}
}
int main()
{
Main::main();
return 0;
}
F
这道题是 合并果子 原题，相信谁都会我就不说了
大意：给定一个大小为 $l$ 的面包，要将面包分成 $n$ 块，第 $i$ 块面包大小为 $a_i$。
每次可以将一块面包切成两个任意大小的面包。每次切割面包都会产生相当于原来面包大小的代价，问完成操作的最小代价是多少。
把这个过程倒过来，变成合并面包就行了。现在问题转化为有 $n$ 个大小为 $a_i$ 的面包和一个大小为 $l - \sum a_i$ 的面包，每次可以合并任意两个面包，合并的代价为两个面包大小之和。问合并出一个大小为 $l$ 的面包的最小代价。
显然，每次选出大小最小的两个面包合并就能保证最后代价最小，用小根堆维护即可。
复杂度：$O(nlogn)$
#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
typedef long long ll;
const int maxn=2e5+5;
ll a[maxn];
priority_queue<ll> que;
int n;
ll l;
void main()
{
scanf("%d%lld",&n,&l);
ll ans=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
que.push(-a[i]);
l-=ll(a[i]);
}
if(l>0)
{
que.push(-l);
}
n=que.size();
for(int i=1;i<n;i++)
{
ll t1=-que.top();
que.pop();
ll t2=-que.top();
que.pop();
ans+=t1+t2;
que.push(-t1-t2);
}
printf("%lld",ans);
}
}
int main()
{
Main::main();
return 0;
}
Ex
题目简略翻译：
有 $C$ 个美丽值，分别为 $1,2,......C$
有 $N$ 个宝石，每个宝石都有一个颜色 $D_i$，和一个美丽值 $V_i$（$V_i \in {1,2,.....C}$，每个美丽值都至少会在某个宝石上出现一次）
现在要在 $n$ 个宝石中选 $C$ 个颜色互不相同的宝石，每个方案的价值是选择的这 $C$ 个宝石的美丽值的异或和。
问价值为第 $k$ 大的方案的价值
题目分析：
老子不会
代码：
#include <bits\/stdc++.h>
using namespace std;
int main()
{
cout<<"老子不会";
return WA;
}
鲁ICP备2025150228号