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

0%

发表于 更新于 Valine：

A

简单减法

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
	int l,r;
	l=r=0;
	string s;
	int n;
	scanf("%d",&n);
	cin>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='L')l--;
		else r++;
	}
	printf("%d\n",r-l+1);
}
阅读全文 »

发表于 更新于 Valine：

题目链接

A

思路

贪心，因为只有一个共享的，所以钱多的先使用

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,c,d,e,f;
	cin>>a>>b>>c>>d>>e>>f;
	long long ans = 0;
	if(e>f){
		ans+=min(a,d)*e;
		d-=min(a,d);
		ans+=min(d,min(b,c))*f;
	}
	else
	{
		ans+=min(d,min(b,c))*f;
		d-=min(d,min(b,c));
		ans+=min(a,d)*e;
	}
	cout<<ans<<endl;
 }
阅读全文 »

发表于 Valine：

题目链接

LOJ6053

思路

分析出来得到这个函数

然后可以使用质数前缀和与质数个数前缀和来维护这个函数的前缀和，然后再套上min25板子就可以了

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e5+10;
const int md = 1e9+7;
ll g[N<<1],id,n,sn,sq,a[N<<1],h[N<<1],sum[N<<1];
int prime[N],cnt;
ll Id(ll x){return x<=sn?x:id-n/x+1;}
ll Solve(ll a,ll b)
{
	if(a<prime[b])return 0;
	ll ans = (g[Id(a)]-g[prime[b-1]]+md)%md;
	for(ll i=b;i<=cnt&&1ll*prime[i]*prime[i]<=a;i++)
	{
		ans+=1ll*(prime[i]^1)*Solve(a/prime[i],i+1)+(prime[i]^2);
		ans%=md;
		for(ll x=1ll*prime[i]*prime[i],j=2;x*prime[i]<=a;x*=prime[i],j++)
		{
			ans+=1ll*(prime[i]^j)*Solve(a/x,i+1)+(prime[i]^(j+1));
		}
	}
	return ans%md;
}
int main(){
	scanf("%lld",&n);
	sn =sqrt(n);
	for(ll i=1;i<=n;i=a[id]+1)
	{
		a[++id]=n/(n/i);
		ll tmp = a[id]%md;
		g[id]=tmp*(tmp+1)/2%md-1;
		h[id]=a[id]-1;
	}
	for(ll i=2;i<=sn;i++)if(h[i]!=h[i-1])
	{
		prime[++cnt]=i;
		sq = 1ll*i*i;
		for(int j=id;a[j]>=sq;j--)
		{
			ll t = Id(a[j]/i);
			(g[j]-=i*(g[t]-g[i-1]))%=md;
			h[j]-=h[t]-(cnt-1);
		}
	}
	for(int i=1;i<=id;i++)(g[i]+=(i>1)*2-h[i]+md)%=md;
	printf("%lld",(Solve(n,1)+1)%md);
}

发表于 Valine：

题目链接

Luogu4213

思路

min25筛是用来处理积性函数的前缀和的一个方法，形如

cmxrynp这篇博客讲的很好。
这道题目我们需要处理出$\phi(i)与\mu(i)$的质数的前缀和权值即可，我们选择两个函数$g(i)表示质数前缀和,h(i)表示质数的个数前缀和$，然后我们就可以通过这两个函数找到

阅读全文 »

发表于 Valine：

C

一开始怎么也想不出来，想着这种题应该用DP或者组合数之类的，所以找了一下规律发现一个递推式过了

1
2
if(s[i]=='0')dp[i]=(dp[i]*2-1);
else dp[i]=(dp[i-1]*3-1)%md;

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long  long
const int N = 1e5+10; 
const int md = 1e9+7;
ll dp[N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		dp[1]=2;
		string s;
		cin>>s;
		int i = 0;
		while(s[i]=='0')i++;
		i++;
		int num=1;
		bool ok =false;
		if(i>=s.size())
		{
			printf("%d\n",1);
			continue;
		}
		for(;i<s.size();i++,num++)
		{
			if(s[i]=='0')dp[num+1]=(dp[num]*2-1)%md;
			else dp[num+1]=(dp[num]*3-1)%md;
		}
		printf("%lld\n",dp[num]); 
	}
}
阅读全文 »

发表于 Valine：

K.Triangle

思路

先用海伦公式求出面积的一半

然后通过正弦函数和余弦定理求出夹角$\alpha$
这样就可以通过公式

这样就能够求出x偏移量，通过偏移量和边上的两个点就够求出答案了

阅读全文 »

发表于 Valine：

扫描线

这个算法就是求二维平面上n个矩形覆盖的面积之和，我们用扫描线来解决。
oi_wiki中的图示说明的很明白
扫描线
我们用线段树维护的就是当前的仍剩余的长度，就是从下至上的那条线的长度。
把线按从y轴小到大排序，然后不停的插入线段树中，并且入边则+1，出边则-1；

扫描线求面积

HDU 1524
这题需要离散化，因为边有小数

阅读全文 »

发表于 Valine：

题目链接

poj1873

思路

观察到一共只有15个点，按位枚举就只有2e15种情况，然后需要特殊判断两种情况，第一种就是砍得只剩下一棵树或者没有得情况，那时候我们需要得长度为0，如果剩下两个树的话那么长度就为他们两个距离的两倍。剩下三棵或者大于三棵的情况，可以用凸包算法来计算最小周长。此处可以加快算法的地方就是，如果剩下树的价值小于当前已经得到的价值，那么就不用计算凸包了，就不可能是这种情况。

阅读全文 »

发表于 Valine：

凸包

在平面上能包含所有给定点的最小凸多边形叫做凸包，凸包用最小的周长围住了给定的所有点

凸包的解法

九茶巨巨九茶巨巨在这篇博客里面讲的非常清楚
我比较喜欢用的是扫描法，找到y轴最下面的点，然后作为基点使用极角排序。
排序过后根据叉积判断就好，时间复杂度就是排序的复杂度。

代码示例

圈奶牛
时间复杂度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
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Vector Point
const double eps = 1e-8;
const int N = 1e4+10;
int syn(double x)
{
	if(fabs(x)<eps)return 0;
	if(x>0)return 1;
	else return -1;
}
struct Point{
	double x,y;
}p[N],s[N];
stack<Point>st;
stack<Point>res;
Vector operator - (Point a,Point b){return {b.x-a.x,b.y-a.y};}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double dis(Point a,Point b){return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));}
bool cmp(Point p1,Point p2)
{
	double tmp=(Cross(p[0]-p1,p[0]-p2));
	if(tmp>0)return 1;
	if(tmp==0&&(dis(p1,p[0])>dis(p2,p[0])))return true;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lf %lf",&p[i].x,&p[i].y);
		if(i!=0&&p[i].y<p[0].y)
		{
			swap(p[i],p[0]);
		}
	}
	sort(p+1,p+n,cmp);
	double ans = 0;
	int tot = 0;
	s[0]=p[0];
	for(int i=1;i<n;i++)
	{
		while(tot>0&&Cross(s[tot]-s[tot-1],p[i]-s[tot])<=0)tot--;
		tot++;
		s[tot]=p[i];
	}
	s[tot+1]=p[0];
	for(int i=0;i<=tot;i++)
	ans+=dis(s[i],s[i+1]);
	printf("%.2lf\n",ans);
}

阅读全文 »