2020.3.23 模拟赛游记 & 题解

这次的模拟赛，实在是水。

数据水，\(\texttt{std}\) 水，出题人水，做题人也水。？？？

游记就说一句：

水。

T1 metro

弱智题。

人均 \(100pts\).

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int main(){

	freopen("metro.in","r",stdin);

	freopen("metro.out","w",stdout);

    int a=read(),b=read(),c=read(),d=read();

    int ans; if(a==c) ans=abs(b-d); //同一站

    else {

    	if(a==1) ans=abs(b-16)+abs(d-6);

    	else ans=abs(b-6)+abs(d-16);

	} //不同站

	if(ans<=5) puts("2");

	else if(ans<=12) puts("3");

	else if(ans<=20) puts("4");

	else puts("5");

	return 0;

}

T2 awake

弱智题。

除了没得 \(100pts\) 的，人均 \(100pts\).？？？

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

inline int num(string x) {

	int s=0;

	for(int i=0;i<x.size();i++) s=s*10+x[i]-'0';

	if(s<'A'-'0') return s;

	if(s=='J'-'0') return 11;

	if(s=='Q'-'0') return 12;

	if(s=='K'-'0') return 13;

	return 14;

} //对应的数字

int main(){

	freopen("awake.in","r",stdin);

	freopen("awake.out","w",stdout);

    string t; int lim;

    int s=0; int ans=0;

    for(int i=1,x;i<=4;i++) {

    	cin>>t; x=num(t);

//        cout<<t<<" "<<x<<endl;

    	if(x!=14) ans+=x;

    	else ans+=11,s++;

	} //printf("%d %d\n",ans,s);

	lim=read();

	for(int i=1;i<=s;i++)

	    if(ans>lim) ans-=10;

	    else break; //只要超过，就不断置换

	printf("%d\n",(ans>lim)?0:ans);

	return 0;

}

T3 contest

弱智题。

尽管弱智，还是错了几次。

比方说要得到 \(x\) 枚金币，\(y\) 枚银币。

那么，你肯定要进行 \(x - 1\) 轮，那么还剩 \(y - (x - 1) = y - x + 1\) 枚银币。

这个数一定是偶数，否则肯定是 NO.

边界问题要仔细！

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int main(){

	freopen("contest.in","r",stdin);

	freopen("contest.out","w",stdout);

	int T=read(),n,m; while(T--) {

		n=read(),m=read();

		if(!n) {puts("No");continue;}

		if(n==1 && m) {puts("No");continue;}

		if((n-1>m) || (m-n+1)&1) puts("No");

		else puts("Yes");

	}

	return 0;

}

T4 homework

这道题目，数据太水了！

你只要输出 \(\leq Y\) 的最大素数，就可以得到 \(80pts\).？？？

暴力判断，可以得到 \(100pts\).？？？

告诉你们，数据小暴力，数据大贪心，完全是错的！！！

下面本人给出正解，吊打 \(\texttt{std}\)！！！

xyx出的题目太渣了吧，数据这么弱

首先，如果 \(X^2 \geq Y\)，就输出最大素数。因为此时，\(\leq Y\) 的所有合数都被筛掉了。

否则，如果数据小，我们预处理素数表，然后爆搜。

否则考虑极限数据时，\(X < \sqrt{10^9}\)，大概是 \(30000\)，而 \(Y = 10^9\).

此时，我们希望复杂度抛开 \(Y\)，但这是不可能的。

你会发现，你可以先求出 \(\leq Y\) 的最大素数 \(K\)。由于在 \(n\) 和 \(2 \times n\) 之间至少有一个素数，所以复杂度较低。

你只需要考虑 \(K+1\) ~ \(Y\) 这一段，是否存在答案。

那么，显然这个数要 \(> x^2\)，否则肯定不如素数优。

由于 \(K\) 和 \(Y\) 的相差一般不超过 \(10^3\)，此时爆搜没有问题！

这才是真正的正解！而不是那些瞎暴力，瞎贪心的做法！

（由于本人偷懒，觉得数据弱，因此比赛的时候就不是按照正解打的）

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

inline bool prime(int n) {

	if(n<2) return 0;

	for(int i=2;i*i<=n;i++)

		if(n%i==0) return 0;

	return 1;

}

int main(){

	freopen("homework.in","r",stdin);

	freopen("homework.out","w",stdout);

	int n=read(),m=read();

	if(m>1e5) {

	for(int i=m;i>=1;i--)

		if(prime(i)) {

			printf("%d\n",i);

			return 0;

		}}

	for(int i=m;i>=n;i--) {

		bool f=0; int x=sqrt(i);

		for(int j=2;j<=min(x,n);j++)

			if(i%j==0) {f=1;break;}

		if(!f) {printf("%d\n",i);return 0;}

	} puts("1");

	return 0;

}

T5 pet

水题。

从大到小一个个抛弃就行了。

不过我的思路比较清奇，从小到大一个个加入。

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,A,B;

int a[N];

inline int chu(int x,int y) {

	return (x%y==0)?(x/y):(x/y+1);

}

