2021.10.04模拟赛

文章目录

  • 1.toy
  • 2.magic
  • 3.earthworm
  • 4.phalanx


1.toy

算法思路:模拟大水
我的代码:

#include
using namespace std;
int n,m,opt;
int a[100005],f[100005],s[100005];
char x;
string name[100005];
int main(){
     
	//freopen("toy.in","r",stdin);
	//freopen("toy.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
     
		scanf("%d",&f[i]); 
		cin>>name[i];
	}
	int it=1;
	for(int i=1;i<=m;++i){
     
		scanf("%d%d",&a[i],&s[i]);
		if(f[it]^a[i])it+=s[i];
		else it-=s[i];
		if(it<=0)it+=n;
		if(it>n) it-=n;
	}
	cout<<name[it];
	return 0;
}

估分:100
实际得分:100
反思:没什么。

2.magic

算法思路:模拟大水
我的代码:

#include
using namespace std;
int a[55][55],n;
int main(){
     
	//freopen("magic.in","r",stdin);
	//freopen("magic.out","w",stdout);
    scanf("%d",&n);
    int x=1,y=(n+1)>>1;
    a[x][y]=1;
    for(int i=2;i<=n*n;++i){
     
        if(x==1&&y!=n){
     
            x=n;++y;
        }
        else if(y==n&&x!=1){
     
            y=1;--x;
        }
        else if(x==1&&y==n)
            ++x;
        else if(x!=1&&y!=n)
            if(a[x-1][y+1]==0){
     
                --x;++y;
            }
            else
                ++x;
        a[x][y]=i;
    }
    for(int i=1;i<=n;++i){
     
        for(int j=1;j<=n;++j)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

估分:100
实际得分:100
反思:没什么。

3.earthworm

算法思路:priority_queue、queue(O(m+nlogn))。
标程:

#include 
#include 
#include 
#include 
#include 
const int N = 7000000 + 10;
using namespace std;

bool cmp(const int &a, const int &b)
{
     
    return a > b;
}

priority_queue<int> ans;
int cut1[N], now[N], cut2[N];
int n, m, q, u, v, t;
int sum;
double p;
int h, h1, h2;
int t0, t1, t2;

int main()
{
     
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    p = (double)u / v;
    int tmp;
    for (t0 = 1; t0 <= n; ++t0)
        scanf("%d", now + t0);
    --t0;
    t1 = t2 = 0;
    h = h1 = h2 = 1;
    sort(now + 1, now + t0 + 1, cmp);
    int top;
    for (int i = 1; i <= m; ++i)
    {
     
        if (h > t0)
        {
     
            if (cut1[h1] > cut2[h2])
                top = cut1[h1++];
            else
                top = cut2[h2++];
        }
        else if (now[h] >= cut1[h1] && now[h] >= cut2[h2])
            top = now[h], ++h;
        else if (cut1[h1] >= cut2[h2] && now[h] <= cut1[h1])
            top = cut1[h1], ++h1;
        else
            top = cut2[h2], ++h2;

        top += sum;
        int a1 = floor(p * (double)top), a2 = top - a1;
        sum += q;
        a1 -= sum, a2 -= sum;
        cut1[++t1] = a1, cut2[++t2] = a2;
        if (i % t == 0)
            printf("%d ", top);
    }
    putchar('\n');
    for (int i = h; i <= t0; ++i)
        ans.push(now[i]);
    for (int i = h1; i <= t1; ++i)
        ans.push(cut1[i]);
    for (int i = h2; i <= t2; ++i)
        ans.push(cut2[i]);
    for (int i = 1; ans.size(); ++i)
    {
     
        if (i % t == 0)
            printf("%d ", ans.top() + sum);
        ans.pop();
    }
    return 0;
}

我的代码:

#include
using namespace std;
int n,m,q,u,v,t,x;
priority_queue<int> s;
double p;
int main(){
     
	//freopen("earthworm.in","r",stdin);
	//freopen("earthworm.out","w",stdout);
	scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
	p=u*1.0/v;
	for(int i=1;i<=n;++i){
     
		scanf("%d",&x);
		s.push(x);
	}
	int cnt=0;
	for(int i=1;i<=m;++i){
     
		++cnt;
		int now=s.top()+(i-1)*q;
		s.pop();
		int a=floor(now*p);
		s.push(a-i*q);
		s.push(now-a-i*q);
		if(cnt==t){
     
			printf("%d ",now);
			cnt=0;
		}
	}
	printf("\n");
	cnt=0;
	for(int i=1;i<=n+m;++i){
     
		++cnt;
		if(cnt==t){
     
			printf("%d ",s.top()+m*q);
			cnt=0;
		}
		s.pop();
	}
	printf("\n");
	return 0;
}

估分:80
实际得分:90
反思:想到满分算法要会写出来。

4.phalanx

算法思路:
标程:

#include
#define MAXNM 300005
#define MAXQ MAXNM
struct node{
     
	int rdm;
	long long v;
	long long sum;
	long long siz;
	int ch[2];
}nodes[1500010];
int root[300010];
void update(int i)
{
     
	nodes[i].siz=nodes[nodes[i].ch[0]].siz+nodes[nodes[i].ch[1]].siz+nodes[i].sum; 
}
int merge(int x,int y)
{
     
	if(!x||!y) return x+y;
	int tmp;
	if(nodes[x].rdm>=nodes[y].rdm)
		tmp=x,nodes[x].ch[1]=merge(nodes[x].ch[1],y);
	else
		tmp=y,nodes[y].ch[0]=merge(x,nodes[y].ch[0]);
	update(tmp);
	return tmp;
}
int tot;
int new_node(long long v,long long sum)
{
     
	if(!sum) return 0;
	tot++;
	nodes[tot].v=v;
	nodes[tot].sum=sum;
	nodes[tot].siz=sum;
	nodes[tot].rdm=rand();
	return tot;
}
void split(int i,int k,int& x,int& y,int& z)
{
     
	if(!i) x=y=z=0;
	else
	{
     
		if(nodes[nodes[i].ch[0]].siz>=k)
			z=i,split(nodes[i].ch[0],k,x,y,nodes[i].ch[0]);
		else
		{
     
			k-=nodes[nodes[i].ch[0]].siz;
			if(k<=nodes[i].sum)
			{
     
				y=i;
				x=nodes[i].ch[0];
				z=nodes[i].ch[1];
				nodes[i].ch[0]=nodes[i].ch[1]=0;
			}
			else
			{
     
				x=i;
				k-=nodes[i].sum;
				split(nodes[i].ch[1],k,nodes[i].ch[1],y,z);
			}
		}
		update(i);
	}
}
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
int main()
{
     
	srand(23333);
	int n,m,q,x,y,i,a,b,c;
	long long t1,t2;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=n;i++)
	{
     
		root[i]=new_node(1LL*(i-1)*m+1,m-1);
		root[0]=merge(root[0],new_node(1LL*i*m,1));
	}
	for(i=1;i<=q;i++)
	{
     
		scanf("%d%d",&x,&y);
		if(y==m)
		{
     
			split(root[0],x,a,b,c);
			printf(LLD "\n",nodes[b].v);
			root[0]=merge(merge(a,c),b);
		}
		else
		{
     
			split(root[0],x,a,b,c);
			root[0]=merge(a,c);
			root[x]=merge(root[x],b);
			split(root[x],y,a,b,c);
			y-=nodes[a].siz;
			printf(LLD "\n",nodes[b].v+y-1);
			root[0]=merge(root[0],new_node(nodes[b].v+y-1,1));
			t1=y-1;
			t2=nodes[b].sum-y;
			b=merge(new_node(nodes[b].v,t1),new_node(nodes[b].v+y,t2));
			root[x]=merge(merge(a,b),c);
		}
	}
	return 0;
}

我的代码:

#include
using namespace std;
int n,m,q,x,y;
long long a[1005][1005];
int main(){
     
	//freopen("phalanx.in","r",stdin);
	//freopen("phalanx.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			a[i][j]=(i-1)*m+j;
	for(int i=1;i<=q;++i){
     
		scanf("%d%d",&x,&y);
		long long p=a[x][y];
		printf("%lld\n",p);
		for(int j=y;j<=m-1;++j)a[x][j]=a[x][j+1];
		for(int j=x;j<=n-1;++j)a[j][m]=a[j+1][m];
		a[n][m]=p;
	}
	return 0;
}

估分:30
实际得分:30
反思:难题,暴力即可,但还有20分可以用链表拿。

你可能感兴趣的