NOIP 2013 DAY 1

DAY1

T1 转圈游戏
在这里插入图片描述
快速幂模板

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x;
long long ans;
long long cmd(long long a,long long b){long long sum=1;for(;a;a>>=1){if(a&1){sum=sum*b%n;}b=b*b%n;
}
return sum;
} 
int main(){//freopen("circle.in","r",stdin);//freopen("circle.out","w",stdout);cin>>n>>m>>k>>x;ans=(x+m*cmd(k,10))%n;cout<<ans;return  0;
}

T2 火柴排队
在这里插入图片描述
通过读题我们发现，当b数组中第i小的数和a数组中第i小的数在同一个位置，就是最优的。然后利用下标的升序对c数组进行归并排序，得到答案。

#include<bits/stdc++.h>
#define mo 99999997
using namespace std;
struct node{int x,y;
}a[100001],b[100001];
int c[100001],p[100001];
int n;
int cmp(node a ,node b){if(a.x==b.x) return a.y<b.y;else return a.x<b.x;
}
int check(int l,int r){int ans,mid=(l+r)>>1,k=1;if(l>=r) return 0;ans=(check(l,mid)+check((mid+1),r))%mo;for(int i=l,j=mid+1;i<=mid||j<=r;){if(i<=mid&&j<=r&&c[i]>c[j]){p[k++]=c[j++];ans+=mid-i+1;}else if(i>mid){p[k++]=c[j++];}else{p[k++]=c[i++];}}for(int i=1;i<k;i++){c[l+i-1]=p[i];}return ans%mo;
}
int main(){//freopen(".in","r",stdin);
//	freopen(".out","w",stdout);cin>>n;for(int i=1;i<=n;++i){cin>>a[i].x;a[i].y=i;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;++i){cin>>b[i].x;b[i].y=i;}sort(b+1,b+1+n,cmp);
/*	for(int i=1;i<=n;i++){cout<<a[i].x<<" "<<a[i].y;cout<<endl;}for(int i=1;i<=n;i++){cout<<b[i].x<<" "<<b[i].y;cout<<endl;}for(int i=1;i<=n;i++){cout<<c[i]<<endl;}*/for(int i=1;i<=n;i++){c[a[i].y]=b[i].y;}cout<<check(1,n);
}

T3 货车运输 在这里插入图片描述

在这里插入代码片

DAY 2

T1 积木大赛
在这里插入图片描述
把整个序列分成多个不下降子序列，然后所有段中最大值的和减去除第一段外的段的最小值。

#include<bits/stdc++.h>
using namespace std;
int n,h,maxx,down,last,ans;
int main(){
//	freopen("block.in","r",stdin);
//	freopen("block.out","w",stdout);cin>>n; for(int i=1;i<=n;i++){scanf("%d",&h);if(down==1 && h>last) {ans+=maxx-last,maxx=0;}maxx=max(maxx,h);if(i==n) ans+=maxx;if(h<last) down=1;last=h;}cout<<ans;
}

T2 花匠
在这里插入图片描述
由题目可知，两个要求分别为任意三个连续的元素满足先增后减或者先减后增，于是我们只需要在单调性发生改变时进行特判，贪心得出答案。

#include<bits/stdc++.h>
using namespace std;
int ans=1,flag,last,now,n;
int main(){//freopen("flower.in","r",stdin);
//	freopen("flower.out","w",stdout);cin>>n>>last;for (int i=2;i<=n;i++){scanf("%d",&now);if ((now>last) && ((flag==-1)||(flag==0))){ans++;flag=1;}else if ((now<last) && ((flag==0)||(flag==1))){ans++;flag=-1;}last=now;}cout<<ans;
}

T3 华容道
在这里插入图片描述
直接深搜，走过的点标记再交换，50pts

#include<bits/stdc++.h>
using namespace std;
const int X[] = {0,1,0,-1};
const int Y[] = {1,0,-1,0}; 
int m,n,ex,ey,a,b,c,d,ans,used[45][45][45][45],ma[50][50],q;
bool can(int x,int y)
{if(x<1||x>n) return false;if(y<1||y>m) return false;if(!ma[x][y]) return false;return true;
}
void dfs(int kx,int ky,int sx,int sy,int cnt)
{if(cnt>=ans) return;if(sx==ex&&sy==ey){ans=cnt;return;
}if(used[kx][ky][sx][sy] <= cnt) return;used[kx][ky][sx][sy]=cnt;for(int i=0;i<4;i++){int x=kx+X[i],y=ky+Y[i];if(can(x,y)){if(x==sx&&y==sy) dfs(x,y,kx,ky,cnt+1);else dfs(x,y,sx,sy,cnt+1);}}
}
int main(){cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&ma[i][j]);for(int i=1;i<=q;i++){memset(used,0x3f,sizeof(used));ans = 1e6;scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&ex,&ey);dfs(a,b,c,d,0);if(ans==1e6) cout<<-1;;else cout<<ans<<endl;}
}

满分暂时打不来（无能咆哮）