ZROIDay2-比赛解题报告

ZROIDay2-比赛解题报告

版权原因不提供题面信息

序

这几天作息有点鬼畜,虽然昨晚很晚睡但是早上精神还不错,看到题发现T1很友好？T2woc这暴力都好难打?T3多项式？！这样下去比赛会不会出现更多高端操作，恐怕凉凉

A

感谢出题人,暴力好打分又多,正解也不难想,这题基本上部分分都打了一遍

50pts

对于每一个炮将其所在的所在的交叉行（暂且这么说）$O(1)$ 标记，然后$O(N^2)$遍历一遍统计就好了

70pts

核心思想是计算出放一个炮新增的贡献,即它能覆盖的点数减去已经覆盖的点数,最后$N^2$减去总和既是答案

拿这部分分还花了不少功夫,终于运用人类智慧找出一些规律,也就是对于一个炮$(x,y)$,它左斜行和右斜行能覆盖的点的个数,然后又发现对于一个确定的左斜行（即确定的$x+y$），可以通过$x,y$计算出与它有公共点的左斜行的$x-y$的相关信息，于是新增一个炮,在他所在的左斜行加上+1标记,加上左斜行覆盖点数,在枚举与左斜行有公共点的右斜行,假设这个右斜行已有标记,则贡献-1。对于右斜行也类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <queue>
#include <cmath>
#define ll long long 
#define ri register int 
#define ull unsigned loong long 
const int maxn=100005;
const int inf=0x7ffffffff;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return;
}
int n,m;
int p[maxn<<1],q[maxn<<1];
int cntp=0,cntq=0;
inline void solve_2(){
	int x,y;ll ans=0;
	while(m--){
      read(x),read(y);
      if(!p[x+y]){
      	p[x+y]=1;
      	cntp++;
      	if(x+y<=n){
      	  int k=x+y-2;//
      	  ans+=x+y-1;//ok
      	  for(ri i=-k;i<=k;i+=2){
      	  	ans-=q[i+n];
		  }
		}
      	else{
      	  int k=n*2-(x+y);
      	  ans+=k+1;
      	  for(ri i=(x+y)-n*2;i<=n*2-(x+y);i+=2){
      	  	ans-=q[i+n];
		  }
		}
	  }
	  if(!q[x-y+n]){
	  	q[x-y+n]=1;
	  	cntq++;
	  	if(x-y<=0){
	  		int k=x-y+n-1;
	  		ans+=n+(x-y);
	  		for(ri i=n+1-k;i<=n+1+k;i+=2){
	  			ans-=p[i];
			}
		}
		else{
			int k=x-y-n+1;
			ans+=n-(x-y);
			for(ri i=n+1+k;i<=n+1-k;i+=2){
				ans-=p[i];
			}
		}
	  }
	}
	printf("%lld\n",1ll*n*n-ans);
}
int main(){ 
	int x,y;
	ll ans=0;
	freopen("dat.in","r",stdin);
	freopen("bf.out","w",stdout);
	read(n),read(m);
    solve_2();
	return 0;
}

100pts

发现每个左斜行能确定的右斜行的x-y范围是连续的的奇数或偶数,于是用线段树维护标记和区间和,复杂度$O( m $ $log $ $N)$

