Atcoder Beginner Contest 449

A：π

直接输出

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100002;

double n;
double pi=3.141592653589793;
signed main()
{
	scanf("%lf",&n); n/=2;
	printf("%lf",pi*n*n);
	return 0;
}

B：Deconstruct Chocolate

观察可知巧克力块永远保持矩形的形状，故只需要定义两个变量维护矩形的长宽即可。

Code：

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1002;
int h,w,q,op,tmp;
int a[maxn][maxn];
signed main()
{
	cin>>h>>w;
	cin>>q;
	int nowx=h,nowy=w;
	while(q--)
	{
		cin>>op>>tmp;
		if(op==1)
		{
			cout<<tmp*nowy<<endl;
			nowx=nowx-tmp;
		}
		else
		{
			cout<<tmp*nowx<<endl;
			nowy=nowy-tmp;
		}
	}
	return 0;
}

C：Comfortable Distance

考虑滑动窗口，维护 这个区间内和 不同的字符的数量，该数量便是以 为右端点的答案数 。复杂度 。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100002;
string s;
int l,r,L,R,n,ans;
int tong[30];
signed main()
{
    cin>>n>>l>>r;
    cin>>s;
    for (int j=l; j<=n-1;j++)
    {
        tong[s[j-l]-'a']++;
        if (j-r-1>=0)
        {
            tong[s[j-r-1]-'a']--;
        }
        ans+=tong[s[j]-'a'];
    }
    cout<<ans;
    return 0;
}

D：Make Target 2

出的相当不错的一道题。首先暴力复杂度 不可行，考虑优化暴力，一个很显然的思路就是对每一列单独统计出有几个黑点。对于一个竖列上的所有点，我们发现其基本可以分成三部分：。显然，对于第二个区间，点为黑/白取决于 的奇偶性；对于第一、三个区间，点为黑/白取决于 的奇偶性（等价地可以转换为这个区间内 为偶数的点的个数）。接下来的细节处理也很容易出错，我们考虑的这一列的区间为 ，我们要求出其与上面三个区间的交集，然后统计答案。具体方法见代码。还有一个小tips，求区间中偶数个数的公式为：对于区间 ，偶数的个数为 。

Code：

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 int long long
const int maxn=100002;

int L,R,D,U,ans;

int get_even(int l,int r)
{
	if(l>r) return 0;
	if(l==r) return (l+1)%2;
	return r/2-(l-1)/2;
}

signed main()
{
	cin>>L>>R>>D>>U;
	for(int i=L;i<=R;i++)
	{
		int maxh=min(abs(i),U);
		int minh=max(-abs(i),D);
		if(abs(i)%2==0&&(maxh>=minh)) ans+=(maxh-minh+1);
		int top_l=max(D, abs(i)+1);
		if(top_l<=U) ans+=get_even(top_l,U);
		int bot_r=min(U,-abs(i)-1);
		if(D<=bot_r) ans+=get_even(-bot_r,-D);
	}
	cout<<ans;
	return 0;
}

E：A += v

略有些麻烦的题。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000002;

int n,m,q,x;
int a[maxn],tong[maxn],qzh[maxn],num;
int tree[maxn];
struct nodd {
	int val,id;
}sorttong[maxn];
struct nodd2 {
	int pos,num,id,ans;
}res[maxn];
bool cmp(nodd x,nodd y) { if(x.val==y.val) return x.id<y.id;else return x.val<y.val;}
bool cmp2(nodd2 x,nodd2 y) { return x.pos<y.pos; }
bool cmp3(nodd2 x,nodd2 y) { return x.id<y.id; }
void ins(int pos, int delta)
{
    for (;pos<=m;pos+=pos&-pos)
    {
        tree[pos]+=delta;
    }
}
int get(int k)
{
	int pos=0;
	for(int i=18;i>=0;i--)
	{
		if((pos+(1<<i)<=m)&&(tree[pos+(1<<i)]<k))
		{
			pos+=(1<<i);
			k-=tree[pos];
		}
	}
	return pos+1;
}
int Getnum(int val)
{
	int pos=0,l=1,r=m;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(sorttong[mid].val<val) { l=mid+1; pos=mid; }
		else r=mid-1;
	}
	if(pos==0) return 0;
	else return val*pos-qzh[pos];
}
int Getpos(int val)
{
	int l=1,r=m,pos=m;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(sorttong[mid].val<=val) { l=mid+1; pos=mid; }
		else r=mid-1;
	}
	return pos;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) { cin>>a[i]; tong[a[i]]++; }
	for(int i=1;i<=m;i++) { sorttong[i].val=tong[i]; sorttong[i].id=i; }
	sort(sorttong+1,sorttong+1+m,cmp);
	for(int i=1;i<=m;i++) qzh[i]=qzh[i-1]+sorttong[i].val;
	cin>>q;
	while(q--)
	{
		cin>>x;
		if(x<=n) { res[++num].ans=a[x]; res[num].id=num; res[num].pos=-1; continue; }
		int l=1,r=2e13;
		int ansH=0;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(Getnum(mid)<(x-n)) { l=mid+1; ansH=mid; }
			else r=mid-1;
		}
		res[++num].num=x-n-Getnum(ansH);
		res[num].pos=min(ansH,n);
		res[num].id=num;
		//cout<<"ansH"<<" "<<ansH<<" "<<Getnum(ansH)<<endl;
	}
	//for(int i=1;i<=num;i++) cout<<res[i].num<<" "<<res[i].pos<<endl;
	sort(res+1,res+1+num,cmp2);
	int treesize=0;
	//for(int i=1;i<=n;i++) cout<<sorttong[i].id<<" ";cout<<endl;
	for(int i=1;i<=num;i++)
	{
		if(res[i].pos==-1) continue;
		while(sorttong[treesize+1].val<=res[i].pos&&(treesize+1)<=m) { treesize++; ins(sorttong[treesize].id,1); }
		res[i].ans=get(res[i].num);
	}
	sort(res+1,res+1+num,cmp3);
	for(int i=1;i<=num;i++) cout<<res[i].ans<<endl;
	return 0;
}

F：Grid Clipping

感觉其实比E简单？正难则反，考虑哪些点不能成为答案。我们发现一个黑点能够“污染”它左上角的一片区域，这片区域的长宽是题目要求的矩形的长宽。换言之，这个区域里的所有点都不可能成为答案（即不能成为题目要求矩形的左上角的点），所以我们对于所有的黑点求“污染区域”的面积之和即可。这便化为了一个经典的矩形面积并的问题。