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

0%

发表于 更新于 分类于 Valine：

题目链接

SPOJ-APS2

思路

用min_25筛的思路，也就是埃筛的思想，维护一个前缀和和一个个数数组，
然后枚举质数来判断合数的贡献。
例如 N=17时，枚举质数2，然后分块的思想，找出17/2所在的块的大小，也就是8
然后2~ 8这个区间乘上2的话也在1~17之中，所以贡献就多了8-(2-1)*2,然后不断枚举下去。
合数部分就解决了，然后我们解决质数部分，就用min_25筛就好了。
最后的g[id]表示区间素数和，然后ans就是我们计算的合数部分了

阅读全文 »

发表于 更新于 Valine：

题目连接

美味果冻

思路

交换枚举项j，就是把分母作为枚举项，然后利用等差数列求和公式以及维护次方数组来完成对第二块的计算，如果用快速幂的话复杂度回事nlognlogn，所以这题不能用快速幂，必须维护次方数组。

阅读全文 »

发表于 更新于 Valine：

题目链接

2019牛客国庆集训派对day4

A

思路

这道题就是把矩阵补全之后，然后求伴随矩阵。
因为把每一列去掉，其实就是补全后的代数余子式。求伴随矩阵的话我们用高斯消元求逆矩阵然后乘上行列式的值即可

然后我们用高斯消元求出逆矩阵即可

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 250;
int a[maxn][maxn],b[maxn][maxn];
const int md = 1e9+7;
int quick_pow(int a,int b)
{
	int ans = 1;
	while(b)
	{
		if(b&1)ans=(1ll*ans*a)%md;
		b>>=1;
		a=(1ll*a*a)%md;
	}
	return ans;
}
void gs(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			b[i][j]=(i==j);
		}
	}
	int det = 1;
	for(int i=1;i<=n;i++)
	{
		int t=1;
		for(int k=1;k<=n;k++)
		{
			if(a[k][i])t=i;
		}
		if(t!=i)det*=-1;
		for(int j=1;j<=n;j++)
		{
			swap(a[i][j],a[t][j]);
			swap(b[i][j],b[t][j]);
		}
		det = 1ll*a[i][i]*det%md;
		int inv = quick_pow(a[i][i],md-2);
		for(int j=1;j<=n;j++)
		{
			a[i][j]=1ll*inv*a[i][j]%md;
			b[i][j]=1ll*inv*b[i][j]%md;
		}
		for(int k=1;k<=n;k++)
		{
			if(k==i)continue;
			int tem = a[k][i];
			for(int j=1;j<=n;j++)
			{
				a[k][j]=(a[k][j]-1ll*a[i][j]*tem%md+md)%md;
				b[k][j]=(b[k][j]-1ll*b[i][j]*tem%md+md)%md;
			}
		}
	}
	det = (det+md)%md;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			b[i][j]=1ll*det*b[i][j]%md;
		}
	}
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			if(i==1)
			{
				for(int j=1;j<=n;j++)a[i][j]=1;
			}
			else
			{
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&a[i][j]);
			}
		    }
		}
		gs(n);
		for(int i=1;i<=n;i++)
		{
			if(i&1)
			{
				printf("%d ",b[i][1]%md);
		    }
		    else
		    {
		    	printf("%d ",(md-b[i][1])%md);
			}
		}
		printf("\n");
	}
}
阅读全文 »

发表于 Valine：

总结

教训

今天早上打了一套codeforces，然后下午打牛客的训练题目，都是读错了题意，然后思路开始走歪，渐渐的就没了，先挂上题目链接。

题目链接

codeforces 586
牛客国庆训练day3

牛客K

思路

一开始竟然用NTT的三模运算来写，复杂度8nlogn*T，很显然，这题出题人特意卡了这个复杂度。
看了题解后发现，这是一道前缀和的题目，写出式子后提取公因式乘法就能解决了。
每次看到题后先考虑方向的正确性再去考虑做法会更好

阅读全文 »

发表于 Valine：

题目链接

D

思路

这题目就是求a,b公约数的个数中互质的个数。
我们对a,b中做质因数分解，然后查找有多少个相同的质因数，就最多可以选几个了。
为什么这样是对的？因为选择的每个数都可以分解成质因数，要求他们互质的话也就是要求他们没有相同的质因子。然后我们就贪心的选择质数就好了。

