算法|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< 估分：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 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 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;
}
【算法|2021.10.04模拟赛】估分：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分可以用链表拿。
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 三门问题（蒙提霍尔悖论）分析与Golang模拟