诈骗题专场
A. Reorder
题意：给你一个长度为 \(n\) 的数组 \(a\)，问是否可以把这个重新排序后，使得
\[\sum\limits^{n}_{i=1}\sum\limits^{n}_{j=i}\dfrac{a_j}{j}=m \]解法：诈骗题 \(\times 1\)
注意到
问题就迎刃而解
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=998244353,INF=9e18;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
int n=read(),m=read(),sum=0;
for(int i=1;i<=n;i++){
int x=read();sum+=x;
}
if(sum==m) printf("Yes\n");
else printf("No\n");
}
return 0;
}
B. Prime Square
题意：定义一个 \(n\times n\) 素数正方形为:
- 所有的数 \(a_{i,j}\in [0,10^5]\) 且为整数
- 所有的数不是质数
- 每行、每列的和都是质数
输入 \(n\)，输出大小为 \(n\) 的素数正方形
解法：诈骗题 \(\times 2\)
注意到 \(0\) 和 \(1\) 都不是质数，考虑用其进行构造
如果 \(n\) 为偶数，注意到形如
的矩阵是满足条件的（每行每列和都是 \(2\) ）
如果 \(n\) 为奇数，那么考虑
也即对角线填 \(1\)，对角线下两格填 \(1\)，右上角两个 \(1\) 无疑是符合条件的
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=998244353,INF=9e18;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
int n=read();
if(n%2==0){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j||i==n-j+1) printf("1 ");
else printf("0 ");
}
printf("\n");
}
}else{
int mp[101][101];
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++) mp[i][i]=1;
mp[1][n-1]=mp[2][n]=1;
for(int i=3;i<=n;i++) mp[i][i-2]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%lld ",mp[i][j]);
}
printf("\n");
}
}
}
return 0;
}
C. Binary Search
题意：给你一个二分代码
再给定三个正整数 \(n,x,pos\) 请你求出满足以下条件的数组 \(a\) 的个数：
- 数组 \(a\) 是正整数 \(1\sim n\) 的一种排列，且 \(a_{pos}=x\)（下标从 \(0\) 开始）
- 对于数组 \(a\) 运行如上代码（见图片，就是二分查找的模板），其返回值为 \(\rm true\) 。
请将答案对 \(10^9+7\) 取模后输出。
解法：不难发现，我们先执行一次二分，对可能访问到的点打上标记
记录每个点需要小于 \(x\) （记为 \(cnt1\)）或是大于 \(x\)（记为 \(cnt2\)）
然后答案就是 \(\operatorname{A}_{x-1}^{cnt1}\operatorname{A}_{n-x}^{cnt2}(n-cnt1-cnt2-1)!\)
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
int n,x,pos;
int f[WR],inv[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
int quick_pow(int a,int b){
int base=a,res=1;
while(b){
if(b&1) res=res*base%mod;
base=base*base%mod;
b>>=1;
}
return res;
}
signed main(){
n=read(),x=read(),pos=read();
f[0]=inv[0]=1;
for(int i=1;i<WR;i++) f[i]=f[i-1]*i%mod;
inv[WR-1]=quick_pow(f[WR-1],mod-2);
for(int i=WR-2;i;i--) inv[i]=inv[i+1]*(i+1)%mod;
int l=0,r=n,les=0,gre=0;
while(l<r){
int mid=(l+r)>>1;
if(mid<=pos) l=mid+1,les+=(mid<pos);
else r=mid,gre++;
}
printf("%lld\n",f[x-1]*inv[x-1-les]%mod*f[n-x]%mod*inv[n-x-gre]%mod*f[n-les-gre-1]%mod);
return 0;
}
D. Bandit in a City
题意：给定以 \(1\) 为根的 \(n\) 个节点的一棵树，每个节点上有 \(a_i\) 个人
每个人可以选择往任意子节点走，直到走到叶子节点为止，问最后人最多的叶子节点最少有多少人。
解法：平凡的树上 \(dp\)
注意到每个点会尽可能地让它的叶子节点人数平均
但是有一种可能就是有一个节点权值巨大，怎么办呢？
维护一个 \(maxx\) 数组记录一下每个节点的最大值就可以了
答案就是 \(maxx[1]\)
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
struct Edge{
int pre,to;
}edge[WR<<1];
int head[WR],tot;
int n,a[WR];
int tag[WR],sze[WR],maxx[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
void add(int u,int v){
edge[++tot].pre=head[u];
edge[tot].to=v;
head[u]=tot;
}
void dfs(int u){
sze[u]=a[u];
for(int i=head[u];i;i=edge[i].pre){
int v=edge[i].to;
dfs(v);
sze[u]+=sze[v];tag[u]+=tag[v];
maxx[u]=max(maxx[u],maxx[v]);
}
maxx[u]=max(maxx[u],(int)ceil(1.0*sze[u]/tag[u]));
}
signed main(){
n=read();
for(int i=2;i<=n;i++){
int fa=read();
add(fa,i);
}
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) if(head[i]==0) tag[i]=1;
dfs(1);
printf("%lld\n",maxx[1]);
return 0;
}
E. Complicated Computations
题意：求出给定区间的 \(\operatorname{mex}\) 的 \(\operatorname{mex}\)
解法：考虑建立一棵线段树维护每个数值最后出现的位置
然后再开一个数组 \(lst\) 记录最后出现的位置
然后对于一个数 \(a_i\) 我们查询 \(1\sim a_{i-1}\) 的最后出现位置的最小值
如果这个最小值大于 \(a_i\) 上一次出现的位置那么显然在 \(lst_{a_i}+1\) 到 \(i-1\) 这段区间内 \(\operatorname{mex}=a_i\)
扫一遍即可，最后为了处理 \(lst_i\) 到 \(n\) 的还要多扫一点
另：这道题目很像 \(Kaiser\_Kell~is~always~there\) 但是我和 \(BE\) 卡了好几份代码。。。
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
struct SegmentTree{
int l,r,val;
}tree[WR<<2];
int n;
int a[WR],lst[WR];
bool tag[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
void pushup(int k){
tree[k].val=min(tree[k<<1].val,tree[k<<1|1].val);
}
void build(int k,int l,int r){
tree[k].l=l,tree[k].r=r,tree[k].val=0;
if(l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int pos,int val){
if(tree[k].l==tree[k].r){
tree[k].val=val;
return;
}
int mid=(tree[k].l+tree[k].r)>>1;
if(pos<=mid) modify(k<<1,pos,val);
else modify(k<<1|1,pos,val);
pushup(k);
}
int query(int k,int l,int r){
if(tree[k].l>=l&&tree[k].r<=r){
return tree[k].val;
}
int mid=(tree[k].l+tree[k].r)>>1,res=INF;
if(l<=mid) res=min(res,query(k<<1,l,r));
if(r>mid) res=min(res,query(k<<1|1,l,r));
return res;
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for(int i=1;i<=n;i++){
if(a[i]!=1) tag[1]=true;
if(a[i]>1&&query(1,1,a[i]-1)>lst[a[i]]) tag[a[i]]=true;
lst[a[i]]=i;
modify(1,a[i],i);
}
for(int i=2;i<=n+1;i++){
if(query(1,1,i-1)>lst[i]) tag[i]=true;
}
int mex=1;
while(tag[mex]) mex++;
printf("%lld\n",mex);
return 0;
}