你最愿意做的哪件事，才是你的天赋所在

0%

发表于 更新于 Valine：

二次剩余

对于这个方程，求出满足的x。

引理1

首先来看一个符号

这个符号叫做勒让德符号，这个符号里有两个值，一个是n,一个是p。假设p为奇素数，且n无法整除p时，他有以下定义

当$(\frac{n}{p})=1$时，存在一个x使得n是p的二次剩余
当$(\frac{n}{p})=-1$时，不存在一个x使得n是p的二次剩余
例如，当p=11时。$(\frac{1}{11})=1^{\frac{11-1}{2}}=1(mod 11)$所以1是11的二次剩余
而，$(\frac{3}{11})=3^{\frac{11-1}{2}}=-1(mod 11)$所以3是11的二次非剩余
现在来证明

阅读全文 »

发表于 更新于 Valine：

题目连接

2019Xuzhou-pretest-I(二维偏序树状数组)

思路

先预处理处第1-第i个满足的集合
这个过程中，考虑从后往前删除的过程中何时需要减去，世界上对删除的每个数，判断因子是否已经被删除，
若没有，则贡献-1，若已被删除就不用管。
然后处理查询，使用二维偏序，对查询从左端点排序，由于删除右边的答案我们已经有了，所以我们考虑删除左边的。
这里要用树状数组维护一个前缀和。

阅读全文 »

发表于 更新于 Valine：

题目链接

Poj1177

思路

裸的线段树扫描线题目了。
首先考虑把单独的一条边独立出来，然后思考周长怎么求?
很显然，在加入一条横边时，我们考虑它的贡献，也就是之前的横轴上没有覆盖的区域。
考虑竖边，竖边一定由相邻两条横着的边构成，我们取上一条加入的横边与当前考虑加入的横边。
他们各自的高也就是一段竖边的高，但是有多少段呢？画一下可以发现，有多少段取决于全部区域内有多少块不连接的区域，例如[2,3],[5,6]，则一共有4条，因为每块区域提供两条，而[1,2][2,4]的话只有两条，因为只有1块区域。
注意：这里讨论的竖边并不是长方形的完全竖边，而是我们把它分段了，一段一段的加上去。
经过上面分析，我们线段树上需要维护的有
1.当前覆盖的区域的长度和val
2.区域的块数，也就是不相连接的部分的数量num
3.当前区域被覆盖的次数s,如果s为0，则这个点对应的区间已经扫描过了，答案已经加上了。s不可能小于0.

阅读全文 »

发表于 更新于 Valine：

题目链接

HDU4553

思路

