\(CSP-J2022\) 题解报告

\(T1\) 乘方:

发现 \(2^{32}>10^9\)，所以这个题只需要特判 \(a=1\) 的情况为 \(1\)，其他直接枚举再判断即可。

Code：

// QwQ

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

#define fi first

#define se second

typedef pair<int,int> PII;

typedef long long LL;

template <typename T> void inline read(T& x)

{

	x=0; int f=1; char ch;

	while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;

	while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();

	x*=f;

}

int main()

{

	int a,b; read(a); read(b);

	if(a==1) printf("1\n");

	else

	{

		LL ret=1;

		for(int i=1;i<=b;ret*=a,i++)

			if(ret>1e9) {puts("-1");return (0-0);}

		if(ret>1e9) {puts("-1");return (0-0);}

		printf("%lld\n",ret);

	}

	return (0-0); // QwQ

}

\(T2\) 解密：

把第二个式子拆开可以得到 \(e\times d=p\times q-p-q+2\)

由第一个式子得到 \(p=n/q\)，然后代进去 \(e\times d=n-\frac{n}{q}-q+2\)

整理 \(-q^2-(n-e\times d+2)q-n=0\)。

由初中知识可知 \(\Delta =(n-e\times d+2)^2-4n<0\) 则无实根，输出 NO。

求出两根后，代入给定式子验证即可。

Code：

// QwQ

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define fi first

#define se second

typedef pair<int,int> PII;

typedef long long LL;

template <typename T> void inline read(T& x)

{

	x=0; int f=1; char ch;

	while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;

	while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();

	x*=f;

}

void solve()

{

	LL n,d,e; read(n); read(d); read(e);

	LL p=n-e*d+2;

	if(p*p-4*n<0) puts("NO");

	else

	{

		LL x=sqrt(p*p-4*n);

		LL s1=(p-x)/2,s2=(p+x)/2;

		if(s1*s2!=n) puts("NO");

		else if((s1-1)*(s2-1)+1!=e*d) puts("NO");

		else printf("%lld %lld\n",s1,s2);

	}

}

int main()

{

	int T; read(T);

	while(T--) solve();

	return (0-0); // QwQ

}

\(T3\) 逻辑表达式：

做过 \(CSP-J2020 T3\) 的应该都看得出来，这两个题本质差不多，都是建表达式树，当一个短路操作发生，只需要舍去他的右儿子即可，不难实现。

Code：

// QwQ

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <stack>

#include <map>

#include <string>

#include <iostream>

using namespace std;

#define fi first

#define se second

typedef pair<int,int> PII;

typedef long long LL;

template <typename T> void inline read(T& x)

{

	x=0; int f=1; char ch;

	while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;

	while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();

	x*=f;

}

const int N=1e6+5;

struct tree

{

	int l,r,op,v;

}e[N];

string opt;

int n,cnt,ret[2];

map <char,int> mp={{'|',1},{'&',2}};

stack <int> num;

stack <char> op;

void get()

{

	int r=num.top(); num.pop();

	int l=num.top(); num.pop();

	char c=op.top(); op.pop();

	++cnt;

	e[cnt].op=(c=='|'?1:0);

	e[cnt].l=l,e[cnt].r=r;

	if(c=='|') e[cnt].v=e[l].v|e[r].v;

	else e[cnt].v=e[l].v&e[r].v;

	num.push(cnt);

	//printf("kk%d %d %c\n",a,b,c);

	//printf("%d %d\n",cnt[0],cnt[1]);

}

void dfs(int x)

{

	//printf("%d %d %d %d %d %d\n",x,e[x].op,e[x].l,e[e[x].l].v,e[x].r,e[x].v);

	if(e[x].op==0)

	{

		if(!e[e[x].l].v) ret[0]++,dfs(e[x].l);

		else dfs(e[x].l),dfs(e[x].r);

	}

	else if(e[x].op==1)

	{

		if(e[x].op && e[e[x].l].v) ret[1]++,dfs(e[x].l);

		else dfs(e[x].l),dfs(e[x].r);

	}

}

int main()

{

	ios::sync_with_stdio(0);

	cin>>opt; opt='('+opt+')'; n=opt.length();

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

	{

		if(opt[i]=='(') op.push(opt[i]);

		else if(opt[i]=='&')

		{

			while(!op.empty() && op.top()=='&') get();

			op.push(opt[i]);

		}

		else if(opt[i]=='|')

		{

			while(!op.empty() && op.top()!='(') get();

			op.push(opt[i]);

		}

		else if(opt[i]==')')

		{

			while(!op.empty() && op.top()!='(') get();

			op.pop();

	    }

	    else

	    {

	    	++cnt;

	    	e[cnt].v=opt[i]-'0';

	    	e[cnt].op=-1;

	    	num.push(cnt);

	    	//printf("%d %d\n",cnt[0],cnt[1]);

	    }

	}

	cout<<e[num.top()].v<<"\n";

	dfs(num.top());

	cout<<ret[0]<<" "<<ret[1]<<"\n";

	return (0-0); // QwQ

}

T4 上升点列：

此题可以 \(dp\)，设状态 \(dp_{i,l}\) 表示到了第 \(i\) 个点，新加了 \(l\) 个点的最多点数。

方程：\(dp_{i,l}=max(dp_{i,l},dp_{j,l-dis(i,j)+1}+dis(i,j))\)

首先要把所有点排序，第一维枚举走到哪个点 \(i\)，第二维枚举由哪个点 \(j\) 走到当前点 \(i\)，第三维枚举新加的点数 \(l\)。

时间复杂度：\(O(n^2k)\)，空间复杂度：\(O(nk)\)。足以通过本题。

Code：

// QwQ

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

#define fi first

#define se second

typedef pair<int,int> PII;

typedef long long LL;

template <typename T> void inline read(T& x)

{

	x=0; int f=1; char ch;

	while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;

	while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();

	x*=f;

}

const int N=505;

PII a[N];

int n,k,dp[N][N];

int get(int x,int y)

{

	if(a[x].fi-a[y].fi<0) return -1;

	if(a[x].se-a[y].se<0) return -1;

	return a[x].fi-a[y].fi+a[x].se-a[y].se;

}

int main()

{

	read(n); read(k);

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

	sort(a+1,a+1+n);

	//puts("caonima");

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

	for(int i=1;i<=n;i++) dp[i][0]=1;

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

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

			for(int l=0;l<=k;l++)

				if(get(i,j)==1)

					dp[i][l]=max(dp[i][l],dp[j][l]+1);

				else if(get(i,j)!=-1 && get(i,j)-1<=l)

					dp[i][l]=max(dp[i][l],dp[j][l-get(i,j)+1]+get(i,j));

					/*

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

		for(int j=0;j<=k;j++)

			printf("%d%c",dp[i][j]," \n"[j==k]);

			*/

	int ret=0;

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

		for(int j=0;j<=k;j++)

			ret=max(ret,dp[i][j]+k-j);

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

	return (0-0); // QwQ

}

尾：欢迎大家来吊打。

CSP-J2022 题解报告的相关教程结束。