0228考试总结

  • 辣鸡果然倒数

本次测试略显失败，辣鸡25分滚粗，而三位大佬都是100+

T1宏大的区间

来自$bzoj3226$，数据加强了一下

传送门

这题是一道比较裸的线段树题目，维护方法也很简单

但是考试中没有想到使用线段树维护区间，我想到了一个与线段树复杂度同阶的二分+枚举算法，在写了100多行的if大讨论后认为这题不可做，放弃了。

首先我们把开区间离散一下，比如$(2,5)$我们可以认为是$[2.5,4.5]$

然后把所有坐标乘2，然后认为奇数坐标为开，偶数坐标为闭

然后上线段树即可，注意标记的下传

写好程序后蒟蒻发现读入写挂了。。。果然是我弱啊

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "interval"
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
const int MAXN=524287,D=50;
int tr[MAXN<<2];
char opt[5];
void pushdown(int p){
	if(tr[p]==1||tr[p]==-1){
		tr[p*2]=tr[p*2+1]=tr[p];
	}else
	if(tr[p]==2){
		tr[p*2]=-tr[p*2];
		tr[p*2+1]=-tr[p*2+1];
	}
	tr[p]=-2;
}
void insert(int p,int l,int r,int x,int y,int v){
	if(x>r||y<l)  return;
	if(x<=l&&y>=r)  {tr[p]=v;  return;}
	pushdown(p);
	int mid=(l+r)>>1;
	insert(p<<1,l,mid,x,y,v); insert(p<<1|1,mid+1,r,x,y,v);
}
void updata(int p,int l,int r,int x,int y){
	if(x>r||y<l)  return;
	if(x<=l&&y>=r)  {tr[p]=-tr[p]; return;}
	pushdown(p);
	int mid=(l+r)>>1;
	updata(p<<1,l,mid,x,y);  updata(p<<1|1,mid+1,r,x,y);
}
void clear(int p,int l,int r){
	if(l>=r)  return;
	pushdown(p);
	int mid=(l+r)>>1;
	clear(p<<1,l,mid);  clear(p<<1|1,mid+1,r);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	memset(tr,-1,sizeof(tr));
	while(scanf("%s",opt+1)!=EOF){
		char ch=getchar();
		while(ch!='('&&ch!='[') ch=getchar();
		int flag=(ch=='('),a,b;  scanf("%d,%d",&a,&b);
		a=a*2+flag;  ch=getchar();
		while(ch!=')'&&ch!=']') ch=getchar();
		flag=(ch==')'); b=b*2-flag;		
		if(opt[1]=='U')  insert(1,0,MAXN,a,b,1);
		else if(opt[1]=='I'){
			if(a)  insert(1,0,MAXN,0,a-1,-1);
			insert(1,0,MAXN,b+1,MAXN,-1);
		}
		else if(opt[1]=='D')  insert(1,0,MAXN,a,b,-1);
		else if(opt[1]=='C'){
			if(a)  insert(1,0,MAXN,0,a-1,-1);
			insert(1,0,MAXN,b+1,MAXN,-1);
			updata(1,0,MAXN,a,b);
		}
		else updata(1,0,MAXN,a,b);
	}
	clear(1,0,MAXN);  tr[MAXN]=-1; int flag=1;
	for(int i=0;i<=MAXN;++i){
		if(tr[i+MAXN+1]==1&&tr[i+MAXN]==-1){
			if(flag){
				printf(i&1?"(":"[");printf("%d,",i>>1);
				flag=0; continue;
			}
			printf(" ");printf(i&1?"(":"[");printf("%d,",i>>1);
		}
		if(tr[i+MAXN+1]==-1&&tr[i+MAXN]==1){
			printf("%d",i>>1);printf(i&1?"]":")");
		}
	}
	if(flag)  puts("empty set"); 
	return 0;
}

-
-
-

T2滑稽

题目大意：有4个数组A,B,C,D，一个四元组是滑稽的当且仅当每个元素来自不同的数组，且他们的乘积模P为1，其中P为质数。求有多少个滑稽的四元组。

说起这题我就心痛啊，由于没有开$long long$，我的正解只拿到了$25$分

这题做法很简单，将$A[i]\times {B[j]}$的值存入一个桶中，然后枚举$C[i]\times {D[j]}$，求其逆元，然后统计答案就行了