然后鬼畜的是刚码完大样例过不了,以为是奇偶数搞错,魔改了半天后发现有一个判定没写到循环里。。。然后又魔改还是不对,于是开始对拍手动gdb调试,发现有一颗线段树操作的上限因为是x+y要设成$2n$,查完这个错后据考试结束还有不到半小时,真TM刺激

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <queue>
#include <cmath>
#define ll long long 
#define ri register int 
#define ull unsigned loong long 
const int maxn=200015;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return;
}
int n,m,N;
bool p[maxn<<1],q[maxn<<1];
int L,R,dta,t;
struct Segment_Tree_1{
	int ns[maxn<<2],odds[maxn<<2];//fff是没用的
	void update(int now,int l,int r,int fff){//printf("%d****%d\n",l,r);
		if(l==r){
			if(l&1)odds[now]++;
			else ns[now]++;
			return ;
		}
		int mid=(l+r)>>1;
		if(t<=mid)update(now<<1,l,mid,fff);
		else update(now<<1|1,mid+1,r,fff);
		odds[now]=odds[now<<1]+odds[now<<1|1];
		ns[now]=ns[now<<1]+ns[now<<1|1];
		return ;
	}
	int odd_query(int now,int l,int r){
		if(L<=l&&r<=R){
			return odds[now];
		}
		int mid=(l+r)>>1,ans=0;
		if(L<=mid)ans+=odd_query(now<<1,l,mid);
		if(mid<R)ans+=odd_query(now<<1|1,mid+1,r);
		return ans;
	}
	int n_query(int now,int l,int r){
		if(L<=l&&r<=R){
			return ns[now];
		}
		int mid=(l+r)>>1,ans=0;
		if(L<=mid)ans+=n_query(now<<1,l,mid);
		if(mid<R)ans+=n_query(now<<1|1,mid+1,r);
		return ans;
	}
}P;
struct Segment_Tree_2{
	int ns[maxn<<1],odds[maxn<<1];
	void update(int now,int l,int r,int fff){
		if(l==r){			
			if(l&1)odds[now]++;
			else ns[now]++;
			return ;
		}
		int mid=(l+r)>>1;
		if(t<=mid)update(now<<1,l,mid,fff);
		else update(now<<1|1,mid+1,r,fff);
		odds[now]=odds[now<<1]+odds[now<<1|1];
		ns[now]=ns[now<<1]+ns[now<<1|1];
		return ;
	}
	int odd_query(int now,int l,int r){
		if(L<=l&&r<=R){
			return odds[now];
		}
		int mid=(l+r)>>1,ans=0;
		if(L<=mid)ans+=odd_query(now<<1,l,mid);
		if(mid<R)ans+=odd_query(now<<1|1,mid+1,r);
		return ans;
	}
	int n_query(int now,int l,int r){
		if(L<=l&&r<=R){
			return ns[now];
		}
		int mid=(l+r)>>1,ans=0;
		if(L<=mid)ans+=n_query(now<<1,l,mid);
		if(mid<R)ans+=n_query(now<<1|1,mid+1,r);
		return ans;
	}
}Q1,Q2;
inline void solve(){
	int x,y;ll ans=0;
	while(m--){
      read(x),read(y);
      if(!p[x+y]){
      	t=x+y;
      	P.update(1,1,N,0);
		p[x+y]=1;
      	if(x+y<=n){
      	  int k=x+y-2;
      	  ans+=x+y-1;
      	  int lxl=-k,rr=k;
      	  if(lxl==rr){
      	  	L=R=0;
			if(q[n])ans--;
		  }
      	  else {
      	    L=0,R=abs(lxl);
			if(R&1)ans-=Q1.odd_query(1,0,n);
			else ans-=Q1.n_query(1,0,n);
		    L=1,R=rr;
		    if(R&1)ans-=Q2.odd_query(1,1,n);
		    else ans-=Q2.n_query(1,1,n);
		  }
		}
      	else{
      	  int k=n*2-(x+y);
      	  ans+=k+1;
      	  int lxl=(x+y)-n*2,rr=n*2-(x+y);
      	  //printf("2--%d ",ans);
      	  if(lxl==rr){
      	  	L=R=0;
			if(q[n])ans--;//ans-=Q1.n_query(1,0,n);
		  }
      	  else {
      	    L=0,R=abs(lxl);
			if(R&1)ans-=Q1.odd_query(1,0,n);
			else ans-=Q1.n_query(1,0,n);
		    L=1,R=rr;
		    if(R&1)ans-=Q2.odd_query(1,1,n);
		    else ans-=Q2.n_query(1,1,n);
		  }
		}		
	  }
	  if(!q[x-y+n]){
	  	t=x-y;
	  	if(t<=0){
	  		t=abs(t);
		    Q1.update(1,0,n,1);
		}
		else {
			Q2.update(1,1,n,1);
		}
	  	q[x-y+n]=1;
	  	if(x-y<=0){
	  		int k=x-y+n-1;
	  		ans+=n+(x-y);
	  		L=n+1-k,R=n+1+k;
	  		//printf("3--%d ",ans);
	  		if(L&1)ans-=P.odd_query(1,1,N);
	  		else ans-=P.n_query(1,1,N);
		}
		else{
			int k=x-y-n+1;
			ans+=n-(x-y);
			L=n+1+k,R=n+1-k;
			//printf("%d %d\n",L,R);
			//printf("4--%d ",ans);
			if(R&1)ans-=P.odd_query(1,1,N);
			else {
			ans-=P.n_query(1,1,N);
	 	    }
		 }
	   }
	}
	printf("%lld\n",1ll*n*n-ans);
}
int main(){
	int x,y;
	ll ans=0;
	double st=clock();
	freopen("dat.in","r",stdin);
	freopen("std.out","w",stdout);
	read(n),read(m);N=n*2;
    solve();
    double ed=clock();
    printf("%lf\n",ed-st);
	return 0;
}

