Reku
0%

Codeforces Round #348 Div 2+Div 1 C 题解

Posted on Edited on In Views: Valine:

http://codeforces.com/contest/669/problem/A 简单题 只要贪心的2 1 2 1 一直取就行啦 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int n;
int num;
int main()
{
	cin>>n;
	num+=n/3;
	num*=2;
	n=n%3;
	if(n>=1) num++;
	cout<<num<<endl;
	return 0;
}
http://codeforces.com/contest/669/problem/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
#include<bits/stdc++.h>
using namespace std;
int n;
bool v[100010]={};
string s;
int d[100010]={};
int main()
{
	cin>>n;
	cin>>s;
	for(int i=1;i<=n;i++) cin>>d[i];
	int p=1;
	bool bj=0;
	while(1)
	{
		if(p<1||p>n) break;
		if(v[p]==1)
		{
			bj=1;
			break;
		}
		v[p]=1;
		if(s[p-1]=='>') p+=d[p];
		else p-=d[p];
	}
	if(bj==1)
	{
		cout<<"INFINITE";
	}
	else
	{
		cout<<"FINITE";
	}
	cout<<endl;
	return 0;
}
http://codeforces.com/contest/669/problem/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
#include<bits/stdc++.h>
using namespace std;
int mi[101][101]={};
int n,m,q;
int t[10010]={};
int r[10010]={};
int c[10010]={};
int x[10010]={};
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>t[i];
		if(t[i]==1) cin>>r[i];
		if(t[i]==2) cin>>c[i];
		if(t[i]==3)
		{
			cin>>r[i];
			cin>>c[i];
			cin>>x[i];
		}
	}
	for(int i=q;i>=1;i--)
	{
		if(t[i]==1)
		{
			int p=mi[r[i]][m];
			for(int j=m;j>=2;j--)
			{
				mi[r[i]][j]=mi[r[i]][j-1];
			}
			mi[r[i]][1]=p;
		}
		if(t[i]==2)
		{
			int p=mi[n][c[i]];
			for(int j=n;j>=1;j--)
			{
				mi[j][c[i]]=mi[j-1][c[i]];
			}
			mi[1][c[i]]=p;
		}
		if(t[i]==3)
		{
			mi[r[i]][c[i]]=x[i];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<mi[i][j]<<" ";
		}
		cout<<endl;
	}
}
http://codeforces.com/contest/669/problem/D 这道题有点儿意思 以下是我的做法 其实顺时针逆时针之类的非常好处理，难以处理的就是变换 其实变换只有两种 第一种我叫做A变换 例子： 1 2 3 4 5 6 到 2 1 4 3 6 5 第二种我叫做B变换 例子： 1 2 3 4 5 6 到 6 3 2 5 4 1 相邻的AA或者BB就相当于没变换，只有ABAB这种交错变换才是有效变换。 然后观察一下，发现交错变换类似于冒泡排序，一半的数向前冒泡，另一半的数向后冒泡 至于是哪一半，取决于交错变换中第一次是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
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
#include<bits/stdc++.h>
using namespace std;
long long n,q;
long long a,b;
long long s;
long long v[4000010]={};
long long num;
long o=0ll;
long long w[1000010]={};
long long ans[1000010]={};
int main()
{
	scanf("%I64d%I64d",&n,&q);
	s=0ll;
	num=0ll;
	v[0]=-1ll;
	for(long long i=1ll;i<=n;i++) w[i]=i;
	for(long long i=1ll;i<=q;i++)
	{
		scanf("%I64d",&a);
		if(a==1ll)
		{
			scanf("%I64d",&b);
			s+=b;
			while(s>n) s-=n;
			while(s<0ll) s+=n;
		}
		else
		{
			if(s%2ll==0ll) o=0ll;
			else o=1ll;
			if(v[num]==o) num--;
			else
			{
				num++;
				v[num]=o;
			}
		}
	}
	if(num>0ll)
	{
		if(v[1]==0ll)
		{
			for(long long i=1ll;i<=n;i+=2ll)
			{
				w[i]+=num;
				w[i]%=n;
				if(w[i]==0ll) w[i]=n;
			}
			for(long long i=2ll;i<=n;i+=2ll)
			{
				w[i]+=num*(n-1);
				w[i]%=n;
				if(w[i]==0ll) w[i]=n;
			}
		}
		if(v[1]==1ll)
		{
			for(long long i=2ll;i<=n;i+=2ll)
			{
				w[i]+=num;
				w[i]%=n;
				if(w[i]==0ll) w[i]=n;
			}
			for(long long i=1ll;i<=n;i+=2ll)
			{
				w[i]+=num*(n-1);
				w[i]%=n;
				if(w[i]==0ll) w[i]=n;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans[w[i]]=i;
	}
	for(int i=n-s+1;i<=n;i++)
	{
		printf("%I64d ",ans[i]);
	}
	for(int i=1;i<=n-s;i++)
	{
		printf("%I64d ",ans[i]);
	}
	return 0;
}

http://codeforces.com/contest/669/problem/E 这题似乎没有D难？... 一个很简单的思路就是对每一个数建立一个树状数组，然后不断插入1 -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
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
#include<bits/stdc++.h>
using namespace std;
struct query
{
	int a,t,x,num,ans,p;
} q[100010];
int T[100001]={};
int lowbit(int t)
{
	return t&(-t);
}
int sum(int end)
{
	int sum=0;
	while(end>0)
	{
		sum+=T[end];
		end-=lowbit(end);
	}
	return sum;
}
void plu(int pos,int num,int count)
{
	while(pos<=count)
	{
		T[pos]+=num;
		pos+=lowbit(pos);
	}
}
map<int,int> ha;
map<int,int> ma;
int u=0;
int n;
bool cmp1(query a,query b)
{
	return a.t<b.t;
}
bool cmp2(query a,query b)
{
	return a.num<b.num;
}
bool cmp3(query a,query b)
{
	return a.x<b.x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&q[i].a,&q[i].t,&q[i].x);
		q[i].num=i;
	}
	sort(q+1,q+n+1,cmp1);
	for(int i=1;i<=n;i++)
	{
		if(ha[q[i].t]==0)
		{
			u++;
			ha[q[i].t]=u;
		}
		q[i].p=ha[q[i].t];
	}
	sort(q+1,q+n+1,cmp2);
	stable_sort(q+1,q+n+1,cmp3);
	q[0].x=0;
	for(int i=1;i<=n;i++)
	{
		if(q[i].x!=q[i-1].x)
		{
			memset(T,0,sizeof(T));
		}
		if(q[i].a==1)
		{
			plu(q[i].p,1,u);
		}
		if(q[i].a==2)
		{
			plu(q[i].p,-1,u);
		}
		if(q[i].a==3)
		{
			q[i].ans=sum(q[i].p);
		}
	}
	sort(q+1,q+n+1,cmp2);
	for(int i=1;i<=n;i++)
	{
		if(q[i].a==3)
		{
			printf("%d\n",q[i].ans);
		}
	}
	return 0;
}
http://codeforces.com/contest/668/problem/C 额，数学题，反正我是不太会... 不过代码很好写 直接搬运题解，他先算出了这两个式子： P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k). P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1)). 然后通过这个公式就能解啦. P(a<=k), P(b<=k) = (u + v ± sqrt((u + v)^2 — 4u)) / 2. u = P(max(a,b) <= k), v = P(min(a,b) <= k). 
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;
const int N=100011;
double a[N][2];
double ans[N][2];
int n;
int main()
{
	cin>>n;
	for (int i=0;i<=1;i++)
		for (int j=1;j<=n;j++)
			scanf("%lf",&a[j][i]);
	double ta,tb,temm;
	for (int i=1;i<=n;i++)
	{
		a[i][0]+=a[i-1][0];
		a[i][1]+=a[i-1][1];
		ta=a[i][1]+a[i][0];
		tb=a[i][0];
		temm=max(0.0,ta*ta-4*tb);
		ans[i][0]=(ta+sqrt(temm))/2;
		ans[i][1]=(ta-sqrt(temm))/2;
	}
	for (int i=n;i>=1;i--)
	{
		ans[i][0]-=ans[i-1][0];
		ans[i][1]-=ans[i-1][1];
	}
	for (int i=0;i<2;i++)
	{
		for (int j=1;j<=n;j++)
		{
			printf("%.10lf ",ans[j][i]);
		}
		printf("\n");
	}
}