526互联

2023 CCPC Henan Provincial Collegiate Programming Contest

发布时间 2023-12-10 20:14:38作者: 空気力学の詩

Preface

徐神在训练前宣称要复习计通网，结果最后还是相当于全程参与了我们的训练

这场我纯纯战犯表现，Easy题E狂挂7发最后发现原来是多测没清空干净，直接红温占用中期1h机时

但好在祁神稳切了一手压轴计算几何，同时最后2h把卡着的题都过完了，最后又靠着题数捧杯（唉还在打弱省省赛找自信）

A. 小水獭游河南

签到，枚举最后合法的前缀然后暴力检验即可，因为合法的前缀个数最多只有\(26\)种因此复杂度不会爆

然后因为没看清两个字符串都要非空还WA了一发

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n; char s[N];
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%s",s+1); n=strlen(s+1);
		static int vis[30]; for (i=0;i<26;++i) vis[i]=0;
		bool sign=0; for (i=1;i<n;++i)
		{
			if (vis[s[i]-'a']) break; vis[s[i]-'a']=1;
			bool flag=1; for (RI l=i+1,r=n;l<=r;++l,--r)
			if (s[l]!=s[r]) { flag=0; break; }
			if (flag) { sign=1; break; }
		}
		puts(sign?"HE":"NaN");
	}
	return 0;
}

B. Art for Rest

暴力枚举\(k\)，用调和级数的复杂度大力检验是否合法即可

只要比对前一块的最大值是否小于等于后一块的最小值即可，用个ST表维护下，复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<cctype>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=1e6+5,INF=1e9;
int n,a[N],mn[N][25],mx[N][25],lg[N];
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        Tp inline void read(T& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        #undef tc
}F;
inline int query_min(CI l,CI r)
{
	int k=lg[r-l+1]; return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline int query_max(CI l,CI r)
{
	int k=lg[r-l+1]; return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int main()
{
	//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
	RI i,j; for (F.read(n),i=1;i<=n;++i) F.read(a[i]),mn[i][0]=mx[i][0]=a[i];
	for (lg[0]=-1,i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
	for (j=1;(1<<j)<=n;++j) for (i=1;i+(1<<j)-1<=n;++i)
	mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]),
	mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
	int ans=0; for (j=1;j<=n;++j)
	{
		bool flag=1; int MX=-INF;
		for (i=1;i<=n;i+=j)
		{
			int pos=min(i+j-1,n),cmn=query_min(i,pos);
			if (MX>cmn) { flag=0; break; }
			MX=query_max(i,pos);
		}
		ans+=flag;
	}
	return printf("%d",ans),0;
}

C. Toxel 与随机数生成器

趣味题，被徐神一眼秒了

不难发现如果用的是错误的随机生成器，那么对其求Z函数就会出现\(1000\)以上的值

而随机生成得到的要有这么长的公共前缀概率是\(\frac{1}{2^{1000}}\)，显然不可能

同时由于随机的性质我们不需要真的去写Z函数/Hash，可以直接暴力判断

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6;
char s[N+5];
int main()
{
	RI i,j,k; scanf("%s",s+1); bool flag=1;
	for (i=2;i<=N;++i)
	{
		for (j=1,k=i;j<=N&&k<=N;++j,++k)
		if (s[j]!=s[k]) break;
		if (j-1>=1000) { flag=0; break; }
	}
	return puts(flag?"Yes":"No"),0;
}

D. Toxel 与多彩的宝可梦世界

防AK论文题，做不了一点

E. 矩阵游戏

最红温的一集，因为想卡个cache因此让徐神教了我一种新的滚存的写法，结果因为不熟悉清空没清干净把心态搞炸了

这题做法很简单，直接暴力DP，\(f_{i,j,k}\)表示走到\((i,j)\)，将\(k\)个?改成1后能得到的最大得分，转移显然

但直接这么做时间复杂度虽然没问题但会爆空间，因此需要滚存一下，按照斜对角线的转移顺序将\(i+j\)的和按顺序滚存即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
int t,n,m,cs,f_base[2][N][N<<1]; char s[N][N];
auto f0 = f_base[0];
auto f1 = f_base[1];
int main()
{
	//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k; for (scanf("%d%d%d",&n,&m,&cs),i=1;i<=n;++i) scanf("%s",s[i]+1);
		for (j=0;j<=n;++j) for (k=0;k<=cs;++k) f0[j][k]=f1[j][k]=0;
		if (s[1][1]=='?') f0[1][1]=1; else f0[1][0]=(s[1][1]=='1');
		for (i=3;i<=n+m;++i)
		{
			for (j=1;j<=min(i,n);++j)
			{
				int x=j,y=i-j; if (x<1||x>n||y<1||y>m) continue;
				for (k=0;k<=min(i,cs);++k)
				{
					f1[j][k]=0;
					if (s[x][y]=='?')
					{
						if (x-1>0) f1[j][k]=max(f1[j][k],f0[j-1][k]);
						if (y-1>0) f1[j][k]=max(f1[j][k],f0[j][k]);
						if (x-1>0&&k) f1[j][k]=max(f1[j][k],f0[j-1][k-1]+1);
						if (y-1>0&&k) f1[j][k]=max(f1[j][k],f0[j][k-1]+1);
					} else
					{
						if (x-1>0) f1[j][k]=max(f1[j][k],f0[j-1][k]+(s[x][y]=='1'));
						if (y-1>0) f1[j][k]=max(f1[j][k],f0[j][k]+(s[x][y]=='1'));
					}
					//printf("f[%d][%d][%d] = %d\n",x,y,k,f1[j][k]);
				}
			}
			swap(f0,f1);
		}
		int ans=0; for (k=0;k<=cs;++k) ans=max(ans,f0[n][k]);
		printf("%d\n",ans);
	}
	return 0;
}