建立两颗线段树，发现NS的可以用DS的，而DS确不可以用女神的，在更新和查询的时候判断一下就好。
然后是区间连续和的板子题了。
前缀后缀，中间找。
以及两个lazy标记的影响要注意就好了
查询的时候，先查左，再到中间，最后右边。因为要求起始标号最小。

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5+10;
struct node
{
	int l,r;
	int pre,suf;
	int val;
	bool clear;
	bool full;
	int len()
	{
		return r-l+1;
	}
}DStree[maxn<<2],NStree[maxn<<2];
void PushUp(node *tree,int rt)
{
	tree[rt].pre=tree[rt<<1].pre;
	tree[rt].suf=tree[rt<<1|1].suf;
	if(tree[rt].pre==tree[rt<<1].len())tree[rt].pre+=tree[rt<<1|1].pre;
	if(tree[rt].suf==tree[rt<<1|1].len())tree[rt].suf+=tree[rt<<1].suf;
	tree[rt].val=max(tree[rt<<1|1].val,max(tree[rt<<1].val,tree[rt<<1].suf+tree[rt<<1|1].pre));
}
void PushDown(node *tree,int rt)
{   if(tree[rt].len()==1)return ;
	if(tree[rt].clear)
	{
		tree[rt<<1].pre=tree[rt<<1|1].pre=tree[rt<<1].suf=tree[rt<<1|1].suf=tree[rt<<1].val=tree[rt<<1|1].val=0;
		tree[rt<<1|1].clear=tree[rt<<1].clear=true;
		tree[rt<<1|1].full=tree[rt<<1].full=false;
		tree[rt].clear=false;
	}
	if(tree[rt].full)
	{
		tree[rt<<1].pre=tree[rt<<1].suf=tree[rt<<1].val=tree[rt<<1].len();
		tree[rt<<1|1].pre=tree[rt<<1|1].suf=tree[rt<<1|1].val=tree[rt<<1|1].len();
		tree[rt<<1].full=tree[rt<<1|1].full=true;
		tree[rt<<1|1].clear=tree[rt<<1|1].clear=false;
		tree[rt].full=false;
	}
}
void build(node *tree,int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].pre=tree[rt].suf=tree[rt].val=tree[rt].len();
	tree[rt].full=0;
	tree[rt].clear=0;
	if(l==r)
	{
		tree[rt].val=tree[rt].suf=tree[rt].pre=1;
		return ; 
	}
	int mid = (l+r)>>1;
	build(tree,rt<<1,l,mid);
	build(tree,rt<<1|1,mid+1,r); 
	PushUp(tree,rt);
}
void Update(node *tree,int rt,int l,int r,int c)
{
	if(tree[rt].l>r||tree[rt].r<l)return ;
	if(tree[rt].l>=l&&tree[rt].r<=r)
	{
		if(c==1)
		{
			tree[rt].full=1;
			tree[rt].clear=0;
			tree[rt].pre=tree[rt].suf=tree[rt].val=tree[rt].len();
		}
		else
		{
			tree[rt].full=0;
			tree[rt].clear=1;
			tree[rt].pre=tree[rt].suf=tree[rt].val=0;
		}
		return ;
	}
	PushDown(tree,rt);
	Update(tree,rt<<1,l,r,c);
	Update(tree,rt<<1|1,l,r,c);
	PushUp(tree,rt);
}
int query(node *tree,int rt,int len)
{   if(tree[rt].val<len)return -1;
	if(tree[rt].l==tree[rt].r)return tree[rt].l;
	PushDown(tree,rt);
	int mid = (tree[rt].r+tree[rt].l)>>1;
	if(tree[rt<<1].val>=len)
	return query(tree,rt<<1,len);
	else if(tree[rt<<1].suf+tree[rt<<1|1].pre>=len)return mid-tree[rt<<1].suf+1;
	else query(tree,rt<<1|1,len);
}
int main()
{
	int t;
	scanf("%d",&t);
	char s[100];
	for(int cas=1;cas<=t;cas++)
	{
		printf("Case %d:\n",cas);
		int n,m;
		scanf("%d %d",&n,&m);
		build(DStree,1,1,n);
		build(NStree,1,1,n);
		while(m--)
		{
			scanf("%s",s);
			if(s[0]=='D')
			{
				int x;
				scanf("%d",&x);
				if(DStree[1].val<x)printf("fly with yourself\n");
				else
				{
					int ans = query(DStree,1,x);
					printf("%d,let's fly\n",ans);
					Update(DStree,1,ans,ans+x-1,0);
				}
			}
			if(s[0]=='N')
			{
				int x;
				scanf("%d",&x);
				if(DStree[1].val<x)
				{
				if(NStree[1].val<x) printf("wait for me\n");
				else
				{
					int ans = query(NStree,1,x);
					printf("%d,don't put my gezi\n",ans);
					Update(DStree,1,ans,ans+x-1,0);
					Update(NStree,1,ans,ans+x-1,0);
				}
			    }
			    else
			    {
			    	int ans = query(DStree,1,x);
					printf("%d,don't put my gezi\n",ans);
					Update(DStree,1,ans,ans+x-1,0);
					Update(NStree,1,ans,ans+x-1,0);
				}
			}
			if(s[0]=='S')
			{
				int x,y;
				scanf("%d %d",&x,&y);
				printf("I am the hope of chinese chengxuyuan!!\n");
				Update(DStree,1,x,y,1);
				Update(NStree,1,x,y,1);
			}
		}
	}
}

发表于 Valine：

java反射机制

这是一点与c++不同的地方，java有一个所有类的超类，也就是Object，不论是系统自带类，或者你自己写的，都是这个类的子类。
还有一个类Class，这个类跟反射机制息息相关。

反射机制作用

1.在运行时判断任意一个对象所属的类；
2.在运行时构造任意一个类的对象；
3.在运行时判断任意一个类所具有的成员变量和方法；
4.在运行时调用任意一个对象的方法；生成动态代理。
第一点，可以获得当前对象是什么类
第二点，既然知道是什么类了，那么我就可以自己构造一个实例对象
第三点，我知道你是什么类了，就可以找到你的成员以及方法。
第四点，我不仅知道你的方法，我还能够用你的方法

阅读全文 »

发表于 更新于 Valine：

题目链接

HDU4614

思路

首先建好线段树，功能是删除连续的1，查询区间和，插入1.就够了
然后二分找出起点，再二分找出终点即可。
注意的是，线段树lazy标记一定要注意两者之间的逻辑关系。

