Reku
0%

Codeforces Div 2 C 天梯 26——30

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/385/C 我开始想了一个树状数组乱搞的方法。 先把所有数质因数分解，然后放到树状数组中，最后搞一搞就行了。 然而一直超时，看来是被卡了质因数分解，但是我算了一下时间复杂度，感觉还是可以过得啊... 

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
#include<bits/stdc++.h>
using namespace std;
int x[1000010]={};
int t[20000010]={};
int n;
int m;
int ma;
void add(int k)
{
    while(k<=ma)
    {
        t[k]+=1;
        k+=k&-k;
    }
}
int read(int k)
{
	if(k>ma) k=ma;
    int sum=0;
    while(k)
    {
        sum+=t[k];
        k-=k&-k;
    }
    return sum;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x[i]);
		ma=max(ma,x[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int la;
		for(int j=2;j<=x[i];j++)
		{
			bool bj=0;
			while(x[i]!=j)
			{
				if(x[i]%j==0)
				{
					bj=1;
					x[i]/=j;
					la=j;
				}
				else break;
			}
			if(bj==1)
			{
				add(j);
			}
		}
		if(x[i]!=1&&x[i]!=la)
		{
			add(x[i]);
		}
	}
	int l,r;
	long long ans;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		ans=read(r)-read(l-1);
		printf("%d\n",ans);
	}
	return 0;
}

因为一直超时，所以看了标算，发现是筛法的时候，加几个操作就好了...突然想到这个题我似乎高二做过... 不得不说越来越蠢了...

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
#include<bits/stdc++.h>
using namespace std;
bool p[10000010]={};
int c[10000010]={};
int a[10000010]={};
int n,m;
int l,r;
int x;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		c[x]++;
	}
	for(int i=2;i<=10000000;i++)
	{
		if(p[i]==0)
		{
			for(int j=i;j<=10000000;j+=i)
			{
				p[j]=1;
				a[i]+=c[j];
			}
		}
	}
	for(int i=1;i<=10000000;i++)
	{
		a[i]+=a[i-1];
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		l=min(l,10000000);
		r=min(r,10000000);
		printf("%d\n",a[r]-a[l-1]);
	}
	return 0;
}

http://codeforces.com/problemset/problem/137/C 因为所有的年代都是离散的（没有相同起点相同终点，终点起点也不同 那就排个序之后记录一下最晚的年份，然后判断一下就行。 

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
#include<bits/stdc++.h>
using namespace std;
int n;
struct pp
{
	int a,b;
} p[100010];
bool cmp(pp x,pp y)
{
	return x.a<y.a;
}
int ma=0;
int ans=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].a>>p[i].b;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(ma>p[i].b) ans++;
		ma=max(ma,p[i].b);
	}
	cout<<ans;
	return 0;
}
http://codeforces.com/problemset/problem/427/C 算法很简单...就是求一下强连通分量，然后很简单的算一算就好了... 但是tarjan这个东西，我高二几乎瞬间就能写出来...但是现在... 于是我又去学习了一下byvoid的tarjan算法... 
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
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m;
int u,v;
int di,bc;
int dfn[100010]={};
int low[100010]={};
bool in[100010]={};
long long co[100010]={};
vector<int> e[100010];
vector<int> f[100010];
stack<int> q;
void tarjan(int x)
{
	int y;
	dfn[x]=low[x]=++di;
	in[x]=1;
	q.push(x);
	for(int i=0;i<e[x].size();i++)
	{
		y=e[x][i];
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(in[y]==1)
		{
			low[x]=min(dfn[y],low[x]);
		}
	}
	if(dfn[x]==low[x])
	{
		bc++;
		while(1)
		{
			int r=q.top();
			f[bc].push_back(r);
			in[r]=0;
			q.pop();
			if(r==x) break;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&co[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	long long ans=0ll;
	long long t=1ll;
	long long u;
	long long g;
	for(int i=1;i<=bc;i++)
	{
		u=2147483600ll;
		g=0ll;
		for(int j=0;j<f[i].size();j++)
		{
			u=min(co[f[i][j]],u);
		}
		ans+=u;
		for(int j=0;j<f[i].size();j++)
		{
			if(u==co[f[i][j]]) g++;
		}
		t*=g;
		t%=mod;
	}
	cout<<ans<<" "<<t;
	return 0;
}
http://codeforces.com/problemset/problem/414/A 傻逼题...瞎构造就行... 但是n等于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
#include<bits/stdc++.h>
using namespace std;
int a[100010]={};
int n,k;
int b;
int p;
int u;
int main()
{
	cin>>n>>k;
	if(n==1&&k!=0)
	{
		cout<<-1;
		return 0;
	}
	if(n==1&&k==0)
	{
		cout<<1;
		return 0;
	}
	if(n%2==1)
	{
		b=1;
		n--;
	}
	if(n/2>k)
	{
		cout<<-1;
		return 0;
	}
	u=2;
	n=n/2;
	for(int i=1;i<n;i++)
	{
		cout<<u<<" "<<u+1<<" ";
		u+=2;
		k-=1;
	}
	for(int i=1;i<=10000000;i++)
	{
		if(k*i>u)
		{
			u=i;
			break;
		}
	}
	cout<<k*u<<" "<<k*(u+1)<<" ";
	if(b!=0) cout<<1;
	return 0;
}
http://codeforces.com/problemset/problem/279/C 预处理出连续不下降的段和连续不上升的段 然后拼一拼就行了 
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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int l,r;
int a[100010]={};
int u[100010]={};
int d[100010]={};
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int s=1;
	int t=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=a[i-1]) t++;
		else
		{
			for(int j=s;j<=t;j++) u[j]=t;
			s=t+1;
			t=t+1;
		}
	}
	for(int j=s;j<=t;j++) u[j]=t;
	a[0]=2147483600;
	s=1;
	t=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=a[i-1]) t++;
		else
		{
			for(int j=s;j<=t;j++) d[j]=t;
			s=t+1;
			t=t+1;
		}
	}
	for(int j=s;j<=t;j++) d[j]=t;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		int p;
		p=u[l];
		if(p>=r)
		{
			cout<<"Yes"<<endl;
			continue;
		}
		else
		{
			p=d[p+1];
			if(p>=r)
			{
				cout<<"Yes"<<endl;
				continue;
			}
			else
			{
				cout<<"No"<<endl;
				continue;
			}
		}
	}
	return 0;
}