F. Art for Last

祁神开场写的，我题目都没看

#include<bits/stdc++.h>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        Tp inline void read(T& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        #undef tc
}F;

const int INF = (int)1e18+5;
const int N = 1e6+5;
int n, k, A[N], B[N];
signed main()
{
	//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
	F.read(n); F.read(k);
	for (int i=1; i<=n; ++i) F.read(A[i]);
	sort(A+1, A+n+1);
	for (int i=1; i<n; ++i) B[i]=A[i+1]-A[i];
	multiset<int> st;
	int ans=INF;
	for (int i=1; i<=n; ++i){
		if (i>=k){
			ans = min(ans, (*st.begin())*(A[i]-A[i-k+1]));
			st.erase(st.find(B[i-k+1]));
		}
		if (i<n) st.insert(B[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

G. Toxel 与字符画

构式模拟题，因为我当时有点红温就扔给祁神写了，祁神也是不负众望瞬秒了此题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

char *tbl[3][10] = {
	{
"................................................................................",
"................................................................................",
"0000000.......1.2222222.3333333.4.....4.5555555.6666666.7777777.8888888.9999999.",
"0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
"0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
"0.....0.......1.2222222.3333333.4444444.5555555.6666666.......7.8888888.9999999.",
"0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
"0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
"0000000.......1.2222222.3333333.......4.5555555.6666666.......7.8888888.9999999.",
"................................................................................",
	},

	{
"............................................................",
"00000.....1.22222.33333.4...4.55555.66666.77777.88888.99999.",
"0...0.....1.....2.....3.4...4.5.....6.........7.8...8.9...9.",
"0...0.....1.22222.33333.44444.55555.66666.....7.88888.99999.",
"0...0.....1.2.........3.....4.....5.6...6.....7.8...8.....9.",
"00000.....1.22222.33333.....4.55555.66666.....7.88888.99999.",
"............................................................",
"............................................................",
"............................................................",
"............................................................",
	},
	
	{
"................................",
"................................",
"........IIIIIII.N.....N.FFFFFFF.",
"...........I....NN....N.F.......",
"=======....I....N.N...N.F.......",
"...........I....N..N..N.FFFFFFF.",
"=======....I....N...N.N.F.......",
"...........I....N....NN.F.......",
"........IIIIIII.N.....N.F.......",
"................................",
	
	},
};

char ans[10][5000]; int pos;

void putsdn(int x){
	for (int i=0; i<10; ++i){
		for (int j=0; j<8; ++j){
			ans[i][pos+j] = tbl[0][i][x*8+j];	
		}
	}
	pos += 8;
}

void putsup(int x){
	for (int i=0; i<10; ++i){
		for (int j=0; j<6; ++j){
			ans[i][pos+j] = tbl[1][i][x*6+j];	
		}
	}
	pos += 6;
}

void putseq(){
	for (int i=0; i<10; ++i){
		for (int j=0; j<8; ++j){
			ans[i][pos+j] = tbl[2][i][j];	
		}
	}
	pos += 8;	
}

void putsINF(){
	for (int i=0; i<10; ++i){
		for (int j=8; j<32; ++j){
			ans[i][pos+j-8] = tbl[2][i][j];	
		}
	}
	pos += 24;	
}

void putsnum(int x, int typ){
	vector<int> vec;
	while (x>0){
		vec.push_back(x%10);
		x/=10;	
	}
	
	for (auto it=vec.rbegin(); it!=vec.rend(); ++it){
		if (1==typ) putsdn(*it);
		else putsup(*it);
	}
}

int calc(int x, int y){
	if (1==x) return x;
	__int128 res=1;
	while (y>0){
		res *= x;
		--y;
		if (res>INF) return -1;	
	}
	return res;
}

signed main(){
//	ios::sync_with_stdio(0); cin.tie(0);
	for (int i=0; i<10; ++i) ans[i][0]='.';
	int t; scanf("%lld", &t);
	while (t--){
		int x, y; scanf("%lld^{%lld}", &x, &y);
		pos=1;
		putsnum(x, 1); putsnum(y, 2);
		putseq();
		int res=calc(x, y);
		if (-1==res) putsINF();
		else putsnum(res, 1);
//		printf("pos=%lld\n", pos);
		for (int i=0; i<10; ++i){
			ans[i][pos]=0;
//			puts(ans[i]);
			for (int j=0; j<pos; ++j) putchar(ans[i][j]); puts("");
		}
		if (t) puts("");
	}
	return 0;	
}

H. Travel Begins

经典因为没特判扔了好久，后面仔细一想原来没考虑\(k>2n\)的情况

最大值的话就考虑先把前\(k-1\)个位置都放上\(0.5\)，然后剩下的数都放最后一个位置

最小值的话同理，先在前面\(k-1\)个位置放\(0.5-\epsilon\)，剩下的数放在最后即可，但要注意一下Corner Case

#include<bits/stdc++.h>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;

class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        Tp inline void read(T& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        #undef tc
}F;

int t, n, k;
signed main(){
	//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
	F.read(t);
	while (t--){
		F.read(n), F.read(k);
		int mn = max(n-(k-1)/2, 0LL); 
		int mx = min(n-(k+1)/2+k, 2*n);
		printf("%lld %lld\n", mn, mx);
	}
	return 0;
}

I. 数正方形

第一眼看很难，仔细一想很简单的一个题

首先容斥一下，用总的\(2\times 2\)正方形个数减去不纯色的正方形个数

不难发现当一个\(2\times 2\)正方形的中心点被任意一个矩形的边经过时，这个正方形就一定不合法了，因此问题转化为统计被至少一条边经过的格点数

不妨再容斥下，因为这题的特殊性质，每个格点最多被两条边经过，因此我们用所有边的边长和减去交点个数即可

这个是个很经典的扫描线问题，用一个树状数组即可维护

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,x_1,y_1,x_2,y_2,L[N],R[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline int get(RI x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x<=2*n;x+=lowbit(x)) bit[x]+=y;
		}
		#undef lowbit
}BIT;
int main()
{
	//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
	RI i; scanf("%d",&n); long long ans=4LL*n*n;
	for (i=1;i<=n;++i)
	{
		scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
		ans-=2LL*(x_2-x_1+y_2-y_1+1);
		L[x_1]=y_1; R[x_1]=y_2; L[x_2]=-y_1; R[x_2]=-y_2;
	}
	for (i=1;i<=2*n;++i)
	{
		auto sgn=[&](CI x)
		{
			return x>0?1:-1;
		};
		ans+=BIT.get(abs(R[i]))-BIT.get(abs(L[i])-1);
		BIT.add(abs(L[i]),sgn(L[i])); BIT.add(abs(R[i]),sgn(R[i]));
	}
	return printf("%lld",ans),0;
}

J. Mocha 沉迷电子游戏

经典计算几何，但是我们有祁神，虽然我连题意都不知道，但我们队就是能一发过这个题，自信.jpg

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LD long double
const LD eps = 1e-8;
const LD PI = acos(-1.0L);

#define RI register int
#define CI const int&
#define Tp template <typename T>
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        Tp inline void read(T& x)
        {
            x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
        }
        #undef tc
}F;

int sgn(LD x){return fabs(x)<=eps ? 0 : (x > eps ? 1 : -1);}
struct Pt{
	int x, y;	
	int crs(Pt b){return x*b.x-y*b.x;}
	int dis2(Pt b){return (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);}
};


signed main(){
//	freopen("J.in", "r", stdin);
	int T; F.read(T);
	while (T--){
		
		Pt A, B, P;
		int v, t, R;
		F.read(P.x); F.read(P.y);
		F.read(A.x); F.read(A.y);
		F.read(B.x); F.read(B.y);
		F.read(v); F.read(t);
		R=v*t;
		int AB2 = A.dis2(B); LD AB = sqrtl(AB2);
		int PA2 = P.dis2(A); LD PA = sqrtl(PA2);
		int R2 = R*R;
		LD dl2 = PA2 - 0.25L*(AB2); LD dl = sqrtl(dl2);
		
		LD sint2 = 1.0L*R2/PA2;
		LD cost2 = 1.0L - sint2;
		LD cost  = sqrtl(cost2);
//		printf("R=%lld AB2=%lld AB=%Lf PA=%Lf dl=%Lf cost2=%Lf cost=%Lf\n", R, AB2, AB, PA, dl, cost2, cost);
		
		LD ans = 0.0L;
		if (sgn(dl2-R2) >= 0){ //圆与直线不相交
			LD alpha = acos(dl/PA);
			LD theta = PI*0.5L - acos(cost);
			LD beta = PI - alpha - theta;
//			printf("alpha=%Lf theta=%Lf beta=%Lf\n", alpha, theta, beta);
			
			ans = dl*AB*0.5L + R*PA*cost + beta*R2;
		}else{
			if (PA2 <= R2) ans = PI*R2;
			else{
				LD theta = PI*0.5L - acos(cost);
				ans = 2*R*PA*cost + (PI-2*theta)*R2;
			}
		}
		printf("%.12Lf\n", ans);
		
	}
	return 0;
}

K. 排列与质数

乍一看很简单，再一想有点难，仔细一想还是很简单的一个构造题

首先很容易想到根据\(2\)是质数这一点尽量把奇偶性相同的数放在一起，但这样交错的地方就不好处理

注意到最不好搞的两个数就是\(2,n-1\)，因此我们考虑先把它们拿出来构造一个合法的解，然后再找个地方塞回去

当\(n\)为奇数时，我们可以这样构造：

\[1,3,5,7,9,\cdots,n-2,n,n-3,n-5,\cdots,8,6,4 \]

当\(n\)为偶数时，我们可以这样构造：

\[1,3,5,7,9,\cdots,n-5,n-3,n,n-2,n-4,\cdots,8,6,4 \]

然后注意到我们总可以把\(2\)放在\(5,7\)的中间，把\(n-1\)放在\(n-4,n-6\)的中间

但要注意这种构造方法只适用于\(n>11\)的情形，因此\(n\le 11\)的情况需要爆搜求解

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,ans[N],cnt;
inline void BF(void)
{
	RI i; for (i=1;i<=n;++i) ans[i]=i;
	auto is_prime=[&](CI x)
	{
		if (x==2||x==3||x==5||x==7) return 1; return 0;
	};
	bool sign=0; do
	{
		bool flag=1; for (i=1;i<=n;++i)
		if (!is_prime(abs(ans[i]-ans[i%n+1]))) { flag=0; break; }
		if (flag) { sign=1; break; }
	} while (next_permutation(ans+1,ans+n+1));
	if (!sign) return (void)(puts("-1"));
	for (i=1;i<=n;++i) printf("%d ",ans[i]);
}
int main()
{
	//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
	RI i; if (scanf("%d",&n),n<=11) BF(); else
	{
		if (n%2==1)
		{
			ans[1]=1; ans[2]=3; ans[3]=5; ans[4]=2; ans[5]=7;
			for (cnt=5,i=9;i<=n-6;i+=2) ans[++cnt]=i;
			for (ans[++cnt]=n-1,i=n-4;i<=n;i+=2) ans[++cnt]=i;
			for (i=n-3;i>=1;i-=2) ans[++cnt]=i;
		} else
		{
			ans[1]=1; ans[2]=3; ans[3]=5; ans[4]=2; ans[5]=7;
			for (cnt=5,i=9;i<=n-3;i+=2) ans[++cnt]=i;
			for (i=n;i>=n-4;i-=2) ans[++cnt]=i;
			for (ans[++cnt]=n-1,i=n-6;i>=1;i-=2) ans[++cnt]=i;
		}
		for (i=1;i<=n;++i) printf("%d ",ans[i]);
	}
	return 0;
}

L. 猜数游戏

好神的题，做不来一点

Postscript

下周开始就开始复习准备期末考了，除了下周末的重庆市赛外可能都没啥训练了

但如果有ECF资格的皇城PK的话再另说，现在也没下定论的说