B

毒瘤期望,n=4的暴力枚举都及其毒瘤,没时间打

题解暂时没搞懂

C

多项式算了吧，考场上暴力模拟感谢出题人拿了40pts,题解推了一大波东西然后什么阶乘卷积。。。

贴一份老师的std

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<string>
#include<assert.h>
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)j;i>=(int)k;i--)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long LL;
const int P=998244353;
const int G=3;
const int N=310000;
inline int Pow(int a,int b){
	int c=1;
	for(;b;b>>=1,a=a*1ll*a%P)if(b&1)c=c*1ll*a%P;
	return c;
}
int w[2][N];
int rev[N];
inline void fft(int *a,int n,int ff){
	rep(i,0,n-1)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1)
	for(int j=0,t=n/(i<<1);j<n;j+=(i<<1))
	for(int k=0,l=0;k<i;k++,l+=t){
		int x=a[i+j+k]*1ll*w[ff][l]%P;
		int y=a[j+k];
		a[j+k]=(x+y)%P;
		a[i+j+k]=(y+P-x)%P;
	}
	if(ff==1){
		int v=Pow(n,P-2);
		rep(i,0,n-1)a[i]=a[i]*1ll*v%P;
	}
}
inline void initfft(int n){
	rep(i,0,n-1){
		int x=i;
		int y=0;
		for(int k=1;k<n;k<<=1,x>>=1)(y<<=1)|=(x&1);
		rev[i]=y;
	}
	w[0][0]=w[1][0]=1;
	int V=Pow(G,(P-1)/n);
	int VV=Pow(V,P-2);
	rep(i,1,n-1){
		w[0][i]=w[0][i-1]*1ll*V%P;
		w[1][i]=w[1][i-1]*1ll*VV%P;
	}
}
int a[N],n;
int fac[N],inv[N];
int ans[N];
inline void init(int n){
	fac[0]=1;rep(i,1,n)fac[i]=fac[i-1]*1ll*i%P;
	inv[n]=Pow(fac[n],P-2);per(i,n-1,0)inv[i]=inv[i+1]*1ll*(i+1)%P;
}
int main(){
	init(200000);
	scanf("%d",&n);
	assert(1<=n&&n<=100000);
	rep(i,0,n-1){
		scanf("%d",&a[i]);
		assert(0<=a[i]&&a[i]<P);
	}
	rep(i,0,n-1)a[i]=a[i]*1ll*fac[i]%P;

	initfft(1<<18);
	fft(a,1<<18,0);
	rep(i,0,(1<<18)-1)a[i]=a[i]*1ll*a[i]%P;
	fft(a,1<<18,1);

	rep(d,0,n-1){
		ans[d]=a[n-1+d];
		ans[d]=ans[d]*1ll*Pow(2,d)%P;
		ans[d]=ans[d]*1ll*inv[d]%P;
	}
	rep(i,0,n-1)printf("%d ",ans[i]);
	return 0;
}