虽然评测时开$O2$，但是本地测试使用$map$约为$1.4s$，所以我将$map$改成了二分，成功卡进$0.6s$

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<map>
#define FILE "huaji"
using namespace std;
typedef long long ll;
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline ll read(){
		ll x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
ll n,mod,cnt,ans,a[1010],b[1010],c[1010],d[1010],A[1001000],B[1001000];
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b) {x=1; y=0; return;}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
}
ll findl(ll v){
	ll l=1,r=cnt,temp(0);
	while(l<=r){
		ll mid=(l+r)>>1;
		if(B[mid]<v)  l=mid+1;
		else temp=mid,r=mid-1;
	}
	return temp;
}
ll findr(ll v){
	ll l=1,r=cnt,temp(0);
	while(l<=r){
		ll mid=(l+r)>>1;
		if(B[mid]<=v)  {temp=mid; l=mid+1;}
		else r=mid-1;
	}
	return temp;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  mod=read();
	for(ll i=1;i<=n;++i)  a[i]=read()%mod;
	for(ll i=1;i<=n;++i)  b[i]=read()%mod;
	for(ll i=1;i<=n;++i)  c[i]=read()%mod;
	for(ll i=1;i<=n;++i)  d[i]=read()%mod;
	for(ll i=1;i<=n;++i)
		for(ll j=1;j<=n;++j)
			A[++cnt]=a[i]*b[j]%mod;
	cnt=0;
	for(ll i=1;i<=n;++i)
		for(ll j=1;j<=n;++j)
			B[++cnt]=c[i]*d[j]%mod;
	sort(B+1,B+cnt+1);
	for(ll i=1;i<=n*n;++i){
		if(A[i]==0)  continue;
		ll x,y; exgcd(A[i],mod,x,y);
		x=(x%mod+mod)%mod;
		ll l=findl(x),r=findr(x);
		if(!l||!r)  continue;
		ans+=r-l+1;
	}
	printf("%lld\n",ans);
	return 0;
}

T3吨吨反应炉

来自$bzoj4593$

传送门

这题数据略水，随便写一发就拿到了$bzoj$的$rank1$（主要还是写的人少）

正解：树形dp

我们用$f[i]$表示i节点不引爆父亲的情况下的最少花费，$h[i]$表示i节点在引爆父亲的情况下的最少花费

那么显然$h[i]<=f[i]$恒成立

对于节点$x$以及它的儿子节点$y$，如果$f[y]-h[y]>=c[y]$，那么我们用$h[y]$来转移，否则我们用$f[y]$来转移

就这样瞎搞搞就行了

当然正解不是这样子的，但是由于数据水，所以这样做就能水过。

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "fusion"
#define MAXN 100010
using namespace std;
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
struct node{int y,next;}e[MAXN*2];
int n,len,ans,Link[MAXN],d[MAXN],c[MAXN],vis[MAXN],f[MAXN],h[MAXN],boom[MAXN],fa[MAXN];
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void dp(int x){
	int temp=0,sum=d[x]; vis[x]=1;
	for(int i=Link[x];i;i=e[i].next)
		if(!vis[e[i].y]&&c[e[i].y]){
			fa[e[i].y]=x; dp(e[i].y);
			if(f[e[i].y]-h[e[i].y]>=c[e[i].y])  temp+=h[e[i].y];
			else temp+=f[e[i].y],sum-=c[e[i].y];
		}
	f[x]=temp+sum;
	h[x]=temp+sum-c[fa[x]];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)  d[i]=read();
	for(int i=1;i<=n;++i)  c[i]=read();
	for(int i=1;i<n;++i){
		int x=read(),y=read();
		insert(x,y); insert(y,x);
		boom[x]+=c[y];  boom[y]+=c[x];
	}
	for(int i=1;i<=n;++i) if(!c[i]) ans+=max(d[i]-boom[i],0);
	for(int i=1;i<=n;++i) if(c[i]&&!vis[i]) fa[i]=0,c[0]=0,dp(i),ans+=f[i];
	printf("%d\n",ans);
	return 0;
}

本文标题:0228考试总结

文章作者:chty

发布时间:2017年02月28日 - 21时28分

最后更新:2018年03月02日 - 17时33分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. T1宏大的区间
  2. 2. T2滑稽
  3. 3. T3吨吨反应炉
,