代码实现

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
#include<bits/stdc++.h>
using namespace std;
const int N =5e4+10;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int n,m;
struct node
{
	int l,r;
	int val;
	bool put;
	bool in;
	int len()
	{
		return r-l+1;
	}
}tree[N<<2];
void PushUp(int rt)
{
	tree[rt].val=(tree[rt<<1].val+tree[rt<<1|1].val);
}
void PushDown(int rt)
{
	if(tree[rt].put)
	{
		tree[rt<<1].put=tree[rt<<1|1].put=tree[rt].put;
		tree[rt<<1].in=tree[rt<<1|1].in=false;
		tree[rt<<1|1].val=tree[rt<<1].val=0;
		tree[rt].put=0;
	}
	if(tree[rt].in)
	{
		tree[rt<<1].in=tree[rt<<1|1].in=tree[rt].in;
		tree[rt<<1].put=tree[rt<<1|1].put=false;
		tree[rt<<1].val=tree[rt<<1].len();
		tree[rt<<1|1].val=tree[rt<<1|1].len();
		tree[rt].in=0;
	}
}
void build(int l,int r,int rt)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].val=0;
	tree[rt].put=tree[rt].in=false;
	if(l==r)
	{
		tree[rt].val=0;
		return ;
	} 
	int mid = (l+r)>>1;
	build(lson);
	build(rson);
	PushUp(rt);
}
void Update(int rt,int l,int r)
{
	if(tree[rt].r<l||tree[rt].l>r)return ;
	if(tree[rt].l>=l&&tree[rt].r<=r)
	{
		tree[rt].put=0;
		tree[rt].in=1;
		tree[rt].val=tree[rt].len();
		return ;
	}
	PushDown(rt);
	Update(rt<<1,l,r);
	Update(rt<<1|1,l,r);
    PushUp(rt);
}
void clear(int rt,int l,int r)
{
	if(tree[rt].r<l||tree[rt].l>r)return ;
	if(tree[rt].l>=l&&tree[rt].r<=r)
	{
		tree[rt].put=1;
		tree[rt].in=0;
		tree[rt].val=0;
		return ;
	}
	PushDown(rt);
	clear(rt<<1,l,r);
	clear(rt<<1|1,l,r);
	PushUp(rt);
}
int query(int rt,int l,int r)
{
	if(tree[rt].r<l||tree[rt].l>r)return 0;
	int ans = 0;
	if(tree[rt].l>=l&&tree[rt].r<=r)
	{
		return tree[rt].val;
	}
	PushDown(rt);
	ans+=query(rt<<1,l,r);
	ans+=query(rt<<1|1,l,r);
	return ans;
}
int bin(int s,int rank)//rank:需要插入的花的数目
{
    int l = s;
    int r = n;
    int ans = -1;
    int mid;
    while(l <= r)
    {
        int mid = (l + r)>>1;
        int tmp = query(1,s,mid);
        if(tmp + rank == mid - s + 1)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            if(tmp + rank < mid - s + 1)
                r = mid - 1;
            else
                l = mid + 1;
        }
    }
    return ans;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		build(1,n,1);
		while(m--)
		{
			int k,a,b;
			scanf("%d %d %d",&k,&a,&b);
			if(k==1&&a==2&&b==3)
			{
				k=1;
			}
			if(k==1)
			{   a++;
			    a=bin(a,1);
			    if(a==-1)printf("Can not put any one.\n");
			    else{
				int tem = query(1,a,n);
				tem = n-a+1-tem;
				if(b>=tem)
				b=tem;
				int res = bin(a,b); 
				printf("%d %d\n",a-1,res-1);
				Update(1,a,res);
			    }
			}
			else
			{
				a++,b++;
				printf("%d\n",query(1,a,b));
				clear(1,a,b);
			}
		}
		printf("\n");
	}
}

发表于 Valine：

题目链接

HDU4578

思路

这道题是一道裸的线段树题目，需要维护3个lazy标记，既然有lazy标记，那么我们就要考虑他们两两之间的影响。
如果set的话，那么mul和add都要初始化为1，0。如果先加后乘，那么add标记就要乘上后面乘上的c。这是主要注意的。
还有就是下方lazy标记的时候，一定要记得刚刚说过的影响，也要往下推。
对于二次和三次的维护，因式分解后就成为了一个递推式。

阅读全文 »

发表于 更新于 Valine：

欧拉定理

内容

若正整数 $a,n$互质，则$a^{\phi(n)}≡1(mod n)$其中$\phi(n)$是1-n中与n互质的数的个数

证明

不妨设$X_1,X_2,{\cdots},X_n$为1~n中与n两两互质的数
那么对一些数进行讨论$aX_1,aX_2,{\cdots},aX_n$

引理1

$aX_1,aX_2,{\cdots},aX_n$中，任意两个数模n的余数一定不同。

阅读全文 »

发表于 更新于 Valine：

题目链接

AtCoder Beginner Contest 139

E

思路

这道题就是纯属暴力，不过学习到了，数组放在栈内比放在堆内跑的要快。

代码实现

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int main()
{
	int n;
  int a[maxn][maxn]={};
bool vis[maxn]={};
int  now[maxn]={};
	scanf("%d",&n);
	for(int i=1;i<maxn;i++)now[i]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n-1;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	int day = 0;
    int round = 0;
    while(1)
    {   memset(vis,false,sizeof(vis));
        bool ok = false;
    	for(int j=1;j<=n;j++)
    	{
		int b = a[j][now[j]]; 
		if(now[j]>=n||vis[b]||vis[j])continue;
		if(a[b][now[b]]==j)
		{
		        ok = true;
    			now[j]++;
				now[b]++;
    			vis[j]=true;
    			vis[b]=true;
    			round++;
    			if(round==n*(n-1)/2)return 0*printf("%d\n",day+1);
    	}
		}
		if(!ok)return 0*printf("-1\n");
		day++;
	}
	return 0*printf("%d\n",day);
}
阅读全文 »