发表于 | 评论数：

#B Different GCD Subarray Query
现在已经口头AC了,我们就是区间不同颜色个数的升级版.我还需要处理一下…

#F Football Games
获得的分是一定的,然后判断一下不会超过最大值然后就可以了

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
#include <bits/stdc++.h>
using namespace std;
int a[50005];
int main()
{
	int t;
	while(~scanf("%d",&t))
	{
		while(t--)
		{
			int n,sum=0,f=0;
			scanf("%d",&n);
			for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
			for(int i=1;i<=n;i++)
			{
				sum+=a[i];
				if(a[i]>((n-1)*2))
				{
					f=1;
					break;
				}
			}
			if(sum!=(n*(n-1))||f)
			puts("F");
			else
			puts("T");
		}
	}
}

G Friends and Enemies

结论题，结论目前没有推….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll x,y;
	while(~scanf("%lld%lld",&x,&y))
	{
		ll a=x/2,b=x-a;
		if(a*b<=y)
		puts("T");
		else
		puts("F");
	}
}

H Function

傻逼玩意暴力跑一遍一看数据就没有卡，就是一个随机数据，做法就是找出右边比他小的一个一个模就完事了我服了

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
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N],nex[N];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		nex[i]=n+1;
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		if(a[j]<=a[i])
		{
			nex[i]=j;
			break;
		}
		scanf("%d",&m);
		while(m--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			int re=a[l];
			for(int i=nex[l];i<=r;i=nex[i])
			{
				if(a[i]==0)
				break;
				re%=a[i];
				if(re==0)
				break;
			}
			printf("%d\n",re);
		}
	}
}

I Sparse Graph

求补图最短路的好题.点多边少我们就bfs暴力找一波.但是也不是这么的暴力,维护两个set,如果原来没有边的话那么d[to]=d[p]+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
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
struct edge
{
	int to,nex;
}E[N<<1];
int cnt,n,m,head[N],d[N];
void add(int x,int y)
{
	E[++cnt].to=y;E[cnt].nex=head[x];head[x]=cnt;
}
void bfs(int s)
{
	set<int> a,b;
	for(int i=1;i<=n;i++)
	if(i!=s)
	a.insert(i);
	memset(d,-1,sizeof(d));
	d[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int p=q.front();
		q.pop();
		for(int i=head[p];i;i=E[i].nex)
		if(a.count(E[i].to))
		b.insert(E[i].to),a.erase(E[i].to);
		for(auto it=a.begin();it!=a.end();it++)
		d[*it]=d[p]+1,q.push(*it);
		a.swap(b);
		b.clear();
	}
	for(int i=1;i<=n;i++)
	if(i!=s)
	printf("%d%c",d[i],i==n?'\n':' ');
}
int main()
{
	int t;
	while(~scanf("%d",&t))
	{
		while(t--)
		{
			cnt=0;
			memset(head,-1,sizeof(head));
			int l,r,s;
			scanf("%d%d",&n,&m);
			while(m--)
			{
				scanf("%d%d",&l,&r);
				add(l,r);
				add(r,l);
			}
			scanf("%d",&s);
			bfs(s);
		}
	}
}

J-Weak Pair

也是够贱的这个还有0,就是我们dfs走的时候下面的完全可以直接查询上面的点,把ai*aj<=k转换一下成为ai<=k/aj所以直接查询k/aj就可以了.离散化的时候也得先把k/aj放进去要不会lower_bound出错,10/3=3直接lower_bound没有3的话会跑到前面去可能中间的点不记录了,其他的就是注意回溯的时候把相应的点删掉就行

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll t[N],a[N],b[N],ans,head[N],n,k,jk,l,r,in[N],cnt;
struct edge
{
	ll nex,to;
}E[N<<1];
void insert(int x,int y)
{
	for(int i=x;i<=N;i+=i&(-i))
	t[i]+=y;
}
void add(ll x,ll y)
{
	E[++cnt].to=y;E[cnt].nex=head[x];head[x]=cnt;
}
ll sum(int x)
{
	ll ans=0;
	for(int i=x;i>0;i-=i&(-i))
	ans+=t[i];
	return ans;
}
void dfs(int p)
{
	ans+=sum(lower_bound(b+1,b+1+jk,k/a[p])-b);
	insert(lower_bound(b+1,b+1+jk,a[p])-b,1);
	for(int i=head[p];i!=-1;i=E[i].nex)
	dfs(E[i].to);
	insert(lower_bound(b+1,b+1+jk,a[p])-b,-1);
}
int main()
{
	ll tt;
	while(~scanf("%lld",&tt))
	{
		while(tt--)
		{
			jk=ans=cnt=0;
			memset(head,-1,sizeof(head));
			memset(in,0,sizeof(in));
			memset(t,0,sizeof(t));
			scanf("%lld%lld",&n,&k);
			for(int i=1;i<=n;i++)
			{
				scanf("%lld",&a[i]);
				b[++jk]=a[i];
				if(a[i])
				b[++jk]=k/a[i];
				else
				b[++jk]=n+1;
			}
			for(int i=1;i<n;i++)
			{
				scanf("%lld%lld",&l,&r);
				in[r]++;
				add(l,r);
			}
			sort(b+1,b+1+jk);
			jk=unique(b+1,b+1+jk)-b-1;
			for(int i=1;i<=n;i++)
			if(!in[i])
			{
				dfs(i);
				break;
			}
			printf("%lld\n",ans);
		}
	}
}

发表于 | 评论数：

