2018南京网络赛补题

发表于 | 评论数： | 阅读次数：

A. The beautiful values of the palace

二维偏序离线操作用树状数组排序一维之后再一个一个放入还是离线操作有魅力啊

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
ll tt,n,m,k,p,re[N],t[N],xx1,yy1,xx2,yy2;
struct point
{
	int x,y,v;
}pt[N];
struct query
{
	ll x,y,id,f;
}q[N];
bool cmp1(point a,point b)
{
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmp2(query a,query b)
{
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
void insert(ll x,ll y)
{
	for(ll i=x;i<=N;i+=i&(-i))
	t[i]+=y;
}
ll sum(ll x)
{
	ll ans=0;
	for(ll i=x;i>0;i-=i&(-i))
	ans+=t[i];
	return ans;
}
ll cal(ll x,ll y)
{
	x=x-n/2-1;
	y=y-n/2-1;
	ll t=max(abs(x),abs(y)),ans,jk=0;
	if(x>=y)
	ans=n*n-4*t*t-2*t-x-y;
	else
	ans=n*n-4*t*t+2*t+x+y;
	while(ans)
	jk+=ans%10,ans/=10;
	return jk;
}
int main()
{
	scanf("%lld",&tt);
	while(tt--)
	{
		p=0;
		memset(t,0,sizeof(t));
		memset(re,0,sizeof(re));
		scanf("%lld%lld%lld",&n,&m,&k);
		for(ll i=1;i<=m;i++)
		scanf("%lld%lld",&pt[i].x,&pt[i].y),pt[i].v=cal(pt[i].x,pt[i].y);
		sort(pt+1,pt+1+m,cmp1);
		for(ll i=1;i<=k;i++)
		{
			scanf("%lld%lld%lld%lld",&xx1,&yy1,&xx2,&yy2);
			q[++p]=(query){xx2,yy2,i,1};
			q[++p]=(query){xx1-1,yy1-1,i,1};
			q[++p]=(query){xx1-1,yy2,i,-1};
			q[++p]=(query){xx2,yy1-1,i,-1};			
		}
		sort(q+1,q+1+p,cmp2);
		ll jk=1;
		for(ll i=1;i<=p;i++)
		{
			while(pt[jk].x<=q[i].x&&jk<=m)
			{
				insert(pt[jk].y,pt[jk].v);
				jk++;
			}
			if(q[i].y==0)
			continue;
			re[q[i].id]+=sum(q[i].y)*q[i].f;
		}
		for(ll i=1;i<=k;i++)
		printf("%lld\n",re[i]);
	}
}

B. super_log

欧拉降幂应用题注意幂塔函数递归的玩法，挺好的这题….但是洛谷好像还有一个跟他相似的题之前没做过….Luogu P4139 上帝与集合的正确用法

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
ll t,a,b,m,bk[N],phi[N],p[N],q;
void get()//线性筛欧拉函数
{
	phi[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!bk[i])
		p[++q]=i,phi[i]=i-1;
		for(int j=1;j<=q&&i*p[j]<=N;j++)
		{
			bk[i*p[j]]=1;
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
}
ll qpow(ll a,ll b,ll m)//快速幂
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1)
		ans=ans%m*base%m,ans%=m;
		base=base%m*base%m,base%=m;
		b>>=1;
	}
	return ans;
}
ll fun(ll a,ll b,ll m)
{
	if(a==1)//题目里面黑体note
	return 1;
	if(b==0)//a^0=1
	return 1;
	if(m==1)
	return 0;
	ll jk=fun(a,b-1,phi[m]);
	if(jk<m)
	return qpow(a,jk,m);
	else
	return qpow(a,jk%phi[m]+phi[m],m);
}
int main()
{
	get();
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld%lld",&a,&b,&m);
		printf("%lld\n",fun(a,b,m)%m);
	}
}

F. Greedy Sequence

题意很难懂就是找左边右边第一个比他小的数一直找下去问能找到最多多少个?
就是给定一个窗口一个一个往里面塞玩意,然后计算出每个的前驱再从第一个数开始更新f[i]=f[pre[i]]+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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
int a[100005],ans[100005],bk[100005],pre[100005];
void read(int &x)
{
    char ch = getchar();x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
struct node1
{
	ll l,r,s;
}t[N<<2];
void build(ll p,ll l,ll r)
{
	t[p].l=l;t[p].r=r;t[p].s=0;
	if(l==r) return;
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void change(ll p,ll x,ll y)
{
	if(t[p].l==t[p].r)
	{
		if(t[p].s+y>=0)
		t[p].s+=y;
		return;
	}
	ll mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) change(p<<1,x,y);
	else change(p<<1|1,x,y);
	t[p].s=t[p<<1].s+t[p<<1|1].s;
}
ll sum1(ll p,ll x,ll y)
{
	if(x<=t[p].l&&t[p].r<=y) return t[p].s;
	ll mid=(t[p].l+t[p].r)>>1,ans=0;
	if(x<=mid) ans+=sum1(p<<1,x,y);
	if(y>mid) ans+=sum1(p<<1|1,x,y);
	return ans;
}
ll sum2(ll p,ll x)
{
	if(t[p].l==t[p].r) return t[p].l;
	ll mid=(t[p].l+t[p].r)>>1;
	if(x<=t[p<<1].s) return sum2(p<<1,x);
	else return sum2(p<<1|1,x-t[p<<1].s);
}
int main()
{
	int t;
	read(t);
	while(t--)
	{
		int n,k;
		read(n);
		read(k);
		build(1,1,n);
		for(int i=1;i<=n;i++)
		read(a[i]),bk[i]=a[i];
		for(int i=0;i<=n;i++)
		ans[i]=0;
		int rm=0;
		for(int i=1;i<=k;i++)
		change(1,a[i],1);
		for(int i=1;i<=n;i++)
		{
			if(i+k<=n)
			change(1,a[i+k],1);
			if(i-k>1)
			change(1,bk[i-k-1],-1);
			if(sum1(1,1,a[i]-1)==0)
			pre[a[i]]=a[i];
			else
			pre[a[i]]=sum2(1,sum1(1,1,a[i]-1));
		}
		for(int i=1;i<=n;i++)
		ans[i]=ans[pre[i]]+1;
		for(int i=1;i<=n;i++)
		printf("%d%c",ans[i],i==n?'\n':' ');
	}
}
就算是一分钱，也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。
本文首发于baccano 博客（ http://baccano.fun ），版权所有，侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆？---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%