int main(){

	freopen("pet.in","r",stdin);

	freopen("pet.out","w",stdout);

    n=read(); B=read(); A=read();

    int x=read(),ans=0;

    for(int i=1;i<n;i++) a[i]=read();

    int S=chu(x*B,A)-x;

    sort(a+1,a+n);

    for(int i=1;i<n;i++)

        if(ans+a[i]<=S) ans+=a[i];

        else {printf("%d\n",n-i);return 0;}

    printf("%d\n",0);

	return 0;

}

T6 fight

水题。

我线段树竟然炸了一次我****

线段树随便维护，或者差分。

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e6+1;

#define L i<<1

#define R (i<<1)+1

inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

struct tree{

	int l,r; ll tag;

	ll sumi;

};

tree t[4*N];

int n,m; ll a[N];

inline void update(int i) {

	t[i].sumi=t[L].sumi+t[R].sumi;

}

inline void pass(int i,ll x) {

	t[i].tag+=x;

	t[i].sumi+=x*(t[i].r-t[i].l+1);

}

inline void pushdown(int i) {

	pass(L,t[i].tag);

	pass(R,t[i].tag);

	t[i].tag=0;

}

inline void build_tree(int i,int l,int r) {

	t[i].l=l; t[i].r=r;

	if(l==r) {

		t[i].sumi=a[l]; t[i].tag=0;

		return;

	} int mid=(l+r)>>1;

	build_tree(L,l,mid);

	build_tree(R,mid+1,r);

	update(i);

}

inline ll query(int i,int l,int r) {

	if(l<=t[i].l && t[i].r<=r) return t[i].sumi;

	int mid=(t[i].l+t[i].r)>>1; ll ans=0;

	pushdown(i);

	if(l<=mid) ans+=query(L,l,r);

	if(r>mid) ans+=query(R,l,r);

	return ans;

}

inline void change(int i,int l,int r,int x) {

	if(l<=t[i].l && t[i].r<=r) {

		t[i].sumi+=x*(t[i].r-t[i].l+1);

		t[i].tag+=x; return ;

	} pushdown(i);

	int mid=(t[i].l+t[i].r)>>1;

	if(l<=mid) change(L,l,r,x);

	if(r>mid) change(R,l,r,x);

	update(i);

}

inline ll ask(int i,int l) {

	if(t[i].l==l && t[i].r==l) return t[i].sumi;

	pushdown(i); int mid=(t[i].l+t[i].r)>>1;

	if(l<=mid) return ask(L,l);

	else return ask(R,l);

}

int main(){

	freopen("fight.in","r",stdin);

	freopen("fight.out","w",stdout);

	n=read(),m=read();

	for(int i=1;i<=n;i++) a[i]=read();

	build_tree(1,1,n);

	while(m--) {

		int l=read(),r=read(),x=read();

		change(1,l,r,-x);

	} for(int i=1;i<=n;i++)

		printf("%lld ",max(ask(1,i),0ll));

	return 0;

}

T7 spell

赵海鲲巨佬关于此题的见解

这道题目爆搜要有技巧不像我第一次乱搜才 30.

首先是枚举全排列。请用库函数！而不是自己模拟，那样会多带来 \(O(n)\) 的复杂度。不像我第一次模拟全排列

然后，由于全排列的不重复性和上面巨佬所说，判断也非常简单不像我第一次排序一个个查

所以，总时间复杂度为：\(O(n! \times n)\).

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,a[11],f[11];

int ans=0;

inline bool check() {

	for(int i=1,s;i<=n;i++) {

		for(int j=1;j<=i;j++) {

			int maxi=INT_MIN,mini=INT_MAX;

			for(int k=j;k<=i;k++) maxi=max(maxi,f[k]),mini=min(mini,f[k]);

			if(maxi-mini==i-j) {

				s=i-j+1; break;

			}

		} if(s-a[i]) return 0;

	} return 1;

}

int main(){

	freopen("spell.in","r",stdin);

	freopen("spell.out","w",stdout);

	n=read();

	for(int i=1;i<=n;i++) a[i]=read(),f[i]=i;

	do {

		ans+=check();

	} while(next_permutation(f+1,f+n+1));

	printf("%d\n",ans);

	return 0;

}

T8 reinforce

[赵海鲲巨佬关于此题的见解]

由于我其它题都说的没他好，所以这题一定要详！细！说！

算法一

\[L=n-1
\]

这是 \(20 \%\) 的数据，直接输出和啊。因为你随便跳到一个地方，都可以再跳到终点。

得分：\(20pts\).

算法二

\[1 \leq L < N \leq 5，0 \leq a_i \leq 3
\]

很显然，枚举全排列作为当前跳法即可。

得分：\(50pts\).

如果前20%和这个不重合，可以到70pts！！！

算法三

暴力 + 贪心。

贪心的认为：每次跳得越远越好。

用那个大佬的几张图。

\(L=4\)，此时他有两种选择。

走近的，他就是脑抽你会发现还是要走到那个远一些的地方。

所以浪费了一片荷叶。（虽然本来也要浪费，但是大数据之下我们要节省）

走远的，他就是天才这时就跳到了终点，还尽量的节省了荷叶。