分治本身的大部分内容还是比较好想的，就是中线划分的左右区间可能出现跨线最小值的操作，所以说我们需要枚举另一个点集.也就是距离中线的距离小于d的点，因为这些才是有可能在更新答案的点集，然后我们再把他们按照y排序枚举看一下如果y差值都大于d那么就不枚举这是一个剪枝，剩下的就是更新答案，然后就ok了 O(NlogN) 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll re[200005],p=0;
struct node
{
	double x,y;
}a[200005];
double dis(ll x,ll y)
{
	return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
bool cmp(node a,node b)
{
	return a.x<b.x;
}
bool cmp2(ll aa,ll bb)
{
	return a[aa].y<a[bb].y;
}
double merge(ll l,ll r)
{
	if(l==r)
	return 1<<30;
	if(l+1==r)
	return dis(l,r);
	int mid=(l+r)>>1;
	double d1=merge(l,mid);
	double d2=merge(mid+1,r);
	double d=min(d1,d2);
	p=0;
	for(int i=l;i<=r;i++)
	if(fabs(a[mid].x-a[i].x)<d)
	re[++p]=i;
	sort(re+1,re+1+p,cmp2);
	for(int i=1;i<=p;i++)
	for(int j=i+1;j<=p&&fabs(a[re[j]].y-a[re[i]].y)<d;j++)
	d=min(dis(re[j],re[i]),d);
	return d;
}
int main()
{
	ll n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+1+n,cmp);
	printf("%.4f",merge(1,n));
}

发表于 | 评论数：

整个算法可谓是神奇!!!!
算法流程:
1.判断当前是否是一个二次剩余用 n^(p-1)/2=p-1(mod p)来判如果等于那就不是直接返回无解
2.循环选取一个随机数并且计算它的w=a^2-n
3.判断w^(p-1)/2=p-1 (mod p)是否正确，如果对的话那么我们跳出
4.计算拓展数域上的 (a+w)^(p+1)/2 即可
拓展数域就是同余的拓展出来一个类似复数的数域，所以我们重载乘法 (a+iw) x (b+jw) = (ab+ijw^2)+(aj+bi)w
5.计算出来之后我们需要判断几个解如果p-拓展域实数位上的数=拓展域实数位上的数 也就是说ans.x=p-ans.x那么总共有一个解
6.否则那就两个解分别输出即可
证明看网上大佬吧…..

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p,w,a;
struct node
{
	ll x,y;
};
node mul(node a,node b)
{
	return (node){(a.x*b.x%p+a.y*b.y%p*w%p)%p,(a.x*b.y%p+a.y*b.x%p)};
}
ll qpow(ll a,ll b)
{
	ll ans=1;
	ll base=a;
	while(b)
	{
		if(b&1)
		ans=ans%p*base%p,ans%=p;
		base=base%p*base%p,base%=p;
		b>>=1;
	}
	return ans%p;
}
node qmul(node a,int b)
{
	node ans={1,0};
	node base=a;
	while(b)
	{
		if(b&1)
		ans=mul(ans,base);
		base=mul(base,base);
		b>>=1;
	}
	return ans;
}
node cip()
{
	n%=p;
	if(n==0)
	return (node){0,0};
	if(qpow(n,(p-1)>>1)==p-1)
	return (node){-1,0};
	while(1)
	{
		a=rand()%p;
		w=((a*a%p-n)%p+p)%p;
		if(qpow(w,(p-1)>>1)==p-1)
		break;
	}
	return qmul((node){a,1},(p+1)>>1);
}
int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&p);
	 	node ans=cip();
		if(ans.x==-1)
		puts("Hola!");
		else if(ans.x==0)
		puts("0");
		else if(ans.x==p-ans.x)
		printf("%lld\n",ans.x);
		else
		printf("%lld %lld\n",min(ans.x,p-ans.x),max(ans.x,p-ans.x));
	}
}

发表于 | 评论数：

解释一下这个A[i]为啥子能用树状数组求出来，加入树状数组里面所有的值，这些值能求出当前的前面的数.
然后枚举的时候因为是全排列所以我们可以知道后面比这个数小的数一定就是sum(a[i])-1个，然后我们把这个a[i]位置的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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000005],pre[1000005],mod=998244353,c[1000005],n,ans;
void add(ll p,ll sum)
{
	for(int i=p;i<=n;i+=i&(-i))
	c[i]+=sum;
}
ll sum(ll p)
{
	ll ans=0;
	for(int i=p;i;i-=i&(-i))
	ans+=c[i];
	return ans;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	pre[0]=1;
	for(int i=1;i<=n;i++)
	pre[i]=pre[i-1]%mod*i%mod,pre[i]%=mod,add(i,1);
	for(int i=1;i<=n;i++)
	{
		ans=ans%mod+(sum(a[i])-1)%mod*pre[n-i]%mod,ans%=mod;
		add(a[i],-1);
	}
	printf("%lld",ans+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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double a[105][105];
int main()
{
	ll n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n+1;j++)
	scanf("%lf",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		int max=i;
		for(int j=i+1;j<=n;j++)
		if(fabs(a[j][i])>fabs(a[max][i]))
		max=j;
		swap(a[i],a[max]);
		if(!a[i][i])
		return puts("No Solution"),0;
		for(int j=1;j<=n;j++)
		if(j!=i)
		{
			double t=a[j][i]/a[i][i];
			for(int k=i+1;k<=n+1;k++)
			a[j][k]-=a[i][k]*t;
		}
	}
	for(int i=1;i<=n;i++)
	printf("%.2f\n",a[i][n+1]/a[i][i]);
}
0%