文章目录
- 1.toy
- 2.magic
- 3.earthworm
- 4.phalanx
1.toy
算法思路：模拟大水
我的代码：
#include<bits/stdc++.h>
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<bits/stdc++.h>
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 <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
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<bits/stdc++.h>
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<bits/stdc++.h>
#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<bits/stdc++.h>
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分可以用链表拿。