所以，每次从起点开始暴力跳一次，并把荷叶弄掉，直到跳不过。

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,L,a[N];

int ans=0;

inline int go() { //跳1次

//	for(int i=1;i<=n;i++) printf("%d ",a[i]);

//	putchar('\n');

	int i=0;

	while(i<=n) {

//		printf("%d\n",i);

		if(i+L>=n) return 1;

		bool f=0;

		for(int j=i+L;j>i;j--)

		    if(a[j]) {

//		    	printf("!%d\n",j);

		    	f=1; i=j; a[j]--;

		    	break;

			}

		if(!f) return 0;

	}

}

int main(){

	freopen("reinforce.in","r",stdin);

	freopen("reinforce.out","w",stdout);

    n=read(); L=read();

    for(int i=1;i<n;i++) a[i]=read();

    while(1) {

	    if(go()) ans++;

		else break;

	} printf("%d\n",ans);

	return 0;

}

而这只能得到 \(80pts\).

？？？

你想，这时间复杂度是 \(O(n \times L \times a_i)\).（如果每次尝试次数达到极值，会导致复杂度炸裂）

下面考虑动态规划。

什么？动态规划？

哦~ 原来是个动态规划水题。

嗯？你突然觉得不对啊？

\(O(n \times L)\) 怎么过得了呢？

谁说过不了呢？

代码中会解释。

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,L,a[N];

int f[N];

int main(){

	freopen("reinforce.in","r",stdin);

	freopen("reinforce.out","w",stdout);

    n=read(); L=read();

    for(int i=1;i<n;i++) a[i]=read();

    memset(f,0,sizeof(f));

	a[n]=INT_MAX; f[0]=INT_MAX;

	for(int i=0;i<n;i++)

	for(int j=min(i+L,n),t;j>i && f[i]>0;j--) {

		t=min(a[j],f[i]);

		f[j]+=t; f[i]-=t;

		a[j]-=t;

	} printf("%d\n",f[n]);

	return 0;

}

这似乎是 \(O(n \times L)\) 啊，怎么就 \(A\) 了呢？~？~？

确实啊。？？？

但是，对于 \(\texttt{xyx}\) 的水随机数据来说，f[i]>0 这一句，就把所有没有荷叶的剪枝了。

那么，如果是随机数据，一半的状态就没了呀。

你再想想，出题人是让荷叶多呢还是不让荷叶多？

当然不让荷叶多啊，这样才能卡得了暴力，让暴力尝试最远的地方达到极值；然后在几个不多的位置堆积荷叶。

那么，没有荷叶的已经没了，那几个位置（或许是几千个，几万个）算个啥？

你可能觉得，什么？盲猜出题人心理也能 \(A\) 题？

没错。

再举个例子，比方说出题人让你验证一个 \([1,10^8]\) 的答案，没有任何单调性，且时限是 \(500ms\)，告诉你用老年机测。

这时，甲乙丙三位选手都发现验证只需要 \(O(1)\) 的时间，然后：

/*

这是甲的程序

for(int i=1;i<=100000000;i++) {

    // do sth

}

*/

/*

这是乙的程序

for(int i=100000000;i>=1;i--) {

    // do sth

}

*/

/*

最后是丙的程序

for(int i=50000000,j=50000000;i>=1;i--,j++) {

    // do sth

}

*/

最终的结果呢？甲和乙去世了，丙存活了。

为什么呢？

因为，出题人想要同时卡你从两边开始枚举的数据，就会让答案接近中间。

然后，丙猜到了这一点，从中间开始枚举，然后 \(A\) 了。

那你说：出题人同时出三个极限，中间，两边，不就行了？那大家得分不都一样？

不。你不懂出题人的心理。

出题人总是想高级的思维、算法能拿到更多的分数，而丙虽然只是一丢丢的优化，但是感动了出题人的心却抓住了问题的关键。

所以呢，出题人的心理很重要。

回到本题，ta 为了卡暴力，肯定会让你尝试荷叶的次数越来越多达到极值，所以会在不多的位置放极多个荷叶。

而动态规划的时间复杂度与荷叶个数无关。

然后你就巧妙的避开了荷叶个数，成功 \(A\) 题了。

xyx的心理不也就这样子

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,L,a[N];

int f[N];

int main(){

	freopen("reinforce.in","r",stdin);

	freopen("reinforce.out","w",stdout);

    n=read(); L=read();

    for(int i=1;i<n;i++) a[i]=read();

    memset(f,0,sizeof(f));

	a[n]=INT_MAX; f[0]=INT_MAX;

	for(int i=0;i<n;i++) //朴素动态规划

	for(int j=min(i+L,n),t;j>i && f[i]>0;j--) {

		t=min(a[j],f[i]);

		f[j]+=t; f[i]-=t;

		a[j]-=t;

	} printf("%d\n",f[n]);

	return 0;

}

后记：

这场比赛仍然不难，抓住本质即可！

2020.3.23 模拟赛游记 & 题解

T1 metro

T2 awake

T3 contest

T4 homework

T5 pet

T6 fight

T7 spell

T8 reinforce

算法一

算法二

算法三