代码实现

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
clude<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e6+10;
bool vis[maxn];
ll prime[maxn],cnt;
ll ans = 0;
void init()
{
	for(int i=2;i<maxn;i++)
	{
		if(!vis[i])
		{
			prime[cnt++]=i;
		}
		for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
} 
void solve(ll x,ll y)
{
	for(int i=0;i<cnt;i++)
	{
		if(x%prime[i]==0&&y%prime[i]==0)ans++;
		while(x%prime[i]==0)x/=prime[i];
		while(y%prime[i]==0)y/=prime[i];
	}
	if(x==y&&x!=1)ans++;
}
int main()
{
	ll a,b;
	init();
	cin>>a>>b;	
	solve(a,b);
	cout<<ans+1<<endl;
}
阅读全文 »

发表于 更新于 Valine：

题目链接

HDU-6053

思路

这道题训练的时候没想到处理出F的方法，同样是用了分块的方法，学到了。
首先我们根据题目，
设

阅读全文 »

发表于 更新于 Valine：

题目链接

Loj6235

思路

一道Min25筛的很基础的入门题。就是对g函数求和的操作。先对n分块，然后从小到达筛素数，然后从大到小对g进行处理，
因为这样就能滚动处理g数组，少了一维空间

代码实现

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;
#define ll long long 
const int maxn = 316300;
ll a[maxn<<1];
ll prime[maxn],cnt;
ll g[maxn<<1];
ll sqr,id,n;
int Id(ll x){return x<=sqr?x:id-n/x+1;}
int main()
{
	scanf("%lld",&n);
	ll sn = sqrt(n);
	sqr=sn;
	for(ll i=1;i<=n;i=a[id]+1)
	{
		a[++id]=n/(n/i);
		g[id]=a[id]-1;
	}
	for(ll i=1;i<=sn;i++)if(g[i]!=g[i-1])
	{
		prime[cnt++]=i;
		ll sq = 1ll*i*i;
		for(ll j=id;a[j]>=sq;j--)
		{
			g[j]-=g[Id(a[j]/i)]-(cnt-1);
		}
	}
	cout<<g[id]<<endl;
}
阅读全文 »

发表于 Valine：

题目链接

Codeforces #588-div2-D

思路

这道题看清楚了思路很简单，我们对一个人单独考虑，假设现在我全部人都选择进队，然后对每个人单独考虑，如果队中有比我更强的，那么我就不用出队，否则，我就需要出队。
所以每次用取和符号判断队伍中是否存在比我更强的人

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 7e3+10;
bool vis[maxn];
struct node
{
	ll a,b;
	bool operator < (const node s)
	{
		return a>s.a;
	}
}arr[maxn];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%I64d",&arr[i].a);
	for(int i=0;i<n;i++)scanf("%I64d",&arr[i].b);
	ll ans = 0;
	ll tans = 0;
	sort(arr,arr+n);//从大到小排序，因为有前置0会影响取和运算 
	for(int i=0;i<n&&n>1;i++)//枚举第i个人是否出队 
	{
		vis[i]=true;
		for(int j=0;j<n;j++)
		{
			if(!vis[j]&&(arr[j].a&arr[i].a)==arr[i].a)
			{
				vis[i]=false;
				ans+=arr[i].b;
				break;
			}
	    }
	}
	cout<<ans<<endl;
}
阅读全文 »

发表于 更新于 Valine：

题目链接

Gym100952

A

思路

很水的题，排个序就好

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
struct node
{
	ll h,m,s;
	bool operator < (const node a)
	{
		if(h!=a.h)return h<a.h;
		else if(m!=a.m)return m<a.m;
		else return s<a.s;
	}
	bool operator == (const node a)
	{
		return a.h==h&&a.m==m&&a.s==s;
	}
}p1,p2; 
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%lld %lld %lld %lld %lld %lld",&p1.h,&p1.m,&p1.s,&p2.h,&p2.m,&p2.s);
		if(p1==p2)printf("Tie\n");
		else if(p1<p2)printf("Player1\n");
		else printf("Player2\n");
	}
}
阅读全文 »