来讲讲我力所能及的骗分
1. 纯暴力
30 分的好成绩
- #include<bits/stdc++.h>
- using namespace std;
- int n,m,p;
- int k[100001];
- int c[1001][1001];
- int main()
- {
- scanf("%d%d%d",&n,&m,&p);
- if(n==1)
- {
- for(int i=1;i<=m;i++) k[i]=i;
- for(int i=1;i<=p;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- int sum=k[y];
- for(int j=y;j<m;j++)
- k[j]=k[j+1];
- k[m]=sum;
- printf("%d\n",sum);
- }
- }
- else
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- c[i][j]=(i-1)*m+j;
- }
- }
- for(int i=1;i<=p;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- int sum=c[x][y];
- for(int j=y;j<m;j++)
- c[x][j]=c[x][j+1];
- for(int j=x;j<n;j++)
- c[j][m]=c[j+1][m];
- c[n][m]=sum;
- printf("%d\n",sum);
- }
- }
- return 0;
- }
2. 另 20 分
非常休闲
发现四个数据点 n=1
那么就是一条链
所以说我们只需要维护一个支持动态删除, 移动, 加入的 array
删除任意, 加入最后
很容易想到线段树
代码:
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=600005;
- int n,m,p;
- ll c[1001][1001];
- ll val[N];
- int cnt;
- struct Sugment_Tree{
- ll s[N<<2];
- #define il inline
- #define mid (l+r)/2
- Sugment_Tree(){memset(s,0,sizeof(s));}
- il void push_up(int num){
- s[num]=s[num<<1]+s[num<<1|1];
- }
- il void build(int l,int r,int num){
- if(l==r){
- if(l<=m) s[num]=1;
- else s[num]=0;
- return;
- }
- build(l,mid,num<<1);
- build(mid+1,r,num<<1|1);
- push_up(num);
- }
- il void del(int l,int r,int num,int POS){
- if(l>POS||r<POS) return;
- if(l==r&&r==POS){
- s[num]=0;
- return;
- }
- del(l,mid,num<<1,POS);
- del(mid+1,r,num<<1|1,POS);
- push_up(num);
- }
- il void ins(int l,int r,int num,int POS){
- if(l>POS||r<POS) return;
- if(l==r&&r==POS){
- s[num]=1;
- return;
- }
- ins(l,mid,num<<1,POS);
- ins(mid+1,r,num<<1|1,POS);
- push_up(num);
- }
- il ll ask(int l,int r,int num,int L,int R){
- if(l>R||r<L) return 0ll;
- if(l>=L&&r<=R) return s[num];
- return ask(l,mid,num<<1,L,R)+ask(mid+1,r,num<<1|1,L,R);
- }
- }T;
- int serch(ll sum){
- int l=1,r=m+p,ans=-1;
- while(l<=r){
- if(T.ask(1,m+p,1,1,mid)<sum) ans=mid,l=mid+1;
- else r=mid-1;
- }
- ans++;
- while(val[ans]==0) ans++;
- return ans;
- }
- int main()
- {
- //freopen("phalanx11.in","r",stdin);
- scanf("%d%d%d",&n,&m,&p);
- if(n==1)
- {
- cnt=m;
- T.build(1,m+p,1);
- for(int i=1;i<=m;i++) val[i]=i;
- //cout<<T.ask(1,m+p,1,1,1)<<"*@**&#@"<<endl;
- int uu=p;
- while(uu--){
- int x,y;
- scanf("%d%d",&x,&y);
- int pos=serch(y);
- ll sumi=val[pos];
- val[pos]=0;
- T.del(1,m+p,1,pos);
- cnt++;
- val[cnt]=sumi;
- T.ins(1,m+p,1,cnt);
- printf("%lld\n",sumi);
- }
- }
- else
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- c[i][j]=(ll)(i-1)*m+j;
- }
- }
- for(int i=1;i<=p;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- ll sum=c[x][y];
- for(int j=y;j<m;j++)
- c[x][j]=c[x][j+1];
- for(int j=x;j<n;j++)
- c[j][m]=c[j+1][m];
- c[n][m]=sum;
- printf("%lld\n",sum);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3280494.html